FESTIVAL問題概要1~Nまでの番号がついたN個のパネルがある。1度のゲームではK回ボールを投げてi回目にパネルjに当てるとi×Aj点が得られ、各回の点の和が得点となる。いう条件の下でありうる最大の得点を求めよ。2秒には間に合わない。ここでjの小さいほうから順にdpを更新していく過程を見ていると、dp(i-1)から区間を横にずらしつつ最大値を取っていく形になっていることがわかる。このような場合スライド最小値(ここでは最大値だが)のやり方が使えて、これだと計算量がならしでO(N)になる。これでlogが落ちて答えが求まる。おまけ:スライド最大値について(たぶん俺にしかわからないので蟻本2版p300を見てください)。両端キュー(deque)を用意する。このキューには値ではなくインデックスが入るこのキューの並び順は、常に次の条件を満たす左にあるものほど、そのインデックスが指す要素の値が大きい要素の値の大きさが同じ場合は、左にあるものほどインデックス自体が小さいこの条件が満たされている場合、区間の最大値は常にキューの左端に入っているインデックスを参照することでO(1)で得ることができる既にキューがこの状態になっていると仮定して、区間を右にひとつずらすことを考えるとまずずれた結果区間から外れたインデックスをキューから削除する。キューの左端を見て、そのインデックスがそれであればそのままpopする。なければそのインデックスはもうキューの中にはないので何も操作する必要がない。次に新しく加わるインデックスをキューに追加する。今度は右からキューを見ていって、キューが空になるかあるいはキューの右端インデックスの指す要素の値が新しいインデックスの要素の値より小さい間は右をpopし続ける。止まったらそこに新しいインデックスをpushする。以上の操作では各インデックスについてpushとpopが高々1回ずつしか行われないので、ならしでO(N)となる感想まんまとlogをつけてTLEした。ゆきことか昔のABC-Dっぽい教育的問題感がある(スライド最小値名前だけ聞いてシカトしてたので勉強になった)。長さNの01文字列Sが与えられる。(1)はてなブログをはじめよう!fluffyowlさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。