読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces AIM Tech Round (Div. 1) B. Array GCD

動的計画法 Codeforces

kmjp さんのコードを見て解法を察しました。ありがとうございます。

codeforces.com

問題概要

数列 an が与えられる。この数列に以下の操作を行う。

  1. 連続する部分列を削除する
  2. 要素をひとつ選び +1 または -1 する。

操作 1 は一回のみでき、操作 2 は同じ要素に 2 回適用できないが異なる要素であれば何回でも適用できる。

操作 1 は選んだ部分列の長さを m としたとき、mA のコストが掛かり、操作 2 は一回あたりコスト B 掛かる。

最終的な数列全体を gcd したものが 1 より大きくなるようにするのに必要な最小のコストを求めよ。

解法

数列全体を gcd すると、数列の左端か右端は必ず gcd に巻き込まれる。 したがって最終的な gcd の値は a0, a0-1, a0+1, an-1, an-1-1, an-1+1 が持つ素因数の倍数になるはずである。 これを用いてこの問題を次の問題に置き換える。

  • 数列のすべての要素を p の倍数にするのに必要な最小のコストを求めよ。

この問題は DP を用いて O(n) で解くことができる。

  • dp[ i 番目まで確定 ][ 状態 j ] := この状態に至るのに必要なコストの最小値

ここで状態は (0) 削除前、(1) 削除中、(2) 削除後の 3 つを考えればよい。

Codeforces AIM Tech Round (Div. 1) B. Array GCD

全体で 1 回しかインクリメントできないと思ってたら同じ要素には 2 回できないだけだった。