BOJ-21869 Maximum Bishop

問題のリンク

Twitterで教えて貰ったのでブログに残そうと思います。

(PCTさんNyaanさんありがとうございました！)

問題概要

N*Nのグリッドが与えられる。互いに攻撃し合わないようにビショップを配置する時、最大で何個置けるか。またその構築の一つを求めよ。

制約

• $1 \leq N \leq 524288$

解法

まずは上限を示す。

$x+y=k$ を満たす $(x,y)$ には高々1つの駒しか置けない。$0 \leq k \leq 2(N-1)$ について、$k=0,2(N-1)$ は同時に置くことができないから、上限は $2(N-1)$

(ただし、$N = 1$ だけ場合分けが必要)

結論から言うとこの上界は常に達成可能である。

二部グラフだから飛車と同じになって飛車の場合は行数と同じだからそれでよさそう

— PCT (@PCTprobability) 2021年6月22日

補足をすると、1つのビショップが攻撃可能なマスは二部グラフの同じ側に属するマスだから2つに分けて考えられる→45度回転したグリッドで飛車の場合と同様に考えられる。という理解をしています。

このように図を書くと結構見え見えで、実際1行目全部N行目の両端以外のような構築で最適解を実現できる。他にも色々構築のしようはあると思います。

実装

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

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

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    if(n==1){
        printf("1\n");
        printf("1 1\n");
    }
    else{
        printf("%d\n",2*(n-1));
        for(int i=0;i<n;i++){
            printf("1 %d\n",i+1);
        }
        for(int i=1;i+1<n;i++){
            printf("%d %d\n",n,i+1);
        }
    }
}