The 46th World Championship ICPC W問題：Riddle of the Sphinx

問題. Riddle of the Sphinx

3種類の生物がいる。それぞれの種類の足の数を答えよ。

問題を解くためにスフィンクスに「」という形式の質問を 5 回行う。これは 3 種類の生物がそれぞれ 匹いるときの足の本数の合計を訊ねる質問である。この質問に対してスフィンクスは と答えるが、5回の質問のうち多くても 1 回は嘘をつく場合がある。

制約： 、

解法.

回目（）の質問を とし、その返答を とする。また、答えである 3 種類の生物の足の本数をそれぞれ とする。
初めの 4 回の質問を次のように行う。

1. 
2. 
3. 
4. 

もし、 ならばこの 4 回の質問で嘘は付かれていないので、答えは となる。

それ以外 の場合を考える。すなわち、4 回の質問の内ちょうど 1 回嘘を付かれている場合である。ここまでの質問で答えの候補 は次の 4 通りに絞られる。

① ：1回目の質問への答えが嘘の場合（2, 3, 4 回目の質問への答えは本当）
② ：2 回目の質問への答えが嘘の場合（1, 3, 4 回目の質問への答えは本当）
③ ：3回目の質問への答えが嘘の場合（1, 2, 4 回目の質問への答えは本当）
④ ：4回目の質問への答えが嘘の場合（1, 2, 3 回目の質問への答えは本当）

残りの 1 回の質問でこれら 4 つの答えの候補から 1 つに絞りたい。ただし、最後の質問は必ず正しいことが上の仮定から保証されている。質問「」で上の 4 つの返答がすべて異なるようにしたい。すなわち、

①'
②'
③'
④'

としたときに、 となる を見つけたい。この条件を であることに注意して書き下すと、

• より、
• より、
• より、
• より、
• より、
• より、

となる。したがって、 を満たす を 5 回目の質問として訊ねる。
候補はたくさんあるので実装では として質問をした。①', ②', ③', ④' の に を代入して計算した が に等しい （①, ②, ③, ④ のどれか）が答えとなる。

計算時間：

ソースコードを表示

#include <iostream>
#include <vector>

// 5回の質問のうち多くとも1回嘘をつく
int ask(const int a, const int b, const int c) {
    std::cout << a << " " << b << " "  << c << std::endl;
    int r;
    std::cin >> r;
    return r;
}

void solve() {
    const int A = ask(1, 0, 0);
    const int B = ask(0, 1, 0);
    const int C = ask(0, 0, 1);
    const int SUM = ask(1, 1, 1);

    if (A + B + C == SUM) {
        // 今までした4回の質問の答えに嘘はない
        ask(0, 0, 0);
        std::cout << A << " " << B << " " << C << std::endl;
    }
    else {
        // 今までした4回の質問の答えにちょうど1回嘘がある

        // 答えの候補：それぞれ異なる（∵ A + B + C != SUM）
        const auto candidate = std::vector<std::vector<int>>({
            {A, B, C}, // SUM の質問が嘘の場合から導出
            {SUM - B - C, B, C}, // A の質問が嘘の場合から導出
            {A, SUM - A - C, C}, // B の質問が嘘の場合から導出
            {A, B, SUM - A - B} // C の質問が嘘の場合から導出
        });

        std::vector<int> abc = {1, 2, 3};
        const int res = ask(abc[0], abc[1], abc[2]);
        for (const auto &cd : candidate) {
            int dot = 0;
            for (int i = 0; i < 3; ++i) dot += abc[i] * cd[i];

            if (dot == res) {
                for (int i = 0; i < 3; ++i) {
                    std::cout << cd[i] << (i == 2 ? "\n" : " ");
                }
                break;
            }
        }
    }
}

int main() {
    solve();

    return 0;
}

　

コンテスト中なら真面目に 5 回目の質問の証明をしないで、 ①, ②, ③, ④ が一意になるような を全探索するかも（そのような が存在することは答えがあるというメタ読みで）。

この問題難しくて時間かかった。8分で通しているチームがあるらして…すごい。