- やった回: ABC304
- 成績: ABCDE5完🎉 / 3ペナ/ 95:33(ペナ込み)
- 推定パフォーマンス: 全体unratedだったので確認できず、1522位あたりだったので多分緑-水色ボーダーくらい(マジで？？)
ratedで参加できていれば個人ベストが取れたという理屈になるんだけど、rated成立していればもっと解かれていたのではという気はする。
A問題: ABC304-A First Player
RubyにはArray#rotateという素晴らしいメソッドがあるので、順に入力を受け取って先頭になるべきインデックスを判断したら名前のリストをrotateしてやる。
B問題: ABC304-B Subscribers
値が10^3以上であれば切り捨てる桁を1つずつ上げていく。
ひたすら1の位だけを切り捨てていたことに気付かないというしょうもないWAを出した後にAC。
C問題: ABC304-C Virus
UnionFindで解いたんだけど、C問題なので基本の想定解法はDFSかBFSだったらしい。多分UnionFindの方が考えるのは楽だと思う。*1
距離が一定以下であれば同じ連結成分としてまとめていって、最後に同じ連結成分に属しているかを順に検証していけばOK。UnionFindに若干の苦手意識があったので、一発で通ってほっとした。
D問題: ABC304-DA Piece of Cake
二分探索の問題。
イチゴが載っているケーキに0,0から順に番号を振っていって、イチゴの座標から置かれているケーキのIDを出してハッシュで数え上げていけばだいたい答えになる。イチゴが乗ってないケーキがあるケースにだけ注意。
ちょっと方針に悩んだけど最終的にちゃんと解けてよかった。
最初無駄にハッシュ全部に初期値を突っ込み、管理するデータ量が多すぎてTLEとランタイムエラーを起こし1ペナ、その後IDの算出をミスっていてもう1ペナ。
冷静にコードを読み直して「計算ミスってそうなのここしかなくね？」と判断して直せたのが良かった。グリッドにIDを振るときの計算方法、絶対覚えられないと思ってスニペットに書いてあった(過去の私えらい)んだけど変数多くて混乱したのがちょっと悔しい。
E問題: ABC304-E Good Graph
これもUnionFindで解いた。
- 最初のm回ループで繋がった両辺をmergeする
- 次のk回ループでxとyの属するグループを確認しておき、「くっつけてはいけないグループの組」としてハッシュに持たせておく
- 最後のq回のループでpとqの属するグループを確認し、くっつけてはいけないグループの組に含まれているかをチェックする
Dの方針に悩んだときにちらっと問題を読み、これワンチャン行けんじゃねと思ってやってみたらわりとすんなり解けてしまって驚いた。
*1:C問題はときどきこういうのがある
