指数時間アルゴリズム

指数時間アルゴリズムというのは,NP困難問題を頑張って指数時間かけて解くアルゴリズムのことで,できるだけ指数の底の小さいアルゴリズムを開発することが目指されています.
コンテスト界では部分和問題の半分全列挙による2^(n/2)時間アルゴリズムなどが特に有名だと思います.
この分野は近年盛んに研究され始め,自分も大学でこの分野を中心に研究をしています.
今回,情報オリンピック春合宿講義とPFIセミナーで発表する機会があったので,この分野の基礎的な手法から最先端の手法までをまとめてみました.

シンプルなアルゴリズムが多く,厳密解&計算量保証あり,という点で非常にコンテスト向けのジャンルだと思います.
これをマスターすれば,TopCoderで頂点数50の最大独立集合が出ても絶対に間に合うプログラムを書くことができるようになったりします.
また,キャンセリングはとても面白いのでみんなで面白いアルゴリズムを考えて半分全列挙のように流行って欲しいです.

嘘解法のススメ

(この記事は Competitive Programming Advent Calendar の 18 日目の記事として書かれました.まだ18日です!セーフ!!!)

自分はICPC時代によく嘘解法を駆使して問題を解いていたので(ジャッジの方々ごめんなさい),よく使われる嘘解法テクニックを紹介したいと思います.
これらのテクニックはマラソンマッチのようにそもそも最適解を求める必要のないコンテストにおいても活用できます.

嘘解法とは

プログラミングコンテストにおいては,ジャッジの用意した入力データに対し,正しい答えを出力できれば正答とみなされます.
このため,正しくない解法(嘘解法)が通ったりすることがときどきあります.
しかし一般に嘘解法で通ることはあまりなく,嘘解法を試すのは終盤まで控えるべきです.
残り時間が少なく今から正しい解法を考える・実装するのは無理だという場合の最終手段と考えてください.
ついでに,正しいけど想定解でもなさそうな解法や本来TLEすると思われる解法も広義の嘘解法として扱っています.

嘘解法の基本

嘘解法で通すためにはまずジャッジの気持ちになることが重要です.
ジャッジがすぐ思いつくような嘘解法はすでに対策されてしまっているでしょう.
また,嘘っぽいけどどうやったら落とせるかすぐには分からないような解法ならジャッジもまた落とせないかも知れませんし,もしかしたらそもそも嘘でないかも知れません.

嘘貪欲

正しくない貪欲法です.
証明ができていないだけで反例が見つからず,実装が簡単であれば提出してみる価値はあります.
反例が見つかるならば,よほどテストデータが弱くない限り通らないので他の手法を考えましょう.

嘘DP

正しくない漸化式によるDPです.様々な嘘DP手法が存在します.
例えば dp[v]=max dp[prev(v)]+cost(prev(v),v) のような漸化式を立てたとします.
このとき状態が不十分でvの最適解はprev(v)の最適解のみからでは本当は構築できないようなDPを嘘DPと呼びます.

状態の圧縮

正しい漸化式ではTLEする場合に,状態を圧縮してTLEを回避するということを行います.
たとえばナップサック問題においては
dp[i][v]:= 品物iまでで価値vを達成する最小のバッグの大きさ
のようにしますが,これをある定数k>1に関して
dp'[i][v]:=品物iまでで価値kvを達成する最小のバッグの大きさ
のように置いて,状態数を1/k倍に圧縮して高速化したりします.
もちろんこのままでは通らないので他のテクニックと組み合わせる必要があります.

複数候補

最大のものだけではなく,大きい方から幾つかを候補としてもっておく手法です.
とくにマラソンマッチでよく使っています.

局所DP

嘘DPなどで求まった嘘最適解を復元し,その周囲の状態のみに関して正しいDPやより精度のよい嘘DPを再度行う手法です.
最適解に近いものがまとまって存在しているようなケースではうまくいくことが多いです.
例えば,障害物があって二点間の最短路を求めよという問題なら,障害物の周りにてきとーにチェックポイントをおいたグラフで最短路を求め,その周囲により細かくチェックポイントを置いて…といった感じです.

