2019-07-07

ICFPC2019 振り返り

ICFPC 2019 にチーム「花脊山の家」として参加しました。メンバーは以下の4人です。（nojima君はあまり参加できなかったけど）

cos
nojima
qwerty
seikichi

リポジトリは https://github.com/seikichi/icfpc2019 です。去年と同じくRust使用。

問題

最大400x400程度のグリッド状のマップが与えられるので、ロボットを操作して全ての移動可能なマスを塗りつぶせ。マップにはブースター（アイテム）が置いてあり、それを取得して使うと塗れる面積が増えたり、2倍速で移動できるようになったりする。 300問程度のマップは全て公開されてあり、オンラインで解く必要はない。

また、ライトニング終了後の追加仕様で本編とは別にマイニングが可能で、指定された制約を満たすマップを15分に1回作成・解くと、本編でブースターが購入可能になるラムダコインが手に入る。こちらはオンラインで解かないといけない。

1日目

仕事が終わってから集合場所のホテルに向かう。

19時過ぎ（ICFPC開始が19時）に、ホテルに着いたら問題を読んだり公式のビジュアライザをさわった所、仕様追加でどうせテレポートが出るでしょとか水没するんでしょとか言いつつ、なんか去年の問題の2D版だなあという感じがした。その後、飯を食べてタスクを洗い出してから実装を開始。

まずは入出力・AIの型を適当に決めて分担作業をできるようにしたら、入力パースと最も単純なAI（塗られてない箇所をとにかく塗るAI）をseikichi君とqwertyさん・出力と座標などのライブラリ作成をcos・チーム名決めとチーム登録と問題のビジュアライザ作成をnojima君が担当。

25時くらいにexample01で正の点数を取れるようになったので、問題が更新されるまで寝ることに。

2日目（ライトニング提出まで）

朝起きたらとりあえず問題を読んで、新仕様の入出力対応をcos、1日目のAIのバグ修正を引き続きseikichi君・qwertyさんでやる。バグが取れたら答えの管理をS3を利用するようにしつつ、マニュピュレータを使うようにして13時くらいに初submit。

次にタスクを整理しなおして、速攻でCloneを取りに行って分裂するAIをcos、解答管理・サブミット管理のスクリプトをseikichi君、初期AIのヒューリスティックの調整（回転とかxyの優先度の変更とか）をqwertyさんが担当して実装する事に。

ライトニングまでにCloningを使ったAIもできたので、（Cloneがない場合は同じ挙動するはずなのに点数が違うのはおかしいなあと思いつつ）Cloneが出るまでは初期AI・それ以降はCloneを使ったAIを使うことにしてライトニングは終了。

2日目（真ライトニングラウンド）

ライトニング終わって疲れたので、問題見るのは後回しにしてとりあえずご飯を食べる。帰ってきてから問題を見ると、ライトニング終了から4時間後にマイニングなるものが始まるとおかしい事が書かれてあった。

この、マイニングで利益を得ると圧倒的に本編で有利になる（Cloneが無いマップでCloneが使えるようになるので上位に入るためには必須）し、可能な限り早い段階からやっておかないといけないし、今までのソルバーとは関係ないし、これをライトニング終了直後の4時間で実装しろというのがひどい。

マイニングの自動化周りはseikichi君にまかせて、マップ生成を実装する事に。

マップの内外の制約が一番厳しく、頂点数、面積上限下限（面積の上限は読み間違え）もちゃんとやらないと引っかかるので結構難しい。とりあえずマップの内の制約を満たすようにbfsで頂点をつなげたが、外側にいないといけない頂点を囲ってしまったので、障害物を置くことにして、面積は適当に増やして、頂点数はマップの端を右手法でたどっていく最中に適当に穴を掘って対応した。

グリッドから出力形式への変換がめんどくさいとか斜めの自己交差がめんどくさいとか言いつつ2時半くらいに実装ができてチェッカーで試した所、障害物は置けないことが判明して実装やり直しに…。

今度は、ダイクストラ法で内側の面積を最小にして外側の頂点を囲わないようにしつつ、マップの内の制約を満たしたら内側のエリアからてきとうに長さrの正方形を内側にして太らせて内外・面積下限の制約を満たすまでランダムでマップを生成することにした。

