2023/9/30に開催された、AtCoder Beginner Contest 322に参加しました。
再入水以降は、なんとか水色レートは維持できているものの、直近のレートは1224というところで、まだまだ一発爆死で緑落ちしかねない位置にいます。
まず、目先はなんとか水色安全圏ぐらいには行きたいところ。今回も水パフォ取って、Highest更新していこうという気持ちで挑みます。
Rated参加します。
— devgenjin77 (@devgenjin77) 2023年9月30日
水パフォ目指して頑張ります✊
AtCoder Beginner Contest 322 - AtCoder https://t.co/4tK0GOSMiL
今回の結果
Dに苦戦したものの、なんとか5完確保しました。
パフォーマンスの方は、余裕で水色に到達出来ており、レートの方もHighestを更新することが出来ましたとさ。
5完水パフォでHighest更新😂
— devgenjin77 (@devgenjin77) 2023年9月30日
次回も頑張ります✊
devgenjin77さんのAtCoder Beginner Contest 322での成績:1154位
パフォーマンス:1478相当
レーティング:1224→1252 (+28) :)
Highestを更新しました!#AtCoder #ABC322 https://t.co/Pc1yglmqeH
振り返り
AからCが簡単目でしたが、D、E問題が実装重めで、だいぶ苦労しました。
A問題
Javaだと、indexOf
を使うだけで解ける問題でした。1分4秒で1完。
提出コード
https://atcoder.jp/contests/abc322/submissions/46057216
B問題
Javaだと、startsWith
とendsWith
を使って解ける問題でした。4分10秒で2完。
提出コード
https://atcoder.jp/contests/abc322/submissions/46062857
C問題
まず、解答用にサイズの配列を作っておき、-1
で初期化する。
次に、花火の打ち上がる日について、解答用の配列に0
を設定する。
あとは、日目から日目にかけて処理していき、であれば、というように、翌日の値プラス1を入れれば良い。
ということで、軽めの実装でACが取れました。8分51秒で3完です。
提出コード
https://atcoder.jp/contests/abc322/submissions/46070083
D問題
問題を読んだ瞬間、これは実装重めの全探索という感じでした。なんかハマりそうな嫌な予感しかしないので、一旦、この問題はスキップすることに。
で、その後E問題が解けて、F問題が解ける見込みがなさそうという事で、D問題に取り組むことに。以下の要領で、頑張って全探索を実装しました。
#
の合計をカウントし、16
でない場合はNo
とする。3つのピースについて、回転のパターンタテの並行移動がからのパターンヨコの並行移動がからのパターンを全探索。
上記のうち、
#
が外にはみ出るパターンや、枠内で#
が重なってしまうパターンは除外することで枝刈りを行う。最終的に、枠内全てが
#
で埋まればYes
回転操作は自作ライブラリになかったので、ネットから拾って来ました。
そんなこんなで、途中で不明なバグに直面しながらも、なんとか時間内にサンプルを通せる実装を完成させ、ACを取り切ることが出来ましたとさ。
88分25秒で5完。都合50分弱実装に掛かった計算。時間があったのでなんとかなったというところです。
提出コード
https://atcoder.jp/contests/abc322/submissions/46116447
E問題
管理するパラメータが多めなのと、制約が程度であることから、もしかするとフローなのかなと思ったりもしたが、よくよく見るととが小さいので、工夫すればナップザックDPに帰着できそうという印象でした。
管理するパラメータの数が動的なので、どう実装するか迷いましたが、とりあえず最大の場合にだけ備えて6次元配列のDPで組んでみることに。
ネストが深いループを書くのが面倒で、正直バグらせてしまいそうでしたが、一回書いてしまえば、後はコピペでなんとかなるという感じです。
そんなこんなで、なんとか実装を完了。無事ACを取り切ることが出来ましたとさ。36分45秒で4完。
提出コード
https://atcoder.jp/contests/abc322/submissions/46097111
F問題
実は最近、遅延セグ木ライブラリを整備したということもあり、この問題の見た目で、いかにも遅延セグ木の典型だろという印象。
しかしながら、肝心のモノイドをどう組むかが全くわからず。。結局この問題は諦めです。
G問題
問題すら見ておりません。
これまでの実績
今回もHighest更新!この調子で、なんとか目先1300台までは乗せたいところです。
総括
D問題のような実装重め問題は、これまで本番中に実装しきれないことが多かったので、なんとか今回通せたことは嬉しいです。
また、今回のFは上位典型のような感じ。こういうのが本番で通せるようになるとレートの方も伸びてくると思うので、また復習しておこうと思います。
ということで、また次回も頑張ります。