競プロ日記#25/05/30

AtCoder

AtCoder Beginner Contest 397

A - Thermometer

• リアルタイムで参加していた回だし余裕ACではあったけど、NoviSteps取り組みでB問題を解くのにaccのCLIで問題を取ってきたのでついでに解いておいた

B - Ticket Gate Log

• 文字の挿入とかややこしいことはしなくてよい。
• あくまでもターゲットを管理するための変数targetをフラグ的に運用して次に来るべきCharが'i'か'o'かを見ていく。ターゲットと実際のCharに差異があればansをインクリメントする。この時差異があったとしてもtargetは変更しないのがポイント。ここがコードベース、結果ベースでは納得できるが直感的に違和感を覚える。
• 要は差異があった場合はansのインクリメントで帳尻を合わせているに過ぎないということを理解する。例としてiiooの場合、targetを「i」で初期化すると最初の「i」はOKなのでtargetが「o」に切り替わって2文字目を判定する。2文字目が「i」なので差異があるということでans++でインクリメントする。
  これが何を意味するかというと2文字目で差異があったからansをインクリメントしてiiとなっている2連続のiの間にoを追加したことを表現しioiを走査し終えたということになっている。その結果次（4文字目＝偶数番目）に来て欲しいのは当然「o」なのでtargetの切り替えは不要ということになる。2文字目に来ていた「i」も適切に2文字目に「o」を追加した結果、適切な場所（3文字目）にスライドされたため必然的にOKとなった。
• そうして出来上がる文字列の文字数が偶数になっているかの判定は最終的なtargetが「i」に戻っているかで判定している。偶数になっていれば最後の文字列が「o」判定されてtargetが「i」に戻るため

int main() {
    string S;
    cin >> S;
    int N = S.size();
    int ans = 0;
    char target = 'i';
    for (char c:S){
        if (c == target){
            target = (target == 'i') ? 'o' : 'i'; // ターゲットの反転
        }else{
            ans++;
        }        
    }
    if (target == 'o'){
            ans++;
        }
    cout << ans << endl;
}

AtCoder Beginner Contest 395

A - Strictly Increasing?

• 簡単

B - Make Target

• 正直添え字ゲーではある。
• jがiを使った式で表されるのだがそのiに下駄を履かせている場合は実際のマス塗では帳尻合わせのデクリメントをしないとおかしなことになる

int main() {
    long long N;
    cin >> N;
    vector<vector<char>> S(N, vector<char>(N, '.'));

    for (long long i = 1;i <= N;i++){
        long long j = N + 1 - i;
        if (i > j){
            continue;
        }

        if (i <= j){
            j--;
            if (i % 2 == 1){
                for (long long k = i - 1;k <= j;k++){
                    for (long long l = i - 1; l <= j; l++){
                        S[k][l] = '#';
                    }
                }
                
            }else{
                for (long long k = i - 1;k <= j;k++){
                    for (long long l = i - 1; l <= j; l++){
                        S[k][l] = '.';
                    }
                }
                
            }
        }
    }
    for (long long i = 0; i < N; i++) {
        for (long long j = 0; j < N; j++) {
            cout << S[i][j];
        }
        cout << endl;
    }
}

C - Uniqueness

• 恥ずかしながら解説AC
• C++における連想配列の使い方をイマイチ抑えてないせいで、連想配列がわからないから別の解法で通そうとしてREみたいな感じだった。
• 「PHPでいいなら正直解けた」とか言うかっこ悪い言い訳を自分に言い聞かせて泣く泣く解説AC

C - Shortest Duplicate Subarray

• 1つ前の問題C - Uniquenessでmapを使ったのでその経験を活かして解けはしたが...って感じですね
• 正直9割自力で実装したのだが無駄に二重ループになっていた部分の解消をGPT先生に聞いて解決したので本番だと通用しないということでNoviStepsでは解説ACにした

C - Debug

• 惜しいところまで実装できた気でいたけどテストケースのうち半分がWAなので余裕で不可
• とりあえずNoviStepsは「挑戦中」にしておいた...。
• まあ解説を読めばわかるし、実際WAをACに変換した後に変換したWの位置をkとしてk-1から走査しなおせば2周以上操作するのを防げるというのはそうだし。実際Wが連続で続いた場合にも帰納法的にWの先頭に戻るだけだからそれはそうなんだけど。本番でその発想に至る自信がない。

余談だん

最近NoviStepsも取り組み始めた。感覚的にはAtCoder ProblemsのBoot camp的な感じだけどより細かく難易度分けされて自分が解けるようになりたいレベルに合わせた難易度で振り分けられている。よって狙っているレーティングに定めた取り組みができるのではないかと。
アルゴ式が一旦落ち着いたのでその枠にNoviStepsを加えて今後は「競技プログラミングの鉄則」「AtCoder Problems(Boot Camp)」「NoviSteps」の3本柱で行こうと思う（後者二つは結局AtCoderの過去問を解くということになるので取り組むコンテンツは実質二つではあるが...）
まだ1日目だが正直NoviStepsの方がBoot campよりは力になる気がする。（鉄則本は全く別のコンセプトなので同時並行必須）問題が細かい難易度準に区分されていることと問題の掲載が直近のABCが優先で出てくるのでちょうど自分が解けるようになりたいレベルの問題が優先的に提供される。Boot campだと簡単すぎたり古いC問題で今のC問題と難易度が乖離していたりする。