最終的には4時過に実装完了してチェッカーが通った。眠かったし、ランダムでてきとうに実装したのに割とちゃんと動いた。疲れたので寝た。

3日目

CloneのAIのバグ取ったり、各ブースターを取って使うようにしたりした。2倍速とドリルの組み合わせで、掘った穴にぶつかって位置調整するとかでひたすらバグるのがつらかった。発生確率が低かったので、最終的にはあきらめて行動中に不可能な行動を取ろうとすると、キャンセルして行動を決めなおすようにした。

他の人は解答管理スクリプト周りやマップをk分割して順番に塗っていくAIを作っていた。

あと、ランダムのシードが変わると得点が良くなることが結構あったので、良い乱数を引くまでEC2上でガチャを回すようになった。

4日目

ビームサーチっぽいのを雑に実装した。スコアの計算を今から実装するのが難しいので、乱択要素を外してそのまま動かしたときのステップ数をスコアにしておいた。後はマップをk分割する方がバグっていたのでヘルプに行ったりした。

ちなみにアイテム購入は前半の問題から1個ずつCloneを購入で220面くらいまで買えた。

感想

文句

ライトニング終了直後にライトイニング始まるのはさすがにきつい
- 実際間に合ったチームが少なすぎて延期になった
- しかも、解くのが難しい割に1回作って後は放置で良い…
- あと、日本はまだましだけど時差によっては悲惨になりそう
- せめて、最初から仕様を公開しておくべきだと思う
- チームとしては延期後の初回には間に合ったのでまあ良し

面白かった所

パズルソルバーがちゃんと動いてて感動した
- なんか眠い中てきとうに作った割には3,4問程度しか落としてなくてすごかった
AIを強化するたびに点数が上がっていくのが楽しかった
- 使うブースターの種類を1種類増やすたびに5%くらいは改善していった
- ガチャしたり、ビームサーチでも上がった
やっぱRustは良い
- コンパイルさえ通ればなんか1発でちゃんと動くことが多かった
- バグってても、ちゃんと落ちるべき箇所で落ちてくれる
- ICFCPの規模になると、もうC++に戻る理由が無さそう

バグ周り

ライトニング前のCloneを使うAIがバグってた
- これはバグを直す時間がなかったのでしょうがない
ビームサーチがバグってて直すのが遅れてガチャが十分回せなかった
- 書いた行数が少なかったので人に任せたが、さっさと直してから他のことに手を付けた方が良かった
thread_rngのせいでバグったときに再現性がなかった
- small_rngに変えてバグが出るまで実行したりでめんどかった
- ガチャするときに同じseedを使わないようにしておけばsmall_rngでも十分足りる
グリッド分割のAIが間に合わなかった
- 自分が書いたAIに、他の人がさらに大きい機能を追加しようとして時間がかかった（ブースターを使わないと話にならないので使いまわすのは必須）
- 特に4日目にバグ取るのに手間取った
- 関数の責務が明示的になるように分割したり、出力のバリデーション強化くらいはしておいた方が良かった

その他

実質3人だとこれ以上複雑なことやるのは厳しい
- 例えば、マニュピュレータは真横以外につけるとか、ダッシュボードの作成とか、アイテム購入の最適化とかはしてない
- まあ15位以内に入ってるっぽいので十分検討はしてる
- たまに一人チームもいるけど…
リモートの人に仕事を振るのが厳しい
- discordとか用意した方が良い？
- リモートが厳しいというよりかは参加時間が短いと厳しいのかも

結果

8位だったようです。去年よりも良い結果だったので嬉しい。

2015-04-26

Integer Game (UVa Live Archive - Asia - Dhaka - 2009)

UVa Live Archive Online Judge

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=346&page=show_problem&problem=2504

問題

略

解法

忘れた

2014-12-06

幾何のテストケースの作り方

Other

これはCompetitive Programming Advent Calendar 2014に投稿された記事です。

