競プロ日記#25/08/30

AtCoder

AtCoder Beginner Contest 420

A - What month is it?

• 元の月XにYか月後のYを足したものが12より大きければ-12をするというif文の制御

int main() {
    long long X,Y;
    cin >> X >> Y;
    if (X + Y >12){
        cout << (X + Y) - 12 << endl;
    }else{
        cout << X + Y << endl;
    }
}

B - Most Minority

• めちゃくちゃ愚直に実装した。
• forの二重ループでそれぞれ0,1の回数をカウントしてそれらに投票した人間をまた別のsetで管理する形
• 最終的には題意で与えられた条件で場合分けして得点を振り分けていく
• 最大値が複数の場合に全列挙する以下の形を使った
  • 解説は実装する前の整理の手順が多少違うが同じようなことをやっていた解説

    int max_val = *std::max_element(ans.begin(), ans.end());

   
    for (size_t i = 1; i < ans.size(); i++) {
        if (ans[i] == max_val) {
            cout << i << " ";
        }
    }

• 以下最終的な実装

int main() {
    long long N,M;
    cin >> N >> M;
    vector<long long> ans(N + 1);
    
    vector<string> A(N + 1);
    for (long long i = 1; i <= N; i++) {
        cin >> A[i];
    }
    for (long long i = 0; i < M; i++) {
        long long counterZero = 0, counterOne = 0;
        set<long long> zeroIndex, oneIndex;
        for (long long j = 1;j <= N;j++){
            if (A[j][i] == '0'){
                counterZero++;
                zeroIndex.insert(j);
            }else{
                counterOne++;
                oneIndex.insert(j);
            }
        }
        if (counterZero < counterOne){
            for (auto index = zeroIndex.begin();index != zeroIndex.end();index++){
                ans[*index]++;
            }
        }else if (counterZero > counterOne){
            for (auto index = oneIndex.begin();index != oneIndex.end();index++){
                ans[*index]++;
            }
        }else if (counterZero == 0 || counterOne == 0){
            for (long long k = 1;k <= N;k++){
                ans[k]++;
            }
        }
    }

    int max_val = *std::max_element(ans.begin(), ans.end());

   
    for (size_t i = 1; i < ans.size(); i++) {
        if (ans[i] == max_val) {
            cout << i << " ";
        }
    }
}

AtCoder Beginner Contest 419

A - AtCoder Language

int main() {
    string S;
    cin >> S;
    if (S == "red"){
        cout << "SSS" << endl;
        return 0;
    }
    if (S == "blue"){
        cout << "FFF" << endl;
        return 0;
    }
    if (S == "green"){
        cout << "MMM" << endl;
        return 0;
    }
    cout << "Unknown" << endl;

}

B - Get Min

• 優先度付きキューを使うと一発で答えが出せる。
• 今回の場合は最小の値から取り出したいのでpriority_queue<long long,vector<long long>,greater<long long>>で定義する

int main() {
    long long Q;
    cin >> Q;
    priority_queue<long long,vector<long long>,greater<long long>> pq;
    for (long long i = 0; i < Q; i++) {
        long long x;
        cin >> x;
        if (x == 1){
            long long y;
            cin >> y;
            pq.push(y);
        }
        if (x == 2){
            cout << pq.top() << endl;
            pq.pop();
        }
    }
}

競技プログラミングの鉄則

A08 - Two Dimensional Sum

• いわゆる二次元累積和
• まずはマス目の値を格納するためのグリッド用二次元配列を用意し、それらの累積和を格納するために別のグリッド用二次元配列を用意する
• あとは横の累積和と縦の累積和を順に求めてZ(c,d) + Z(a-1,b-1) - Z(a- 1,d) - Z(c,b-1)を求めていく
• ほぼ解説AC

int main() {
    long long H,W,Q;
    cin >> H >> W;
    long long X[1509][1509],Z[1509][1509];
    long long A[100009],B[100009],C[100009],D[100009];
    for (long long i = 1;i <= H;i++){
        for (long long j = 1;j <= W;j++){
            cin >> X[i][j];
        }
    }

    
    cin >> Q;
    for (long long i = 1; i <= Q;i++){
        cin >> A[i] >> B[i] >> C[i] >> D[i];
    }
    for (long long i = 0;i <= H;i++){
        for (long long j = 0;j <= W;j++){
            Z[i][j] = 0;
        }
    }

    for (long long i = 1;i <= H;i++){
        for (long long j = 1;j <= W;j++){
            Z[i][j] = Z[i][j - 1] + X[i][j];
        }
    }

    for (long long j = 1; j <= W;j++){
        for (long long i = 1; i <= H;i++){
            Z[i][j] = Z[i - 1][j] + Z[i][j];
        }
    }
    
    for (long long i = 1;i <= Q;i++){
        cout << Z[C[i]][D[i]] + Z[A[i] - 1][B[i] - 1] - Z[A[i] - 1][D[i]] - Z[C[i]][B[i] - 1] << endl;
    }
}

余談だん

A問題はともかくB問題もだいぶ前から確定得点問題になっているが（沼ったり250点問題特有の複雑さについていけないと稀に落とすが）、今回の様にABCに参加する前の指慣らしで勉強するときに解説をしっかり読み込むか迷う。当然間違えてたら解説読むのは必須だが、そうでない場合どうしようかと。
その時間あるなら別回のに手を付けたりC、D問題にトライする時間にした方が良い気がする。