てきとーな日記

2010-08-28

[]プログラミングコンテストチャレンジブック 21:36

id:iwiwiとkita_masaとの3人で、一年ほど前からのんびり書いていた本がついに発売されるらしいです。

http://book.mycom.co.jp/book/978-4-8399-3199-5/978-4-8399-3199-5.shtml

ちょい高めですが、自分たちがプログラミングコンテストで得た知識、ノウハウが詰まってるので、ぜひどうぞー!

Yuki SaitoYuki Saito 2010/08/30 05:31 紹介してくださってありがとうございます、ぜひこれで勉強させていただきます!

2010-08-05

[]TCO10 Marathon Round 3 18:24

Subgraph Isomorphismする問題

暫定8位だけど、おそらくシステムテストで順位が超入れ替わると思われるので安心出来ない

通過できてるといいなぁ

戦略上重要なこと

スコアが絶対評価なので、点が稼げるところで一気に稼がないといけない

難しいケースは頑張っても20〜40点とかそれくらいの点数しかとれないのに対し、簡単なケースは300点以上取れる

forum情報だと1ケースで2600点とった人までいるとか…

このことに終盤で気づいたので、そっからは点数低いのをあげようとするのをやめて、点数高いやつをさらに高くするために頑張った

基本的な方針

基本的には全探索するだけ

まず最初に、H(小さい方のグラフ)の頂点の順番を固定し、その順に探索を行う

固定せずに、候補数の少ない点からやったほうがよさそうな気がするが、候補数の計算に時間がかかる、ちょっと先の方に難しい場所があってもそっち方法に進むとは限らない、といった問題があってスコアが悪かったので最終的には固定順で行くことにした

Hの順番を決めたら、次はHの1点目に対応するG(大きい方のグラフ)の点を決めて(全頂点回す)、探索を行う

全探索だととても時間がかかってしまうので、まず最初に嘘探索を行った

ある頂点のマッチングに失敗したときに、普通の全探索だとひとつ前の頂点まで戻るところを、マッチングに失敗した原因となる頂点まで一気に全部戻る

あとで気づいたのだが、これをもうちょっと改良すると嘘でなくなるので全探索の改良もできた(終盤で一気に伸びたのはこれの影響が大きい)

また、うまく行くときはたいていすぐに解が見つかって、うまく行かないときはいつまでたっても終了しない感じだったので、いきなり全探索をするのではなくて探索木の分岐数を最初1に制限し(つまり、バックトラックしない)、それで見つからなければ2にし、それでもだめなら嘘探索→全探索を行った

固定順の計算

固定順の計算法は、まず最初に1点を決めて、すでに決めた頂点集合Uに次のような方法で頂点を追加していくことにより行った

  • Uの2点以上と接続している頂点があれば、その中でUとの接続次数がもっとも大きい物を加える
  • そのような頂点がなければ、Uから出発してUに戻ってくる最小無向閉路を探し、その閉路上の点を順番に追加する
  • そのような閉路がなければ、Uから出発して、どこにも進めなくなる最小のパスをさがし、そのパス上の点を順番に追加する

最初の一点の計算は、全ての点に対して、そこを1点目とした場合にその後5回閉路を辿るのに何頂点必要かを計算し、もっとも小さいのを採用した

こんな感じで序盤に難しい場所(基本的に辺の数が多いほど難しい)を探索すれば、できるだけ早い段階で解がないと判定できて実行時間が短くなるはず

探索の方法

f(v)=v2をv∈V(H)に対応する点がv2∈V(G)であることを意味するとする

探索はf(v)の値をv=0から順に決めていくことにより行う

最初の点は|V(G)|個の可能性があるので全通り回すことによって決めるとして、1番から先の点vに対しては次のように行う

  • vに隣接する点u(<v)を探してくる
  • f(u)に隣接する点v2を探してくる
  • f(v)=v2としたときに、v2の隣接関係が大丈夫かチェックする
  • 大丈夫ならf(v)=v2としてv+1のマッチングを行う
  • v+1のマッチングに失敗したらv2の他の候補を調べる

よく考えると、v+1のマッチングに失敗した原因がf(v)=v2とは無関係であった場合、v2を他の点に変えてもやはり失敗することが確定しているのでさらに前の頂点まで一気にもどることができる

