The 2nd Universal Cup. Stage 2: SPb L. "Memo" Game With a Hint

問題のリンク：https://qoj.ac/contest/1356/problem/7186

問題概要

25枚の絵柄から構成される50枚のカードを用いて神経衰弱を行う。ミスの回数を平均13.5回に抑えるような2人分の操作を記述せよ(Run Twice)。

prepare

横一列に並んだ50枚のカードの絵柄の入力が与えられる。

長さ50のバイナリ列を出力する。

play

絵柄情報は与えられないが、上記で出力されたバイナリ列が入力で与えられる。

インタラクティブで神経衰弱をプレイする。

解法

解法は非常にシンプル。

1回目の実行では、25枚の絵柄の片方の位置情報を送る。

2回目の実行では、13手かけて上記の位置にある絵柄情報を特定する。その後はもう片方の位置が分かっているので、1つずつペアを完成させれば良い。

本番時は終了間際まで別問題に張り付いていたので見れていなかったのですが、終了後の感想戦でチームメイトが悔しがる姿が印象的でした。分かってしまえば簡単枠なのに、順位表上でもあまり解かれておらず完全にマジック枠でした。

実装

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) { return (ull)rng() % B; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string str;
    int q;
    cin >> str >> q;
    if (str == "prepare") {
        while (q--) {
            string s; cin >> s;
            vector<bool> used(25);
            for (char c : s) {
                cout << used[c - 'A'];
                used[c - 'A'] = true;
            }
            cout << endl;
        }
    } else {
        while (q--) {
            string s, t; cin >> s;
            vector<int> pos(25);
            vector<int> one;
            for (int i = 0; i < (int)s.size(); ++i) {
                if (s[i] == '1') one.push_back(i);
            }
            one.push_back(one[0]);
            for (int i = 0; i < one.size(); i += 2) {
                cout << one[i] + 1 << endl;
                cin >> t;
                pos[t[0] - 'A'] = one[i] + 1;
                cout << one[i + 1] + 1 << endl;
                cin >> t;
                pos[t[0] - 'A'] = one[i + 1] + 1;
            }
            for (int i = 0; i < (int)s.size(); ++i) {
                if (s[i] == '0') {
                    cout << i + 1 << endl;
                    cin >> t;
                    cout << pos[t[0] - 'A'] << endl;
                    cin >> t;
                }
            }
        }
    }
}