[ICFPC] ICFPC 2013 の記録 - 菊やんの雑記帳

初日

問題だけ読んで、/myproblemsを送ってみるのを試して仕事に行く。23時ごろから作業開始。
とりあえず、JSONとかHTTPとかをCとかで書きたくないので、Rubyで適当に書いたドライバとopen3で通信するソルバ群にしようということにする。

最初のソルバは「xor, and, shift」だけの問題を解ける簡単なのを作ってみる。すなわち、線形なので(1 << i)に対応する値だけで答ができるやつ。

すぐにできたんだけど、解ける問題が少なかったのでお蔵入りして、HTTPとJSON部分のテスト用にしか使わなかった。

簡単な問題をまず全探索で解こうということになり、式の生成方法を考える。変数の数は1個か3個の場合を考えればいいかなと勘違いをする。最後のぎりぎりまでこの問題に気づいてなかった。「tfold」のときは変数が一個隠蔽されるので、2個の場合も作っておけば枝が減ってた。

サイズが1の式をまず列挙する

// terms[サイズ][使う変数の数: 0は1個。1は3個]
terms[1][0] << "(0)"
terms[1][0] << "(1)"
terms[1][0] << "(x)"
terms[1][1] << "(y)"
terms[1][1] << "(z)"

サイズがS-1の式まで列挙できたら、サイズSの式を列挙する

