2023/9/16に開催された、トヨタ自動車プログラミングコンテスト2023#5(AtCoder Beginner Contest 320)に参加しました。
現状のレートは、水色ギリギリの位置におり、一度爆死すれば再度の緑落ちになってしまうという状況。
とりあえず、なんとか目先水色安全圏ぐらいまでは上げていきたいところです。水パフォ目指して頑張っていきます。
Rated参加します。
— devgenjin77 (@devgenjin77) 2023年9月16日
今回も、水パフォ以上獲得で水色レート維持を目標に頑張ります✊
トヨタ自動車プログラミングコンテスト2023#5(AtCoder Beginner Contest 320) - AtCoder https://t.co/HZ3oJhpA3D
今回の結果
なんとか5完確保という結果になりました。
しかしながら、複数のペナを食らったりしたため、順位の方はそれほど伸びず。レートも水色に到達せずで、今回は負け。
レート程度で済んで良かったという感じです。
かすり傷で済みました😅
— devgenjin77 (@devgenjin77) 2023年9月16日
devgenjin77さんのトヨタ自動車プログラミングコンテスト2023#5(AtCoder Beginner Contest 320)での成績:2073位
パフォーマンス:1194相当
レーティング:1222→1219 (-3) :(#AtCoder #トヨタ自動車プログラミングコンテスト2023#5(ABC320) https://t.co/WJ1DCJh8rT
振り返り
5完早解き回が必須の回でしたが、くだらないミスが続き、相当順位を落としてしまいました。
A問題
いかにもA問題という感じのシンプルな問題。普通に実装して、普通にACが取れました。
1分48秒で1完。
提出コード
https://atcoder.jp/contests/abc320/submissions/45583300
B問題
あり得る部分文字列を全探索して、一番文字列長が長い回文を判定すれば良いだけ。
あとは、適当に実装して提出。その後、C問題に進みましたが、なんと後で確認するとWA喰らってました。。
どうも、全探索のループの判定がバグってた模様。修正してなんとかACを取ることができましたとさ。
この時点で、先行して取り組んでたC問題でもペナを喰らってたので、都合20分47秒2ペナで2完。大分出遅れてしまいまいた。
提出コード
https://atcoder.jp/contests/abc320/submissions/45601800
C問題
なんか、昔同じような問題を見たような気がするという感じの問題。
各リールについて、0
〜9
の数字それぞれを止めるための最短秒数を管理し、あとは、一番最短の秒数で止めることができる数字を全探索すれば解けるかという感じで実装しました。
が、、これが提出してみるとWA。。実は、同じ秒で止める事ができるリールは1つだけという制約を見逃しておりました。サンプルをテストしておけば防げただけに痛いミスです。
という事で、これをどうやって解くか結構悩みましたが、結局止める順番を順列全探索することにしました。
Javaだと標準で順列全探索が無いので、実装に時間がかかりましたが、なんとかACを取る事ができました。38分50秒2ペナで3完。
提出コード
https://atcoder.jp/contests/abc320/submissions/45616644
D問題
最初、問題を見たときに、Union-Findが要るかなあという感じがしたので、とりあえず各頂点の連結をUnion-Findで管理してみることにしましたが、結局不要でした。
解法としては、まず、各頂点の関連について、隣接リストで構築するグラフとして管理。あとは頂点を始点としたBFSを実施し、それぞれの頂点の位置を計算する感じで実装。
提出して、問題なくACが取れました。
少し無駄な実装があったので、余計な時間を掛けてしまいました。64分29秒2ペナで4完です。
提出コード
https://atcoder.jp/contests/abc320/submissions/45629956
E問題
やたら難しそうな見た目をしているが、順位表のAC数からすると、これを解けないと緑パフォすら怪しいという感じ。何がなんでも解く必要がある問題。
で、解法を検討した結果、人が並んでいる列をTreeSetで管理し、最小の要素の人がそうめんを取れることにすれば良さそう。
また、そうめんを取った人を、TreeSetから一旦削除し、次に列に戻る時刻をPriorityQueueで管理しておけば、次のイベントを見た時に誰が列に戻れるかを計算できそうである。
というわけで、あとは上記の要領で実装して提出。なんとかコンテスト時間内にACを取り切ることができましたとさ。91分31秒2ペナで5完です。
提出コード
https://atcoder.jp/contests/abc320/submissions/45640126
F問題
一応、問題を見てみましたが、何もわからずです。
G問題
問題すら見ておりません。
これまでの実績
再入水後、初の負けを喰らいましたが、なんとか緑落ちは避けることができました。
総括
今回のミスは、サンプルを通しておけば防げたミスだったので勿体なかったという感じです。
また、いつも5完止まりではせいぜい水色パフォーマンスが限界という感じ。今後は6完以上目指せるように高難易度の問題に取り組んでいこうと思います。
ということで、また次回も頑張ります。