山登り

時間のあるかぎり局所改善を繰り返して最適解を目指す手法です.
ラソンマッチではより高度な焼きなまし法などと共に頻繁に使用されますが,全てのケースで最適解を求める用途だとあまり使えた試しはありません.
しかし,例えば最小包含球問題のような凸最適化であればこの手法で最適解を求めることができます.

ランダムでコーナーケースを回避

想定誤答を落とすための入力をジャッジが用意している場合があります.
そのような場合,ランダムに入力を変化させることによって回避できることがよくあります.
例えば,シンプルな探索ではTLEするようなケースをジャッジが用意していても,最初に探索順序をランダムシャッフルしておくことでそのケースでのTLEを回避できたりします.
また幾何の問題においては3点が一直線上にあったり,同じx座標に複数の点があると処理が難しくなるケースなどでは,ランダムに座標をεずらす,ランダムに全体を回転させるなどにより回避できる場合があります.
有名な例として,最近点対問題があります.
この問題は分割統治法を用いてO(n log n)で解けますが,かなり賢い手法なので知らなければ多分思いつけません.
x座標でソートして,各点についてx座標がその点からすでに見つかった解以内の点だけを調べる,という嘘解法くらいならすぐに思いつけるでしょう.
しかし,明らかに全ての点が同じx座標にあるようなケースでは結局全ての点対を調べることになるのでO(n^2)です.
そこでランダムに回転してみましょう.どんな方向についても悪くなるようなケースがすぐには思いつきません.O(n√n)くらいかかるケースなら思いつきますが実際はこの嘘解法で通ることが多いです.

嘘枝刈り

探索系の問題でTLEが取れない場合に,おそらく最適でなさそうな遷移を証明なしで枝刈りして探索空間を削減します.
他にも現在の状態から推移できる状態のうち,よさそうな方からk個だけを調べるなどというテクニックもあります.

嘘A*

正しい下界ではTLEを食らった場合,その下界を+α,×αなどして大きくするとスピードアップさせることができます.
真の下界を超えてしまった場合,正しい解が求まるとは限らなくなるので,解が見つかっても時間のあるかぎり探索を続けてよりよい解を探しましょう.
また,良い感じの下界が求まらない場合に,嘘貪欲などで求めた上界-αのような嘘下界を使うという手法も存在します.

複数の解法の組合せ

一つの嘘解法を落とす入力が様々な想定される嘘解法に対して用意してあっても,複数の嘘解法を同時に落とす入力を用意するのは難しいものです.
したがって複数の手法を組み合わせることで通る確率はグーンとアップします.
また,最大ケースが大量に入っているとは限らないので,ある程度のサイズまで正しく解ける解法があるのならば,
それを用いて解ける範囲は正しく解いた上で解けないケースだけを嘘解法を用いて解いた方がよいです.

定数倍高速化

本来はTLEする解法をビット並列化などを用いて頑張って高速化して通す手法です.
私は普段Java言語を使っており,あまり定数倍高速化で通すことはしてないので詳しく無いです.

埋め込み

