http://agc017.contest.atcoder.jp/tasks/agc017_c
解説を見るとこんなうまいやり方があったのかぁ…となるんですが、それをどうやって思いつけるようになるかが重要だと思います。
僕はこう考えたらしっくりきました。
まず魔法をかける前、ボールがどうなっているか見てみます。例えば
2 2 5 5 5 6
について考えて
1 2 3 4 5 6と「見比べる」と、2つの5が3,4に、1つの2が1になっていることがわかります。
つまりnがk個あると、n,n-1,...,n-k+1に「言い換えられる」ような気がしてきます。
この言い換えをボールの数を変える前の数列に「適応」してみましょう。
3 3 4 5 5 6は
2 3 4 4 5 6となります。ここまでくれば、4がダブっているので4のどっちかを1に変えればうまくいくとわかります。
これを区間で表したのが解説となります。
このようにまず性質がいいものを特殊なケースと「見比べる」ことで、「言い換え」を思いつき、それをいろんなケースにも「適応」してみるのが、競プロでありがちな思考回路な気がします。
性質がいいものってなんだよと思いますが、例えば等差数列だったり、時系列で物を使っていく問題なら時間がそれに該当すると思います。
本番は1,2,3...と見比べるところまでは言ったが、言い換えるところに至らず、500点どまり。言い換えるのが苦手なのはいろんな問題を通じてわかっているので、強く意識すべきですね。
int N, M; int S[MAX_N], A[MAX_N], C[MAX_N]; void solve() { cin >> N >> M; rep(i, 0, N) { int a; cin >> a; a--; A[i] = a; if(a - C[a] >= 0) S[a - C[a]]++; C[a]++; } int res = 0; rep(i, 0, N) res += S[i] ? 1 : 0; rep(i, 0, M) { int a, b; cin >> a >> b; a--; b--; int pb = A[a]; A[a] = b; if(pb - C[pb] + 1 >= 0) { S[pb - C[pb] + 1]--; if(!S[pb - C[pb] + 1]) res--; } C[pb]--; if(b - C[b] >= 0) { S[b - C[b]]++; if(S[b - C[b]] == 1) res++; } C[b]++; cout << N - res << "\n"; } }
こういう抽象的なことって言葉にするのが難しいですね。