yukicoder No.819 Enjapma game

ゲーム問題にしては面白い(といっても典型だと思う)問題だったので。

問題概要

H×Wのグリッドに駒がいくつか置かれている。相手スタートで以下の操作を交互に繰り返す。

  • 駒を1つ選んで取り除く。
  • 駒を1つ選んで、左か下のどちらか隣のマスに移動させる。ただし、移動先に他の駒があってはならない。

操作を行えなくなった方の負け、というルールで、お互いに最善手を取ったとき勝てるか判定せよ。

No.819 Enjapma game - yukicoder

解説

ゲーム分野にはいくつか解法があって、大体そのどれかに該当する。

  • DFSを行って最善手を全探索するタイプ(grundy数が使えない場合はこっち)
  • grundy数を用いるタイプ(上のよりシンプルな問題で用いることが出来る)
  • その他数学的な考察を行うことで規則的に問題を解くタイプ

今回は上2つをやろうとすると探索範囲が広すぎて計算が間に合わない。ということで自然と規則を見つけて解く形に。

3x3辺りまで適当に脳内シミュレーション・grundy数の設定を行っていると、「盤面を一松模様と捉えて、移動=白黒を1つひっくり返す」と捉えるとよさそうなことに気が付きます。主に駒が2個の時に勝利条件=白黒1つずつだったので。
これは、最終的に駒を1つ取り除いたほうがその次に相手が最後の駒を取り除いてくるので負けるため、お互い可能な限り移動し続けます。その結果必ず白黒1つずつの状態になって移動できなくなるので、それと同じ状態(白黒→白黒の遷移は出来ないけど、必ず白白→白黒と黒黒→白黒は存在するので)で負けることが分かります。

さて、市松模様の白黒を用い始めたところで、駒の個数ごとに勝てる条件を探してみましょう。探し方は「2個の基準が存在するので、3個以降はn-1個の時の勝利条件を相手が作れない」状態を探すことです。

  • 1個→相手が取り除くので必ず負けます
  • 2個→前述の通り白黒1つずつで勝ち
  • 3個→白白白と黒黒黒で勝てます(色を変えてきても取り除いてきても白黒の状況が作れます)
  • 4個→白白黒黒で勝てます(同様相手の行動に応じて必ず白白白か黒黒黒が作れます。それ以外は逆に白白白か黒黒黒を作られます)
  • 5個→白白白白黒か白黒黒黒黒が勝利条件です
  • 6個→白×6、白×3黒×3、黒×6が勝利条件です

という感じです。これを見直して規則を探すと、「白の個数-黒の個数が3の倍数で勝利」という規則が見えてくるのではないでしょうか。

ということで、これをそのまま実装すると通ります。O(HW)。

int main() {
    int h, w;  cin >> h >> w;
    vector<string> s(h);  cin >> s;
    int cnt = 0;
    rep(i, h)   rep(j, w) {
        if (s[i][j] == 'o') cnt += ((i + j) & 1 ? 1 : -1);
    }
    cout << (cnt % 3 == 0 ? "YES" : "NO") << endl;
    return 0;
}

感想

僕がゲーム分野得意なのって、絶対にこの解き方で解けるからなんだよね…あまりいいことではない気がする…

TSG LIVE2!の感想・反省等を適当に書いたポエム

この記事はTSG Advent Calendar 2018の13日目の記事として書かれたはずでした。書き始めたの23:45分なんですが。15分で書けるかボケ。

昨日はpizzacat83プロの『語彙力ゲーム「弓箭」であそぶ』でした。今日はkakinotaneプロの「linux sourcecode readingでやった環境構築」だそうです。

編集後記:この記事は異常に長いので読むことを推奨しないことを書いておきます。

続きを読む

ちょっとしたlsのtips

この記事はTSG Advent Calendar 2018の5日目の記事が当日18:00になっても出てこないことから「やべぇ」となって慌てて作られた記事です。昨日はmoratorium08さんのTSG live CTF writeup - cruel dd, rop4, rop1, simple pwn, RSA modoki, repeat64, leap it, TSG shooter - moragramming!でした。

さて、来週or再来週のコンテンツ制作に奔走している僕ですが(無駄に期待値を上げる人)、今学期のTSG分科会で触れた内容を少しここに書いてみたいなと思いました。

続きを読む

AtCoder Grand Contest 025: D - Choosing Points

思考過程を文章として残してみたので、公開してみようっと。

問題

2N*2Nのグリッド上で、どの2点間の距離もd1、d2とは異なるようなN*N要素からなる集合を作ってください。

D - Choosing Points

解説

最初の方針

特に何も考えなければ全体の1/4を選べれば正解で、d=1の時は市松模様、d=2の時はストライプになる感じでd1,d2でそれぞれ1/2になりそう?(d=25とかa2+b2=c2になるときは要検証)

