問題 atcoder.jp 解法 区間DPで解く。 区間DPとは、区間を表す添え字を持つ動的計画法(DP)のことです。 𝑑𝑝[𝑙][𝑟] := 区間 [ l, r ) について、最適な状況下での何かしらの値 dp[0][0]から、幅0でdp[0][0], dp[1][1], dp[2][2] ....と計算していく。 先攻後攻…

問題 atcoder.jp 解法 K個の石の山に対して、 dp[k] := k個の石からなる山で先手が勝ち状態か(=1なら勝ち状態） というdpを設計。 数が小さい方から、Kまでの石の山をシミュレーションしてdpの数値を埋めていく。 まずはk = 0と非常に単純な状態から調べてい…