A No.1033 乱数サイ

$K$ 個のサイコロを振ると考えればよいんですかね？サンプルを見ながら式変形してたら $N/2$ になってびっくりしました。期待値なのでそれはそうかも。

B No.1034 テスターのふっぴーさん

この問題、コンテスト中じゃなくて普段の精進で出会いたかったですね。

解き方は分かっても実装の前にだいぶ慎重になりました。良問な気がする。

4つの壁までの距離を出しておいて、タマネギの皮を外すみたいに外側から削っておき、壁沿いに $(I, J)$ があるような状態に帰着させて解きました。

包除原理

「 $M$ 種類以下」のペンキで塗り分ける方法を各 $M$ について求めて足したり引いたりします。

連続部分列という問題設定、またある連続部分列が条件を満たしたらそれを左右に延長したものも条件を満たすことから、尺取り法ができそう。

しかし、ある区間でgcd=1として、左端をひとつ右にずらしたらgcdがどうなるかというのは $O(1)$ では計算できない。

セグ木ぺたり（ええ）

これで $l$ を1ずつforループで動かしながら $r$ を適宜右にずらすと答えが出ます。計算量 $O(n \log n \log a)$

gcdの単位元は $0$ でしたね（毎回ちょっとだけ不安になる）

追記：sliding window aggregationなるものを使うとlogが落とせる。

パッと見て最初に浮かぶのは蟻本P73のExpedition（めっちゃ似てる）なんですが、 $w_i$ の処理をどうしたものかとしばらくストールしてしまいました。

各地点での最適な状況はその地点にいるときにはまだわからないけど、 $(地点, 残り燃料)$ について最適化して遷移していけば良さそうなので、DP。実際 $O(NV)$ が入りきります。

$\mathrm{DP}(i, j) = x_i$ 地点で残り燃料が $j$ のときの最小費用

$x_0 = 0, x_{n+1} = L$ とすると楽でした。