競技プログラミング用 知識集積所
ABC403D - Forbidden Difference
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
まず、D=1の場合を考えてみる。
Aの最大値がそこまで大きくないので、各値の出現数カウントが可能なことに注目する。
例えばAが{3,1,4,1,5}であれば、個数のvectorを{0,2,0,1,1,1}と用意できる。
これを、いくつかを0に変更することで0以外の値が連続しないようにする方法を考える。
例えばAが{3,1,4,1,5}であれば、個数のvectorを{0,2,0,1,1,1}と用意できる。
これを、いくつかを0に変更することで0以外の値が連続しないようにする方法を考える。
しかし、これを単純な計算で出すのは難しい。
例えば、{1,3,1,3,1}のように、奇数個の連続でもあえて両端を残さない方がいい場合もある。
また、{3,1,1,3,1,1,3}のように連続する2つを0にしてしまった方がいい場合もある。
そこで、求めるものが最小値である、つまりこれが最適化問題であることを考えて、動的計画法が使えないかと考えてみる。
例えば、{1,3,1,3,1}のように、奇数個の連続でもあえて両端を残さない方がいい場合もある。
また、{3,1,1,3,1,1,3}のように連続する2つを0にしてしまった方がいい場合もある。
そこで、求めるものが最小値である、つまりこれが最適化問題であることを考えて、動的計画法が使えないかと考えてみる。
まず、長さが0である場合、明らかに消す最小個数は0である。
長さが1である場合、例えば{3}であれば、1番目を消すなら最小値は3、消さないなら最小値は0である。
長さが2である場合、例えば{3,1}であれば、2番目を消すなら最小値は1、消さないなら最小値は3である。
というのは2番目を消さない場合は1番目を消す選択しか取れないため。
以下繰り返すと、{3,1,1,3,1,1,3}の場合、
長さが1である場合、例えば{3}であれば、1番目を消すなら最小値は3、消さないなら最小値は0である。
長さが2である場合、例えば{3,1}であれば、2番目を消すなら最小値は1、消さないなら最小値は3である。
というのは2番目を消さない場合は1番目を消す選択しか取れないため。
以下繰り返すと、{3,1,1,3,1,1,3}の場合、
| 3 | 1 | 1 | 3 | 1 | 1 | 3 | |||
| 消す場合 | 0 | 3 | 1 | 2 | 4 | 3 | 4 | 6 | 1つ前の少ない方+その数 |
| 消さない場合 | 0 | 0 | 3 | 1 | 2 | 4 | 3 | 4 | 1つ前の消さない場合と同じ |
となり、最小値は6と4のうち小さいほうである4であるとわかる。
以上がD=1の場合の解法である。
次にD>=2の場合。
これは、連続ではなくD個離れた位置に1以上の数があってはいけないことになるが、結局それはD個おきに値を取り出してD=1のときの解法を実行するのと同じである。
よって、forループで各余りについての処理をD回繰り返せばよい。
これは、連続ではなくD個離れた位置に1以上の数があってはいけないことになるが、結局それはD個おきに値を取り出してD=1のときの解法を実行するのと同じである。
よって、forループで各余りについての処理をD回繰り返せばよい。
最後に、D=0の場合。
これは値の重複が許されないという全く別の問題になる。
setか何かを使えばすぐだが、そもそもD=0の場合の特殊対応が必要だと気が付くのが難しい。
これは値の重複が許されないという全く別の問題になる。
setか何かを使えばすぐだが、そもそもD=0の場合の特殊対応が必要だと気が付くのが難しい。
解答例
注意点
入力制限をよく見る
考え方のところにもある通り、D=0は特殊対応が必要である。
見落とさないように注意。
見落とさないように注意。
