---
title: "ABC313 D問題の考え方"
date: 2023-08-10
tags: ["AtCoder"]
url: https://aruma256.dev/posts/abc313-d
---

[D - Odd or Even](https://atcoder.jp/contests/abc313/tasks/abc313_d) の考え方を書きました。

# 最小ケースを考える

厳密な最小ケースは `K = 1` ですが、これでは "合計値の偶奇から特定する" という本質から外れてしまうため、ここでは実質的な最小ケースとして `K = 3` とします。
制約 `N > K` より、最小ケースとして `N = 4` とします。


# 最小ケースにおける解法

* 質問を投げられる回数は `N = 4` 回
* 1回の質問では任意の `K = 3` 個の要素の和を取得できる

質問を最大限に活用するなら、4C3ですから以下の選び方しかないでしょう。

||A[1]|A[2]|A[3]|A[4]|
|-|-|-|-|-|
|質問 1||✅|✅|✅|
|質問 2|✅||✅|✅|
|質問 3|✅|✅||✅|
|質問 4|✅|✅|✅||

それぞれの質問に対する回答を `R1, R2, R3, R4` と置きます。

```
(すべて mod 2)
Q1:        A[2] + A[3] + A[4] ≡ R1
Q2: A[1] +        A[3] + A[4] ≡ R2
Q3: A[1] + A[2]        + A[4] ≡ R3
Q4: A[1] + A[2] + A[3]        ≡ R4
```

4式の和を取ると
```
3*A[1] + 3*A[2] + 3*A[3] + 3*A[4] ≡ R1+R2+R3+R4
```

mod 2 より係数 3 は無視でき
```
A[1] + A[2] + A[3] + A[4] ≡ R1+R2+R3+R4
```
となります。

これをXOR (`^`) で表現し、Q1と並べると
```
Q1:        A[2] ^ A[3] ^ A[4] = R1
**: A[1] ^ A[2] ^ A[3] ^ A[4] = R1^R2^R3^R4
```
となり、どちらの式も右辺は既知ですから、`A[1]` を求めることができます。  
また、同様にして `A[2], A[3], A[4]` を求めることができ、これで最小ケースは解けます。

# 一般化する

`K` を大きくする場合、つまり `K = 5, 7, 9, ...` ( `N = K+1` ) についても、前述の手順の質問を増やすことで同様に解けます。

あとは `N` を大きくする場合、つまり `N > K+1` でも解ければ、全てのケースに対応できることになります。

さて、 `N = 4, K = 3` は既に解けていて、 `A[1] ～ A[4]` の値を求められていました。  
ここで、後から "実は `N = 5` で、 `A[5]` が存在する" ということが判明したとしましょう。  
残り質問回数が1増えるため、1回の質問で `A[5]` の値を特定できれば十分です。  
`A[5]` と、既知の `A[1] ～ A[4]` から適当に選んだ2つ、例えば `? 1 2 5` で質問することで `A[5]` の値を特定できます。  
以上より、ある `X` 個の要素を `X` 回の質問で特定できる → `X+1` 個の要素を `X+1` 回の質問で特定できる となることから、帰納的に `N > K+1` についても合計 `N` 回の質問で解けることがわかりました。

以上の処理を正しく実装すると、ACとなります。
