AtCoder Beginner Contest 470 でやらかしてしまいました。C – Inc, Dec, Xorが解けず 4ヶ月ぶりの2完です。
C – Inc, Dec, Xor とはどんな問題？
問題の概要
長さ N の整数列 A が与えられる。はじめは A の要素はすべて 0 である。
Q 個のクエリを順に処理せよ。
クエリ 1：A[x] の値を 1 増やす。
クエリ 2：すべての要素に対し A[i] ≧ 1 ならば A[i] の値を 1 減らす。
各クエリを処理した直後の A のビット単位 XOR を求めよ。
（ただし N, Q ≦ 5 × 10^5）
差分更新をミスして不正解
問題はクエリ 2をどうするかです。すべての要素に対して A[i] ≧ 1 かどうかを確認して A[i] の値を 1 減らす処理をしていたのでは間に合いません。
しばらくああでもないこうでもないと考えて気がついたことは「A[i] の種類数はそれほど大きくはならない」ということです。A[i] = k となるものが何通りあるかを数えて Dictionary で管理すればいいのではないかと考えました。dic[k] が奇数のものだけで xor を計算すればそれが出力すべき解となります。
問題は A をどうやって更新するかです。A はクエリ 1 が来たときだけインクリメントし、クエリ 2 が来たらその回数（minus_count）を数える、A[i] の本当の値は minus_count から計算できるのではないかということで以下のようなコードを書きました。
結果は「不正解」です。
嘘解法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
class Program { static void Main() { int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nq[0]; int Q = nq[1]; int[] add_counts = new int[N]; // 各要素がインクリメントされた回数 int minus_count = 0; // クエリ 2 が飛んできた回数 Dictionary<int, int> dic = new Dictionary<int, int>(); // A[i] が取りうる値の種類とその個数 dic.Add(0, N); // 最初は全部 0 なので List<int> res = new List<int>(); for (int i = 0; i < Q; i++) { int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int t = query[0]; if (t == 1) { int idx = query[1] - 1; // add_counts と minus_count から 更新前と更新後の A[idx] の値を求めようとしている // が、これは間違っている。 int old_value = Math.Max(add_counts[idx] - minus_count, 0); int new_value = old_value + 1; add_counts[idx]++; // A[idx] が変更されたので dic も変更する dic[old_value]--; if (dic[old_value] == 0) dic.Remove(old_value); if (!dic.ContainsKey(new_value)) dic.Add(new_value, 0); dic[new_value]++; } if (t == 2) { minus_count++; // A[idx] > 0 ならデクリメントしないといけないので dic は丸ごと作り直す // 処理自体はこれでも間に合う。 var pairs = dic.ToArray(); dic = new Dictionary<int, int>(); foreach (var pair in pairs) { int key = pair.Key - 1; if (key < 0) key = 0; int val = pair.Value; if (!dic.ContainsKey(key)) dic.Add(key, 0); dic[key] += val; } } int ans = 0; foreach (var pair in dic) { if (pair.Value % 2 == 1) ans ^= pair.Key; } res.Add(ans); } // 結果を出力 foreach (var v in res) Console.WriteLine(v); } } |
どこが間違っているのか？
何が難しいかというと問題のページに書かれているサンプルのテストケースにはこれでも正しい答えが出力されてしまうということです。なので、不正解の場合はどこで不正な処理が行われているのか気づくことが難しいのです。
このようなケースでは正しい解が出力されません。
|
1 2 3 4 5 |
2 4 2 2 1 1 1 1 |
この場合、A は以下のように更新されます。
初期状態： A = {0, 0}
1回目： A = {0, 0}
2回目： A = {0, 0}
3回目： A = {1, 0}
4回目： A = {2, 0}
なので出力は
1回目： 0
2回目： 0
3回目： 1
4回目： 2
となります。
しかし、上記のコードでは
1回目： 0
2回目： 0
3回目： 1
4回目： 0
となってしまいます。
要は、クエリ 2 が来たときに A[idx] がデクリメントされるのは A[idx] ≧ 1 のときだけなので処理を切り分ける必要があったのです（どんなときに上記のコードでは不正な出力がされるのかに気づくことができれば修正できていた）。
クエリ 1 の部分が間違っていて、この 2 行を入れるだけで AC できます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
if (t == 1) { int idx = query[1] - 1; int old_value = Math.Max(add_counts[idx] - minus_count, 0); int new_value = old_value + 1; add_counts[idx]++; // A[idx] の本当の値が 1 になるときは // 次回の Math.Max(add_counts[idx] - minus_count, 0) で 1 が得られるように // add_counts[idx] の値を調整する if(new_value == 1) add_counts[idx] = minus_count + 1; dic[old_value]--; if (dic[old_value] == 0) dic.Remove(old_value); if (!dic.ContainsKey(new_value)) dic.Add(new_value, 0); dic[new_value]++; } |
別の考え方
A[idx] の本当の値を求めるというのは気づきにくいバグを埋め込んでしまうため、もっとスマートなやり方があります。
「A[idx] の種類数はそれほど大きくはならない」のは事実ですが、ここでは少し見方を変えて「A[idx] ≧ 0 となる idx の種類数」を考えます。実はこれもそれほど大きくなりません。クエリ 1 がたくさん飛んできて A[idx] ≧ 0 であるものが増えると種類数は増えそうなのですが、クエリ 2 で A がデクリメントされると種類数は一気に下がります。一気に下がらない場合として A の値がバラバラである場合が考えられますが、そうなると本当に idx の種類数は少なくなります（最悪で 1,000 通りくらい）。
以下のコードは A[idx] ≧ 0 となる idx を set に格納してクエリ 2 が飛んできたらその要素だけデクリメントしています。デクリメントすることで A[idx] == 0 となったら idx は set から remove します。
XOR の計算はクエリ 1 であれば、「二回繰り返すと元に戻る」という性質を利用して
|
1 2 3 |
ans ^= A[idx]; A[idx]++; ans ^= A[idx]; |
とやればすぐにできるし、クエリ 2 の場合はいったん ans はリセットして計算しなおすという方法で実行時間制限に充分間に合わせることができます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
class Program { static void Main() { int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nq[0]; int Q = nq[1]; int[] A = new int[N]; List<int> res = new List<int>(); int ans = 0; HashSet<int> set = new HashSet<int>(); for (int i = 0; i < Q; i++) { int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int t = query[0]; if (t == 1) { int idx = query[1] - 1; ans ^= A[idx]; A[idx]++; ans ^= A[idx]; set.Add(idx); } if (t == 2) { int[] arr = set.ToArray(); foreach (var idx in arr) { A[idx]--; if (A[idx] == 0) set.Remove(idx); } ans = 0; foreach (var idx in set) ans ^= A[idx]; } res.Add(ans); } foreach (long v in res) Console.WriteLine(v); } } |
XORが難しい？
XORには「2回繰り返すと元に戻る」という興味深い性質があります。その反面計算結果がイメージしにくく（1 + 2 + 3 + 4 の答えは小学生でもわかるが、1 xor 2 xor 3 xor 4 がどうなるかすぐにはわからない）難しいと思います。どうしても XOR の問題が出てくると「出たな。妖怪」と身構えてしまい、今回のように差分更新と同時に出現されると食い殺されてしまうようなことがよくあります。
ということで、次回は差分更新系の練習問題を解いてみることにします。
これは ChatGPT が鳩のために出力してくれた問題集です。
| 問題 | 難度目安 |
| ABC035 C – オセロ | ★★☆☆☆ |
| ABC014 C – AtColor | ★★☆☆☆ |
| ABC183 D – Water Heater | ★★☆☆☆ |
| ABC080 D – Recording | ★★★☆☆ |
| ABC256 D – Union of Interval | ★★★☆☆ |
| ABC188 D – Snuke Prime | ★★★☆☆ |
| ABC221 D – Online games | ★★★☆☆ |
| ABC369 C – Count Arithmetic Subarrays | ★★★☆☆ |
| AWC0099 C – 水やり | ★★★★☆ |
