More than 3 years have passed since last update.

共円ゲームの決まり手数を考えてみた

Last updated at 2021-05-05Posted at 2021-05-05

#0. 自己紹介
初めまして！　AtCoderを楽しむ高校生です。
Qiitaは実質初投稿ですので至らない点があるかと思いますがよろしくお願いします。

#1. ボードゲーム「共円」とは
正方形のマス目があり¹、その格子点に何人かで1つずつ点を置いていくのですが、「置かれてある点の中から異なる4点をどのように取っても、それらが同一円周上（共円）でない、かつ同一直線上（共線）でない」ようにします（説明が下手）。

たとえば、共円（kyouen）で遊べます。

共円には定石（型みたいなもの）もあり、以下のサイトが詳しいです。
ボードゲーム『共円』について - 灘校数研の旧HP

####～注意～
以下では、直線を半径無限大の円と考え、共線のことも含めて「共円」と呼ぶことにします。
また、以下で掲示する画像はいずれも共円（kyouen）から取得したものです。

#2. 何をやるか
「これ以上どこに置いても共円が出来てしまう」という状態は必ず訪れます。この状態を飽和と呼び、これまでに置いた点の数を 決まり手数 と呼ぶことにしましょう。

ここでは、$n\times n$ の格子点の集まりに対する 決まり手数の範囲らしきもの を求めるプログラムを作りたいです。また、そのときの点の置き方も出力したいと思います。

以下は、$7\times 7$ の飽和した状態で、このときの決まり手数は $10$ です。

#3. プログラミングの手順
##3.1. 環境・言語
wandboxを使います。言語はC++です。
競プロっぽいコードの書き方をしていると思いますが、どうかご了承ください。
まずは下に使用するテンプレをあげておきます。

template.cpp

#pragma GCC optimize("Ofast") // これは単なる高速化
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<int(n);i++)
#define REP(i,k,n) for(int i=k;i<int(n);i++)
#define all(a) a.begin(),a.end()
#define eb emplace_back
#define fi first
#define se second
using P=pair<int,int>;
using vi=vector<int>;
using vvi=vector<vi>;
constexpr int INF=1001001001;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}

##3.2. 共円判定
異なる4点が共円であることはどのように判定すればよいだろう？っと思って調べてみると、4点が同一円周上にある条件 - 受験の月がヒットしました。

どうやら格子点を複素数平面と見て、$\frac{(\beta-\gamma)(\alpha-\delta)}{(\alpha-\gamma)(\beta-\delta)}\in\mathbb{R}$は、4点 A($\alpha$), B($\beta$), C($\gamma$), D($\delta$)が共円または共線であることと同値であるようです。

これを実装すると、以下のようになりました²。

kyouenjudge.cpp

// 複素数の差
P diff(P a,P b){
    return P(a.fi-b.fi,a.se-b.se);
}
// 複素数の積
P prod(P a,P b){
    int a1=a.fi,a2=a.se;
    int b1=b.fi,b2=b.se;
    return P(a1*b1-a2*b2,a1*b2+a2*b1);
}
// 4点の共円判定
bool kyouen(P a,P b,P c,P d){
    P x=prod(diff(a,c),diff(b,d));
    P y=prod(diff(b,c),diff(a,d));
    return x.fi*y.se==x.se*y.fi;
}

##3.3. 結局どう調べるか
こんな流れでいきます:
　　ランダムな点Pを指定（すでに調べてたら無視）
　-> すでに置かれてる点3つとPの組み合わせで共円が生じるかチェック
　-> 生じないならPを置く
　-> 飽和したら、決まり手数を記録（更新）して初期化
これを、指定した時間制限いっぱい繰り返します。

main.cpp

int main(){
    srand((unsigned)time(NULL)); // randomのおまじない
    // ただの高速化
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n; cin>>n; // マス目大きさ
    double limit; cin>>limit; // 時間制限(10秒まで)

    vector<P> v;
    vvi used(n,vi(n,0));
    int ansM=0,ansm=INF; // ansM:=最大決まり手数, ansm:=最小決まり手数
    INT cnt=0,ope=0; //cnt:=置いた点の数, ope:=試行回数
    vector<P> tM,tm; //tM:=手数ansMのときの点, tm:=手数ansmのときの点

    //時間いっぱいrandomに探索
    while(double(clock())/double(CLOCKS_PER_SEC)<limit){
        // randomに点を指定
        int a=rand()%n,b=rand()%n;
        P p=P(a,b);
        // すでに調べてたら操作しない
        if(used[p.fi][p.se]) continue;
        used[p.fi][p.se]=1;
        if(v.size()<3){
            cnt++;
            v.eb(p);
        }
        else{
            int sz=v.size();
            // 共円になり得るか判定
            bool f=true;
            rep(i,sz-2){
                if(!f) break;
                REP(j,i+1,sz-1){
                    if(!f) break;
                    REP(k,j+1,sz){
                        if(kyouen(v[i],v[j],v[k],p)){
                            f=false; break;
                        }
                    }
                }
            }
            if(f){
                cnt++;
                v.eb(p);
            }
        }

        // 飽和したら初期化
        bool g=true;
        rep(i,n)rep(j,n) g=g&&used[i][j];
        if(g){
            rep(i,n)rep(j,n) used[i][j]=0;
            if(chmax(ansM,cnt)) tM=v;
            if(chmin(ansm,cnt)) tm=v;
            v.clear();
            cnt=0;
            ope++;
        }
    }
    
    sort(all(tM));
    sort(all(tm));
    
    // 結果出力
    cout<<"-Trials: "<<ope<<'\n';
    out("-Points");
    cout<<"   MAX "<<ansM<<": ";
    outvp(tM);
    cout<<"   min "<<ansm<<": ";
    outvp(tm);
}