foreach (s1 + s2 == S - 1)
 foreach (v1 in [0, 1])
  foreach (v2 in [0, 1])
   foreach (t1 in terms[s1][v1])
    foreach (t2 in terms[s2][v2)
     terms[S][max(v1, v2)] << "(plus t1 t2)"

こんな感じ。簡単だね。実際のコードもこんな感じ。まんまそのまま簡単だね。

    # if0
    1.upto(s - 3) {|s1|
      1.upto(s - s1 - 2) {|s2|
        s3 = s - s1 - s2 - 1
        2.times {|v1|
          2.times {|v2|
            2.times {|v3|
              v = [v1, v2, v3].max
              $terms[s1][v1].times {|t1|
                $terms[s2][v2].times {|t2|
                  $terms[s3][v3].times {|t3|
                    gen_if0(s, v, [s1, v1, t1], [s2, v2, t2], [s3, v3, t3])
                  }
                }
              }
            }
          }
        }
      }
    }

で、生成した大量の式の保存先はどうしようかと考えたんだけど、一番お手軽なやり方を思いついたので(すぐに破綻する)やってみる

// ばばーーん
#include "bf.h"
Term t_s2_v0_0 = { NOT, &t_s1_v0_0, 0, 0 };
ull f_s2_v0_0(const ull *v)
{
  return run_NOT(f_s1_v0_0(v));
}

Term t_s2_v0_1 = { SHL1, &t_s1_v0_0, 0, 0 };
ull f_s2_v0_1(const ull *v)
{
  return run_SHL1(f_s1_v0_0(v));
}

Term t_s2_v0_2 = { SHR1, &t_s1_v0_0, 0, 0 };
ull f_s2_v0_2(const ull *v)
{
  return run_SHR1(f_s1_v0_0(v));
}

Term t_s2_v0_3 = { SHR4, &t_s1_v0_0, 0, 0 };
ull f_s2_v0_3(const ull *v)
{
  return run_SHR4(f_s1_v0_0(v));
}

Term t_s2_v0_4 = { SHR16, &t_s1_v0_0, 0, 0 };
ull f_s2_v0_4(const ull *v)
{
  return run_SHR16(f_s1_v0_0(v));
}

Term t_s2_v0_5 = { NOT, &t_s1_v0_1, 0, 0 };
ull f_s2_v0_5(const ull *v)
{
  return run_NOT(f_s1_v0_1(v));
}

Term t_s2_v0_6 = { SHL1, &t_s1_v0_1, 0, 0 };
ull f_s2_v0_6(const ull *v)
{
  return run_SHL1(f_s1_v0_1(v));
}

Term t_s2_v0_7 = { SHR1, &t_s1_v0_1, 0, 0 };
ull f_s2_v0_7(const ull *v)
{
  return run_SHR1(f_s1_v0_1(v));
}

Term t_s2_v0_8 = { SHR4, &t_s1_v0_1, 0, 0 };
ull f_s2_v0_8(const ull *v)
{
  return run_SHR4(f_s1_v0_1(v));
}

// まだまだ続く

これのすごいところは、実行時の式の評価がネイティブコードなので凄い速いところだ！

このあたりで寝る。

二日目

昨日書いたコードで巨大なCのソースを吐き出してコンパイルを始める。
簡単な問題は瞬殺できるようになったので、自動ポストを1時間ほど動かして160点ゲットする。

送信した答えを見てたら、ほとんどの問題が簡単な式で解けているので、実はサイズが大きくても簡単な問題がいっぱいあるんじゃないかってことに気づく。これにより、ソルバの最終バージョンで最終日に全問題特攻すればかなり点数が伸びそうなことが分かった。

調子に乗って生成する式のサイズを少し増やしてみたら、大変なことに気づいた。Cのソースが大きくなりすぎて、コンパイルが全くおわらない。確かに2000万行あるソースを2GBのメモリでコンパイルするのは無理がある。gccはやめてclangにしてもだめで、tccも試したけどあんまりよくなかったので、新しい64bitVMを作ることにする。

とりあえずLinux Mintにしてみたんだけど、ミラーサイトが遅くてなかなか落ちてこないとかで、3時間ぐらいこの辺で使ってた気がする。
でも、8GBのVMはさくさく動いて快適だった。

けど、やっぱり2000万行のソースは無理ぽだったので、ツリーだけ吐いて関数部分は吐かないようにしてみたりしたんだけど、やっぱりコンパイラがネックになって全然サイズが増やせないし、これもうツリーだけ吐くんならバイナリファイルに保存すればいいんじゃねってことになって、そうした。

// これはディスクに残ってたやつ。PLUSとXORだけで1000万行ある。
// 問題ごとにこんなのをコンパイルして万全の体制で挑もうとしてた。
#include "bf.h"
static Term t_s3_v0_0 = { XOR, &t_s1_v0_0, &t_s1_v0_1, 0 };
static Term t_s3_v0_1 = { PLUS, &t_s1_v0_0, &t_s1_v0_1, 0 };
static Term t_s3_v0_2 = { XOR, &t_s1_v0_0, &t_s1_v0_2, 0 };
static Term t_s3_v0_3 = { PLUS, &t_s1_v0_0, &t_s1_v0_2, 0 };
static Term t_s3_v0_4 = { XOR, &t_s1_v0_1, &t_s1_v0_2, 0 };
static Term t_s3_v0_5 = { PLUS, &t_s1_v0_1, &t_s1_v0_2, 0 };
static Term t_s3_v1_0 = { XOR, &t_s1_v0_0, &t_s1_v1_0, 0 };
static Term t_s3_v1_1 = { PLUS, &t_s1_v0_0, &t_s1_v1_0, 0 };
static Term t_s3_v1_2 = { XOR, &t_s1_v0_0, &t_s1_v1_1, 0 };

このあたりで寝る。自動ポストをしかけて寝たので、起きたときには220点ぐらいになってた。

三日目

昨日のツリー生成をRubyでやると遅いので、C++でやることにした。そうすればいちいちファイルを読み書きしなくてもいいし。
コードもどうせforループが10個ぐらい入れ子になったのをコピペしてくるだけだし。

そのあと、もう少し頭いい方法はないものかと色々試行錯誤するも全然うまくいかなかった。仕方がないので、bonus問題ぐらい解けるようになろうと思っていじってたんだけど、完全に体力の限界で何を書いてるのかさっぱりわからんぐらいだったので諦めた。「if test then else」の「then」か「else」かのどっちかに当たる部分は大体一発で生成できてるから、あとはヒントを元に残りの部分を埋めるだけだったんだけど、どんどんコードがぐちゃぐちゃになっていって４時になっちゃったので諦める。

今までできたぶんで、自動ポストを走らせて寝る。

最終結果

{
 "easyChairId":"370",
 "contestScore":992,
 "lightningScore":0,
 "trainingScore":103,
 "mismatches":333,
 "numRequests":3100,
 "requestWindow":{"resetsIn":11.065,"amount":1,"limit":5},
 "cpuWindow":{"resetsIn":11.065,"amount":0.8,"limit":20},
 "cpuTotalTime":3072.344
}

まあ一人でやったらこんなもんだよね。

最終コード
https://gist.github.com/kik/6209891
結局、起動するごとにツリーを作ってるしぐだぐだやね。