No.2940 Sigma Sigma Div Floor Problem
解説AC。
コンテスト中は、各i(<=N)について大体√iの計算時間で計算できるので、それをN回やっても間に合うか？ と思ったがTLE。埋め込めばACはできそうだけど実装しなかった。
解説を読むと、シグマを交換するのが本質だった。
割る数を固定するのではなく、割られる数を固定すると約数を考える問題になる。
割る数を固定しても良いところまでいくこともあって思いつかなかったけど、頭の柔軟さが足りないね。
No.2942 Sigma Music Game Level Problem
一応自力AC。
セグ木を二本立てれば簡単にできる問題に見えたがWA。配列Lおよび三つ目のクエリの意味が分からないので、どこか誤読しているのかも……と思ってDへ戻ったが、単純な実装ミスでした。
Aを回数順にしてからセグ木に入れなくてはいけないのにAをそのままでやっていた、セグ木の内部をちょっと書き換えたとき間違っていた、クエリ1でAに何か付け加えるときのupdateの仕方を間違えていた、と三ヶ所。
こんな短い中で三つもミスしているのは良くないねぇ。
No.2943 Sigma String of String Score Problem
自力AC。
DPして部分列の個数を求めて、他の箇所を使うか使わないか決めれば良い。計算量10^8がPyPyで間に合うのか分からないまま提出しましたが、1sもかかりませんでした。
No.2944 Sigma Partition Problem
しばらく考えた後、これって分割数ってやつでは？ と気付き、検索し、ここを参考にしてAC。
分割数のDPを自力で導出するのは難しいけれど、有名な概念だということはすぐ気付きたい。
0 件のコメント:
コメントを投稿