ABC313 D問題の考え方

D - Odd or Even の考え方を書きました。

最小ケースを考える

厳密な最小ケースは 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となります。