ABC366 参加記

AtCoder Beginner Contest 366に参加しました。

A - Election 2

AかSが過半数を超えているときYes、超えていないときNoを出力すればよい。A問題にしては考察が少し難しめな気がした。

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N; cin >> N;
    int T, A; cin >> T >> A;
    int S = N / 2;
    if(T > S or A > S){
        cout << "Yes\n";
    }else{
        cout << "No\n";
    }
}

B - Vertical Writing

横書きで入力された文章を縦書きにして出力する問題。縦書きにするときに空白となってしまう部分に*を埋めないといけないのが厄介なので、最初に埋めました。あとは向きとインデックスを頑張って考えて通しました。範囲外参照を解消し忘れて1回WAを喰らいました。

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N; cin >> N;
    vector<string> S(N); v_cin(S);
    int M = 0;
    rep(i, N){
        M = max((int) S[i].size(), M);
        while(S[i].size() < M){
            S[i].push_back('*');
        }
    }
    rep(i, M){
        for(int j = N - 1; j >= 0; j --){
            if(S[j].size() <= i){
                continue;
            }
            cout << S[j][i];
        }
        cout << "\n";
    }
}

C - Balls and Bag Query

multisetなどで毎回種類数を数えると最悪$O(Q^2)$となって間に合わない。種類ごとに個数を持っておき、0が1になったら種類数+1、1が0になったら種類数-1とすればよい。mapでも間に合いそうなのでmapで実装したが普通の配列で十分だった。

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int Q; cin >> Q;
    int ans = 0;
    map<int, int> S;
    while(Q --){
        int k; cin >> k;
        if(k == 1){
            int x; cin >> x;
            if(S[x] == 0){
                ans ++;
            }
            S[x] ++;
        }else if(k == 2){
            int x; cin >> x;
            if(S[x] == 1){
                ans --;
            }
            S[x] --;
        }else{
            cout << ans << "\n";
        }
    }
}

D - Cuboid Sum Query

3次元累積和をやるだけの問題。重複の処理は包除原理のお気持ちでできる。バグらせてかなり時間をかけてしまった。

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N; cin >> N;
    rep(i, N) rep(j, N) rep(k, N){
        cin >> A[i][j][k];
    }
    rep(i, N + 1) rep(j, N + 1) rep(k, N + 1){
        S[i][j][k] = 0;
    }
    rrep(i, 1, N + 1){
        rrep(j, 1, N + 1) rrep(k, 1, N + 1){
            S[i][j][k] = S[i - 1][j][k] + A[i - 1][j - 1][k - 1];
        }
    }
    rrep(j, 1, N + 1){
        rrep(i, 0, N + 1) rrep(k, 0, N + 1){
            S[i][j][k] += S[i][j - 1][k];
        }
    }
    rrep(k, 1, N + 1){
        rrep(i, 0, N + 1) rrep(j, 0, N + 1){
            S[i][j][k] += S[i][j][k - 1];
        }
    }

    int Q; cin >> Q;
    while(Q --){
        int a, b, c, d, e, f; cin >> a >> d >> b >> e >> c >> f;
        ll ans = 0;
        ans += S[d][e][f];
        ans -= S[a - 1][e][f];
        ans -= S[d][b - 1][f];
        ans -= S[d][e][c - 1];
        ans += S[d][b - 1][c - 1];
        ans += S[a - 1][e][c - 1];
        ans += S[a - 1][b - 1][f];
        ans -= S[a - 1][b - 1][c - 1];
        cout << ans << "\n";
    }
}

E - Manhattan Multifocal Ellipse

尺取り法未履修なので要復習…。

結果

コンテスト成績表

4完55分1ペナ
パフォーマンス: 961
レーティング: 1102 → 1089