MediumもHardもしょうもないミスで落とした…。
https://community.topcoder.com/stat?c=problem_statement&pm=17587
問題
正整数X,Yが与えられる。
Xに以下の操作を最大200回行い、Yに変換せよ。
- Xに1~13のいずれかの値を加える。
- Xの各桁を並べ替える。並べ替えた後leading zeroができるのは良いが、並べ替え前にleading zeroを仮定して並べ替えるのは不可である。
解法
X→1にするのと1→Yにするそれぞれのステップを考えよう。
- X→1にする
- Xの最下位桁を0にするよう1桁の値を足し、並べ替えて0をleading zeroに持っていけば2手で1桁減らせる
- 1→Yにする
- まずXの桁をYにそろえよう。
- 今10000という値で1桁増やしたいなら、9の加算と並べ替えを繰り返して19999にした後、99991に並べ替えて9足せば100000と1桁増やせる。
- Yの最上位桁以外0の場合
- 例えば100000→500000にしたい場合、上と同じ手順で999991にした後、1の位を調整して999994にした後、並べ替えて499999、インクリメントして500000にすればよい。
- Yの最上位桁以外に1以上の値がある場合
- 1の位で欲しい数字を作った後、並べ替えて1桁ずつ値をそろえていこう。
- 最後に最上位桁が1以外の場合、すでに作った最上位桁以外の0以外の値をいったん最上位桁に持ってきて、その間最上位桁にあった1をいったん最下位桁に持ってきて適切な値にし、また最上位桁に持っていこう。
- まずXの桁をYにそろえよう。
class RearrangeAndIncrement { public: int X; vector<int> ret; void go(int v) { if(v!=ret.back()) { X=v; ret.push_back(v); } } int ok(int a,int b) { if(b-a>=1&&b-a<=13) return 1; string A=to_string(a); string B=to_string(b); if(B.size()>A.size()) return 0; while(B.size()<A.size()) B+="0"; sort(ALL(A)); sort(ALL(B)); return A==B; } vector <int> change(int X_, int Y) { X=X_; ret={X}; int i; while(X>1) { go(X+(10-X%10)); string S=to_string(X); sort(ALL(S)); go(atoi(S.c_str())); } int T=1; while(1LL*T*10<=Y) T*=10; while(X<T) { while(X%10==0) { go(X+9); string S=to_string(X); sort(ALL(S)); reverse(ALL(S)); go(atoi(S.c_str())); } go(X+9); } if(Y%T==0) { if(Y>T) { int a=Y/T; while(X%10==0) { go(X+9); string S=to_string(X); sort(ALL(S)); reverse(ALL(S)); go(atoi(S.c_str())); } go(X+a-2); string S=to_string(X); sort(ALL(S)); go(atoi(S.c_str())); go(X+1); } } else { string TY=to_string(Y); for(i=1;i<TY.size();i++) if(TY[i]!='0') { string XS=to_string(X); XS.back()=TY[i]; go(atoi(XS.c_str())); swap(XS[i],XS.back()); go(atoi(XS.c_str())); } if(Y/T>1) { int a=Y/T; string XS=to_string(X); for(i=1;i<XS.size();i++) if(XS[i]!='0') { if(i==XS.size()-1) { swap(XS[0],XS[i]); } else { swap(XS[0],XS[i]); swap(XS[i],XS.back()); } go(atoi(XS.c_str())); XS.back()=a+'0'; go(atoi(XS.c_str())); if(i==XS.size()-1) { swap(XS[0],XS[i]); } else { swap(XS[i],XS.back()); swap(XS[0],XS[i]); go(atoi(XS.c_str())); } go(atoi(XS.c_str())); break; } } } cout<<"!"<<ret.size()<<endl; FOR(i,ret.size()-1) assert(ok(ret[i],ret[i+1])); assert(ret.size()<=200); assert(ret.back()==Y); return ret; }
まとめ
せっかくチェックするコードも書いたのに、結局落としてる…。