結論

コーナーケースには気を付けようという話です。

要約

水色昇格チャンスのコンテストでギリギリ届かなかった。
コーナーケースに気が付いていたら水色になっていた。
コーナーケースには気を付けよう。
色変前に歯がゆい思いをしたとしても、最後まで頑張ってほしい。

はじめに

この記事はAtCoderのABC253で起きた出来事です。1年以上前の出来事ですが、失敗したことで昇格を逃すというのは全員が経験するものではないと思いました。今振り返れば貴重な経験だったのかもしれないと思い、記事として投稿する次第です。

ABC253

当時の状況

ABC253に臨むときの私のレーティングが1165です。

ratedのコンテスト参加回数はおおよそ60回。その中で最高パフォーマンスはABC245で出した1597です。
もし、同じぐらいのパフォーマンスを出すことができればABC253で水色に昇格することも十分可能です。
AtCoderを始めた当初から、水色を目標としており、いよいよゴールに届くとこまで来てます。
ということで個人的にはいつもより緊張するコンテストになっていました。

コンテスト中

A～Dは難なくAC。

C、Dはハマるときは本当にハマります。でも今回は約28分でACできたので、水色になれるのではとさらに期待が膨れます。

緊張を抑えながらE問題を開きます。

具体的な解説は割愛しますが、累積和を利用した動的計画法で条件を満たすものを数え上げていけば答えが求められる問題です。考察も早い段階で気が付くことができたので、実装は難しいですが何とか頑張って実装していきます。

コードが完成。サンプルケースが通っていることも確認し、提出します。

しかし結果はWA

2ケースが失敗していました。ここでかなりテンパったのを覚えています。しかし、ここは一度冷静に。問題文、提出コードを見直します。
失敗ケースが少ないことから、もしかしたらコーナーケースかもしれない。そこに焦点を絞ったところ、$K=0$の場合、2重でカウントしてしまっているコードになっていることが分かりました。

E.cpp

// ...
    for(ll i = 1; i <= N; i++) {
        for(ll j = 1; j <= M; j++) {
            if(j + K <= M) {
                // →(1)ここで「(以前の項) + K」以上のものをカウント
                dp.at(i + 1).at(j) += (sum.at(i).at(M) - sum.at(i).at(j + K - 1));
            }
            if(j - K >= 1) {
                // →(2)ここで「(以前の項) - K」以下のものをカウント
                dp.at(i + 1).at(j) += (sum.at(i).at(j - K) - sum.at(i).at(0));
            }
            /*
            K = 0の場合、(1)と(2)の両方が該当する。つまり2重カウントをしてしまう。
            */
        }
        for(ll j = 1; j <= M; j++) {
            sum.at(i + 1).at(j) += sum.at(i + 1).at(j - 1) + dp.at(i + 1).at(j);
        }
    }
// ...

そこで$K = 0$の場合を考えます。この場合は各項が$1$以上$M$以下であれば何でもOKなので$M^N$を出力すれば良さそうです。そのようにコードを修正して提出。

結果、AC

コーナーケースを見落としたものの、それでもEはACすることができました。

その後は何もできないまま、コンテストは終了。

結果

もしかしたら水色になれるかもしれない、どうだとドキドキしながら待ってました。
そして出てきた最終結果がこちら

1足りない・・・・

いや、最高レートは更新してます。パフォーマンス1462なんてなかなか取れないです。結果としては大成功なんです。それでも、レーティングはあと1足りなかった。

この時、ふと脳裏をよぎるのです。
「WAのペナルティが無ければ届いてたよな・・・？」
「ってことは、E問題のコーナーケースに気が付いていれば昇格できた・・・」

最高レートを更新した嬉しさと、あと少しの注意でチャンスを逃した悔しさが混ざった何とも言えない気持ちになったことを今でも覚えています。

WAを1度出して、その結果を見てからコーナーケースの存在を疑いました。このことから、当時の実力では提出前に気づく余地がなかったかもしれません。しかしそれでもコーナーケースに気づいていればと考えてしまうものです。

この結果を通しての教訓

教訓になったと感じている点を挙げます。

提出前にサンプルケースが通っているかは必ず確認しておく
少しでもコーナーケースがありそうと思ったら、自作でケースを作って確認する。
- 各制約の最小値(N = 1, H = 1, W = 1, K = 0など)は特にコーナーケースが発生しやすい
WAになった時、失敗のケースが少なければコーナーケースがある可能性が高い。今一度発生しやすいところがないか調べる。
実装が難しい問題は注意すべきところを見落としやすい。だからこそ見落としがないかより慎重に。

ということでこの記事を読んでくれた方1人でも私の失敗が役に立っていただけると幸いです。

その後

その後もレーティングは上下しましたが、ABC258にて水色に到達できました。

水色になってからは燃え尽き症候群とか育児とかで恥ずかしながらめっきり参加してないです。それでもAtCoderはとても楽しいですし自分のペースで過去問を解いていきたいと考えております。

最後に、紆余曲折ありましたが、こうして水色まで到達することができております。
私の例のみで話すことになりますが、「茶・緑・水色までもう一歩」というところまで来ている方がいらっしゃれば、到達する実力は十分ついていると思います。だからこそ色変前に歯がゆい思いをしたとしても、最後まで頑張ってほしいと僭越ながらアドバイスしたいと思います。

以上です。