てきとーな日記

2011-12-18

[]嘘解法のススメ 01:36

(この記事は 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のアルゴリズムは(結構有名ですが)かなり巨大なグラフでも高速に動作し,別の想定解の問題であっても通る可能性がありますし,他にも一般グラフの最大マッチング,平面グラフの完全マッチングの個数,マトロイド交差,高速な漸化式解法,最近きたまさが開発していた怪しい爆速行列累乗法などはジャッジが知らなかったり,知っていても実装が大変だからという理由で見逃してしまう可能性があります.

その他

世の中にはここに書かれていない嘘解法テクニックはたぶんいっぱいあります.

様々な嘘解法を試し,嘘解法力を磨いて行きましょう!

おしまい