Eまで五完の上、ペナルティをたくさん出してまずい。
コンテスト後のツイート
E 累積和Sを取り、S[i+K]以外の箇所に現在の場合の数を加算。累積和を使って加算する個数は処理できる。減産についても累積和を考え、dict Dを使ってD[i+K]-=（現在の場合の数）のようにする。
— titia (@titia_til) September 7, 2024
F - Cake Division
解説AC。
二分探索するのは分かるが、全点から試さなくてはいけなそうで、どうすれば良いか分からなかった。コンテスト中はそこを高速化することは思いつかず、全部試さなくてもいくつか点を試せば良いのかなぁ、というのを提出してWA。
ダブリングで高速化できるのはなるほど、でした。
あと、コンテスト中は、全点を試す→二分探索の順番で考えていたことも思いつかなかった原因かも。順番を変え、二分探索→全点を試すで考えるのが重要だった。
結構難しいが、以前、類題を解いたことがあったことを考えると解けなくてはいけない問題だった。
0 件のコメント:
コメントを投稿