Sat Apr 13 2019

Google Code Jam は毎度, 起床に失敗してきた. 今日は 01:00 UTC から Round 1A があり, 珍しく起床に成功できた. また, 運良く通過することが出来たので write up を書く.

\(R \times C\) のマス目の碁盤を, 好きなところからスタートしてジャンプしてくことで, 全てのマスをちょうど一回ずつ訪れることが出来るかを判定, できるならその経路を示すという問題. ただしジャンプできるのは今いるマスから水平でも垂直でもまた対角線上でもない任意のマス (つまり飛車でも角行でも行けないマスならどこにでもジャンプできる.)

スタート位置は大体どこでもいいに決まってるので分かりやすく一番隅っこ \((0,0)\) スタートでいい.

テストセットは Visible (smallのこと) と Hidden (large のこと) との2つがあり, それぞれ, \(R,C\) が \(5\) 以下と \(C\) 以下である. 私は全探索する以外に方法が分からなかったので large は諦めて small さえ通ればいいという気持ちのコードを書いた.

一つのテーブルを持ち回って深さ優先探索するにはおおよそ次の関数 dfs を行えばよい (Python 風の疑似コードで書く):

global table[R][C]

def dfs(i, j, nth):
    table[i][j] = nth
    for i2, j2 in next_candidates(i, j):
        dfs(i2, j2, nth + 1)
    talbe[i][j] = None # reset

つまり, 最初に table をいじってそのまま更に深いところを探索し, 戻ってきたら table を元に戻す. 戻すことをしておこないと別な探索のときに不都合が起きる.

これは再帰で書いたけれど, 言語に依っては再帰の深さに制限がある (Stack Overflow など). 一般に再帰というのは for ループに書き直すことが出来る. ただ今の dfs のように, 終わりがけに処理を施す (table をもとに戻す操作) ようなものはちょっとだけ面倒.

def dfs(i, j, nth):
    table[i][j] = nth
    for i2, j2 in next_candidates(i, j):
        dfs(i2, j2, nth + 1)

というものをループに書き直すのは頻出で, スタック構造を用いれば良い

global stack

# ここで stack に起点となる何かを push しておく

while (i, j, nth) = stack.pop():
    table[i][j] = nth
    for i2, j2 in next_candidates(i, j):
        stack.push(i2, j2, nth + 1)

とできる. ほとんど見た目が同じであるが, stack にその値が入っていることが, そのまま, その値を引数として dfs 関数を呼ぶこと, と同一視して見做せる. 問題は関数を呼び出すことは表現しているが, 関数を抜けることまでは表現していないことだ. すればよい. 二値の値を取るもの, たとえば true と false をタグとして用いて, 一方を関数呼び出し, もう他方を関数から抜け出すことと思えばよい.

global stack

# ここで stack に起点となる何かを push しておく

while (call, (i, j, nth)) = stack.pop():
    if call:  # 関数呼び出し
        table[i][j] = nth
        for i2, j2 in next_candidates(i, j):
            stack.push(i2, j2, nth + 1)
    else:  # 関数脱出
        table[i][j] = None

さて large であるが, ある程度大きい盤面だと必ず経路は存在するようで, 適切に盤面を区切ってやって, その分割ごとに解けば良いらしい.

Golf Gophers

羽数がバラバラだとなんだか難しいが, 全部揃えて \(B\) 枚ずつあるとする. それで返ってきた答えが \[a_1,a_2,\ldots,a_{18}\] だとする. 各 \(i=1,2,\ldots,18\) について, 風車がどれだけ回されたかを考えると, 大体 \(a_i\) なのだが, ちょうど一周した分については観測できないので, mod を取ったものだと分かる. 従って \(i\) 番目の風車がどれだけ回されたかは, ある自然数 \(m\) があって \[a_i + Bm\] だと言える. これが全ての \(i\) について言えてしかも \(B\) は共通だとしたので, 全体で回された数は \[\sum_i a_i + Bm'\] だと言える. この \(m'\) もやっぱり適当な自然数である. そしてこの値こそが求めたい Gophers の数でもあった.

あなたが出来ることは \(n\) 種類の \(B\) (\(2 \leq B \leq18\)) をクエリとして投げることである. それぞれの場合に \(A=\sum_i a_i\) が返ってくるので, 候補として \[A, A+B, A+2B,\ldots\] が得られる. ところでこの数の上限は最初に入力として与えられるので候補は有限通りである.

あとはいい感じに \(B\) をチョイスしていって候補を絞っていけば良い.

私は大して何も考えず \(B=18,17,\ldots,12\) を選択したら通った. が, 互いに素な数を選択すれば良さそうではある.

Alien Rhyme

\(n\) つの文字列が与えられるのでできるだけ多くマッチングしていく問題. 2つの文字列をマッチングさせるとは, 空ではない共通の接尾辞 (suffix) を見出すこと. マッチングに使った文字列は他の文字列とはマッチングさせない. 別なマッチングで使った接尾辞は別なマッチングでは使えない.

貪欲にマッチングさせた場合に困るのは, その接尾辞を持つ文字列が3つ以上持つ場合だろう. 例えば

という4つがあると ABC と XC は "C" によってマッチングできるが, 他の文字列でも "C" でマッチングできるので勿体無い. ABC と XBC を "BC" でマッチングさせたほうが有利だ.

できるだけ長い suffix でマッチングさせたほうがよいと気づける. 与えられる文字列の長さは 50 以下だと書いてあるので

for len 50..1:
    matching(words, len)

としたほうがよい. len でマッチングを考えるときは len+1 以上の suffix でマッチングしたものは全て取り除く. こうすると len でマッチングするペアを見つけたら無条件でマッチングさせて良いことが分かる.

Sat Apr 13 2019

GCJ Round 1A

Pylons

Golf Gophers

Alien Rhyme