そこで、マッチングに失敗した原因となる頂点のリストretを用意し、次のように改良した

  • vのマッチングにおける失敗の原因リストret_vを別に用意する
  • vに隣接する点u(<v)を探してきて、ret_vにuを追加(f(u)が変化すれば、f(v)の候補点が変化するので可能性が生じる)
  • f(u)に隣接する点v2を探してきて、f(v)=v2としたとき、v2の隣接関係が大丈夫かチェック。駄目だった場合にはその原因のうちで最も番号の小さいものをret_vに追加する(一番小さいの以外が変化しても、結局一番小さいやつのせいでf(v)=v2のマッチングは失敗する)
  • 大丈夫ならf(v)=v2としてv+1のマッチングを行う(この時点でretとret_vは別物のまま)
  • v+1のマッチングに失敗したとき、retにvが含まれているかを調べ、含まれていなければ他の候補を調べる必要はなく、そのままリターン(retもそのまま)
  • 含まれている場合は、v2を変化させればうまく行くかもしれないので他の候補を調べる
  • 全ての候補で駄目だった場合は、ret_vの要素を全部retに加えてリターン

この改良によりローカルでは1000点以上上がった(TC鯖上では500点くらいしか上がらなかった)

高速化

簡単なケースでは、ほとんど詰まることなく単に時間との勝負だったので、高速化が必要だった

Javaでも高速化を結構がんばっていたが、やはりC++にしたほうが良いのは明らか

でも、C++に移行するとアルゴリズム的な改良が出来ない自信があったので、終盤ギリギリまでJavaでやってからC++に移行してひたすら高速化祭りをした

結局C++移行によりローカルでは800点くらい上がった(TC鯖上では400点くらい)

反省点

ローカルテスターとビジュアライザの仕様上、インタラクティブにするのがめんどかったので、どうせ300点くらいまでしか取れないだろうと思って入力は300点分あらかじめファイルに吐いておき、リダイレクトで起動するということを行っていたが、終盤になって300点なんて軽ーく超えるという状況になってしまった

実はこいつらの中には1000点近く取れてるのがいたみたいで、そうなるとおそらく探索だけでなく固定順の計算とかもボトルネックになっていると思われ、そこら辺もちゃんと最適化すべきだったorz

あと、ほぼ全部解けるのなら、Gに含まれるクリークの位置をあらかじめ調べておくっていうのも有効だったかもしれない

Gにクリークが少ししかない(多くのケースで3クリークは大量に含まれているが、簡単なケースだと4クリークが一桁個ということがある)場合に一気に候補が絞れるのだが、Gに少ししかないということはHに含まれている可能性も少ししかなくて役に立たないだろうと思っていた

しかし、簡単な問題ではかなり大きいグラフまで解けることを考えると、Hにも結構含まれていそうだった

おまけ

デバッグなどの目的でグラフビジュアライザを作成した

大量の頂点を平面に描画すると辺が重なってワケが分からなくなるので、三次元で配置して、くるくる回せるようにした

頂点数が多くなっても全体の構造も細かい部分の接続関係もちゃんとわかっていい感じ

f:id:wata_orz:20100805160446p:image

せっかくなので公開

http://ow.ly/2ll3X

ぱすわーどはてきと

使い方

ダブルクリックで起動

始点 終点 (辺のラベル)

を一行に1辺ずつ入力

まともな配置になるまでShowボタンを連打

ドラッグで回転

頂点を右クリックでその点に接続する辺のみを表示

2010-06-22

[]ICFP Programming Contest 2010 03:01

きたまさが数学界に引きこもってしまったので今年はid:iwiwiと二人で参加。

チーム名はHITOCry

前回は劣化マラソンな感じで初日で飽きてしまったが、今回はなんか面白かったので完走した。

結果は7位だったorz

作業はGmailチャット+DropBoxのファイル共有で行った。

以下チャットのログから掘り起こした全体の流れ

続きを読む

2010-06-07

[]IPSC 2010 11:54

今年は個人で参加した。

8問半解いて、全体で15位、個人の部では1位だった。

A

数列が与えられるので、ソートされてないように並び替える問題

やるだけ

B

平面上に一本直線があり、この直線上と上下左右への移動のみによる二点間の最短距離を求める問題

二点から水平・垂直な直線引いて交点求めてそれらからなるグラフの最短距離求めるだけ

C

「変数=数式」っていう形の入力を受け取って、各変数の値を求める問題

ただしループはしない

頑張ってパースするだけ

D

N個の頭を持つドラゴンを倒したい

二種類の剣があって、剣iはドラゴンの頭をci減らすがその後gi本の新しい頭が生えてくる

ドラゴンの頭を全て切ることができればあなたの勝ち

ドラゴンの頭がci未満だとその剣は使えない

