読者です 読者をやめる 読者になる 読者になる

TopCoder SRM 575 Div2

Easy - TheSwapsDivTwo

Johnさんは数列を持っています。Brusさんは、その数列の異なる位置にある任意の2つの数字を選んで、1度だけ入れ替えることができます(Brusさんが選んだ2つの数字は、同じ数字になることもあります)。

Brusさんはこの入れ替え操作によって、最大で何種類の数列を作ることができるでしょうか。


Johnさんの持っている数列の要素数Nは 2 <= N <= 47 とのことなので、愚直にvectorを大量生成してuniqueすれば良いでしょう。

Medium - TheNumberGameDivTwo

JohnさんとBrusさんは数字を使ったゲームをすることにしました。

ゲームは正の整数Nから始まります。プレーヤーは自分の番になったとき、現在の数字に対して次のような操作をします。

  1. 現在の数字をCとします
  2. Cの約数の中で1とCを除いたものから数字を1つ選びます。選んだ数字をkとします。
  3. 現在の数字をC-kに変更して、相手と手番を変わります。

このような操作を手番を入れ替えながら続けていきます。現在の数字が1とC以外の約数を持たなくなったとき、その手番のプレーヤーは敗北します。

JohnとBrusは、Johnさんの先行でこのゲームをすることにしました。両者が最良の選択をしたとき、勝つのはどちらですか?


bool solve(int C) := 現在の数字がCのとき、自分は勝つことができるか?

という関数を定義しましょう。

  1. Cが素数または1のときは、明らかにfalseです
  2. 「次の数字」にすることができる候補(問題文で言えばC-k)の中で solve(C-k) == false となるものが1つでも存在するならば、次の数字としてC-kを選べば勝てるということなので、戻り値はtrueになります
  3. 2.に該当する数字が無いということは、どの数字を選んでも相手が勝ってしまうということなので、戻り値はfalseです

もしかしたら不要なのかもしれませんが、私は念のためメモ化再帰させながら実装しました。

Hard - TheTilesDivTwo

JohnとBrusは長方形のチェス盤を使って遊ぶことにしました。そのチェス盤の行と列を、左上から0-indexedで呼ぶことにしましょう。チェス盤のi行j列のマスは (i + j) % 2 == 0 のときは黒色、(i + j) % 2 == 1 のときは白色です。

既に、そのチェス盤の上にはいくつかチェスの駒が置かれています。vector<string> board に駒が置かれているかどうかの状態が書かれています。

JohnとBrusはL字のタイルを無限に持っています。このL字タイルは、チェス盤のマスと同じ大きさの正方形のタイル3枚からできています。JohnとBrusは、次の条件に従ってL字タイルをチェス盤の上に置いていったとき、最大で何枚のL字タイルを置けるのか調べることにしました。

  • L字タイルは自由に90度回転させてよい
  • L字タイルを構成する3枚のタイルは、どのタイルもチェス盤からはみ出してはいけない
  • L字タイル同士は重なってはいけない
  • 既にチェスの駒が置いてあるマスにL字タイルを置いてはいけない
  • L字タイルを構成する3枚のタイルの中で、角の部分のタイルは必ず黒マスの上に置かれなければならない

本番中には解くことができませんでした。解法はビットDPです。蟻本の「ドミノ敷き詰め」が参考になります。ただし僕はDPを書けないので、メモ化再帰で解きました。実装量がぱないので、書ける人はDPで書いたほうが良いと思います。

チェス盤の左上から、文章を横書きで書くときの向きで、タイルを詰めていくと考えましょう。

int solve(int i, int j, int bit) := 既に置いたタイルの状態をビットにエンコードしたものをbitとしたとき、チェス盤の (i, j) 以降に置くことができるタイルの枚数は最大で何枚か?

という関数を定義します。また、チェスの駒が置かれているかどうかの情報は、グローバル変数で持たせてみました。

いま (i, j) にいるとします。(i, j) 以前のマスは既に埋まっているか、タイルを置ける場所が無いと仮定します。

f:id:kujira16:20130407171044j:plain

引数のbitで渡される情報は、下の写真で示している範囲にタイルが置かれているかというものです。蟻本に載っている問題とは違って、1行+1マスの情報を持たせる必要があります。

f:id:kujira16:20130407171919j:plain

さて、(i, j) が黒マスだと仮定しましょう。L字タイルの角は黒マスの上に無ければならないので、普通なら4方向の置き方が考えられますが、(i, j) 以前のマスは既に埋まっていると仮定しているので、置き方は次のような1種類しかありません。

f:id:kujira16:20130407171331j:plain

次は、(i, j) が白マスだった場合です。白マスに置けるのはL字タイルの端の部分(角でない部分)です。黒マスの場合と同様に (i, j) 以前のマスが埋まっていると仮定しているので、置き方は次の3種類しかありません。

f:id:kujira16:20130407171613j:plain

f:id:kujira16:20130407171623j:plain

f:id:kujira16:20130407171632j:plain

