今までの自分のライブラリを公開します 2014
https://db.tt/KixudqAX
ライセンスはCC0です。何でも自由に使って・コピペ・改変・再配布してよいです。これを使用した場合のいかなることにも責任を持ちません。
'#'で始まるファイルは未検証、'!'で始まるファイルは検証済みであることを表していましたが、あんまり一貫していません。それがついていないファイルもあります。サブフォルダに入っているものが別に特別ということはありません。
ライブラリまとめ.txtに自分と他の人のライブラリをまとめてあります。このファイルが一番重要かもしれません。
去年のものと特に重複は除いていません。更新されているファイルもあります。
ちょっとしない解き方メモ色々 part2
フィボナッチ数の小ささ
fib(n)は指数オーダーで結構大きいが、2^nよりは全然小さい。
"SRM 451 DIV1 Hard BrickPuzzle"は列DPを特定の形のブロックでするもの。ブロックの形が、下側が絶対2つ単位で隣接しているため、そのような形の状態しか覚えなくてよい。このような状態の数はfib(n+1)になる(漸化式を見ればわかる)。2^nでは大きすぎるが、fib(n+1)はギリギリ小さいため解ける。実際にはMLEにならないために状態にインデックスを付ける必要がある。
コストで直接辞書順最小を求める
part1で紹介した"辞書順ペアをコストにする"のさらなる一般化。大事なのは、計算量は漸近的には変わらない(たぶん)が、ビット並列化のようなことで高速化できるということ。
"SRM 457 DIV1 Hard TheSquareDivOne"では普通にやってはギリギリ時間に間に合わない(実際には定数倍高速化を頑張れば通る)が、これを利用することで余裕を持って通すことができる。自分は実装に固定長の多倍長整数のようなものを使ったが、「先頭から整数に収まる範囲だけやり、それを固定して次の範囲へ」というように普通の辞書順greedyとのハイブリッドにやることでもできる。
また、自作の問題"最初のコンテスト - E 辞書順最大の経路履歴"(問題文)でも同じようなテクニックが適用出来る。この場合はダイクストラ法の重みとして多倍長整数を採用する。なお、その問題はunion-find-deleteのようなもので解けるように思えるが(当時知らなかったし、今でもわかってない)…どうだろうか。
整数計画を分岐限定法で?
ヒューリスティックとかあまり実装しなくても、問題がうまくLPとフィットすれば解けるかも。
LPのboundが効率的に効くような問題では十分解けうる。変数の数が多かったりすると、ナイーブな実装ではMLEとなってしまうことが多いかもしれないので、変数の範囲はまあまああるが変数の数が少ないような問題がいいかもしれない。
"SRM 488 DIV1 Hard TheBoringGameDivOne"では何のヒューリスティクスも無しのプレーンの分岐限定法でも1ケース以外は通る。さらに、変数を割り当てる前にその範囲をLPで制限するようにしたら(これは何と呼ばれているのかわからない)全ケース通った。この問題は変数の数が9と少ない。また範囲も0〜1000と比較的少ない。しかし当然1000^9はできないわけだが、実際に解けた。
もっと実装すれば、もっと色々な問題が解けるかもしれない。解ける率を考えるとライブラリとしてそれなりのものを実装するのはありかもしれない。
浮動小数点数重みの最短路は誤差に注意
Dijkstra'sやFSPAなどは特に注意。誤差によって負サイクルができることがあり、負サイクルがあると無限ループしてしまうからだ。
最短路はそのままの形だけでなく、様々なアルゴリズムのサブルーチンとしても用いられることに注意する。特に多いのが最小費用流、特に重み付き2部マッチングである。
最小費用流のPrimal-Dualではポテンシャルを加減算する関係上誤差が大きくなりやすいように思える。
例として、"SRM 491 DIV1 Hard FoxCardGame"は浮動小数点数重み付き2部マッチングを使う。実際自分はこの無限ループのせいで1回Failしてしまった。
最小費用流のPrimal-Dualの場合、
Weight d = dist[i] + edgeCost + potential[i] - potential[j];
if(d < dist[j]) ...
のようになると思うが、これに1行足す。
Weight d = dist[i] + edgeCost + potential[i] - potential[j]; if(d < dist[i]) d = dist[i]; //* if(d < dist[j]) ...
こうすることで解決できる。
Dijkstra'sでなく負辺も存在する場合はEPSを適切に使って比較すればよい。
サイズごとの総和で包除原理
包除原理の±はサイズによって決まる。つまり同じサイズの集合は全て同じ符号。
そのため、あるサイズの集合の総和を求めることができるなら包除原理ができる。
"SRM 498 DIV1 Hard FoxJumping"で使っている。この問題の場合はサイズごとの総和はsubset-sum数え上げのDPと二項係数などで求める。
包除原理といえば2^nかかると思ってnが大きい時できなそうだが、このようなやり方もあるということ。
Dijkstra's風で、単純な足し算以外の重み
Dijkstra'sは辺の重みを距離→距離の関数と考えたとき、その関数が広義単調増加なら正当(たぶん)。証明はしてないけどなんとなくそうっぽい?
普通の重みつき辺は重みが非負なら足し算関数はそれを満たすので正当であるといえる。
よくあるのは「ある時刻まで待つ」という重み。できるだけ早く行ったほうがいいのがわかる。
"SRM 479 DIV1 Medium TheAirTripDivOne"は周期的な区間を待つような形。これも明らかに広義単調増加なのでいけるといえる。
"SRM 462 DIV1 Hard WarTransportation"はmaxを取る。これも同様に正当性がいえる。
常識とか発想とか雑多な
- 多項係数は二項係数のかけあわせになる。(n!/x_1!/x_2!/... = C(n,{x_1,x_2,...}) = C(n-��_{j=1..i-1}x_j,x_i))
- 隣同士に限定してもswapが自由な回数できるなら任意の順列を作れる(たぶんどんなswapなら任意の順列ができるか、とか考えられるのかな?知らないけど)
- longest common prefix → 辞書順ソートする。"SRM 496 DIV1 Hard YetAnotherHamiltonianPath"とか"SRM 330 DIV1 Medium PrefixFreeSubsets"とか。
- (rank(s)+k)番目を辞書順で求めたくて、rank(s)がlong longに入りきらないほど大きい時はsandwich(s≦x≦tとなるxの数)で数を数えるルーチンを作れればいける。"SRM 467 DIV1 Hard NextHomogeneousStrings"。ただ多倍長でもいけそうだが。
- 連結成分の集合をsubsetとして数えるときには(ab)(cd)と(abcd)を重複して数えないように、連結成分が区切られる時に最低でも1つスペースを開けないといけないようにすればいい。"SRM 421 DIV1 Hard "TeamManagement"は木上。
- greedyは分岐がある時に「片方の選択肢だったら絶対良い解になる」という優先順位をいかにつけられるかがポイント。辞書順greedyはその点自明。"SRM 429 DIV1 Hard SpecificPolyominoCovering"。
- 平面上の矩形とかのunionの面積を求めるのはline-sweep的にやればΘ(n log n)とかでできる。"SRM 441 DIV1 Hard PaperAndPaint"。
- 行列の足し算とか。それでバイナリ法とか。"SRM 444 DIV1 Hard AvoidFour"。この問題の解法頭良くて好き。
- modが小さいとき、modをとった後の値ごとに考える(それが同じなら同じなので)。"SRM DIV1 Hard IncreasingNumber"。
- できるだけ対角線上いようとするようなメモ化再帰でO(n)。"SRM 454 DIV1 Hard MegaSum"。
- 2部マッチングで絶対使わないといけない頂点があるときは、それ以外の頂点を(k-そのような頂点数)の容量の辺に通すようにして制限する(それが負になったら絶対無理)。2部マッチング以外にも一般に同じような考え「重要なものを絶対使う <-> 重要でない物の数を制限する」が使えるだろう。"SRM 459 DIV1 Hard TheContest"。
- 常に前の状態に戻れて、その「前の状態」という状態遷移にサイクルが無いとわかるとき、森である。"SRM 463 DIV1 Hard RabbitPuzzle"。この問題のこの状態が森で、さらに無限で一様であるから区別する状態数が少ないという議論はとても面白かった。
- (��_{i=1}^n x_i / n)以下の値x_jが必ず存在する。"SRM 468 DIV1 Hard MallSecurity"。
- FPTの自明でないアルゴリズムであっても、DPなら柔軟性がある。"SRM 470 DIV1 Hard BuildingRoads"の解法は、steiner treeのDreyfus-Wagner algorithmの変形であるとみなせる。
- "SRM 477 DIV1 Hard KingdomTour"のgreedyな、minimum cost flowのPrimal Dualにも似た謎アルゴリズム。practice roomの自分の解答(自分はzhuojie氏のものを参考にしたが、誰が最初に書いたかは知らない)参考。
- Hyperplane separation theorem。2つの凸多角形が交差しないとき、それらを分割する直線が存在する(さらに多次元でも)。この直線はn^2試せば良いので、分割のし方もO(n^2)となる。"SRM 486 DIV1 Hard BatmanAndRobin"の肝。
- グリッド上で各列で区間を決めるとき、それを領域として連結にするために区間の左と右を伸縮する順番を適切に決める。"SRM DIV1 Hard AmoebaDivOne"で綺麗に書けた。伸縮をインクリメンタルにやるDPで、縮める方を最初に縮めきってからもう片方をやれば、縮める方はもう片方より左右には縮まないので必ず連結にできるというテク。自分で思いついて、とても面白いと思った。
ちょっとしない解き方メモ色々 part1
SRM400代のHardで使ったものを見てみる。最初は全部記事書こうかと思ったがめんどくさくてやめた。
桁落ち誤差回避
ほとんど等しい2つの数を引き算すると、有効桁数が減少する。
式変形をして引き算をなくしたりする必要がある。
SRM 400 DIV1 Hard CollectingBonusesではさらにlog1p関数を使ったりする。
凸多角形は上部と下部に分割できる
左・右でも同じ。
それぞれの折れ線がy座標の関数と見た時に凸・凹となることが重要。
SRM 401 DIV1 Hard NCoolでは、それを利用して多角形内の点を列挙している。
"SRM 493 DIV1 Hard AmoebaDivOne"でも凸多角形を生成するDPでこの性質を大いに使っている。
集合を求める時に順番が関係ないことを利用して、フラグで持たずにそのフラグが立っている数で持ったりする
一般的なテクニック。あえて言及するほどでもないかもしれない。
数値の辞書順最小を求めたい時には必ず桁数が単調なことを利用して数値が終わったかどうかをΘ(数値の数)の状態で持てる。SRM 403 DIV1 Hard TheLuckySumで言っているが、実際にはこの問題では桁ごとにも数値の順番を入れ替えられるので、辞書順最小ということはあまり関係ない。
変数を1つ以外固定して近づけてくサーチ
"SRM 405 DIV1 Hard ReasonableOdds"で用いられる。
一般にベクトル引数の最適化の手法としてあるものだと思う。名前知らない。
��_{x=0}^[n-1} floor((a*x+b)/m) をO(log m)で
やばいアルゴリズム。
SRM 410 DIV1 Hard WifiPlanetの最重要部分。
応用は多そう。実際に全く別の問題SRM 406 DIV1 Hard ShortPathsでも使えて、漸近的な計算量を減らすことが出来る(と思う)。
凸とは限らない多角形内の何かを符号付き面積みたいに
SRM 410 DIV1 Hard WifiPlanetの1つ目のテクニック。
構造の差分上でのk番目クエリに対応しているデータ構造なら多角形内のk番目クエリにも使える気がする。
平面で領域が2色に分かれているとき、その両方のそれぞれを頂点として隣接を辺とすると木になる(?)
"SRM 411 DIV1 Hard MinimumTours"で使われる。
なんというか自明でないと思う。実際自分は解法を見た時驚いた。上の記述で合っているかどうかもわからない。
もし上の記述や理解が合っているなら応用性はかなりあると思う。
有理数上でもLCM,GCDが定義できる
"SRM 414 DIV1 Hard KPlanetaryAlignment"の肝。
"lcm(x/y,z/w) = lcm(x,z)/gcd(y,w)"。
整数上と同じく、周期を考える時に用いることが出来る。
重み付き数え上げのアルゴリズムで確率を求める(?)
"SRM 425 DIV1 Hard RoadsOfKingdom"の別解としてやばいアルゴリズムが存在する。
この問題は辺が存在する確率が与えられる時、全域木ができる確率を求める。
全域木はMatrix-tree theoremで数え上げられる。また、多重辺と考えれば重み付きバージョンもできる。
しかしそのアルゴリズムで確率が求められるというのだ。
辺がある確率をpとしたとき、重みをp/(1-p)に設定する。それで求めた後、(1-p)の総乗をかける。するとなんと確率が出るというのだ!
p=1の場合が0割りだが、特別扱いして連結成分を1つの頂点として適切にサイクルをチェックしたりしてもよいし、p=1-1e-10とするという方法もある。
なんでこれで求められるのかわかってないが、もしこれが一般的に適用できるのであれば応用は広がる。
determinantに限っても例えば有向木とかオイラー路とか平面グラフの完全マッチングなどがあるが…"もし"適用できたら面白いなあ。
Warshall-Floydで不等式を解く
うまくできる。あんまりわかってない。
"SRM 426 DIV1 Hard LongStraightRoad"や、最近では"SRM 586 DIV1 Medium History"で出されている。
SRM586ではみんな解いてるようなので、いまや常識らしい。
分割数の小ささ
分割数は指数オーダーだが、小さな方ではそれなりに小さい。だいたい(13^√n)/7n 程度。
「x個を順番関係なくいくつかに分割する」が分割数。
"SRM 427 DIV1 Hard PSequence"ではDPの状態として出た。一見制約が30で階乗オーダー・指数オーダーの解法は無理そうだが、実際の数は関係なく前の数と等しいかどうかだけを持てばいいことを利用すると分割数で抑えられて(Σ_{i=0}^30 p(i) = 28629)なので十分いける。
辞書順ペアをコストにする
"SRM 433 DIV1 Hard BarbarianInvasion"で最小カットとして出た。
最近では"Maximum-Cup 2013 - F 3人の騎士と1匹の犬"で重みつき二部マッチングの最小費用流として出た。
巡回する <-> 文字列としての2乗を考える
極めて典型的。
- "SRM 436 DIV1 Hard CircularShifts"
- SRM 286 DIV1 Hard InfiniteSoup
長くなったので分割。part2