🐙

[AtCoder ABC313 D Odd or Even]

2023/08/06に公開

C++

プログラミング

AtCoder

tech

(問題ページ) ABC313 D Odd or Even

1.考え方

この問題では、テストのやり方をどうすればいいか、はじめよくわかりませんでした。
が、想定される質問の答えを標準入力にあらかじめ記載しておけばいいとわかりました。

例えばA = [1,0,1,1,0] とした場合に、以下のようなテストデータを用意しました
(今回使用したテストデータを、code内容の後に記載しておきます。)

5 3  (← N K の値)
0    (← 質問「? 1 2 3」の回答)
0    (← 質問「? 4 2 3」の回答)
1    (← 質問「? 5 2 3」の回答)
1    (← 質問「? 1 4 3」の回答)
0    (← 質問「? 1 2 4」の回答)

まず想定する数列を、A = [1,0,1,1,0] とします。
はじめに、数列の先頭からK個の偶奇を質問します。
その後、A[0]と、K～(N-1)番めの要素A[i]と入れ替えて、質問します。
すると、A[0]とA[i]が同じ値であれば、質問の回答も同じになるとわかります。

そこで、A[0]=1と仮定してみることにします。
すると、K～(N-1)番めの要素の値が決定できます。
(A[0]が0か1かは、最後にチェックします)

次に、先頭からK個の要素について考えます。
この時点で、K番め以降の要素は決定しています。

ここでは0～(K-1)番めの要素A[j]を、A[K]と入れ替えて、質問します。
すると、A[K]とA[j]が同じ値であれば、質問の回答も同じになるとわかります。
このことから、0～(K-1)番めの要素の値が決定できます。

最後に、A[0]が0か1かチェックします。
ここまでの処理の中で、質問した内容と回答の内容を配列にメモしておき、そのメモの内容を使ってチェックします。

ここまでの処理の結果、数列はresult = [1,0,1,1,0]となっています。
これを元に、これまでに行った質問すべてに対する回答を計算し、
　　・「メモ内容の回答」が計算結果と一致していれば、数列resultはそのままでOK。
　　・一致していなければ、数列resultは0と1を逆にする
となります。

2.code

code

#include <iostream>
#include <vector>
#include <limits>
using namespace std;
#include <algorithm>
#include <numeric>


int N, K;

int ask(const vector<int> &question) {
    printf("? ");
    for (int i = 0; i < K; i++) {
        printf("%d", question[i]);
        if (i != (K-1)) {
            printf(" ");
        }
    }
    printf("\n");
    int ans;
    cin >> ans;
    return ans;
}

void add_answer(vector<int> &question, int &ans, vector<vector<int>> &answer_list) {
    vector<int> q(K);
    copy(question.begin(), question.end(), q.begin());
    q.push_back(ans);
    answer_list.push_back(q);
}

int main() {
    cin >> N >> K;

    vector<int> question(K, -1), result(N, -1);
    result[0] = 1;
    vector<vector<int>> answer_list;

    for (int i = 0; i < K; i++) {
        question[i] = i+1;
    }

    int a_start = ask(question);
    add_answer(question, a_start, answer_list);

    for (int i = K; i < N; i++) {
        question[0] = i+1;
        int a = ask(question);
        if (1 & a) {
            result[i] = a_start;
        } else {
            result[i] = 1 - a_start;
        }
        add_answer(question, a, answer_list);
    }

    question[0] = 1;  // questionを初期状態に戻す

    for (int i = 1; i < K; i++) {
        int q_tmp = question[i];
        question[i] = K + 1;
        int a = ask(question);

        if (a == a_start) {
            result[i] = result[K];
        } else {
            result[i] = 1 - result[K];
        }
        add_answer(question, a, answer_list);
        question[i] = q_tmp;
    }

    bool flag = true;
    for (vector<int> question_ans : answer_list) {
        int calc = 0;
        for (int i = 0; i < K; i++) {
            int idx = question_ans[i] - 1;
            calc += result[idx];
        }
        if ((calc % 2) != question_ans.back()) {
            flag = false;
            break;
        }
    }

    printf("! ");
    for (int i = 0; i < N; i++) {
        if (flag) {
            printf("%d", result[i]);
        } else {
            printf("%d", 1 - result[i]);
        }
        if (i != (N-1)) {
            printf(" ");
        }
    }
    printf("\n");
}

test data 1 (数列A = [1,0,1,1,0] とした場合)

test data 2 (数列A = [0,0,1,1,0] とした場合)

1.考え方

2.code

Discussion