ってことで取り敢えず(0,0)から貪欲に選択していく方式で実装してみる。O(N3)くらいにしなきゃいけないので、

  1. 最初に(0,0)から距離がd1,d2の点を列挙->O(N2)
  2. 1で生成したリストの要素を(x,y)としたとき、他の点でも使えるよう(-x,y)、(x,-y)、(-x,-y)もリストに加える。
  3. 各点について2で生成したリスト分ずらした点を1つも使用していなければ使える。リストの点は実際ほとんど存在しないはずなので、O(1)位に見積もっても悲惨なことにはならないはず。

という感じです。

で、勿論WAしました(だから検証しろって言ったじゃん…)

a2+b2=dで分解できるとき

取り敢えず20×20でd=25の時の残りマス数を見ると「139/400」。1/2未満です。実際提出してみた結果を見ても、このケースさえ何とかなればACぽい。

生成されたマス目(以下。oを使用しています)をみるとかなり不規則なので、これを規則的に直したいと思います。

oooooxxxxxoooooxxxxx
oooooxxxxxoooooxxxxx
oooooxxxxxoooooxxxxx
xoooxxxxxxxoooxxxxxo
xxoxxxxxxxxxoxxxxxxo
xxxxxxxxxxxxxxxxxxxo
xxxxxxxxxxxxxxxxxxoo
xxxxxxxoxxxxxxxxxooo
oxxxoxoooxoxxxoxxoox
ooxooxxoxxooxoxxxoxx
oooxoxxxoxoxoxxxxxox
xoxxxoxoxoxxxxxxxoxx
xxoxxxxxxxxxoxxxoxxx
xxoxxxxxxoxoxxxoxxxo
xxoxxxoxoxxxoxoxoxox
xxxoxoxoxoxoxoxoxoxo
oxoooxxxxxoxoxoxoxox
ooxoxxxoxoxoxoxoxoxo
oxxxoxoxoxoxoxoxoxox
xoxoxoxxxoxoxoxoxoxo

ところでd=25の時に限って言うと、「市松模様」で実は通ります。ただ、同じ形状のd=100では2x2単位の市松模様にする必要があります。これは分解後のa,bの偶奇に依存しそうです。

こっちの方面の考察をもう少ししてみましょう。a,bの偶奇について考えます。

  • dが奇数⇔a,bの偶奇が異なるとき
  • d≡2(mod 4)⇔a,bがともに奇数のとき
    • d=50が(1,7)と(5,5)で分解できるなど。斜めのみのパターン。d=130が結構厄介で、貪欲解はこいつに殺されます。
    • でもその原因は「貪欲だから」で、少し控えめの「偶数行目のみ取る」という方針を取れば解決。(両方奇数ダカラネ!)
  • d≡0(mod 4)⇔a,bともに偶数のとき
    • これは、全体を2で割って座標を圧縮することで上のどちらかのパターンに持ち込むタイプ?縮小して上のケースに持ち込んだ後、拡大するのを忘れずに。

また、上の考察で用いられる模様は全て「残りの個数を1/2にするけど、他の模様と独立」という点があるため、問題無く1/4取り切ることが出来るはず。

bool use[610][610];

void fill(int d, int n) {
    int cnt = 0;
    while (d % 4 == 0) {
        d /= 4;
        cnt++;
    }
    int m = 1 << cnt;
    if (d % 4 == 1) {
        // 市松模様
        rep(i, n) {
            rep(j, n) {
                if (((i>>cnt)+(j>>cnt)) % 2 == 1) {
                    use[i][j] = false;
                }
            }
        }
    }
    else if (d % 4 == 2) {
        // ストライプ
        rep(i, n) {
            if ((i >> cnt) % 2 == 1) {
                rep(j, n)   use[i][j] = false;
            }
        }
    }
}

int main() {
    int n, d1, d2; cin >> n >> d1 >> d2;
    int N = n << 1;
    rep(i, N)   rep(j, N)   use[i][j] = true;
    fill(d1, N);
    fill(d2, N);
    // 同じフィルターをかけたりすると密度が1/4にならないので、cnt必須
    int cnt = 0;
    rep(i, N) {
        rep(j, N) {
            if (use[i][j]) {
                cout << i << " " << j << endl;
                if (++cnt == n * n)   return 0;
            }
        }
    }
    return 0;
}

感想

超考察寄りの構築ゲーでした。このレベルで試行していたら分かりやすいな…と思って書いてみたけど、どうなんだろ(コードの読みやすさは度外視)

SRM599(div1) Med: FindPolygons

昨日こんなことをし始めました。

hyoga.hatenablog.com

ただ、今の自分は黄色手前の青。div1Easyは流石に解けていないといけない領域です。ということで、一緒にMedも解くことで精進をしよう!というのが本来の趣旨です(絶対分かるかこんなん)

続きを読む