AtCoder ABC379 振り返り

AtCoder Beginner Contest 379 の振り返りです。

AtCoder Beginner Contest 379

今回こそはD問題をと意気込んで挑んだものの、逆に大爆死しました。
D問題どころかC問題も解けず、結果的にはA・Bの2問だけの正解でした。
タイムが良かったからか、レーティングは下がらなかったことは不幸中の幸いと言うべきだろうか。

コンテスト成績 >

A: Solved

与えられた３桁の数字において、各桁の順番を２パターン入れ替えて表示する問題。

色々解き方ありそうだけれど、単純に各桁を変数に入れておいて順番通り表示する戦略にした。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    int a = n/100;
    int b = (n/10)%10;
    int c = n%10;
    cout << b << c << a << " " << c << a << b << endl;
}

B: Solved

OとXで構成された文字列からOがK個連続する部分列の個数をカウントする問題。
いちごがどうとか、歯がどうとか意味のわからない問題設定だったのが気になって問題文が全然頭に入ってこなかった。

文字列の前から順番にOが連続する個数をカウントしてK個を超えたところでカウントしつつ、Xが出てきたらカウントをリセットするというロジックでACできた。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n,k,c=0,ans=0;
    cin >> n >> k;
    string s;
    cin >> s;
 
    for(int i = 0; i < n; i++){
        if(s[i] == 'O'){
            c++;
            if(c == k){
                ans++;
                c = 0;
            }
        } else {
            c = 0;
        }
    }
    cout << ans << endl;
}

C: Up-solve

複数ならべた箱の個数と、何番目の箱に何個の石が入っているかが与えられた時、石を一つずつ片方向に移動させていき、何回の移動ですべての箱に石がある状態にできるかと言う問題。

まず、単純に箱の配列を用意して、後ろから足りない石の数を足し上げていく戦略をとったが、これが見事にLTEとWAになってしまう。
そこで、与えられる箱の番号ごとに後方から空いている箱の数から石の移動回数を割り出して、足し上げていく方針に変更する。 なお、石の入っていない箱がd個連続した場合に必要となる石の移動回数はd * (d+1) / 2で求められる。 さらに、与えられる箱の番号と石の数がソートされていないことに気がつきpairに詰めてからソートする処理を足した。

これでテストケースは突破して提出したところ、どうしてもWAが取れなくなってしまい、そのままタイムアップとなってしまった。

その後、解説を読みつつ解き直してみたが、解説に書いてある全ての石についてそれが入っているマスの番号の総和がどうして石の移動回数と一致するのかはイマイチ理解し切れていない。

D: Up-solve

コンテスト時間内には手をつけられなかったD問題を終了後に見てみたところ、解けそうだったので解いてみた。

問題としては、クエリに基づいて植えた苗木の成長を管理して、一定以上に成長したら収穫して、その本数を答える問題。

まず、苗の成長ペースはすべて同じなので、植物の高さを累積和で管理することにして、その上で苗を植えたタイミングだけQueueで管理することで割と素直に解けた。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int q;
    queue<long long> que;
    cin >> q;
 
    vevtor<long long> h(q+1);
    h[0] = 0;
    
    for(int i; i < q; i++){
        int n;
        cin >> n;
 
        if (n == 1){
            que.push(i);
            h[i+1] = h[i];
        } else if(n==2){
            long long t;
            cin >> t;
            h[i+1] = h[i]+t;
        } else {
            long long hei,ans = 0;
            cin >> hei;
            h[i+1] = h[i];
            while(!que.empty() && h[i+1] - h[que.front()] >= hei){
                ans++;
                que.pop();
            }
            cout << ans << endl;
        }
    }
}

所感

ABの2問しか解けなかったのが悔しいが、特にC問題にこだわりすぎてしまい、解けたはずのD問題を放置してしまったのが反省点。 ある程度の早解きは大事だけれど、C問題で詰まったらちゃんと戦略的なモードに切り替えて他の問題も読んでみるようにしようかと思う。

とはいえ、早解きの効能なのかレーティング自体は少し上がったので、悔しさは拭えないものの少しホッとした。
このところアカウント登録からのハネムーン期間が終わり、レーティングが自分の能力の適正値に近づいてきている実感がある。 そもそもレーティングってそう言うものなんだけれど、ここからは自分の実力をしっかり伸ばしていかないとだな。

来週も頑張ります。