しかし、自分も頭があるので、ドラゴンの頭がci-1個の時は自分の頭も一緒に切ることで引き分けにできる

勝敗判定せよって言う問題

拡張ユークリッドして場合分けしまくったら通ったが怪しい

E

ちゃんと読んでないが、たぶんインタラクティブ問題

時間かかるので放置

F

N個のサイズが異なる立方体があるので、それらを積み上げて二つの等しい高さの山を作るとき、最大の高さを求める問題(全部使い切らなくても良い)

に対する嘘解法が4つ与えられるのでそれらを全て同時に撃墜できる入力を作る問題

ランダムに入力生成すればそのうち落ちるかと思ったが全然落ちなかったのでちゃんと考えて作ったら落とせた

G

読んでない

H

指定されたMD5値になるようにファイルを生成する問題

無理ゲー

I

多角形(凸とは限らない)が与えられて、その内部の点から各辺の延長線上におろした垂線の長さの和の期待値を求める問題

頑張って積分するだけ

J

N個の机があり、各机に青と赤で数字を書く

最初、N人の男女が各机に一人ずつ居て、一定時間ごとに男は青の数字の机に移動し、女は赤の数字の机に移動する

N回の移動で、各男女が全ての机に移動し、各男が全ての女と同じ机になることがあるような番号付けを求めよっていう問題

サンプルからてきとーに類推して出したら通った

K

二人プレーのゲーム

3次元中に点がN個あって、各点は原点からのユークリッド距離が真に小さくなる格子点上へ移動させれる

各ターンに最大K個の点を動かすことが出来、全部原点に移動させたプレーヤーの勝ち

勝敗を判定せよっていう問題

同時に1〜K個のゲームを進められるNimは山のサイズを二進表記の各桁毎に和を取って全部mod(K+1)で0なら負け、そうでなければ勝ち

座標が超でかくて山のサイズがナイーブに求まらないのでちょっと大変

位置(x,y,z)に対応する山のサイズは|(x,y,z)|^2=Mとすると、|(x',y',z')|^2=K<Mとなる点(x',y',z')が存在するようなKの個数に等しい

つまり3つの平方数の和で表せるような数の個数を求めればよい

google先生に聞いたところ、表せない数は4^n(8k+7)であることが分かったため、サイズがO(log M)で求まって解けた

L

1円の切手がN種類と、2円の切手がM種類あるから、これらからK円分買うような方法の総数を求める問題

smallはKが小さいので2円の切手を何円分買うかが全通り試せる

largeはKが超でかいが、行列累乗で解けると思う

最後10分くらいで気づいたが組み終わらなかった

M

ペナルティーを減らすサービス問題

コンテスト開始〜2時間と2時間30分〜4時間30分に2回ゲームが開かれる

好きなタイミングで提出して、全参加者の提出時間の平均の2/3に近いほどペナルティーが下がる

点は入らないので、終了直前に暇になったらやればいいやと思って、4時間30分過ぎた時点でようやく問題読んだらすでに終わっていた

トラックバック - http://d.hatena.ne.jp/wata_orz/20100607

2010-05-04

[]Marathon Match 59 00:59

TCOのシードを得るために一年ぶりに参戦

結果は11位orz

まぁ、久しぶり過ぎた上に時間がなさすぎたのでしょうがない…

方針はまず、何段にするかと、それぞれの段の高さを決めるために、次のように制約をきつくした問題を考え、それを解くことにした。

  • i段目に入っている本はi+1段目に入っているどの本よりも高さが低い

こういう制約を付けると次のような二段階のDPにより最適解を求めることができる。

  • まず、本を高さでソートする
  • dp1[i][j] := [i,j]から幅Wで選ぶときの最大価値
  • dp1[i][j]の計算はiを固定しておいて、ナップサックするだけ
  • サイズが大きいと計算量がやばいので、ナップサックDPは諦めて貪欲法を使用
  • dp2[h][i] := i番目までで高さがhとなるときの最大スコア
  • dp2[h][i]=max{dp2[h-book[j].height-10]+dp1[j][i]}みたいな感じ
  • こっちも計算量がやばいので、嘘DPを使用

何段にするかと、高さが決まったら、次は高さの低い段から貪欲的にナップサックDPを行って本を入れる

これだけだと、空きスペースができてもったいなかったので、本を別の段に移動させることにより、新たに別の本が入れれるようになるっていうのを探して頑張って詰め込む

時間が余るので、高さをランダムにちょっとだけ変更して繰り返しー