問題

$2$次元平面上に$n$個のチェスのナイトを置く。 まだナイトが置かれておらず$4$個のナイトから攻撃を受けているマスにナイトを置くことを、停止するまで再帰的に繰り返す。 上手く初期配置を定めてナイトを $\mathrm{ceil}(\frac{n^2}{10})$ 個以上に増やせ。

解法

概要

$2$乗で増やさないとだめなので解の形は絞られる。 複数の別解があり、例えば以下のような形。 $n$が小さいときに注意。

.............................................................
.............................................................
.....#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.....
....#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#....
.....#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.....
.............................................................
.............................................................

................................
...............#................
...............#................
...............#................
...............#................
...............#................
....########################....
...............#................
...............#................
...............#................
...............#................
...............#................
................................

実装

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define ALL(x) begin(x), end(x)
using namespace std;

const int dy[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
const int dx[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };

int count_attaking_knights(int y, int x, set<pair<int, int> > const & ps) {
    int cnt = 0;
    REP (dir, 8) {
        int ny = y + dy[dir];
        int nx = x + dx[dir];
        cnt += ps.count(make_pair(ny, nx));
    }
    return cnt;
}

int count_knights(vector<pair<int, int> > const & init) {
    set<pair<int, int> > cur(ALL(init)), prv_delta(ALL(init));
    while (not prv_delta.empty()) {
        set<pair<int, int> > delta;
        for (auto p : prv_delta) {
            int y, x; tie(y, x) = p;
            REP (dir, 8) {
                int ny = y + dy[dir];
                int nx = x + dx[dir];
                if (cur.count(make_pair(ny, nx))) continue;
                if (count_attaking_knights(ny, nx, cur) < 4) continue;
                cur.emplace(ny, nx);
                delta.emplace(ny, nx);
            }
        }
        prv_delta = delta;
    }
    return cur.size();
}

vector<pair<int, int> > solve(int n) {
    vector<pair<int, int> > ps;
    for (int z = 0; ps.size() < n; ++ z) {
        ps.emplace_back(0, 2 * z);
        ps.emplace_back(1, 2 * z + 1);
        ps.emplace_back(-1, 2 * z + 1);
    }
    while (ps.size() > n) ps.pop_back();
    assert (count_knights(ps) >= n * n / 10);
    return ps;
}

int main() {
    int n; cin >> n;
    auto ps = solve(n);
    for (auto p : ps) {
        int y, x; tie(y, x) = p;
        cout << x << ' ' << y << endl;
    }
    return 0;
}