ICPC 2014 Tokyo Regional Contest 参加記

7完でチーム順位6位（大学順位5位）でした。上のチームに中国チームが多いのでまた世界大会参加できるかも？
基本戦略は予選と同様にzerokugi君とn_vip君に読解・解法を丸投げして私が実装するという流れでした。
WFが狙える順位をとるという目標はとりあえず達成できたような気がするものの、Colorful Jumbo Chickenに僅差で負けてしまったのがかなり悔しいので台湾でリベンジしたいですね。

続きを読む

ICFP Programming Contest 2014

http://icfpcontest.org/

今年も会社の人と合宿で参加、チームメンバーは @foota, @logicmachine, @nabesan_tofu, @tanakmura, @tomerun の5人でした。


提出物: https://onedrive.live.com/redir.aspx?cid=ecb59e566c2d71f1&page=self&resid=ECB59E566C2D71F1!4174&parId=ECB59E566C2D71F1!3550&authkey=!Alp6E3GNPHKNM7k&Bpub=SDX.SkyDrive&Bsrc=Share
tanakmuraさんの参加記: http://d.hatena.ne.jp/w_o/20140728#1406555463

やったこと

基本的にLambda-ManのAIに必要なものばかりやっていました。アセンブラでライブラリ書いたりAI実装したり。

Lambda ManのAI

小さい盤面用・大きい盤面用とゴーストが接近しているとき用の3種類のAIをくっつけてあります。

小さい盤面では、毎ターン最寄の点数源を持つセルへの最短路を求めてその方向へ移動します。あとPower Pillをとった後はゴーストの方に近づこうとしてみたり。最短路を求めるのにはダイクストラ法を使っています。（重みづけできたりBFSでもlog nが消せなかったりするため。）

大きい盤面では毎ターン経路探索をするとCycleLimitに引っかかるので事前に求めた経路をたどるだけにしています。初期化時は割と十分な時間があるので最初に幅優先探索（実装はダイクストラ法）をしてその結果のBFS-Treeを深さ優先でたどっていくことで全セルを通る経路を生成しています。実際にはゴーストなどの影響による中断・再開を考慮するため、各セルに4方向の部分木の処理が終わったかの情報も持たせて、適宜それを参照して再開します。あとは自明な最適化として得点源を持たないサブツリーはまとめて枝刈りしたり。一応、妨害が少なければ制限時間内に256x256でも辿れるようにはなっているはず。

ゴースト避けAIでは4近傍のセルについて、各セルからすべてのゴーストより先に到達可能なセルの数をある程度の範囲内で求め、その数が最大のセルに移動するようになっています。セルの周囲の壁の数やアイテムなどで重みをつけてみたりしたものの、結局最後まであんまりいい感じにはならず……

ライブラリ

クリティカルなところはアセンブラを書いてライブラリ化。一応そこそこ高速なものは作れたつもり。
最終版で使ってたライブラリは以下のような感じ。

  • higher_order (よく使う高階関数。mapとかfoldrとか。)
  • list (各種リスト操作。lengthとか(push|pop)_(back|front)とか。)
  • array (配列。実際は二分木になっていてランダムアクセスはO(log n)。)
  • heap (Skew heap。ダイクストラ法で利用。)

時系列

きちんと文章でまとめるのめんどくさいので箇条書きで。

あんまり他の人がやってることに首突っ込めなかったんで自分がやってた作業中心に。

1日目
  • 問題読む。長い。けど半分くらいは謎アーキテクチャの説明に見える。
  • どうやら先のアーキテクチャ用のパックマンAIを作ればいいらしい。とりあえず簡易アセンブラを書いてシミュレータで遊んでみる。
    • carとかcdrとかLispっぽいけどLispわからない……
    • 破壊的代入とかできないっぽい
    • スタックマシンなら昔ActionScriptのVMいじってた時のあれこれが使えるかと思ったけどなんか思っていたのと違う
    • むしろ関数型な思想で書いた方がよさそう
    • Environment Frameとかいまいち理解できなかったけど何となく手でもある程度は書けそうな気はする
    • なんかゴースト用CPUの仕様もある。どうせLightning終わってから書かされるんだろうと思いつつ読み飛ばす。
  • とりあえず最寄りの点数源へ向かう処理（→幅優先探索）を書こうとする
    • そのための下地になるライブラリを書いていく（よく使いそうな関数とか配列とか）
  • 日が昇りそうになってきたあたりでとりあえず配列まで書けたので寝る
2日目
  • 朝食時に昨晩やったことを伝えて二度寝。結局再開は昼から
  • 二度寝している間にGCC-Cコンパイラの初期版が出来上がっていた
  • とりあえずLightningまでにそこそこの点数をとれるように幅優先探索を書く
    • 配列とか性能に響きそうなところはアセンブラで残りのレイヤー高そうなところはGCC-Cで
  • かなり遅いけどとりあえずそれっぽい動作をするようになる
  • よくGhostにぶつかって死ぬのでなんとなくゴーストの周りを避けるように修正
    • パラメータによってはサンプルくらいはクリアできるようになる
  • ここまでで一旦提出
  • 案の定「ゴーストも書いて提出してね！」
  • 現状まだできてなくてやったほうがよさそうなもの
    • 大きい盤面をどうにかしてたどれるようにする
    • ゴースト対策があんまりにも雑なので改善する
    • 強いゴーストを書く
