AtCoder Beginner Contest 122に参加した記録

忘れないうちに書いておきましょう、と思って既に二週間が経過しました……。

この日はちょうど私の所属しているサークルの合宿の日で、サークルのメンバーのうち何人かがAtCoder Beginner Contest (ABC) に参加するという感じで盛り上がっていました。

私はコードを書くのをせかされる感じが嫌なのでコンテストは嫌いだったのですが、まぁ食わず嫌いなのもよくないので参加することにした感じです。

一応、数年前に、競技プログラミングの過去問を解く授業を受けたことはあったし、その授業の教科書（参考書だったかな）として買った蟻本はすべて読んだので、このくらいのレベルの問題は解けないとまずいなぁという思いもありつつ。

（以下、時系列で書いていきますが、少なくともコンテストに関しては初心者中の初心者なので、参考になるところはないと思われます……）

18:30～19:00

サークルメンバーのみんなで夜ご飯を食べました。ABCがあるので参加しようという話が出ました。

20:00～20:45

二分探索難しいとかいう話題で盛り上がりました。C#は書いたことがあるがC++は書いたことのないというメンバーに、最低限の知識（std::cin、std::cout、std::vector、std::string）を教えました。

20:55

やっぱり参加しようと決断し、ノートパソコンを取り出したものの、ファンが壊れていて異音がします……。うるさいので別室で受験することにしましょう。一時間しか寝ていないのでねむい……。

21:00

ABCスタート。とりあえずD問題をちらっと見てDPっぽいなぁと思いました。

21:01

A問題を解きましょう。特に難しいところはないようですが、if文を書くのはめんどくさいなぁとか、条件演算子を書くとみづらくなるなぁとか、そういうことを考えてやや時間を無駄にした感じがあります。 switch文を使ったコードを書いて正答になりました（3:04）。

なお、sed y/ATGC/TACG/でよいということに気付いたのは、コンテスト終了後でした（後述）。

21:03

B問題を解きましょう。制約が非常に緩いので、全ての部分文字列を列挙する手法が可能だなぁと思いました。この手法は、配列インデックス境界バグ*1を生みにくいので制約が緩い以上こっちの方針でやろうと思いました。実際、その方が読みやすく、つまりバグを埋めにくいようなコードになるはずです。

……と思ったら、C++のstd::string::substr関数は（何文字目から、何文字分）みたいな指定方法なので結局境界値バグを生みやすい形ですね……。

冷静に考えると、Θ(N)解法があることに気付きました。尺取り法（の退化したバージョン？）を使えばよさそうです。

私の実力では、このあたりになってくると頭の中だけでプログラミングするのは無理です。特に準備もしてこなかったので環境が整っているわけでもなく、wandboxでコンパイルして確かめることにしました。

とりあえずテストケースに成功したので提出してみます（8:52）。

21:08

C問題を解きましょう。クエリですか、なるほどです。クエリといえば、前処理です。これは累積和でできそうですね。 累積和でやるとすると、落とし穴になりそうなところ（コーナーケース）は、

  • 配列境界（-1要素目とか、N要素目とかにアクセスしてはいけない）
    • 'AC'という二文字を考えるので、str[i-1]とかstr[i+1]で失敗しないように気を付ける必要があります
  • 文字列の切れ目がちょうど'AC'にまたがる場合
    • 単純な累積和よりミスを誘うポイントが増えています
  • その複合
    • 文字列の切れ目が、ちょうど1文字目とか、末尾とか、そういうところになった場合、上記二つ同時に気を付けないといけません
    • （番兵を置いておけばこの問題はなくなりますが、このことに気付いたのはコンテスト終了後でした）

あたりでしょうか。

21:10

あれー、B問題がWAになっています。ちらっとコードを見た感じではバグっている箇所を見抜けませんでした。テストケースの後半が全滅しているのもよくわかりませんが……。とりあえず放置してC問題を解く作業に戻りましょう。

クエリの形式が1-originであることとか、いろいろ混乱し悪戦苦闘した結果、30分弱時間を溶かしましたが、なんとか正答です（35:10）。

サンプルケースがコーナーケースを網羅していたのはやさしさでしょうか。

ちなみに、紙とペンを用意していなかったので、以下のようなアスキーアートをメモ帳（notepad.exe）に描いて考えていました。

 A C A C T A C G 
| | | | | | | | |
0 0 1 1 2 2 2 3 3

21:35

B問題の提出コードをもう一度見てみましょう。文字列終端に達した時に、尺取虫のしっぽを引っ込める作業を忘れていることに気付きました。時間を置くと見つかるものですね。正答です（36:44）。

21:36

さてあと一時間ほどしかありませんが、D問題を解きましょう。【違反してない文字列】の末尾に文字をくっつけた時、【違反】が発生するかを考えればよさそうです。なぜなら、【違反している文字列】の末尾に何かを付け加えても、違反していない状態に戻るわけではないからです。よく考察していませんが、たぶん末尾3文字が「状態」であるDPでうまくいくのではないでしょうか。コピペで以下のコードを作り出しました。

std::uint64_t arr[4][4][4][101]
for( int i = 0; i < 4; ++i )
for( int j = 0; j < 4; ++j )
for( int k = 0; j < 4; ++k )
     if( i == 0 && j == 2 && k == 1 ) arr[i][j][k][3] = 0;
else if( i == 0 && j == 1 && k == 2 ) arr[i][j][k][3] = 0;
else if( i == 2 && j == 0 && k == 1 ) arr[i][j][k][3] = 0;
else arr[i][j][k][3] = 1;

std::size_t N;
std::cin >> N;
for( std::size_t t = 4; t <= N; ++t )
for( int i = 0; i < 4; ++i )
for( int j = 0; j < 4; ++j )
for( int k = 0; j < 4; ++k )
     if( i == 0 && j == 2 && k == 1 ) arr[i][j][k][t] = 0;
