AtCoder Beginner Contest 132
解法は見れば分かるが、さらに進んだ考察をしないと実装で手間取る (特に D と F) 回だった。
D - Blue and Red Balls
操作回数 $i$ を固定すると、青いボールの配置と赤いボールの配置は独立。 組合せ ${} _ n C _ r$ の計算をやるだけなので $O(N)$。
それぞれ長さ $N, N - K$ の列の中に $i - 1, i$ 個の区切りを入れて分割する感じのやつ。 ただし長さ $0$ でもいい区間とだめな区間に注意する。 私は理解が甘かったので青いボール側は愚直 DP $O(N^2)$ をしてしまったが、十分な理解があれば実装は軽かったはず。
E - Hopscotch Addict
Dijkstra やるだけ。$O(M \log N)$。
ただし「けん」「けん」「ぱ」のどの位置かの情報をグラフに乗せるため $3 = { 0, 1, 2 }$ との直積 $V \times 3$ の上のグラフで Dijkstra を行う。
F - Small Products
DP。$O(NK)$ の愚直 DP の状態をまとめることで $O(\sqrt{N} K)$ でやる。 $1, 2, 3, \dots, \lfloor \sqrt{N} \rfloor, (l_1, r_1], \dots, (l _ {\lfloor \sqrt{N} \rfloor}, N]$ という $2 \sqrt{N}$ 個に分割してもよいが、約数を用いての分割をするとより楽。
得られる教訓は「DP の基礎となる整礎関係上で区別できない状態はまとめることができる」「$\sqrt{N}$ 個への分割のときは $N$ の約数を境界とするとよい可能性がある」などか。
D: 青をi個に分割して、赤を{i-1,i,i+1}個に分割
— Joe★☆☆☆☆ (@xuzijian629) June 29, 2019
E: 各頂点についてmod3で0,1,2ステップ目に訪れるための最短を記録。幅優先
F: nの各約数aについてdp[i][a]: i個要素を並べて、最右の要素がa以下でaよりひとつ小さい約数より大きいような場合の数
更新は累積和で