Dasha and Chess [Codeforces Round #532 (Div. 2) D]

https://codeforces.com/contest/1100/problem/D

インタラクティブ問題。
999×999のマスでゲームをする。
　
プレイヤーは1つのキングを持っている。
キングは1ターンで周り8マスを動ける。
最初は(x,y)にいる。
プレイヤー先攻
　
相手は666個のルークを持ってる。
相手は1ターンであるルークを任意の場所に動かせる。
ただし、ルーク・キングは同じ場所に置けない。
　
プレイヤーはキングを移動させたあと、縦横のどちらかに1つでもルークがあると勝ち。
適切に動き、2000ターンで勝て。

解説

https://codeforces.com/contest/1100/submission/48368664

この問題はデバッグできないので、インタラクティブ練習には向かない。
解法が思いついたら神に祈る問題であることを先に伝えておく。
　
必勝ムーブがある。
① キングを中央に持ってくる
② 中央を基準に4象限に分けて、もっともルークの少ない象限の反対側の角に移動する
こうすると、①②の過程で必ず勝てる。
これは②を始める前を考えてみると、もっともルークの少ない象限以外のルークを数えると、666*3/4以上のルークがいることが分かる。
そして、この状態で最もルークの少ない象限の反対側の角に移動すると、同時に666*3/4のルークを攻めることができる。
500手で角に到達できるが、その間に666*3/4全部は逃がせないので、勝てる。
　
これで実装するが、GoTo関数を作るのがおすすめ。
GoTo(tx, ty) := (tx,ty)にキングを移動させる
　
実装上の注意点としては「キングの左右への移動時は問題ないが、対角線上での移動ではルークがいる可能性があるので注意」。
もし対角線上にルークがいた場合は、横に移動することで勝てるので、そういう処理も入れておく。

int X, Y;
int RX[1010], RY[1010];
int rook[1010][1010];
//---------------------------------------------------------------------------------------------------
bool ask(int x, int y) {
    if (rook[y][x]) return false;

    X = x, Y = y;
    printf("%d %d\n", x, y);
    fflush(stdout);
    int a, b, c;
    cin >> a >> b >> c;

    if (a < 0) exit(0);
    a--;
    rook[RY[a]][RX[a]] = 0;
    RX[a] = b;
    RY[a] = c;
    rook[RY[a]][RX[a]] = 1;

    return true;
}
//---------------------------------------------------------------------------------------------------
void GoTo(int tx, int ty) {
    while (X != tx or Y != ty) {
        int xx = X;
        int yy = Y;

        if (xx < tx) xx++;
        else if (tx < xx) xx--;

        if (yy < ty) yy++;
        else if (ty < yy) yy--;

        if (!ask(xx, yy)) ask(xx, Y);
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> X >> Y;
    rep(i, 0, 666) {
        cin >> RX[i] >> RY[i];
        rook[RY[i]][RX[i]] = 1;
    }

    // Move to the center
    GoTo(500, 500);

    int LU = 0, RU = 0, LD = 0, RD = 0;
    rep(i, 0, 666) {
        if (RX[i] <= 500) {
            if (RY[i] <= 500) LD++;
            else LU++;
        } else {
            if (RY[i] <= 500) RD++;
            else RU++;
        }
    }

    int mi = min({ LU, RU, LD, RD });
    
    if (mi == LU) GoTo(999, 1);
    else if (mi == LD) GoTo(999, 999);
    else if (mi == RU) GoTo(1, 1);
    else GoTo(1, 999);
}