AtCoder ABC426 [A-D] 振り返り(C++)

AtCoder3回目の参加です！
今回はA-Cの3完達成、D問題もかなり惜しい所まで解けました。
少しずつですが成長を感じます…！

問題のリンク

A - OS Versions

問題

古い順に"Ocelot", "Serval", "Lynx"という3つがあります。
ここから2つ（同じものを含む）が与えられるので、1つ目が2つ目より同じか新しければ"Yes"を出力します。

解答例

文字のままでは比較しづらいため、数字に置き変えました。
"Ocelot"が0, "Serval"が1, "Lynx"が2ですね。

あとはxがyより新しい、つまり数字が同じか大きければ"Yes"を出力します。

#include <bits/stdc++.h>
using namespace std;

int main(){
    //文字列の取得
    string X,Y; cin >> X >> Y;
    //小文字のx,y => 文字を数字に置き変えたもの
    int x,y;

    //Xについて置き変え
    if(X == "Ocelot") x = 0;
    else if(X == "Serval") x = 1;
    else x = 2;

    //Yについて置き変え
    if(Y == "Ocelot") y = 0;
    else if(Y == "Serval") y = 1;
    else y = 2;

    //X >= Y ならば "Yes" を出力
    if(x - y >= 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}

B - The Odd One Out

問題

3文字以上の文字列の中に、1文字だけ違うものがあります。
それを出力してください。

解答例

まずは違う文字ではなく、残りの「同じ文字」を特定します。
3文字以上という制約があるので、最初の3文字で特定しましょう。

1. 1文字目と2文字目が同じなら、それが「同じ文字」です
2. 同様に、1文字目と3文字目が同じなら、それが「同じ文字」です
3. 1・2のどれにも属さないとき、2・3文字目は「同じ文字」で、1文字目は「違う文字」です

あとは前から一文字ずつ確認し、「同じ文字」と違うものがあれば出力します。

無くても問題ない処理ですが、3の場合は「違う文字」が特定できたのですぐさま出力し、コードを終了させました。
（今思うと、2の場合も2文字目が「違う文字」なのですぐに出力できましたね…）

ちなみにstring型は配列と同様に、添え字[i]で文字（char型）を引っ張り出したり、.size()で文字数を数えたりできます。

#include <bits/stdc++.h>
using namespace std;

int main(){
    //文字列の取得
    string S; cin >> S;
    //「同じ文字」を入れる
    char same;

    //「同じ文字」の特定
    if(S[0] == S[1]){
        same = S[0];
    }else if(S[0] == S[2]){
        same = S[0];
    }else{
        cout << S[0] <<endl;
        return 0;
    }

    //「違う文字」を探し出し、出力
    for(int i=0; i<S.size(); i++){
        if(same != S[i]){
            cout << S[i];
        }
    }
}

C - Upgrade Required

問題

初めに、1,2,3,4,……,Nのように、1ずつ増えてく数列があります。（問題の「バージョン」に当たるもの）
この数列から、「x以下のものをyに置き変える」という操作を繰り返します。
各回の操作で、数字を置き変えた回数を出力してください。

解答例

問題を見た感じだと、1,2,3,4,……,Nの数列を配列で用意して、毎回指示通りに置き変えれば良さそうに見えますが、この方針だとタイムアウトする予感がしますね。

そこで、配列を v として、各要素に「その数字が何個あるか」を入れましょう。

例えばN=6のとき、最初はどれも1個ずつなのでv = {1, 1, 1, 1, 1, 1}です。

「2以下のものを4に置き変える」動作をすると、v = {0, 0, 1, 3, 1, 1}です。
v[0]とv[1]を0にして、v[3]に足してます。

その後「4以下のものを6に置き変える」動作をすると、v = {0, 0, 0, 0, 1, 5}です。
v[2]とv[23]を0にして、v[6]に足してます。

これをすることで、変更がある数字のみを参照するので、ループ回数がぐっと減ります。
特に、だんだんと先頭が0で埋まっていくため、0の羅列の終わりを変数frontでメモれば、ループの回数をかなり減らすことができます。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N,Q;
    cin >> N >> Q;

    //各バージョン1台ずつでスタートなので、全要素を1で初期化
    vector<int> v = vector<int>(N, 1);
    //frontは0の羅列が終わる位置を示す
    int front = 0;

    for(int i=0; i<Q; i++){
        int x,y; cin >> x >> y;
        int count = 0;
        //frontよりも前の部分はループしない
        for(int j=front; j<x; j++){
            //バージョン変更を行った回数
            count += v[j];
            //古いバージョンの台数は必ず0になる
            v[j] = 0;
        }
    
        cout << count << endl;
        //新しいバージョンの数を増やす
        v[y-1] += count;
        //0の位置 = frontが更新されたら書き換える
        if(front < x-1) front = x-1;
    }
}

