kmjp's blog

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

TopCoderOpen 2021 Round2B : Hard IncorrectCancellation

本番謎枝刈りで通してしまったが、Easy/Mediumも微妙でレート減。
https://community.topcoder.com/stat?c=problem_statement&pm=17009&rd=18700

問題

16/64という分数は、分子分母から同じ6を消すと、1/4になる。
この前後で、実は値としては同じである。

正整数Dが与えられる。
以下を満たす正整数Cがあれば1つ答えよ。

  • Cは1以上D未満
  • CとDで、それぞれ1つ以上数字を消す。消した数字の数が一致すれば、順番は不一致でよい。ただし全桁消すのは不可。
    • 消した後の値をC'、D'とするとC/D=C'/D'とできる。

解法

Dは高々7桁なので、D'を総当たりしよう。
D'を総当たりする際、C'も総当たりすることを考える。
そうするとD,C',D'がわかるのでCもわかる。
C→C'にするために消す数字と、D→D'にするために消す数字が一致するか確認しよう。

class IncorrectCancellation {
	public:
	
	map<int,int> sub(int a,int b) {
		string A=to_string(a);
		string B=to_string(b);
		map<int,int> M;
		int i=0;
		FORR(c,A) {
			if(i<B.size()&&c==B[i]) {
				i++;
				continue;
			}
			M[c-'0']++;
		}
		
		if(i!=B.size()) M.clear();
		return M;
	}
	
	
	int find(int D) {
		
		string S=to_string(D);
		int N=S.size();
		
		int mask,i;
		for(mask=1;mask<(1<<N)-1;mask++) {
			int v=0;
			map<int,int> del;
			FOR(i,N) {
				if(mask&(1<<i)) {
					v=v*10+(S[i]-'0');
					if(v==0) break;
				}
				else {
					del[S[i]-'0']++;
				}
			}
			if(v==0) continue;
			
			for(int c=1;c<v;c++) {
				ll cd=1LL*c*D;
				if(cd%v) continue;
				ll p=cd/v;
				auto M=sub(p,c);
				if(M==del) return p;
			}
		}
		return -1;
		
	}
}

まとめ

まぁ前回割と良かったから多少はしょうがないか…。