http://codeforces.com/contest/900
A
はい。
B
解けなかったです。(絶望)
でもこれまあまあ難しい気がするんだけどどうなんだろう。
a*10^k/bの1の位を求めたいとします。以下の文字(a,b,c,d,e,f)はすべて整数です。
a*10^k/b=e+d/b(d < b)と表されているとしましょう。すると、
a*10^(k+1)/b=10*e+d*10/bとなり、d*10/bの1の位がcと一致するか確認すればいいです。
一致しない時、d*10/b=f+d'/b(d' < b)と表せば、d→d'と同じ形になるので帰納法を適用できます。
またdの値としてありうるのはb個しかないので、この操作をb回繰り返せばcが出るか出ないか判定できます。
てそれって結局筆算そのままじゃないですか?ということに気づいて悲しくなりました。
int A, B, C; void solve() { cin >> A >> B >> C; for(int i = 1; i < B + 1; i++) { A *= 10; if(A / B == C) { cout << i << "\n"; return; } A %= B; } cout << -1 << "\n"; }
C
ある要素vが条件を満たすとき、消された可能性がある要素uは区間の形で求まります。
なので累積和を取ればいいです。
めちゃくちゃWA出した。
D
包除原理すればいいです。一番すんなりできました。
E
dp[i][x]=i番目まで文字列を見た時、x個tを取るとする。その時の最小コストはなにか、でO(N^2)ですが、良く考えるとxはあり得るものの中で最大のもの以外の情報はいらないので、dp[i]=pair