AT_intro_heuristics_c Incremental Scoring

[problemUrl]: https://atcoder.jp/contests/intro-heuristics/tasks/intro_heuristics_c $ D $ 日分のコンテストの日程と、$ M $ 回の日程の変更クエリが与えられます。 $ i $ 番目のクエリでは整数 $ d_i $ と $ q_i $ が与えられるので、$ d_i $ 日目に行うコンテストのタイプを $ q_i $ に変更し、変更後の日程における最終的な満足度を出力してください。 注意: 変更はクエリ後も継続します。つまり $ i $ 番目のクエリは $ (i-1) $ 番目のクエリでの変更後の日程に対して適用します。

入力は問題Aの入力の末尾に問題Aの出力とクエリの情報が続く形で与えられる。 > $ D $ $ c_1 $ $ c_2 $ $ \cdots $ $ c_{26} $ $ s_{1,1} $ $ s_{1,2} $ $ \cdots $ $ s_{1,26} $ $ \vdots $ $ s_{D,1} $ $ s_{D,2} $ $ \cdots $ $ s_{D,26} $ $ t_1 $ $ t_2 $ $ \vdots $ $ t_D $ $ M $ $ d_1 $ $ q_1 $ $ d_2 $ $ q_2 $ $ \vdots $ $ d_M $ $ q_M $ - 問題Aの入力に該当する部分の制約及び生成方法は問題Aのものと同じである。 - 問題Aの出力に該当する部分は、各 $ d $ について $ 1\leq\ t_d\ \leq\ 26 $ を満たし、範囲内から一様ランダムに生成される。 - クエリ数 $ M $ は $ 1\leq\ M\leq\ 10^5 $ を満たす整数値。 - 各 $ d_i $ は $ 1\leq\ d_i\leq\ D $ を満たす整数値で、範囲内から一様ランダムに生成される。 - 各 $ q_i $ は $ 1\leq\ q_i\leq\ 26 $ を満たす整数値で、クエリ時点での日程における $ d_i $ 日目のコンテストのタイプと異なる 25 個の値の中から一様ランダムに生成される。

$ i $ 番目のクエリを処理した後の日程における最終的な満足度を $ v_i $ としたとき、以下のフォーマットで出力せよ。 > $ v_1 $ $ v_2 $ $ \vdots $ $ v_M $

### 入門者向けガイド 出来るだけ良い解を求めるための非常に強力な手法の一つが「局所探索法」です。 この手法では、闇雲に一から解を探すのではなく、既に見つけた解を少し変化させることで、より良い解に出来ないかを試します。 解が良くなっていれば更新し、悪くなってしまったら元に戻します。 この操作を繰り返し反復することで、時間をかけて徐々に解の質を高めていきます。 疑似コードで表すと以下のようになります。 ``` solution = 初期解(ランダム生成や、貪欲法など他の手法で求めたものを利用) while 時間のある限り: solution を(ランダムに)少し変形 if 変形前より解が悪化: solution を変形前の状態に戻す ``` 例えばこの問題の場合、変形操作として「日付 $ d $ とコンテストタイプ $ q $ をランダムに選び、$ d $ 日目に開催するコンテストをタイプ $ q $ に変更する」というものを考えることが出来ます。 疑似コードで表すと以下のようになります。 ``` t[1..D] = 初期解(ランダム生成や、貪欲法で求めたものを利用) while 時間のある限り: d と q をランダムに選ぶ。 old = t[d] # 後で戻せるように元の値を記憶しておく t[d] = q if 変形前より解が悪化: t[d] = old ``` 局所探索法を用いる上で最も重要なことは、どのように変形を行うかの設計です。 1. 変化させる量が小さすぎるとすぐに行き止まり(局所最適解)に陥ってしまい、逆に、変化させる量が大きすぎると闇雲に探す状態に近くなって、改善できる確率が低くなってしまう。 2. 反復回数を増やすために、変形後のスコアが高速に計算出来ることが望ましい。 この問題Cでは特に2番目の点に挑戦します。 変形後のスコアはもちろん一からスコア計算を行うことで計算が可能ですが、変化のあった部分だけに着目して変形前からの差分を計算することで、より高速に行うことができる可能性があります。 逆に、そのような高速化が出来ないということは部分的な変更がスコア計算の大部分に影響を与えているということであり、変形操作の見直しが必要であったり、そもそも局所探索には向いていない問題である可能性が高まります。 さて、高速な差分計算に挑戦してみましょう。 ABCやARCなどで培ったアルゴリズムやデータ構造の力を発揮するチャンスです。 今回のような最適解ではなく出来るだけ良い解を求めるタイプのコンテストでは、バグのあるプログラムを提出しても不正解とはならないため、バグに気づくのが遅れる可能性があります。 バグの早期発見のために、複雑な処理を実装した箇所に対しては単体テストをしておくのも一つの手です。 例えばスコアの差分計算を行う場合は、この問題Cのような形で、一からスコアを計算した場合と一致することをテストしておくと良いでしょう。 ### 次のステップ 問題Aに戻って局所探索法による解答を実装をしてみましょう。 この問題の場合、「日付 $ d $ とコンテストタイプ $ q $ をランダムに選び、$ d $ 日目に開催するコンテストをタイプ $ q $ に変更する」という変形操作は実はあまり良くありません。 なぜ良くないかを考え、別の変形操作に改良してみましょう。 局所探索法の改良版として、悪化する変形を確率的に受け入れることで優れた解に到達しやすくした「焼きなまし法」がよく用いられます。 他の変形操作の例と焼きなまし法やその他の局所探索法についてはコンテスト終了後の解説を参照してください。 ### Sample Explanation 1 注意: この入出力例は問題仕様の確認用の小さいもので、制約 $ D=365 $ を満たしておらず、実際にテストケースとして与えられることはない。