- やった回: ABC320
- 成績: ABD3完 / 2ペナ(＋未AC2ペナ) / 63:28(ペナ込み)
- パフォーマンス: 931
緑復帰は次回以降にお預けですが、少しパフォーマンスが持ち直してきたのでうれしいです。
なんか問題文の誤読とか難しく考えすぎて無駄にWAとかがあるので落ち着いてやっていきたい。
A問題: ABC320-A Leyland Number
ごくシンプルな問題なのでちょっとfirst AC狙ってみたくなって書いたままテストせずに出したんだけど、これでもRubyだけでもあと2人早い人がいた。
B問題: ABC320-B Longest Palindrome
先頭と末尾の組み合わせを全探索でreverseしたやつと都度比較、一番長い文字列を探す。 なんか変に難しく考えてしまって無駄に2WAしたのがくやしい。
C問題: ABC320-C Slot Strategy 2 (Easy)
(upsolveコード) atcoder.jp
upsolveコードはコンテスト後、Rails Girlsの競プロ同好会にも参加してくださっているべーた(@beta_chelsea)さんと感想戦やりながらモブプロして書きました。String#indexというこの問題には便利すぎるメソッドを教えていただく🙌
Mが100と短いので全探索の気配を感じつつも、コンテスト中は「どのリールを先に止めてもよい」というポイントに気付かずとりあえずサンプルが通った(なんで？)ところで投げてみたら全然ダメで、興味本位で順位表を見てみたらAC率にデジャブを感じたので飛ばしました。
D問題を通してE問題に挫折したところで戻ってきて問題文を読み直し、残り10分のところで解説に近い解法に気付く。
この問題のポイントは2つ。
- 問題の制約上最大10個しか最小値を取りうる値の選択肢がないこと
- 最悪リールが3周するまでには探索が終了し、リールの長さは最大100なので3倍に伸ばしても十分高速に探索できること
- これを教えてもらって前にやった典型90のCake Cut(★3)を思い出した
3つのリールの値をArray#intersectionしてさらに探索する数を減らし(ついでに対象の値がない問題も解決させる)、String#indexの第2引数で指定したインデックス以降の値を見ることが出来るのがめちゃありがたくて、他にもいろいろ便利メソッドを活用して解いていったのでupsolveしてる間「Ruby素敵！」ってずっと言ってました。めちゃ楽しかったです。べーたさんありがとうございました！
D問題: ABC320-D Relative Position
「これはUnionFindとDFSの合わせ技ですね！？」と思ってやってみたんですが、解いてACしたのを確認した後にDFSだけで十分だったことに気付きました。TLE起こさなくてよかったです*1。
パッと見有向グラフに見えるんですが符号をひっくり返せば逆向きも普通に表現できるのでそれで普通に無向グラフにした後、1からDFSしていって座標を順に計算していく。1から繋がってなければ今回は座標が出せないのでその判断だけすればOK。
コンテスト後にUnionFind削って出してみたのがこちらとなります。 atcoder.jp
E問題: ABC320-E Somen Nagashi
(upsolveコード) atcoder.jp
SortedSetとHashで素朴にシミュレーションしたらTLE起こしたのでコンテスト中はそのまま撤退、終了後に他の人のコードを参考にしながら ac-library-rb にあるPriorityQueueを使って書き換えてみたらびっくりするほどすんなり通った。
新ジャッジサーバーにはac-library-rbのgemが入ってるので、定義のコピペ不要でありがたや～🙏
これ、最初優先度付きキューを管理するのに使っていたSortedSetが重いのかと思っていたらむしろ戻ってくるタイミングを管理する構造に問題があったみたいで、待ち行列の方はSortedSetに戻しても通った。SortedSetに対する冤罪がひどい。(というか3.0でSortedSet消えてたの全然気づいてなかった…)
戻りのタイミングはちょっとキーの二分探索でもしないとつらそうで、シンプルにやりたいならPriorityQueue使うのが正攻法っぽかった。
そうなると待ち行列の方に敢えてSortedSetを使う理由もないので、前者のコードが一番シンプルでよいのかなという感じ。
ぽつぽつとE問題も現実的に射程に入り始めているので、 ac-library-rb もそろそろ読み込み始めないといけなさそうな気配を感じています。UnionFindもこっちの使うスタイルにしていきたい。
今週も対ありでした～
*1:あんまりUnionFindでTLE起こすイメージはないんですが
