i 文字目を A にした時の文字列の作り方の総数を f(i,0) = dp[i-1][0] として f(n) = sum(dp[n-1]) を求める。 例えば７文字の作り方の総数 f(7) を考えるときは新たに条件を満たさなくなるのは、 ○○○○AGC、○○○○GAC、○○○○ACG、○○○A○GC、○○○AG○C、 となるもの…

サンプル２が結構ヒントになった。 まず m が最大値の時に条件を満たせばいいとわかる。 そして、初めの割り当ての２数 ( a, b ) の差(a 一周すると (1,b+n-a+1) となるから、 n = 奇数のときは一周すると偶奇が変わる、n = 偶数のときは偶奇が変わらないと…

atcoder.jp要約すると Σ|Ai-b| (0≤i≤n) を最小にするbがわかるかどうかという問題。 ネタバレすると Ai (0≤i≤n) の中央値が答えとなる。知らなかった。 例題の出力をみて、入力と同じものになっていることに気づくべきだった。 分かりやすい図説があったので…