3日目
  • どうせ配列アクセスがO(log n)なせいで幅優先探索がO(|E| log |V|)みたいになってしまっているからとダイクストラ法を書いてみる
    • 重みづけとかできるといろいろ便利そう
    • 結果的にそこそこ高速に動作したので採用
  • ライブラリの再調整
    • 配列のパフォーマンスチューニング: Readが2倍くらい、Writeも1.5倍くらい速くなった（気がする）
    • コンパイラに無名関数機能を追加してもらって高階関数入れてコーディング速度上げたり
  • Power Pill 取得時にゴーストを叩きに行くようにする
  • どうやらゴーストがもりもり強くなっているらしい
    • デバッグの様子を覗いてみると確かに瞬殺されてしまっている……
  • 大きいフィールド対策も実装する
    • 初期化時間はかなり長くてもいけるのでそこでまとめて計算する
    • BFSして求めた全域木を順にたどるような感じで処理
      • 最初のBFSがワーストケースで 180,000,000 [cycles] のうち 100,000,000 [cycles] くらいで済むのでまぁ行けそう
    • 木の途中から再開できるようにしたりしてとりあえず256x256マップも妨害がなければ解けるようになる
4日目
  • Scoreboardに提出してみる
    • "Game over! Timed out. You scored 0 after 257109 game ticks."
    • !?
  • タイムアップまで一歩も動いていないらしい。さすがにやばいのでデバッグする。
    • ジャッジからのレスポンスはスコアのみでデバッグ命令なども使えないのでそこそこ難航……
    • 何かしらの実行時エラーでクラッシュしているらしいので二分探索的にバグを探す
    • 結局負数の乗算でオーバーフローが発生したときの挙動がブラウザ版と異なっていたらしい
      • "LDC 2; LDC -2^31; MUL" の結果がブラウザ版だと0でScoreboardでは2^31-1になる
      • IRCで確認したところブラウザ版の挙動が正解だけどすぐに修正できないとのこと（結局コンテスト期間中には修正されなかった）
    • さすがにラスト半日の時点で3時間持って行かれたのはつらい
  • 大きいフィールド用AIと毎回探索するAIを結合する
  • ついでにゴーストが近くにいるときも別のAIを用意する
    • ゴーストとの距離がある程度あるときに同じところを行ったり来たりして煽ってるような挙動をする……
  • 結局ゴーストAIが強すぎてずっと負けっぱなし……
  • 時間内にできそうなレベルだと大した改善も思いつかなくなってきたので全域木の枝刈りを追加して提出。終了。

雑感

  • 数時間でコンパイラ実装する人々やばい（しかも結構な比率で存在するらしい）
    • 「こんなのできますか？」と聞いた1時間後に言語機能が追加されていたり
  • ゴースト強すぎてかなりつらい
  • きちんと履歴をとって膠着状態を回避すべきだった
  • 割と最後の方までなぜか自分だけゴーストをロボットと呼んでしまっていた

SRM620 D1-Hard PerfectSquare

TopCoder

線形代数やらないといけないと思いつつやってない。

問題

n*n行列が与えられる。そのなかからいくつかの要素を以下の制約を満たすように選ぶ。

  • 各行から選ばれた要素の数が奇数個となる
  • 各列から選ばれた要素の数も奇数個となる
  • すべての選ばれた要素の積が平方数となる

このような条件を満たす要素の選び方の数 (MOD 1000000007) を求めよ。

  • n <= 20
  • 行列の要素 <= 1,000,000,000
続きを読む

SRM608 D1-Medium BigO

TopCoder

最後の詰めが甘い。

問題

頂点数nの有向グラフが与えられる。そのグラフ上で長さLのウォークの数が O(L^K) に漸近するとしたとき、Kとして取りうる最小の値を求めよ。
指数オーダなど O(L^K) では表せない場合は-1。

  • n <= 50
続きを読む

SRM588 D1-Hard GameInDarknessDiv1

TopCoder

問題

2次元上のn*mセルからなる盤面にアリスとボブのトークンが1つずつ配置されている。盤面には壁があり、壁でないセルの隣接関係をグラフにすると木になっている。
アリスとボブが交互にトークンを隣接したセルに移動させる。もしアリスとボブのトークンが同じセルに入るとアリスの勝ち、100000手逃げ切ることができればボブの勝ちとなる。
ただし、アリスには双方の初期位置しかわからず、ボブの移動経路は知ることができない。また、ボブはアリスがゲーム中にどのようにトークンを移動させるかがすべてわかっている。
この条件のもとで、双方が最善な手を取った時にどちらが勝利するかを求めよ。

  • 2 <= n, m <= 50
続きを読む