Codeforces Round #450(Div. 2)

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(x, cost)で更新すればO(N)です。