2021/11/20に開催されたトヨタシステムズプログラミングコンテスト2021(AtCoder Beginner Contest 228)に参加しました。
ここ最近のレートの推移は順調な上昇トレンドを刻んでおり、前回までのコンテストで10回連続でレート上昇という状況。
今回もその流れを途切れさせないようにという気持ちで臨むこととしました。
参加します。ここ最近レート上昇傾向が続いているので、途切れさせないように頑張ります。
— devgenjin77 (@devgenjin77) 2021年11月20日
トヨタシステムズプログラミングコンテスト2021(AtCoder Beginner Contest 228) - AtCoder https://t.co/Kw4YnnO52W
今回の結果
で、今回はなんとか4完を確保することが出来たというところです。
今回もパフォーマンスは4桁台を出すことが出来、レートの方は11連騰となりましたとさ。
4完でレート続伸です😃
— devgenjin77 (@devgenjin77) 2021年11月20日
devgenjin77さんのトヨタシステムズプログラミングコンテスト2021(AtCoder Beginner Contest 228)での成績:1723位
パフォーマンス:1102相当
レーティング:911→931 (+20) :)#AtCoder #トヨタシステムズプログラミングコンテスト2021(ABC228) https://t.co/Cq1qyEkqc5
振り返り
A問題で想定外のWAを喰らったりしましたが、なんとかDまでを解き切ったというところです。
A問題
最近、結構難易度が上がってきた感があるA問題。今回の問題も一読してそこそこ手強い感じがする。
とりあえず、日付が変わることも考慮するということで、の場合、に24を足して、であればYesという感じでいいのでは?
と、雑な考察で投げてみたら、いきなりのWAを喰らってしまいましたorz
その後もをに変えてみたらどうかいう感じで投げてみても再度WAを喰らってしまう。
ここで、それならばと、の場合に、にも24を足して、であればYesという感じでいいのでは?
で、これで投げてみたらやっとこさACがとれましたとさ。
A問題からいきなりの2WAのスタートで、出鼻をくじかれた格好です。
提出コード
https://atcoder.jp/contests/abc228/submissions/27356758
B問題
これについては、解法がすぐに思いついたので助かった。
秘密が伝わったかどうかをON、OFFで管理する配列を用意しておく。友達に秘密が伝わった時、友達に秘密がまだ伝わっていない場合は、をONにする。
この処理を再帰的に繰り返していき、友達に秘密が伝わっている場合は処理を終了する。
最後に、の配列内でONになっている数を答えとして出力すればよい。
ということで、あとは実装だけしてACが取れました。
提出コード
https://atcoder.jp/contests/abc228/submissions/27363241
C問題
各生徒の得点の合計を計算し、降順ソートを行う。あとは、上位から番目の点数に対して、各生徒の得点+300した点数で届く場合YES、そうでない場合NOとすればよい。
あとは実装だけしてACが取れましたとさ。
提出コード
https://atcoder.jp/contests/abc228/submissions/27371650
D問題
そもそも、問題文を理解するところから時間をかけてしまった。。
整理してみると、サイズがの配列があり、要素に値を設定するクエリを処理する際、既に値が入っていた場合は一つずつ右を見ていくというのがやっと理解できた。
どの要素に何の値が入っているかは、Mapなどを使って処理すれば良さそうだが、ある要素を編集しようとした時に最悪ケースだと右の項目を見ていく処理でTLEになってしまいかねないという感じがした。
このような性質の処理について、どのデータ構造を使えば良いかは分からず。で、いろいろ考えた結果一度値を設定しようとした要素の位置と何回その要素に値を入れようとしたかを別のMapで管理しておき、既に値が入っている要素を編集しようとした時は、その要素を参照した回数分右を見るようにすればある程度効率化できるのではというやり方が思いついたので、とりあえずこの方針で実装してみることに。
で、初回の提出は小バグがありREとなったものの、2回目の提出でなんとかギリギリTLEにならずにACを取ることが出来ましたー。
実行時間は、なんと3100msということで想定解法ではなかったようだが、これでなんとか4完を確保。
初っ端のA問題から2WAを喰らい、さすがに今回は冷えるやも?という不安があったのですが、これでとりあえず一安心することが出来ました。
提出コード
https://atcoder.jp/contests/abc228/submissions/27393270
E問題
Dを解いたあとチラ見しましたが、なにも解法が思いつかずで終了です。
F問題
問題すらみれておりません。
G問題
問題すらみれておりません。
H問題
問題すらみれておりません。
これまでの実績
レートの方は11連騰。もう少しでHighest更新というところです。
総括
今回なんとか4完を確保できたというところですが、A問題でWAを出したり、D問題での解法がサッと出てこなかったりと、反省点も多い回でした。
一旦D問題まではちゃんと解き直しの復習をして次回同様の問題に手こずらないようにしたいと考えております。
ということで、また次回も頑張ります。