kmjp's blog

競技プログラミング参加記です

Google Code Jam 2021 Round 1A : A. Append Sort

遅いと思ったけどいい順位だった。
https://codingcompetitions.withgoogle.com/codejam/round/000000000043585d/00000000007549e5

問題

整数列Xが与えられる。
各要素に1の位に任意の数字を1文字足す、ということを行い、Xを昇順にしたい。
最小何文字足せばよいか。

解法

先頭から順に、隣接する2要素を比較して後者が前者を上回るようにしていく。
その際、後のことを考えると、後者もできるだけ大きくしないようにしたい。

今P,Qの2要素を文字列とみなし、QをPより大きくすることを考える。

  • すでにP<Qなら何もしない
  • PとQのprefix |Q|文字を比較する
    • prefixがQの方が小さいなら、|Q|>|P|となるまでQの末尾に0を追加する
    • prefixがQの方が大きいなら、|Q|==|P|となるまでQの末尾に0を追加する
    • prefixが一致するなら、Pの残りのsufixをインクリメントした数値を文字列としてQに加える。ただし、Pのsuffixが99999…ならどうしても桁が増えるので、代わりに|Q|>|P|となるまでQの末尾に0を追加する
int N;
string X;

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	string P;
	int ret=0;
	
	FOR(i,N) {
		cin>>X;
		
		if(X.size()<=P.size()) {
			if(X<P.substr(0,X.size())) {
				while(X.size()<=P.size()) X+='0', ret++;
			}
			else if(X>P.substr(0,X.size())) {
				while(X.size()<P.size()) X+='0', ret++;
			}
			else {
				string T=P.substr(X.size());
				for(j=T.size()-1;j>=0;j--) {
					if(T[j]!='9') {
						T[j]++;
						for(x=j+1;x<T.size();x++) T[x]='0';
						break;
					}
				}
				if(j==-1) {
					T=string(T.size()+1,'0');
				}
				
				ret+=T.size();
				X=X+T;
				
			}
		}
		P=X;
		
	}
	
	
	_P("Case #%d: %d\n",_loop, ret);
}

まとめ

こういうのコーナーケース漏れが怖いので、今回即時Largeケースまでジャッジしてくれたのはありがたいね。