ローカルのPC上で前計算をして,解や途中計算結果をソースコード中に埋め込みます.
入力が整数一つ,のような入力空間が小さいケースではよく使われます.
入力は整数が一つだけど,値の範囲は大きいというケースでも,a[n+1]=f(a[n])のような単純な漸化式ならば,一定間隔毎に間引いた値を埋め込むことで実行時の処理を軽減することができます.
他にも,複雑な和の計算を展開(http://d.hatena.ne.jp/wata_orz/20091223/1261582436)して埋め込んだりもします.

LP

整数解になるか分からないけどとりあえずLPでやってみたら通ったということもよくあります.
もっとも,そのようなケースはほとんど最短路・最大流・最小費用流あたりで解けます.
LPで整数解が求まるような係数行列の代表的な例は覚えておくとよいでしょう.
よくあるのは,

  1. 有向グラフの接続行列 (つまり,各行or列に係数1と-1がちょうど1つずつ現れる)
  2. 区間行列 (行or列について1が連続した区間にしか現れない,ある区間の和がいくつ以上みたいな制約など)

です.これらに単位行列くっつけたのとかも整数になります.
実は下のケースは変数の和を別の変数で置き換えることで上のケースになり,上のケースは大体すぐに最短路・最大流・最小費用流に帰着できます.
また,整数解にならなくても少し書きたしてIPにすれば整数解を求めることができます.

あまり知られていないアルゴリズムの使用

世の中には爆速だけどあまり知られていないアルゴリズムがたくさん存在し,それらを用いることでTLEすると思われる解法が通ったりすることもよくあります.
例えば,Dinicのアルゴリズムは(結構有名ですが)かなり巨大なグラフでも高速に動作し,別の想定解の問題であっても通る可能性がありますし,他にも一般グラフの最大マッチング,平面グラフの完全マッチングの個数,マトロイド交差,高速な漸化式解法,最近きたまさが開発していた怪しい爆速行列累乗法などはジャッジが知らなかったり,知っていても実装が大変だからという理由で見逃してしまう可能性があります.

その他

世の中にはここに書かれていない嘘解法テクニックはたぶんいっぱいあります.
様々な嘘解法を試し,嘘解法力を磨いて行きましょう!
おしまい

ICFP Programming Contest 2011

日本開催ということで今年は初めて大規模なチームを組んで本気参加
チーム名は"Unagi: The Gathering"で,チームメンバーは
自分,秋葉,いるーん,いもす,hos先生,tos先生
競技プログラミングに最適化された6人

結果は多分今ひとつな感じぽいけど,問題も自分が過去に参加した中では一番面白かったし,初めてのチーム戦も非常に楽しかった.

一日目

お昼

大学の授業出ながらルールを読む.
どうやらカードゲームのAIを作るらしい.
SKとか出てきてよくわからんのでとりあえず「β 簡約! λカ娘」を読んで勉強することになった.
なんかtwitterで他のチームの人たちが進んでる雰囲気を出していたのでとりあえずブラフでてきとーな発言をしておいた.

夕方

授業後秋葉家へ移動しつつ,妄想上の作戦を色々作った.
このころ作った作戦はあとになってみるとワロス過ぎた.
ゾンビゲーという言葉が聞こえてきたので,とりあえずブラフでputゲーという事にしておいた.


@imos,@ir5と合流して秋葉家へ着いた.
最強の GUI が完成していてテンションが上がる.
関数適用の回数が良く分からないので,decループを作って解析.
decループだと167しか効かないことがわかり,敵を倒すにはhelpループ→attack かーということになった.
とりあえず一体倒さないことにはゾンビゲーもできないので,まずは敵を一体倒すことから始めることになった.

メンバーで唯一関数型が得意な@toslunarが合流.
役割分担を決め,@iwiwiがC++でシミュレータを書いて,他の人は有用そうな関数を作成しておくことになった.
探索とかもしたいので,C++でnewして参照渡しだとメモリリークで死ぬから毎回コピー渡しすることになった.
(f x) (g y) の適用ができないと255番以外への攻撃すらできない…
SKを駆使することで,gがカードの場合はできるようになった.

(f x) (g y) = (S(K(f x))g)y

一般の場合はtos先生とhos先生に考えてもらうことにした.
用意されているインタプリタに打ち込む作業が修行だったのでundo機能とかステップ関数適用とか搭載したGUIでも作るかーと思ってJavaで作りはじめた.

二日目

深夜

パーサ部分は書き終わったので,秋葉さんと一緒にC++Javaでシミュレータを書いた.
とりあえずブラフでゾンビパウダーが完成したことにした.
いるーんにより相手の255をループdecするだけの最初のサブミットがされた.

シミュレータがゾンビ以外できた気分になったので寝た.

起きたら@hos_lyricが合流していた.
どうやら指数的に大きくなる関数があって,コピーを使っているC++版シミュレータが落ちるらしい.
C++オワコン感が漂ってきてhos先生がD言語でシミュレータの実装を始めた.
C++はコピーやめて参照にし,メモリ管理機能つけて,探索終了時に探索で使ったメモリを解放することにした.
自分はコンボデバッグ用にワンステップずつ関数適用する機能の実装をすることにした.
tos先生によりSK変換器がなぜかHaskellで実装されていて他の人の環境で動かなくて大変だった.

秋葉さんのシミュレータが完成していたので,動作チェックをした.
decループのダメージはltgと一致するのだが,helpループの回復量が一致しない…
C++Javaでは一致したのでどうやら我々の解釈が間違っているらしい
部分適用もカウントする解釈にしたら一致した.

夕方

昼飯食べに行って,そのままTCOに参加するため一度帰宅.
GUIとかイラネと思って,ltg互換のCUIにして満足した.
コンボ作ろうと思って色々考えたが,getループだと決められた場所からしか発動できないので不動点関数が欲しいなーと思い,SK版の不動点関数をググって調査.
普通の不動点関数だとcall by valueで動かないのでググッて見つけたcall by value用の普通のλ式YコンビネータをSKに変換すれば良いに違いないと思ってλ→SK変換器を実装し始める.
実装班の方はいもすがtos先生のSK変換器をC++に変換して秋葉さんのシミュレータとマージし,まともなAIが書けるようになったらしい.

tos先生も変換器を実装しているらしく,任せてTCOに備えて少し休憩

三日目

深夜

眠さでTCOが壊滅的だったが,とりあえず通過はできたのでよしとしてコンボ考えながら寝ることにした.
が,まともなコンボがいろいろできたのでwikiに書きこんでたら秋葉さんが早く来いというので秋葉家へ出発.

秋葉家へ到着.
helpループ→attackで敵を672ターンくらいで殲滅するAIが秋葉さんといるーんの実装班により作られていた.
相手の0付近を速攻で倒しに行くためのコンボを搭載してもらいつつ,ゾンビ用の関数を作ることにした.
ゾンビ用関数はIを受け取って発動するので,forループさせるためには別の関数をもう一つ送り込む必要があるなぁ…と思ったらcopyを使えば自分の場に用意するだけでよかった.
help i i をループさせれば,限界突破して殺せるので便利.
いつの間にかSK変換器が関数合成とかもできるようになっていたらしいが,すでにSK慣れしすぎて直接SK式書いた方が速かった.
66体を一気に殲滅できるゾンビパウダーが完成した.

昼〜夜

起きてゾンビパウダー実装してもらった.
面倒なので.shに直書きされたw
シミュレータは探索とかしなくてもnewしっぱなしだとメモリがヤバいらしく,C++オワコン感が非常に漂っていたが,秋葉さんがガベコレ実装するという激しいことをしていた.
いもすにより内部リーグが構築され,色んなAIを自動対戦させれるようになった.
相手より先に4発打てればほぼ殲滅できるので,hos先生とtos先生と一緒にゾンビパウダーのショートコーディングを開始した.
ゾンビ送り先はこちらから倒しやすい255にした方が便利で,255倒すのも01のHPを大きく犠牲にしてattackのみで倒すことにした.
01のHP減らすと敵のゾンビ対策にもなって一石二鳥.
最終的に123ターンで殲滅できるものが完成した.
hos先生によりincゲーということになったので,putマシンからput-incマシンに進化した.

四日目

深夜〜朝

色々な作戦が開発された.

  • 永続dec
    • 毎ターンdecを行えるコンボ
    • 敵が普通のreviveを必ず行って来る場合,敵の行動を完全に封じつつ,こちらは2ターンに一度自由行動ができるので確実に勝てる
  • dec-zombie
    • decとzombieを同一ターンで行うことにより敵の関数を消す
  • でこぼこ
    • help 2i (2i+1) ループによりでこぼこさせて敵のゾンビを防ぐ
    • 関数構築が遅すぎてゾンビに間に合わないorz
  • 撃墜
    • コピー版C++シミュレータが死んだ関数を作ることにより敵のシミュレータを倒す

速攻ゾンビで敵をほぼ殲滅したあと,中盤はダメージ可変の小ゾンビ,永続dec,dec-zombie,普通のdecを適切に行うという戦略に決まり,実装してもらうことにした.

中盤以降の戦略を実装前のはそんなに強くなくて,先の中盤戦略がどれくらい強いかもよく分からないので,強いチームはゾンビゲーだろうと推測し,対ゾンビハメAIも並列で作ってもらってどのくらいハマるは試してもらうことにした.

はめ殺しAI
  • 255を速攻で作る
  • 相手の0番を倒す
  • 相手が0をrevive→永続dec
    • 0番を必ずreviveするAIの場合,勝利確定
  • 相手がこっちの255を倒しにきた→永続revive
    • ゾンビを送るために255を必ずdecしに来るAIの場合,勝利確定

われわれのゾンビAIには余裕勝ちできるが,ゾンビを打たれる前に構築するには0番に永続reviveを設置する必要があり,0番使えないのは痛い,強いチームはハマらないだろうなどの理由により結局普通のゾンビで行くことになった.
中盤以降の戦略を実装したAIが提出されたが,結構負けるため,原因を考えることに.
序盤でのほぼ殲滅には成功し,その後reviveのスピードに追いつけずに,逆転されているという分析になったので,forループdecで敵を殲滅するショットガンを搭載してもらうことにした.
decは敵が死んでいてもエラーにならないのでとても便利.
撃墜は強いチームには効かないだろうということで,結局組み込まれなかったが,ひょっとすると結構効くのかも知れない…

最終的に提出したAI

  • まず最初に255を倒し,ダメージ6144の大ゾンビ発射機を設置(6144は255倒すのにも使用して再利用)
  • 大ゾンビで倒せる一番小さいインデックスに発射
    • 我々のゾンビは相当速そうなので,0付近を倒されてかつゾンビで上書きされない限り,敵をほぼ殲滅できるはず
  • 大ゾンビで倒せないなら一番関数の複雑度が高い場所を攻撃
    • すでに一度倒してreviveしてきたところの場合,永続decコンボを設置して攻撃
      • 重要なスロットが死んだら必ずreviveするというAIの場合,これが決まった瞬間勝利確定
    • HPが高い場合はダメージ可変の小ゾンビを飛ばして攻撃
    • 低くて十分複雑ならdec-zombieで消す
    • 全部のHPが低ければショットガンを設置して撃ち続ける
  • 0123のみrevive
    • もう少し守るべきだった

終了後

終了直前に,関数構築中にそのスロットが死んでもそのまま構築を続けるというバグが発覚したが時間中に治すことができなかった.
そのまま構築するとターンが無駄になるだけでなく,関数も消えてしまうので痛い.
他にも実はもう二箇所バグっていたらしく,それらを直すと関数消してしまわなくなり,結構強くなったぽい.

反省点

  • 初動が遅すぎ
    • 授業とかあって,実装開始時すでにスタートからすでに12時間以上たっていた
    • 序盤にいろいろ戦略妄想しても大抵役に立たないので,実装ゲーなシミュレータとかすぐに組み始めたほうがよい
  • 言語バラバラ
    • 言語の統一が全くされていなかったのも他の人の書いたコードが実行できなくて色々と大変だった
    • シミュレータは結局C++,Java,Dの3つも実装された
    • しかし,C++とかデバッグ無理ゲーなので来年からは非実装戦略専門要員として活躍することにしよう
  • デバッグ
    • 最後までずっと戦略の搭載をしていてテストする時間がなかった
    • チーム内対戦機能が搭載されたが,その棋譜を見て怪しい動作をしていないか分析する係を作ればよかったのか
  • チーム開発
    • そもそも3人以上のチームで協力して開発したことがなかった
    • 後半は実装班とコンボ班でお互いのやっていることがさっぱり分からなくなってしまった←バグの原因
    • もっと知識の共有をすればよい?

TopCoder Open 2010

ラソンで奇跡が起きて優勝しちゃった!


Marathon Final

今年から24hになったので大変だった・・・

問題概要

崩壊する洞窟からコインを回収するゲームのAIを作成せよ
通路は単位時間で1歩移動でき,壁を壊すのにはT時間かかる
通路上にはところどころにコインが落ちていてその上に移動すると回収できる
崩壊は毎時間一定の確率で起こり,崩壊が起こると周囲のDマスが一気に壁に変わる
コインが埋もれると消滅してしまう
運悪く,崩壊に巻き込まれた場合はゲームオーバー(0点)
最初はマップの左端にいて,左端か右端にある出口に到達すると脱出成功となり,回収したコインの個数に比例した点数が入る
マップの難易度により重み付けがされ,各マップに対するスコアの和で順位が決まる

自分の解法

基本的にはダイクストラして一番近いコインを見つけ,てきとーなタイミングで帰還するだけ
マップがそこそこ広いが,目的地に到着したときと,目的地までのパス上で崩壊が起こったときだけ計算すれば十分な上,一番近いコインは結構すぐ見つかるので,なんとかなる
あまり遠くに行ってしまうと帰れなくなるので,コインを取って帰還する間に埋もれて死んじゃう確率をてきとーに見積もって,取りに行ったほうがよさそうな位置にあるコインのうち,一番近いのを狙うようにした
どれも取りに行かない方がいいと判定されたら帰還する
帰還するのにかかる時間の計算は,一番近いコイン見つけるのより時間がかかるので,1000ターンに一回だけ計算しなおすことにした
ビジュアライザ眺めてたら,たったひとつ取り残したコインを回収しに行って,そのせいで脱出が遅れて死んでしまうことが時々あったので,コインの周りに他のコインがどのくらいあるかも考慮した(コインがいっぱいあるのでマンハッタン距離で代用したが,意外とBFSでも速かったらしい)

結果

システムテスト前は2位だったけど,中には1ケースで0.5くらい取れるのとかがあるため,そういうのでたまたま運悪く死んでたりする可能性があるからあんまりあてにならないなーと思っていたが,意外とシステムテストで他の人達が点数伸びなくて,なんと1位になってしまった!

Algorithm Semi Final

ラソン終了後3時間くらい睡眠をとってから挑んだ

250

やるだけな感じの問題
なんかバグるーと思ったら,スワップ
int[] tmp = crt; crt = next; next = crt;
とか書いてたorz (最後がcrt→tmpが正しい)

500

品物集合を二つに分けて,平均価格の和を最小化する問題
寝不足+オンサイト補正(オンサイトだし激ムズに違いない)により解けなかったorz
冷静に考えたら簡単だったし…もうだめぽorz

1000

サイズ制約がどう見ても二つに分けてくださいと言っていたので二つに分けてRangeTreeだー!と思って組んでたがどっかバグってサンプル通らずorz
てか冷静に考えてBITでいいし…なにやってんの俺orz

Challenge

ACRushの250開いたらなんか7重ループが見え,それぞれ最大50回る感じだったのでエェ…と思って撃墜しそうになったが,冷静になって考えたら全体で50C7で間に合ってることに気づいた
他のは怪しいのすらなかった

System Test

8位orz (7位までならWildCard進出)
オンサイトはあまり得意じゃないがさすがにこれはひどいorz

感想

ラソンは夕飯食べたくらい(10h経過くらい)で体力の限界を感じ,そこからは定期的に横になって休んでた
てか,普段のマラソンもコーディングとかあまりせずに,ベッドで転がって方針考えてるのでこういうスタイルで最初からやったほうがいい気がした
アルゴリズム敗退して自分の出るのが全部終わった後は,カジノに入れる年齢になった+超アクティブな社員(大学のクラスメイト)を連れていったため例年よりいっぱい観光して,すごいハードスケジュールだったけどその分面白かった
ラスベガス4泊のはずが2回しか寝てないし…
社員が英語ペラペラでカッコ良かったので自分もいい加減英語何とかしたいなぁと思ったがなんともならないorz
あと,来年はダブル優勝目指す!(無理ゲー)

全探索+二分探索

前回のSRMでLayCurseさんの900の解法を見て思い出したので解説。

次のように、二分探索の中で全探索をしているようなプログラムを考える。

int lb = 0, ub = INF;
while (ub - lb > 1) { // 二分探索
	int mid = (lb + ub) / 2;
	boolean tmp = false;
	for (State s : allStates) { // 全探索
		if (check(s, mid)) tmp = true;
	}
	if (tmp) ub = mid;
	else lb = mid;
}
return ub;

このプログラムを実行すると、check(s, r)を満たすようなsが存在する最小のrが求まる。

このプログラムの計算量は、状態数N=|allStates|、二分探索の反復回数をR、checkの計算量をKとすると、O(NRK)となる。

ここで、二分探索と全探索の順番を入れ替えてみると次のようになる。

int r = INF;
for (State s : allStates) { // 全探索
	int lb = 0, ub = INF;
	while (ub - lb > 1) { // 二分探索
		int mid = (lb + ub) / 2;
		if (check(s, mid)) ub = mid;
		else lb = mid;
	}
	r = min(r, ub);
}
return r;

こうやって書いてみると、二分探索によって求まった最小値ubがそれまでの最小値rを更新するためには、少なくともcheck(s, r - 1)はtrueでないといけないので、次のような枝刈りを入れることができることに気がつく。

int r = INF;
for (State s : allStates) { // 全探索
	if (!check(s, r - 1)) continue; // 枝刈り
	int lb = 0, ub = INF;
	while (ub - lb > 1) { // 二分探索
		int mid = (lb + ub) / 2;
		if (check(s, mid)) ub = mid;
		else lb = mid;
	}
	r = min(r, ub);
}
return r;

これで、時々二分探索が不要になるので高速になるような気がする。
実際、この枝刈りをいれた場合の計算量は見積もることが可能で、1/k番目の状態において、それまでの最適解を更新できる確率は、探索順がランダムならば期待値的に1/kであるので、二分探索が実行される回数の期待値は、1+1/2+1/3+...+1/N=O(logN)となる。
したがって全体の計算量はO(NK+RKlogN)となり、Nが大きければ二分探索の反復回数がほぼ無視できるようになる。

というわけで、二分探索中の全探索は外に出して枝刈りいれると高速になるよっていう話でした。

で、SRM481の900にもどると、全探索してマッチングで判定する場合、N=15C7=6435、K=16^3、R=20くらいなので、全部掛けると危なそうだが、枝刈り入れれば余裕で間に合うと判断できる。

プログラミングコンテストチャレンジブック

id:iwiwiとkita_masaとの3人で、一年ほど前からのんびり書いていた本がついに発売されるらしいです。
http://book.mycom.co.jp/book/978-4-8399-3199-5/978-4-8399-3199-5.shtml
ちょい高めですが、自分たちがプログラミングコンテストで得た知識、ノウハウが詰まってるので、ぜひどうぞー!

TCO10 Marathon Round 3

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にも結構含まれていそうだった

おまけ

デバッグなどの目的でグラフビジュアライザを作成した
大量の頂点を平面に描画すると辺が重なってワケが分からなくなるので、三次元で配置して、くるくる回せるようにした
頂点数が多くなっても全体の構造も細かい部分の接続関係もちゃんとわかっていい感じ

せっかくなので公開
http://ow.ly/2ll3X
ぱすわーどはてきと
使い方
ダブルクリックで起動
始点 終点 (辺のラベル)
を一行に1辺ずつ入力
まともな配置になるまでShowボタンを連打
ドラッグで回転
頂点を右クリックでその点に接続する辺のみを表示