ABC452の記録

AtCoderBeginnerContest452の感想と自分が解いたところまでの解説を書いていきます
今回はA,B,C,D,EをC++,A,B,Cをpythonで解きます
AtCoder Beginner Contest 452

1.感想

A問題
書くだけ
B問題
書くだけ
C問題
少しめんどくさい
D問題
めんどくさい
E問題
数学だった

2.結果

入水
いつか記事書く

3.解説

A問題 Gothec

リストを作って試す

C++での例

#include <iostream>
using namespace std;

int main(){
    pair<int, int> A[] = {{1, 7}, {3, 3}, {5, 5}, {7, 7}, {9, 9}};

    pair<int, int> M;
    cin >> M.first >> M.second;
    for (auto i : A){
        if (i == M){
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;
}

pythonでの例

A = [(1, 7), (3, 3), (5, 5), (7, 7), (9, 9)]
M = tuple(map(int, input().split()))

for i in A:
    if i == M:
        print("Yes")
        exit()
print("No")

B問題 Draw Frame

1行目とH行目は全部'#'
それ以外は1列目とW列目だけを'#'

C++での例

#include <iostream>
#include <string>
using namespace std;

int main(){
    int H, W;
    cin >> H >> W;

    for (int i = 0; i < H; i++){
        if (i == 0 || i == H-1) cout << string(W, '#') << endl;
        else cout << '#' << string(W-2, '.') << '#' << endl;
    }
}

pythonでの例

H, W = map(int, input().split())

for i in range(H):
    if i == 0 or i == H-1:
        print('#'*W)
    else:
        print('#'+'.'*(W-2)+'#')

C問題 Fishbones

st[i][j]で長さiの文字列のj番目の文字の集合とする
そもそもS[j]の長さがNではないときはNo
それ以外だったら確かめる

C++での例

#include <iostream>
#include <vector>
#include <string>
#include <set>
using namespace std;

int main(){
    int N, M;
    cin >> N;
    vector<int> A(N), B(N);
    for (int i = 0; i < N; i++) cin >> A[i] >> B[i], B[i]--;
    cin >> M;
    vector<string> S(M);
    vector<vector<set<char>>> st(11, vector<set<char>>(11));
    for (auto& s : S){
        cin >> s;
        for (int i = 0; i < s.size(); i++) st[s.size()][i].insert(s[i]);
    }

    for (auto s : S){
        if (s.size() != N){
            cout << "No" << endl;
            continue;
        }
        bool ok = true;
        for (int i = 0; i < N; i++) if (!st[A[i]][B[i]].count(s[i])) ok = false;
        cout << (ok? "Yes": "No") << endl;
    }
}

pythonでの例

N = int(input())
A, B, S = [], [], []
for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b-1)
M = int(input())
st = [[set() for i in range(11)] for j in range(11)]
for _ in range(M):
    s = input()
    S.append(s)
    for i in range(len(s)):
        st[len(s)][i].add(s[i])

for s in S:
    if len(s) != N:
        print("No")
        continue
    ok = True
    for i in range(N):
        if not s[i] in st[A[i]][B[i]]:
            ok = False
    print("Yes" if ok else "No")

D問題 No-Subsequence Substring

DP
next[i][j]をその文字が右に最初に出てくる位置とする

C++での例

#include <iostream>
#include <vector>
#include <string>
using namespace std;
using ll = long long;

int main(){
    string S, T;
    cin >> S >> T;
    int N = S.size(), M = T.size();
    vector<vector<int>> next(N+1, vector<int>(26, N));
    for (int i = 0; i < 26; i++) next[N][i] = N;
    for (int i = N-1; i >= 0; i--){
        next[i] = next[i+1];
        next[i][S[i]-'a'] = i;
    }

    ll ans = 0;
    for (int i = 0; i < N; i++){
        int pos = i;
        bool ok = true;
        for (int j = 0; j < M; j++){
            pos = next[pos][T[j]-'a'];
            if (pos == N){
                ok = false;
                break;
            }
            pos++;
        }
        if (!ok) ans += N-i;
        else ans += pos-i-1;
    }

    cout << ans << endl;
}

E問題 You WILL Like Sigma Problem

式を分割する

C++での例

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const ll MOD = 998244353ll;

int main(){
    int N, M;
    cin >> N >> M;
    vector<ll> A(N), B(M), S(N+1, 0);
    for (int i = 0; i < N; i++) cin >> A[i], S[i+1] = (S[i]+A[i])%MOD;
    for (int i = 0; i < M; i++) cin >> B[i];

    ll suma = 0, sumb = 0;
    for (int i = 0; i < N; i++) suma = (suma+A[i]*(i+1))%MOD;
    for (int i = 0; i < M; i++) sumb = (sumb+B[i])%MOD;
    ll alpha = suma*sumb%MOD;

    ll beta = 0;
    for (int i = 1; i <= M; i++){
        ll b = B[i-1];
        for (int j = 1; i*j <= N; j++){
            int l = i*j, r = min(N, (j+1)*i-1);
            ll sub = (S[r]-S[l-1]+MOD)%MOD;
            beta = (beta+((b*i*j)%MOD*sub)%MOD)%MOD;
        }
    }

    cout << (alpha-beta+MOD)%MOD << endl;
}