TopCoderOpen 2022 Round2A : Medium RearrangeAndIncrement

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をいったん最下位桁に持ってきて適切な値にし、また最上位桁に持っていこう。

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;
		
		
	}

まとめ

せっかくチェックするコードも書いたのに、結局落としてる…。