問題概要
ダイヤルロックがあり、各桁は 0 〜 9 の十通りの状態のいずれかをとる。ダイヤルロックの現在の状態は文字列 S で与えられ、文字列 T で表される状態になると解錠される。
ダイヤルロックの操作は、連続する範囲をプラス方向かマイナス方向に 1 動かす操作のみが可能である。解錠するために最小で何回の操作が必要か、求めよ。
解法
T から何らかの操作を経て S が得られたと考えて、その「何らかの操作」の手数を求めるという方向性で考えます。必要な情報は T[ i ] と S[ i ] との差のみで、実際の値は重要ではないので、
とした列 d についてだけ考えます。
区間に対する一様な加算というといもす法があるので、d を mod 10 の剰余系の数列と見做し、この列に対するいもす法を考えます。この場合、ダイヤルを回転させる操作は区間に一様に値を加減するので、いもす法で区間の両端を +1, -1 する操作に対応します。d から、いもす法で累積和をとる前の状態を復元すれば、各要素の変位が求まります。累積和の列から階差数列をとる操作が、累積和をとる操作の逆演算となるので、d から階差数列を計算すればこれを得られます。
d の階差数列を b と呼ぶことにします。元の問題は、（ b と長さが等しく）全ての項が 0 の列に対し、一箇所を +1 、異なるもう一箇所を -1 する操作により b を作ったときの手数を復元する問題に帰着されます。加算された値の合計か、減算された値の合計が分かれば、手数が求まります。このとき、最小手数であることを考えると、ある要素が加算と減算の両方の操作の対象となることはありません。また、4 以下の値は加算、6 以上の値は減算によって作られたことも分かります。問題は 5 の場合で、これは値からはどちらの操作によって作られたか分かりません。これが分からなければ加算（または減算）された値の合計を求められません。
実は、減算の対象となった要素の数を求めることができます。まず、一回の操作では +1, -1 されるので、構成途中の列の総和は常に 0 と合同です。更に、総和の値は 0 から 9 を作るときに限り 10 増えます。最小手数であることを考えると、ある要素に対する最初の減算要素では 0 -> 9 という変化をし、二度以上 0 -> 9 という変化をすることはありません。従って、総和を 10 で割った結果が、減算の対象になった位置の数です。減算の対象となるのは b の内で値が大きい方からなので、b を昇順ソートすれば末尾の sum( b ) / 10 個が減算の対象となった要素であると分かります。それ以外の要素の総和を計算すれば、それこそが操作回数であり問題の答えです。
typedef vector<int> VI; #define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) #define ALL( c ) (c).begin(), (c).end() #define PB( n ) push_back( n ) class CombinationLockDiv1 { public: int minimumMoves( vector <string> P, vector <string> Q ) { const string S = accumulate( ALL( P ), string() ); const string T = accumulate( ALL( Q ), string() ); VI diffs; transform( ALL( S ), T.begin(), back_inserter( diffs ), []( const char c1, const char c2 ){ return ( ( c2 - '0' ) - ( c1 - '0' ) + 10 ) % 10; } ); diffs.PB( 0 ); VI adiffs; adjacent_difference( ALL( diffs ), back_inserter( adiffs ) ); transform( ALL( adiffs ), adiffs.begin(), []( const int a ){ return ( a + 10 ) % 10; } ); sort( ALL( adiffs ) ); const int sum = accumulate( ALL( adiffs ), 0 ); return accumulate( adiffs.begin(), adiffs.end() - sum / 10, 0 ); } }
