No.2276 I Want AC
自力AC。
左側のいくつかを"A"に、残りを"C"にするのが最適。凸性がありそうなので三分探索（今回は中央の二点を調べれば二分探索でOK）。
これくらいのことも思いつかない状態なら、寝て正解だったとも言える。
No.2277 Honest or Dishonest ?
自力AC。これは手間取らずに解けた。
No.2278 Time Bomb Game 2
解説AC。
自分が最初にいるマスの幅以外関係ないのでは？ というのが直感で、大体それは合っていたものの、幅が1のときなどコーナーが多く、解き切るのは難しい。
No.2279 OR Insertion
解説AC。
桁ごとに考えるのは分かる。制約を見ると、その後DPすれば良さそうなのだが、どういうDPをすれば良いか分からなかった。
DPで分割方法を求めようと思うのが重要。
問題文に「分割の仕方は$2^{N-1}$」とある通り、分割の仕方はDPしなくても求められるが、DPでも求められるのは頭に入れておきたい。
そう思えば、orの桁iが立っている/立っていないで場合分けして、Sのj文字目まで見たときのそれぞれの分割の仕方をDPで求めようという方針は立ちそう。
No.2280 FizzBuzz Difference
解説AC。
全く中国剰余定理を思いつかなかったが、分かってしまえば中国剰余定理の良い練習問題、という感じがする。適切に式を変形すれば中国剰余定理を使える形になるのだが、慣れていないと思いつくのも容易ではなさそう。
こういうタイプの問題で中国剰余定理を使えることがある、と頭に入れておくしかないか。
0 件のコメント:
コメントを投稿