CODE RUNNER 2015 予選A 参加記

昨年に引き続き参加.
(※ この投稿は予選中に最後のプログラムを回しながら書かれたもの)

coderunner.jp

詳細なルールは公式ページを見てもらうとして, ゲームの簡単な説明としては200×200の格子点に交差しないように線分を引きまくるというゲーム. HTTP通信でサーバに頂点リストを送信し,サーバから帰ってきたスコアを基にして最終スコアを競う.

後記

放送で聞いた直大さんのアイデアが凄かったのでもうそれでいいんじゃないかな. 少なくとも(おおまかな)座標を求められることが判明したので, 以下の文章は今や完全に陳腐化しているので注意.

考察

200×200の格子点上で2つの頂点を指定して線分を引いていく. スコアに用いるのはユークリッド距離. 全頂点は40000あるのに対して,線分を引くのに使える頂点は1000頂点しかない. 如何に格子形の正方形を塗りつぶすかとして考えてみた. 線分の方向性を揃えて,できうる限り平行な線分を引きまくるのが最大値だろうか? でも頂点の位置情報とかとれないし,せいぜいが近いか遠いかくらい. 近い頂点集団で塊,をつくれるかもしれないが自分にそれが扱える気がしなかった. とりあえず線分数の最大化を狙っていく.

やったこと

スタートダッシュ (約4000点まで)

とりあえずスタートとしてペアを作りまくる戦略を取る. 1から1000まで2つずつのペアを作って交差しなければ追加. これをするだけで4000点はいった.

for i in range(0, 1000, 2):
    ans_list = kouho[:]
    ans_list.append(i)
    ans_list.append(i + 1)
    ans = ','.join(map(str, ans_list))
    url = 'https://game.coderunner.jp/query?token=%s&v=%s' % (token, ans)
    result = query(url)
    if int(result) > 140:
        print ans, result
        kouho = ans_list

しかしこのやり方でできた頂点ペアはたったの60ペア. 最大が500ペアなのにこれは少ない. 使用可能な頂点のうち約1割程度しか使えていない. もっと使用する線分を増やせないか考える.

頂点の張り替え (増加なし)

使用している頂点の中から邪魔な頂点を外そうとした.

kouho = (一番scoreの良かった線分ペアのリスト)
for i in range(1, len(kouho)):
    lest = all - set(kouho)
    for j in lest:
        try_kouho = kouho[:]
        try_kouho[i] = j
        ans = ','.join(map(str, try_kouho))
        url = 'https://game.coderunner.jp/query?token=%s&v=%s' % (token, ans)
        result = query(url)
        if int(result) > score:
            print ans, result
            kouho = try_kouho
            score = int(result)
            break

しかしほとんど外せない. というか60ペア=120頂点に対して残りの880頂点張替えを試行するのは時間がかかりすぎる. 全然変動しなかったのでプログラムを動かしながら次のプログラムを書き始める.

線分の張り替え(増加なし)

試行が頂点単位だから遅いのではないか. 線分単位で張替えを考える. 使用している線分と残りの線分リストを次々に試していって追加できないかを試す. ともかく使用線分数を増やしたかった. しかしこれもほとんど変化がない.

for i in range(1, len(kouho)):
    # for elem in itertools.combinations(lest, 2):                                                                                                                     
    flag = True
    for j in range(0, len(lest), 2):
        try_kouho = kouho[:]
        #try_kouho[i], try_kouho[i + 1] = elem[0], elem[1]                                                                                                             
        try_kouho[i], try_kouho[i + 1] = lest[j], lest[j + 1]
        ans = ','.join(map(str, try_kouho))
        url = 'https://game.coderunner.jp/query?token=%s&v=%s' % (token, ans)
        result = query(url)
        if int(result) > score:
            print ans, result
            kouho, score = try_kouho, int(result)
            flag = False
            break
    if flag:
        continue
    for j in range(0, len(lest), 2):
        try_kouho = kouho[:]
        try_kouho.append(lest[j])
        try_kouho.append(lest[j + 1])
        ans = ','.join(map(str, try_kouho))
        url = 'https://game.coderunner.jp/query?token=%s&v=%s' % (token, ans)
        result = query(url)
        if int(result) > score:
            print ans, result
            kouho, score = try_kouho, int(result)

線分の追加(6541点まで)/ 最終ver

いやいや,張り替えとか言わずにそもそもペア数が少ないっていうんだから,増やす方法はもっとあるはずだ. 実は今までひとつ隣の頂点IDの頂点としか線分を作っていなかった. きちんと線分の作り方を総当りしてやればもっと追加できる線分はあるはず.

while True:
    for elem in itertools.combinations(lest, 2):
        try_kouho = kouho[:]
        try_kouho.append(elem[0])
        try_kouho.append(elem[1])
        ans = ','.join(map(str, try_kouho))
        url = 'https://game.coderunner.jp/query?token=%s&v=%s' % (token, ans)
        result = query(url)
        if int(result) > 0:
            print ans, result
            kouho, score = try_kouho, int(result)
            break
        else:
            print elem
    kouho_set = set(kouho)
    all = set(range(1000))
    lest = list(all - kouho_set)

張り替えに使っていた時間をもっとこちらに回してやればもっと点数が稼げたはず. 最終的に272頂点,136ペアまで作ることができた. 最終成績は55位.50位ボーダーには届かなかった.

やってみたかったこと

距離が小さい線分を大量に用意して,それらを組み合わせるだけでも高得点がとれたのではないだろうか. 距離が小さいからスコアが小さくなる可能性はあるが,その分線分の交差する確率が下がり,ペア数で優位にたてるのでは. 逆に距離が大きい線分を用意して,組み合わせるパターンも試したい. 2014年の予選Aのように今後またフリーで遊べるようになったら試してみよう.
(放送を聞いた感じ距離が大きいのを基にしたほうが良さそうだった.線分の方向性を決定づけられるので.)

感想

やっぱりCODE RUNNER面白い.
でもそろそろプロコン界の有名人参加率が上がってきたようで, 上位に入ることはできなくなってきた.
本戦にギリギリいけるかもしれない,くらいになっている.
これで本戦参加枠が狭まったら参加せずに観戦するだけで終わりそうだ.

予選Bも頑張ります.