2012-03-29
■[Algorithm]指数時間アルゴリズム
指数時間アルゴリズムというのは，NP困難問題を頑張って指数時間かけて解くアルゴリズムのことで，できるだけ指数の底の小さいアルゴリズムを開発することが目指されています．
コンテスト界では部分和問題の半分全列挙による2^(n/2)時間アルゴリズムなどが特に有名だと思います．
この分野は近年盛んに研究され始め，自分も大学でこの分野を中心に研究をしています．
今回，情報オリンピック春合宿講義とPFIセミナーで発表する機会があったので，この分野の基礎的な手法から最先端の手法までをまとめてみました．
- 指数時間アルゴリズム入門@情報オリンピック春合宿講義
- 指数時間アルゴリズムの最先端(キャンセリング)@PFIセミナー
シンプルなアルゴリズムが多く，厳密解＆計算量保証あり，という点で非常にコンテスト向けのジャンルだと思います．
これをマスターすれば，TopCoderで頂点数50の最大独立集合が出ても絶対に間に合うプログラムを書くことができるようになったりします．
また，キャンセリングはとても面白いのでみんなで面白いアルゴリズムを考えて半分全列挙のように流行って欲しいです．
2011-12-18
■[Algorithm]嘘解法のススメ
（この記事は 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を回避できたりします．
また幾何の問題においては３点が一直線上にあったり，同じ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で整数解が求まるような係数行列の代表的な例は覚えておくとよいでしょう．
よくあるのは，
- 有向グラフの接続行列 (つまり，各行or列に係数1と-1がちょうど１つずつ現れる)
- 区間行列 (行or列について1が連続した区間にしか現れない，ある区間の和がいくつ以上みたいな制約など)
です．これらに単位行列くっつけたのとかも整数になります．
実は下のケースは変数の和を別の変数で置き換えることで上のケースになり，上のケースは大体すぐに最短路・最大流・最小費用流に帰着できます．
また，整数解にならなくても少し書きたしてIPにすれば整数解を求めることができます．
あまり知られていないアルゴリズムの使用
世の中には爆速だけどあまり知られていないアルゴリズムがたくさん存在し，それらを用いることでTLEすると思われる解法が通ったりすることもよくあります．
例えば，Dinicのアルゴリズムは(結構有名ですが)かなり巨大なグラフでも高速に動作し，別の想定解の問題であっても通る可能性がありますし，他にも一般グラフの最大マッチング，平面グラフの完全マッチングの個数，マトロイド交差，高速な漸化式解法，最近きたまさが開発していた怪しい爆速行列累乗法などはジャッジが知らなかったり，知っていても実装が大変だからという理由で見逃してしまう可能性があります．
その他
世の中にはここに書かれていない嘘解法テクニックはたぶんいっぱいあります．
様々な嘘解法を試し，嘘解法力を磨いて行きましょう！
おしまい
2010-09-10
■[Algorithm]全探索+二分探索
前回の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くらいなので、全部掛けると危なそうだが、枝刈り入れれば余裕で間に合うと判断できる。
2010-01-27
■[Algorithm] 空間凸包
以前O(n log n)の空間凸包を組もうとして挫折してずっと放置してたが、こないだの冬コンテストで出たのでそこそこ高速で楽な実装を考えてみた。
とりあえず、４点が同じ平面上に乗ってるのはないとして、
1. 点を徐々に追加していく
2. 凸包の各面が見えるか判定
3. 見える面を取り除き、見える面と見えない面の境界と追加する点を結ぶ面を新たに追加
っていうのをやるとO(n^2)になる。
見える面と見えない面の境界を探すのに、以前は面の隣接関係を保持してたけど、そうすると新たに追加したときに隣接関係修正するのとかが意外とめんどくさい。
よく考えたら、辺i->jをこの向きに含むような面は一つしかないので、O(n^2)でいいならてきとーに二次元配列に記憶しておけばよくて、面abcに対しては、辺ba,cb,acを含むような面を調べれば良い。
こんな感じで実装してみたらまともなコード長になったのでこれならICPCでも使えそう。
int[][] vs = new int[n][n]; //vs[i][j]=辺i->jをこの向きに含む三角形が、まだ調べてない:0、残った:-1、取り除かれた:1 List<int[]> crt = new ArrayList<int[]>(); crt.add(new int[]{0, 1, 2}); crt.add(new int[]{2, 1, 0}); for (int i = 3; i < n; i++) { List<int[]> next = new ArrayList<int[]>(); for (int[] t : crt) { int v = ps[t[1]].sub(ps[t[0]]).det(ps[t[2]].sub(ps[t[0]])).dot(ps[i].sub(ps[t[0]])) < 0 ? -1 : 1; if (v < 0) next.add(t); for (int j = 0; j < 3; j++) { if (vs[t[(j + 1) % 3]][t[j]] == 0) { vs[t[j]][t[(j + 1) % 3]] = v; } else { if (vs[t[(j + 1) % 3]][t[j]] != v) { if (v > 0) next.add(new int[]{t[j], t[(j + 1) % 3], i}); else next.add(new int[]{t[(j + 1) % 3], t[j], i}); } vs[t[(j + 1) % 3]][t[j]] = 0; } } } crt = next; }
ちなみに、見えるかどうかの判定を衝突グラフを作って行い、点の追加をランダム順にすると期待値的にO(n log n)になるらしい。
点pから面abcが見えて面dbaが見えない時、新たに面pabができ、面abcが取り除かれる。
この時、面dbaから見える点の集合は変化せず、面pabから見える点は面abcもしくは面dbaのどちらかから見えるのでこれらだけを調べれば良い。
(計算量の解析の部分ちゃんと理解してないので、ほんとにコレだけでいいのかは知らない)
実はO(n log n)のもがんばれば意外と短く出来るのかなー？？
あと、WorldFinal頑張ってください！！