ここで、L字タイルを置こうとしている場所にチェスの駒も、過去においたタイルも無ければ、そこにL字タイルを置くことができます。置けるなら、「そこにも追加でタイルを置いた」という情報をビットにエンコードして、次のマスについてどんどん探索していきます。

ビットに持たせる情報は1行+1マスだけで良いわけですが、それでも普通にやると、チェス盤の1行に含まれるマスの数は最大で47あり、状態をもたせることができないようにもみえます。これを解決するのは簡単で、1列に含まれるマスの数はたかだか4マスしか無いので、チェス盤の縦と横を入れ替えればいいだけです。

まともなビットDPを解けたことがないので、記念にソースも付けておこうと思います。

const int MAX_W = 47;
const int MAX_H = 4;
int W, H;

// チェスの駒が置かれているか?
int state[MAX_W][MAX_H];

// 情報を持たせるための構造体 (map<node, int>に状態を持たせたかった)
struct node {
    int i, j, bit;
    node(int i_, int j_, int bit_) : i(i_), j(j_), bit(bit_) { }
    bool operator <(const node &x) const {
        return i != x.i ? i < x.i : (j != x.j ? j < x.j : bit < x.bit);
    }
};

// デバッグ用
/*
void trace_board() {
    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            cerr << (state[i][j] ? 'X' : '.');
        }
        cerr << endl;
    }
}

string to_bit(int n) {
    string res;
    for(int i = W; i >= 0; i--) {
        res.push_back( (n & (1 << i) ) ? '1' : '0');
    }
    return res;
}
*/

map<node, int> memo;

int solve(int i, int j, int bit) {
    // すでに計算結果があるならそれを利用
    if(memo.count(node(i, j, bit))) return memo[node(i, j, bit)];
    
    // 右端に来た時は1行したの左下へ
    if(j == W) {
        return memo[node(i, j, bit)] = solve(i + 1, 0, bit);
    }
    
    // 下端まで来てしまったので探索終わり
    if(i == H) {
        return memo[node(i, j, bit)] = 0;
    }
    
    // (i,j) にはチェスの駒があるか、過去にタイルを置いた
    if(state[i][j] || (bit & 1)) {
        int b = bit >> 1;
        // cerr << "skip: " << to_bit(b) << endl;
        // 次のマスを調べる
        return memo[node(i, j, bit)] = solve(i, j + 1, b);
    }
    
    int res = 0;
    // 黒マスのとき
    if( (i + j) % 2 == 0) {
        // 写真の case: B の置き方でタイルを置ける
        if(i + 1 < H && j + 1 < W && state[i + 1][j] == false && state[i][j + 1] == false && !(bit & (1 << 1)) && !(bit & (1 << W))) {
            int b = bit;
            b |= (1 << 1);
            b |= (1 << W);
            b >>= 1;
            // cerr << "put b1" << endl;
            // cerr << to_bit(b) << endl;
            res = max(res, solve(i, j + 1, b) + 1);
        }
    }
    // 白マスの時
    else {
        if(i + 1 < H && j + 1 < W && state[i][j + 1] == false && state[i + 1][j + 1] == false && !(bit & (1 << 1)) && !(bit & (1 << (W + 1)))) {
            int b = bit;
            b |= (1 << 1);
            b |= (1 << (W + 1));
            b >>= 1;
            // cerr << "put w1" << endl;
            // cerr << to_bit(b) << endl;
            res = max(res, solve(i, j + 1, b) + 1);
        }

        if(i + 1 < H && j + 1 < W && state[i + 1][j] == false && state[i + 1][j + 1] == false && !(bit & (1 << W)) && !(bit & (1 << (W + 1)))) {
            int b = bit;
            b |= (1 << W);
            b |= (1 << (W + 1));
            b >>= 1;
            // cerr << "put w2" << endl;
            // cerr << to_bit(b) << endl;
            res = max(res, solve(i, j + 1, b) + 1);
        }

        if(i + 1 < H && j - 1 >= 0 && state[i + 1][j] == false && state[i + 1][j - 1] == false && !(bit & (1 << W)) && !(bit & (1 << (W - 1)))) {
            int b = bit;
            b |= (1 << W);
            b |= (1 << (W - 1));
            b >>= 1;
            // cerr << "put w3" << endl;
            // cerr << to_bit(b) << endl;
            res = max(res, solve(i, j + 1, b) + 1);
        }
    }

    {
        // (i, j) は空いてるけど、あえて置かない
        int b = bit >> 1;
        res = max(res, solve(i, j + 1, b));
    }

    return memo[node(i, j, bit)] = res;
}

struct TheTilesDivTwo {
    int find(vector <string> board) {
        memo.clear();
        for(int i = 0; i < MAX_W; i++) fill(state[i], state[i] + MAX_H, 0);
        H = board.begin()->length();
        W = board.size();
        for(int i = 0; i < H; i++) {
            for(int j = 0; j < W; j++) {
                state[i][j] = (board[j][i] == 'X' ? 1 : 0);
            }
        }
        // trace_board();
        int res = solve(0, 0, 0);
        return res;
    }
};