- やった回: ABC322
- 成績: ABCD4完 / 1ペナ / 104:50(ペナ込み)
- パフォーマンス: 1033
何とか前回のつらみを取り返しました。
手を出せていないE問題も一応問題文は読んでいて、何となくABC317-D*1みを感じつつもそのままコンテスト終了。後で解いてみようとは思っていますが今日のところは右目が眼精疲労に因ると思われる職務放棄を始めたのでこの記事を仕上げたら寝ます。
A問題: ABC322-A First ABC 2
String#byteindexを使って最初の"ABC"の出現位置を探索。
今回の制約上問題なかったので実害はなかったのだけど、これは単純にString#indexで良かったのではというセルフツッコミはしておきたい。(単にメソッドを見つけられなかった せっかく教えてもらったのに頭から吹っ飛んでた…)
B問題: ABC322-B Prefix and Suffix
こちらもString#byteindex String#byterindexを使って出現位置を探索し、最初と末尾であるかを検証する。
これもRubyにはString#start_with?とString#end_with?というドンピシャなメソッドがあるのでこっち使えよという感じの問題。
A問題の話とCodeQUEENでの大失態を鑑みるに、私は一度るりまのArray Hash String Integer あたりを通読する必要があるんでないか。
C問題: ABC322-C Festival
にぶたん！にぶたん！
ということで二分探索して都度次の花火がいつかを見ていったんだけど、解説を読んで花火日程の方をeachして行った方が計算量としては軽量に実装できることに気付く。覚えとこ。
D問題: ABC322-D Polyomino
ありうる置き方の可能性をとにかく全探索して、条件が成立する配置が見つかるかどうかを調べる。
せっかくCまで15分未満で片付けたのにえらく苦労したんですがコンテスト時間内に解けたのはとても嬉しかったです。1WAのあと問題読み直して終了10秒前(！)に何とか投げて手を合わせて祈っていたら通ったのでこれは本当に嬉しかった。変なミスがあってランタイムエラーとか起こしてたら泣いてたかもしれない。
でももうちょっと早い段階でACする余地があったので精進頑張ります。
制約から探索量を計算して全探索が可能であるという点は早い段階で確認していて、解説にもある通りABC307-Cで一度経験しているので、実装の重さを感じつつも頑張ってみることにしました。
基本方針としてはおそらく解説の通りの「回転パターン4つ×(3+4+3)2のオフセット位置×テトリミノポリオミノ3個」の全探索。これを素朴に全部ネストすると実装で死ぬと思ったのでDFS的な実装をすることにしました。それでもネスト深くてつらかった。メソッド切り出しとかやったらもうちょっとシンプルに書けたかしら。
なんかあちこちバグらせて結局80分以上この問題に溶かしたんだけど、多分主要なミスはこの辺。
- ループのネストが深くてどこでやる処理なのかこんがらがっていて変なところでループを打ち切ったりなんだりしていた
- 二次元配列のコピーの仕方が間違っていた、
array.map(&:dup)でやらないといけないのにarray.dupでやってておかしなことになっていた- コピーが出来てないことにわりと早いうちに気付いてたんだから自分の頭だけで悩んでないでさっさとやり方調べなさいよという事案
- 問題文の読み落としがあり、グリッドの中を全部埋めないとダメなことに終了5分前に気付いた
二次元配列の回転はABC298-Bで悲鳴上げながらグリッド回転させた後に書いたスニペットが役に立ってよかった。
反省点はありつつも過去の積み上げが確実に生きていると感じた問題でした。
ちなみに多分EはDPだと思う(※まだ解説読んでない)んだけどこっちもそれなりに実装が重そうで、両方を行ったり来たりしている時間はなさそう、かつDの方が確実性が高いであろうと言う判断はまぁまぁよかったのではと思っています。もう75点積めたらよかったのは間違いないけれど。
それでは今週も対ありでした～