else if( i == 0 && j == 1 && k == 2 ) arr[i][j][k][t] = 0;
else if( i == 2 && j == 0 && k == 1 ) arr[i][j][k][t] = 0;
else arr[i][j][k][t] = (arr[i][j][0][t-1] + arr[i][j][1][t-1] + arr[i][j][2][t-1] + arr[i][j][k][3][t-1]) % 1'000'000'007;

std::uint64_t sum = 0;
for( int i = 0; i < 4; ++i )
for( int j = 0; j < 4; ++j )
for( int k = 0; j < 4; ++k )
sum = (sum+arr[i][j][k][N]) % 1'000'000'007;

エレガントさのかけらもありませんが、こちらも必死なので少なくとも自分にはぎりぎり読める感じの、わけのわからないコードになってきました。

いちおう、ケチらずにstd::uint64_tを選択したことにより、貰うDPとして書いてもオーバーフローの心配がないのは良かった点ですが、やっぱり配るDPで書いた方がよかったかなぁと思いつつ、しかし貰うDPとして書いた方が直感的だし(?)こっちでよかったかなとか思っていました。

このコードで3を入力すると61が出るのは当然ですが、4を入力すると235が出てきてテストケースと合いません。つまり、何か漏らしている条件があるのですが、まぁおおむね方針は立ちました。

22:01

arr[i][j][k] = (arr[0][i][j][t-1] + arr[1][i][j][t-1] + arr[2][i][j][t-1] + arr[3][i][j][k][t-1]) % 1'000'000'007;

の方が正しいことに気付きました。 233って出てきました。依然、何か見落としています。

22:04

"xxxxAGx"のような文字列の末尾にCを付け加えると条件に違反することに気付けました。

else if( i == 2 &&  k == 1 ) arr[i][j][k][t] = (arr[1][i][j][t-1] + arr[2][i][j][t-1] + arr[3][i][j][t-1]) %  1'000'000'007;

231って出てきました。もう一条件あるのを見落としていそうです。時間間に合わないかもなぁ、とか思いつつ、N=4のケースで違反する26通りを手で列挙するという作業を地道にこなすことにします（というかコード上で考えるのではなく、最初からそうするべきでした）。

22:18

末尾三文字が"AGC"、"ACG"、"GAC"になっている場合（"AGC"の原因が固まって存在している場合）のほかで違反してしまうパターンがなんとなくわかりました。 つまり、末尾四文字の中に"AGC"の原因が、関係ない一文字を挟んで存在している場合（"AGxC"と"AxGC"）というパターンでした。

else if( j == 2 &&  k == 1 ) arr[i][j][k][t] = (arr[1][i][j][t-1] + arr[2][i][j][t-1] + arr[3][i][j][t-1]) %  1'000'000'007;

ちゃんと230って出ました。N=100のケースを試してみたところ、ぴったり一致したため、ほぼあっている確信を得て提出、正答でした（79:28）。

22:19

この時点では、287位だったっぽいです。知り合いの順位を調べたり、Twitterをしたりして、暇をつぶします。

22:30ごろ

ふと順位表を見たら300位になっていました。なるほど、WAが一回あったから、WAなし80分完答みたいな参加者に抜かされたわけですね。

22:40

コンテストおわり。サークルメンバーと雑談します。

感想戦

D問題（DPのやつ）

  • やはり貰うDPではなく配るDPの方が筋がよかったらしい
  • あと、初期化のために「文字なし」っていう状態を付け加えた、53状態のDPをやるときれいに書けたらしい

C問題（クエリのやつ）

  • あるメンバーは累積和は思いつかなかったものの、（事前に二分探索の話をしていた影響もあって）二分探索で解く方法にたどり着いたらしい
    • 二分探索でも解けるということ自体が興味深い話に思えるので、後日記事を分けて書こうと思います
  • 累積和でどこを基準にするかみたいな話は、自分の中で何かルールを決めておくと、コンテストの限られた時間で思考をまとめやすいという話を伺いました

A問題（簡単なやつ）

  • こういうのはesolangで解く参加者もいるよね、あー普通にsedで解けるじゃん、みたいな話をしました
    • とはいっても、初めてのコンテストで緊張している中、勝手もわからないesolangを使う気にはなれないような……

コンテスト参加者のC問題の正答例を見て

どうやら、ACの区切れ目を気にするのではなく、Aが直前に存在するCっていう風にとらえてカウントしていけばよかったようです（解説ではCが直後に存在するAって書いてありますが、同じことです）。

さすがに配列境界の問題に警戒しすぎたっていうことなのかな？

反省

見通しを立てるのは数秒でできているのに実装に何十分もかかっているあたり、やはり細かいところを詰めるのが苦手だなぁと改めて実感しました。

B問題でのWAのようなものは、単なるケアレスミスと甘く見ず、本当に意識して練習しないとなおらないということを大学受験で経験している*2ので、ちゃんと反省したいです。

準備不足は、いつでも完璧なコンディションでできるわけではないので、それほど悔いていませんが、最低限紙と鉛筆はあった方がよさそうということは学びました。

結果

  • AtCoder Beginner Contest 122
  • 300th / 3024
  • パフォーマンス 1600
  • レーティング 400 (初参加)
  • 段級位 9級

*1:N要素の配列の（0-originで）N番目にアクセスしてしまうみたいなバグ。私はこのバグを発生がちなので、警戒していました

*2:化学の計算問題で計算ミスを多発させていましたが、「本質はわかっているのだから気を付ければ問題ない」と甘くスルーしてしまっていました。幸い、受験までの残り時間が十分にある時期に、この考えが誤りであることに気付いてなおせたので事なきを得ましたが。