TopCoder SRM 607 Div1 Medium CombinationLockDiv1

475ptという珍しいMedium。
正答率は17%とそこそこ低めだが、475ptというだけあって実装はかなり軽い。
http://community.topcoder.com/stat?c=problem_statement&pm=12968

問題

0-9の数字がN個並んだダイヤル錠がある。
１回の処理を行うと、N個の数字のうち連結したいくつかの数字を1増やすまたは1減らすことができる。
もちろん、一般的なダイヤル錠の通り9と0はつながっている。

初期のダイヤル状態Pと、目的のダイヤル状態Qが与えられたとき、PをQにするための最小処理回数を求めよ。

解法

終了後にTwitterで流れた情報を参考に解答。

まず、各桁についてR[i]=P[i]-Q[i]を求めて各桁の数字の差分を求めておく。
このように差分を取ると、PがQになるというのはRが000000…になるように回転させるのと同じ意味となる。

ここで、Rを0000…にする以上、R[i]とR[i+1]の差は10の倍数でなければならない。
そこで、Rの隣接要素の差分を取り、S[i]=(R[i]-R[i-1])%10を考える。(ただしi==0の時はS[i]=R[i])

ダイヤルを１回回すというのは、Sに対し以下の処理に相当する。

• P[i]～P[j]を1増やす ＝ S[i]を1増やしてS[j+1]を1減らす
• P[i]～P[j]を1減らす ＝ S[i]を1減らしてS[j+1]を1増やす
• P[i]から最後までを1増やす = S[i]を1増やす
• P[i]から最後までを1減らす = S[i]を1減らす
• 先頭からP[i]までを1増やす = S[i+1]を1減らす
• 先頭からP[i]までを1減らす = S[i+1]を1増やす

これらを組み合わせると、結局１回の処理でSに対し以下のいずれかの処理を行うことができる。

1. 1か所1増やす
2. 1か所1減らす
3. 1か所1増やし、1か所1減らす

最小処理数ですべてのS[i]を0または10にすれば良い。
当然3つめの処理をできるだけ利用するため、大き目のS[i]を1増やして10に近づけると同時に、小さ目のS[i]を1減らして0に近づけると効率が良い。

そのため、Sを昇順ソートし、Sのどこまでを減少して0にし、残りを増加して10にするかの境目を定めて、必要減少数と必要増加数を求めると、多い方が必要処理数とおなる。
あとは境目を総当たりで調べ、最小値を求めればよい。O(N^2)で処理可能。

class CombinationLockDiv1 {
	public:
	int minimumMoves(vector <string> P, vector <string> Q) {
		string PP,QQ;
		int L,i,j;
		ITR(it,P) PP+=*it;
		ITR(it,Q) QQ+=*it;
		
		L=PP.size();
		vector<int> D;
		FOR(i,L) QQ[i]=(10+QQ[i]-PP[i])%10;
		D.push_back(QQ[0]);
		FOR(i,L-1) D.push_back((10+QQ[i+1]-QQ[i])%10);
		sort(D.begin(),D.end());
		
		int mi=1000000;
		FOR(i,D.size()+1) {
			int down=0,up=0;
			FOR(j,D.size()) {
				if(j<i) down+=D[j];
				else up+=10-D[j];
			}
			mi=min(mi,max(down,up));
		}
		
		return mi;
	}
}

まとめ

終わってしまえばコードは簡単。
DPも要らない当たりが475ptの所以か。