ABC365 参加記

トヨタ自動車プログラミングコンテスト2024#8（AtCoder Beginner Contest 365）に参加しました。

A - Leap Year

うるう年かどうかを判定する問題。条件が面倒でしたが思考をしたくなかったのですべて分岐させました。

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int Y; cin >> Y;
    if(Y % 4 != 0){
        cout << 365 << "\n";
    }else if(Y % 100 != 0){
        cout << 366 << "\n";
    }else if(Y % 400 != 0){
        cout << 365 << "\n";
    }else{
        cout << 366 << "\n";
    }
}

B - Second Best

最大のインデックスを求めるなら、*max_element(all(A))と等しいときに出力すればいいですが、2番目だといろいろ値を持たないといけなそうで面倒だったので、値とインデックスをpair<int, int>にいれてソートしました。

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N; cin >> N;
    vector<pair<int, int>> A(N);
    rep(i, N){
        int a; cin >> a;
        A[i] = {a, i + 1};
    }

    sort(rall(A));

    cout << A[1].second << "\n";
}

C - Transportation Expenses

最大値を求める問題ということなので、二分探索が真っ先に思いつきました。「答えで二分探索」のライブラリを持っているので、ペタッと貼り付けて答えがinfiniteとなるときの例外処理だけしてAC。

int N; ll M;
vector<int> A;

bool ans_check(long long x){
    ll val = 0LL;
    rep(i, N){
        val += min(x, (ll) A[i]);
    }
    if(val <= M) return true;
    else return false;
}

long long ans_binary_search(){
    long long left = -1, right = 1e18;
    if(ans_check(right)){
        while(right - left > 1){
            long long mid = (left + right) / 2;
            // cout << "debug: left = " << left << ", mid = " << mid << ", right = " << right << " ans(" << mid << ") = " << ans_check(mid) << endl;
            if(ans_check(mid)) right = mid;
            else left = mid;
        }
        return right;
    }else{
        while(right - left > 1){
            long long mid = (left + right) / 2;
            // cout << "debug: left = " << left << ", mid = " << mid << ", right = " << right << " ans(" << mid << ") = " << ans_check(mid) << endl;
            if(ans_check(mid)) left = mid;
            else right = mid;
        }
        return left;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N >> M;
    A.resize(N); v_cin(A);

    if(accumulate(all(A), 0LL) <= M){
        cout << "infinite" << "\n";
        return 0;
    }

    cout << ans_binary_search() << "\n";
}

D - AtCoder Janken 3

相手のじゃんけんの手が決まっていて、自分の手をうまく選んで勝利数の最大値を求める問題。ただし、同じ手を連続で出せない条件付き。動的計画法の典型問題だなと感じました。

\[dp_{i,j}=i番目でjを出したときの勝利数の最大値\]

として、たとえば、$i$番目の相手の手が「グー」だったとすると、

\[\begin{align*} dp_{i,グー}&=-\infty \\ dp_{i,チョキ} &= \text{max}\{dp_{i - 1,グー},dp_{i - 1,パー}\} \\ dp_{i,パー} &= \text{max}\{dp_{i - 1,グー},dp_{i - 1,チョキ}\} + 1 \end{align*}\]

と遷移すればいいことが分かります。

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N; cin >> N;
    string S; cin >> S; S = "."+ S;

    vector<vector<int>> dp(N + 1, vector<int> (3, 0));

    rrep(i, 1, N + 1){
        if(S[i] == 'R'){
            dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]);
            dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + 1;
            dp[i][2] = -1e9;
        }else if(S[i] == 'P'){
            dp[i][0] = -1e9;
            dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]);
            dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + 1; 
        }else{
            dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + 1;
            dp[i][1] = -1e9;
            dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]);
        }
    }
    cout << *max_element(all(dp[N])) << "\n";
}

E - Xor Sigma Problem

2進数として見たときの桁ごとに分けて考えてよく、1が現れる回数が奇数となる連続部分列の個数を数えれば良いことはわかったが、これを$O(N\log N)$で求める方法がわからなかった。累積xorのxorをとる(?)方法が解説にあったので要復習。

解説を読んだときのメモとACコード

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N; cin >> N;
    vector<int> A(N + 1, 0); rrep(i, 1, N + 1) cin >> A[i];

    ll ans = 0;

    rep(d, 30){
        vector<int> B(N + 1); // Aのd桁目のbit
        rep(i, N + 1) B[i] = (A[i] >> d) & 1;
        vector<int> C(N + 1, 0); // 累積XOR
        rrep(i, 1, N + 1) C[i] = C[i - 1] ^ B[i];
        int zero = 0, one = 0;
        rep(i, N + 1){
            if(C[i] == 0) zero ++;
            else one ++;
        }
        ll val = (ll) zero * one;
        rrep(i, 1, N + 1) val -= B[i];
        ans += (1LL << d) * val;
    }

    cout << ans << "\n";
}

結果

コンテスト成績表

4完19分
パフォーマンス: 1089
レーティング: 1104 → 1102