遅いと思ったけどいい順位だった。
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ケースまでジャッジしてくれたのはありがたいね。