本番謎枝刈りで通してしまったが、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; } }
まとめ
まぁ前回割と良かったから多少はしょうがないか…。