ABCEの四完。Dは結構思いつきにくい気がする。Fは難し過ぎませんか？
D - National Railway
解説AC。
難しい！ DPは全く思い浮かばなかった。マンハッタン距離だから、45度回転ばかり考えてたのが敗因か。
F - Coprime Solitaire
色々解説を読んだけど、主にkyopro_friendsさんの公式解説でAC。
2-SATに帰着する問題。
2-SATに帰着できるということは、コンテスト中は思いつかなかったけれど、言われれば確かに、という感じ。少し慣れている人なら思いつけそう。
だけど、その後の処理は難しすぎませんか？
累積和を使えば二乗から線形に計算量を落とせる、と。これは思いつける気がしない。
結構すんなり解けている人もいるようなのだけど、典型テクニックなのだろうか……。
さらに、データの持ち方が悪いとTLEしたり、再帰を使ったSCCだとTLE+MLEしたりと大変でした。（ので、SCCは借りてACしました）
非再帰のSCCは実装しないとまずいですね。
0 件のコメント:
コメントを投稿