ICPCではいる君に幾何は任せていたので担当ではないのですが、JAGに入ってからは何故か高頻度で幾何の担当になってしまっています。幾何のプロがJAGに入ってもう当たらんだろうと思ったら、この前のICPC模擬地区予選も幾何が2問あって結局データセットを作ってました。
というわけで今まで作ってきたテストケースの手法を書いていきます。

2次元幾何の場合

最低限、コーナーケースや誤差死を防ぐための制約などの洗い出しは事前にやっておきましょう。
generatorを作るのが難しい場合は問題自体を少し変えるのも有りです。例えば、流れ星に願いをでは、当初は最後の星が消える時間のみを出力する予定だったのですが、1つのテストケースで落とせる確率が無駄に減るので、星が消える時間を全て出力するようにしました。

ランダムに作る

点の位置くらいしかない場合はランダム生成でもある程度機能します。この時ランダムの分布をいじって偏りのあるケースなども作っておくと良いです。例えば、平行な線分がコーナーケースの場合はそういったものが多く出るようにします。もしくは、誤答を先に作っておいて誤答になるケースが出るまで生成するというのもありです。
注意点としては、問題によっては生成した入力が、幾何でよくある「EPS以下の距離には〜が無い」といった制約に引っかかる場合があります。そういった制約に引っかかる場合はgeneratorの中でvalidatorを動かして、そういった入力があったら再生成してしまいましょう。あまり適当にやっているとgeneratorが無限ループにおちいる場合もあるので、一旦小さいサイズで生成し、validatorが通ったらサイズを徐々に大きくするなどもありです。

人力で作る

ランダムだけではまともなケースを作るのが厳しい、例えば自己交差の無い多角形とかグラフ要素が混ざってくる場合などです。個別のテストケースを１つずつプログラムを書いて作るのは大変すぎるので、手で作ってしまうのが楽です。
私はdiaというダイアグラム作成ツールでテストケースを作成しています。diaで線分、多角形、折れ線などベクター画像を書き、svgで出力し、C++でパースして問題の入力に変換してます。多角形の頂点の追加などが面倒ですが、100頂点くらいの物ならこれで作れると思います。

色も付けれますし、コピペもできるのでこんくらいのテストケースならすぐに作れます。ただし、入力サイズが大きかったり、数値をちゃんと計算しないと作れないコーナーケース等を作るのは難しいので、プログラムを書いて生成するのと併用する必要があります。

ビジュアライズする

手入力で作った方は既にあるので良いのですが、ランダム生成したものは本当に意図した入力になっているか画像で確認しておきたいです。やり方は人それぞれだと思いますが、私はsvg形式で出力してます（こんな感じ）。利点は標準のファイル形式なのでブラウザやubuntuのフォルダから画像が普通に見れることです。ちゃんと書けばアニメーションもいけると思いますが、そこまでやってないです。

3次元幾何の場合

頑張ってください。
人力でやるのはかなり無理があるので、プログラムを書くしか無いと思います。
テクニックとしては、z=0の入力を作る際は2次元と同じ方法が使えます。縮退した入力はどっちみち必要になるので、2次元で落とせる解答は2次元で落としましょう。3次元の入力が弱くてもなんとかなるかもしれません。
また、ランダムな正規直交基底（平面）を作りたい場合はランダムなベクトル $e_1,v$ を作って $e_3=e_1 \times v$ 、 $e_2=e_1 \times e_3$ と外積を2回かけるとできます。

ビジュアライズする

ply形式で保存すると楽です。ply形式は下のような感じのtxtファイルで、ちゃんとヘッダーを書けばポリゴンも扱えます。

ply
format ascii 1.0
element vertex 2000 
property float x
property float y
property float z
property uchar diffuse_red
property uchar diffuse_green
property uchar diffuse_blue
end_header
1.122748 2.322027 2.471454 255 0 0
1.125541 2.323361 2.465986 255 0 0
1.128307 2.324675 2.460499 255 0 0
1.131045 2.325967 2.454994 255 0 0
1.133755 2.327239 2.449470 255 0 0
1.136438 2.328489 2.443927 255 0 0
1.139093 2.329717 2.438367 255 0 0
...

ply形式はMeshLab等で見ることが可能です。以下はRingsのデータです。