トヨタシステムズプログラミングコンテスト2021(AtCoder Beginner Contest 228) 参加記

2021/11/20に開催されたトヨタシステムズプログラミングコンテスト2021(AtCoder Beginner Contest 228)に参加しました。

atcoder.jp

ここ最近のレートの推移は順調な上昇トレンドを刻んでおり、前回までのコンテストで10回連続でレート上昇という状況。

今回もその流れを途切れさせないようにという気持ちで臨むこととしました。

今回の結果

で、今回はなんとか4完を確保することが出来たというところです。

ABC228結果
ABC228結果

今回もパフォーマンスは4桁台を出すことが出来、レートの方は11連騰となりましたとさ。

振り返り

A問題で想定外のWAを喰らったりしましたが、なんとかDまでを解き切ったというところです。

ABC228提出結果
ABC228提出結果

A問題

A - On and Off

最近、結構難易度が上がってきた感があるA問題。今回の問題も一読してそこそこ手強い感じがする。

とりあえず、日付が変わることも考慮するということで、S \gt Tの場合、Tに24を足して、 S \le X \ le TであればYesという感じでいいのでは?

と、雑な考察で投げてみたら、いきなりのWAを喰らってしまいましたorz

その後もS \gt TS \ge Tに変えてみたらどうかいう感じで投げてみても再度WAを喰らってしまう。

ここで、それならばと、X \gt Sの場合に、Xにも24を足して、 S \le X \le TであればYesという感じでいいのでは?

で、これで投げてみたらやっとこさACがとれましたとさ。

A問題からいきなりの2WAのスタートで、出鼻をくじかれた格好です。

提出コード

https://atcoder.jp/contests/abc228/submissions/27356758

B問題

B - Takahashi's Secret

これについては、解法がすぐに思いついたので助かった。

秘密が伝わったかどうかをON、OFFで管理する配列Sを用意しておく。友達iに秘密が伝わった時、友達A_iに秘密がまだ伝わっていない場合は、S_{A_i}をONにする。

この処理を再帰的に繰り返していき、友達A_iに秘密が伝わっている場合は処理を終了する。

最後に、Sの配列内でONになっている数を答えとして出力すればよい。

ということで、あとは実装だけしてACが取れました。

提出コード

https://atcoder.jp/contests/abc228/submissions/27363241

C問題

C - Final Day

各生徒の得点の合計を計算し、降順ソートを行う。あとは、上位からK番目の点数に対して、各生徒の得点+300した点数で届く場合YES、そうでない場合NOとすればよい。

あとは実装だけしてACが取れましたとさ。

提出コード

https://atcoder.jp/contests/abc228/submissions/27371650

D問題

D - Linear Probing

そもそも、問題文を理解するところから時間をかけてしまった。。

整理してみると、サイズが2^{20} の配列があり、要素に値を設定するクエリを処理する際、既に値が入っていた場合は一つずつ右を見ていくというのがやっと理解できた。

どの要素に何の値が入っているかは、Mapなどを使って処理すれば良さそうだが、ある要素を編集しようとした時に最悪ケースだと右の項目を見ていく処理でTLEになってしまいかねないという感じがした。

このような性質の処理について、どのデータ構造を使えば良いかは分からず。で、いろいろ考えた結果一度値を設定しようとした要素の位置と何回その要素に値を入れようとしたかを別のMapで管理しておき、既に値が入っている要素を編集しようとした時は、その要素を参照した回数分右を見るようにすればある程度効率化できるのではというやり方が思いついたので、とりあえずこの方針で実装してみることに。

で、初回の提出は小バグがありREとなったものの、2回目の提出でなんとかギリギリTLEにならずにACを取ることが出来ましたー。

実行時間は、なんと3100msということで想定解法ではなかったようだが、これでなんとか4完を確保。

初っ端のA問題から2WAを喰らい、さすがに今回は冷えるやも?という不安があったのですが、これでとりあえず一安心することが出来ました。

提出コード

https://atcoder.jp/contests/abc228/submissions/27393270

E問題

E - Integer Sequence Fair

Dを解いたあとチラ見しましたが、なにも解法が思いつかずで終了です。

F問題

F - Stamp Game

問題すらみれておりません。

G問題

G - Digits on Grid

問題すらみれておりません。

H問題

H - Histogram

問題すらみれておりません。

これまでの実績

レートの方は11連騰。もう少しでHighest更新というところです。

コンテスト実績
コンテスト実績

総括

今回なんとか4完を確保できたというところですが、A問題でWAを出したり、D問題での解法がサッと出てこなかったりと、反省点も多い回でした。

一旦D問題まではちゃんと解き直しの復習をして次回同様の問題に手こずらないようにしたいと考えております。

ということで、また次回も頑張ります。