ABC266E 期待値DP. 素直に考えると再帰になる． 再帰で考えた後に，高速化として for などが可能か考えればよい． 最初から綺麗に書こうとしない方が楽． 残り \(x\) ターンのときの答えを \(f(x)\) とおく．\(f(x) = \sum_{d \in [1,6]} \frac{1}{6} max(d,…

ABC265E 移動したときに出てくる座標が少ない事がポイント． ただし，map を使って座標を記録すると重いので， 移動回数を状態に持ちながら dp. 解法0: DP\(dp_{i,s,t} := \) \(i\) 回移動して，そのうち タイプ \(0\)の移動を \(s\) 回， タイプ \(1\)の移…

ABC264E Union-find, クエリ先読み，クエリの逆算． 切断するのは難しいが，結合するのは Union-find を用いれば簡単． クエリを先読みして，逆算すれば結合に書き換えられる． 実装\(M\) 個の発電所は，役割がすべて同じなので区別する必要がない． よって…