D - Pop and Insert

問題

0と1の羅列があります。
「先頭 or 末尾の数を0→1 or 1→0に入れ替えて任意の場所に入れる」という操作を繰り返します。
全てを0 or 1にするのに必要な操作数を出力してください。

解説

入力例の"110010111100101"について、すべてを1にすることを考えてみましょう。
注目すべきは1が4つ並んでいる部分ですね。
ここは何も操作せずに、ここの1の長さを伸ばしていく方針が分かりやすいでしょう。
他の部分"110010"と"00101"についても考えてみましょう。
端に来た数が0なら反転させて1の羅列に入れます。
一方、端に来た数が1なら2回反転させて1の羅列に入れます。

要するに、0と1がどういう順番で端に来るかは関係ない訳ですね。
まとめると、

• 1が最も長く並んでいる場所を探す
• そこ以外の1の数の2倍だけ、「操作」を行う
• 0の数だけ「操作」を行う

式で書くとこうですね。
答え1 = (「1の個数」-「1が最も多く並んでる個数」) * 2 +「0の個数」

あとはこれを0にする場合でも求めましょう。
答え0 = (「0の個数」-「0が最も多く並んでる個数」) * 2 +「1の個数」

あとは答え0と答え1のうち、小さい方を出力するだけです。

解答例

与えられる時に、標準入力欄には1つの数字のように書き込まれます。
これを1文字ずつ欲しいときにはchar型で取得すればよいみたいですね。
また、char型をint型にしたい場合は'0'を引きます。
文字コードにおいて、char型の数字の文字コードから0の文字コードを引けば0の文字コードとの差、つまりその数字がint型で手に入るって原理らしいです。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int T;  cin >> T;

    for(int i=0; i<T; i++){
        int sum0 = 0, sum1 = 0, count0 = 0, count1 = 0, N, maxCount0 = 0, maxCount1 = 0;
        cin >> N;
        for(int j=0; j<N; j++){
            //1文字ずつchar型で取得、int型に変換
            char c; int n; cin >> c; n = c - '0';
            
            if(n == 0){
                //0の個数をカウント
                sum0++;
                //0が何個連続してるかを記録
                count0++;
                //1の連続カウントはリセット
                count1 = 0;
                //0の連続カウントが過去最大だったらmaxCount0に記録
                if(count0 > maxCount0) maxCount0 = count0;
            }else{
                //1についても0と同様
                sum1++;
                count1++;
                count0 = 0;
                if(count1 > maxCount1) maxCount1 = count1;
            }
        }
        //答え0 = (「0の個数」-「0が最も多く並んでる個数」) * 2 +「1の個数」
        int ans0 = (sum0 - maxCount0) * 2 + sum1;
        //答え1 = (「1の個数」-「1が最も多く並んでる個数」) * 2 +「0の個数」
        int ans1 = (sum1 - maxCount1) * 2 + sum0;
        //小さい方を出力
        cout << min(ans0, ans1) << endl;
    }
}

まとめ

今回は、初めて本番時間内にC問題を解けたので満足な結果です！
B問題に時間がかかってた前回からはかなりの成長！
D問題については本番時間中に解法を特定しコードも書けてたのですが、ちょっとしたミスでWAになってしまったのがもったいなかったです。あと20分くらいあればWAの原因も特定できそうでした…

今回のCやDは特定のアルゴリズムに頼る問題ではなかったため解けましたが、次回に向けてアルゴリズムの勉強を進めたいと思います。
近所の図書館に鉄則本があったので、とりあえず借りてくる予定です。本当は購入したいのですが、鉄則本に限らずプログラミングの解説書ってどれもいい値段しますよね。学生にはつらい出費です…