Codeforces Round #602 (Div. 1, based on Technocup 2020 Elimination Round 3) - D2. Wrong Answer on test 233 (Hard Version)

問題リンク

解説

右隣と同じならば、どの数字を選んでも点数に差がでないです。

以下、右隣と違うものを考えます。

右隣と違うものが cnt個あるとしましょう。

  • 右の数字を選ぶ→点数の差が+1
  • 左の数字を選ぶ→点数の差が-1
  • どちらも選ばない→点数の差がそのまま

となります。よってここで、 cnt個のうち、左右のどちらかを選ぶ個数 iを固定しましょう。

このとき、 cnt - kは左右のどちらでもない数字を選ぶので、 (k - 2) ^ {cnt - i}通りあります。

左右のどちらかを選ぶときは、基本的に 2^{i - 1}通りあります(左右どちらかが多いのは対称なので)

ただし、 iが偶数の場合は左右が同じ数になるのを引いてから考えておきましょう。( {} _ {i} C _ {i/2}通りあります)

提出コード

実装では左右に選ばない数を iとしています

codeforces.com