Hatena::ブログ(Diary)

komiyamの日記

2014-12-07

マラソンの感想

Competitive Programming Advent Calendar 2014の記事です。

自分はかつてTopCoder Marathon Matchに参加していた時期があったのですが、今回はその感想を書きます。

続きを読む

2013-12-02

Segment Treeをちょっと高速化したい

Competitive Programming Advent Calendar Div2013の12月2日の分です。

ときどき脱線しながらも主にsegment treeの再帰展開について書こうと思います。

はじめに

segment treeの資料といえば蟻本やiwiさんのスライドが非常に分かりやすくお勧めです(定番中の定番ですね)。この資料で使われている図をイメージしながら読んでください。同じくiwiさんの平衡二分探索木のスライドもぜひ目を通しておきましょう。

これら以外にもsegment treeについてまとめたブログ記事などは検索すれば色々引っかかります。去年や今年のAdvent Calendarでも初学者向けの記事があるようです。初学者向けの詳しい解説はそちらをご覧ください。

私なりにsegment treeの動作原理を短くまとめると、「区間をたかだかO(log n)個の交わらない区間に分割する」で終わりです。余談ですが私の好きなデータ構造であるsparse tableの動作原理は「区間をたかだか定数個の交わりうる区間に分割する」とsegment treeとの対比が見られます。

定数倍最適化について

ところで、プログラミングコンテストというのはとにかく通れば正義です。逆もしかりで、「私はO(n)解法を考案しました」だけではスコアは増えません。それを実装して、TLEせずに通さなければ順位は上がらないのがプログラミングコンテストの面白さの一つだと思っています。

TLEせずに通すにあたって定数倍というのは結構大事で、もしこれを無視してよいのであればdoubleなんてfloat並の化石扱いで__float128使うし、座標圧縮でmap使ったらTLEしたとかよくあるし、逆では4重ループだけど係数1/24が乗るから行けた!とか4*10^9だから愚直は無理だなーと思ったら通ったとかあったりします。また想定解は累積和だけどbinary indexed treeでも通ったとか、しゃくとりするところを二分探索でlogがかかったけど行けたとかは頻繁にありますね。

私はあまり詳しく無いのですが、どうも計算時間で支配的になりがちなのはメモリアクセスだという話です。この問題とかは有名なようで。キャッシュに乗りやすくするようデータをコンパクトに保つことなども大事らしいです。平方分割がsegment treeに比べて思ったより遅くないのもメモリアクセスの効率の差なんですかね。

segment treeに話を戻しましょう。先ほど動作原理を「区間をたかだかO(log n)個の交わらない区間に分割する」と書きましたがこれだけなら平衡二分探索木を使って列を扱うのにもあてはまります。binary indexed treeも同じです。実際にこれらのデータ構造は諸々の処理に必要な計算量はどれも同じです。初期化O(n)、空間O(n)、点クエリや区間クエリO(log n)など。大雑把に言って、平衡二分探索木からinsert,delete,split,mergeなどができないよう制限したのがsegment treeで、segment treeの区間[L,R)に対するクエリをL=0に制限したのがbinary indexed treeだと見なすことができます。機能を制限した分だけ実装や速度やメモリの面で利点が得られるようになっています。

binary indexed tree

binary indexed treeはsegment treeから無駄なノードを削ったデータ構造です。その名の通り、二進表示と配列の番号が絶妙に対応付けられています。

計算量はO(log n)ですが、[0,n)というクエリに対して毎回コンスタントにlog n回必要ということもなく、二進表現で0が連続する箇所だとか1が連続する箇所だとかをまとめてスキップしたり、普通に書けば再帰を使わなくて済んだり、配列へのアクセスが昇順または降順で効率がよいことなどからかなり高速に処理できます。

元のデータと同じ長さの配列で済む(サイズを無理やり2のべきにする必要すら無い)というのが驚異的で、次元の上昇にも強いデータ構造です。

segment tree

コンテストでの使用頻度が高いsegment treeですが、当面は動的でないものを考えます。また、簡単のため扱うデータのサイズ(=:N)を2のべきにしておきます。

segment treeでは扱う木の形を完全二分木に限定しています。これにより各ノードについて配列インデックスが非常に沢山の情報を持つことになります。

特に子ノードや親ノードへのリンクを陽に持たなくてよいというのは空間的にかなりおいしいです。元データの2倍しかメモリ使わないというのは考えてみると結構すごい。

蟻本での実装とは異なりますが、配列を1-indexedで扱うことにします。配列の長さは2*Nで、0番目は使いません。そうすることで色々綺麗に扱えます。

iの親のindexi/2
iの子のindexi*2+0, i*2+1
iの兄弟(sibling)i^1
iの深さ(depth)log_2 iの整数部分
iの区間幅(width)N/highest(i)
iの区間の左端(i-highest(i))*width(i)
左からx番目の葉x+N

ここでhighest(i)はJavaでいうところのInteger.highestOneBit(i)のことでiを越えない最大の2べきで書ける数のことです。ビット演算を用いてO(log log n)で求めても良いしO(n)の前処理で求めておいてもよいです。

また、1,2,...,2*N-1がトポロジカル順序になっている点も美味しくつまり初期化は単純にループを後ろから回せば良いことになります。例えばRMQの場合

for(int i=0; i<N; ++i) minimum[i+N] = A[i];
for(int i=N-1; i>0; --i) minimum[i] = min(minimum[i*2+0], minimum[i*2+1]);

初期化できます。

xを含む区間のインデックスを下から順に列挙するには次の様に葉から親を辿ればよいです。

for (int i=x+N; i>0; i>>=1) {
    //iが対応するインデックス
}

[L,R)を分解した区間のインデックスを列挙するにはこう書きます。

L += N;
R += N;
for (;L<R; L>>=1, R>>=1) {
    if(R&1) --R; //--Rが対応するインデックス
    if(L&1) L++; //L++が対応するインデックス
}

実装量も再帰で書くより少なくなってよいですね。[L,R)を分解した区間は互いに交わらないのでどういう順番で列挙してもよいのですが、この方法ではインデックスの大きい順に列挙されていることも分かります。

何をやっているのかというと、[L,R)に対応するノードの山を真ん中でぶったぎって山の左側と右側に分けてごちゃごちゃやっているだけです。binary indexed treeの様に、i&(-i)で最右ビットを取り出せることを利用して連続する末尾の0をスキップする実装もあります。(上の実装と比べて早くなっているのかどうかはよく分かりません)

遅延型segment tree

例えば区間への更新や加算クエリと区間への求値クエリを両方サポートする必要がある時、値の伝播を遅延させるテクニックを用いるとうまくいくことがあります。この技法を遅延更新とか遅延評価とか遅延伝播とか呼ぶようです。英語だとLazy Propagationという表現をよく見かける気がします。実装の関数名ではpushとかpush_upとかpush_downとかupdateとかpropagateとかmergeとかlazyなどが使われているようでした。具体的に何ができるかといえば、例えば区間更新と区間加算と区間最小値と区間和を対数時間で処理できる列などが扱えます。遅延を使わなければならない、ということはあまりないのですが結構応用範囲が広いので多くの人に使われている印象を受けます。

この技法についての詳細はここでは触れませんが、これも再帰を展開をしてみたいところです。

上でやったように簡単に書くことは難しいです。[L,R)を分解した区間を取り出すだけではダメで、そのノードに必要な情報を伝播するために直上のノードも取り出す必要があるからです。とはいえ

  • あるノードを扱うとき、親ノードはpropagate済にしておく。
  • ノード以下に触るときは事前にpropagateしておく。
  • ノードが完全な状態になった後に子ノードの情報をmergeする。

くらいに気をつけておけば大丈夫です。またpropagateやmergeは順序さえ間違わなければやっといて損をすることはありません。

と、ここまで書いといて申し訳ないんですが公開しようとしていたコードにバグがありました。基本的な考え方としては共通する部分は上から下ってそれから山を左右に分けて左側で下って上って、右側で下って一番上まで上って…という感じでうまく行くはずなんですが何かがバグっているようです。近日中にバグとって追記しておきます。一番肝心な部分が公開できずに申し訳ないです。

後、再帰で実装する場合でもC++ならpropagateやmergeをinline化するだけで実行速度は大分変わります。

12月4日追記:不恰好ながら一応実装できたので公開します。まず、遅延なしのsegment treeだとこんな感じに区間に分割されます。山とか言っていたのは図を見て察してください。

................................
................................
........LLLLLLLLRRRRRRRR........
........................RRRR....
......LL....................RR..
.....L..........................

遅延なしだとこれらを列挙するだけでよいのですが、遅延ありだと下の*のついたノードでpropagate/mergeを行う必要があります。

&#42;*******************************
********************************
********LLLLLLLLRRRRRRRR********
....****................RRRR****
....**LL....................RR..
.....L..........................

たくさんあるように見えますが、上の方は一つの配列がカバーする区間が大きいので、ノード数としては対数個で収まっています。

図を見ると一目瞭然ですが、propagate/mergeが必要なノードは山の両裾のノードから親を辿ることで得られます。ちょっと恰好悪い方法ですが、配列に処理すべきノードインデックスを溜め込むことで再帰を展開してみます。まずはインデックスを溜め込むコード。

void getIndexes(int indexes[], int &len, int L, int R) {
    len = 0;
    for(int a=L?(N+L)/(L&-L)>>1:0, b=R?((N+R)/(R&-R)-1)>>1:0;;b>>=1){
        if(a==b){
            for(;a;a>>=1) indexes[len++] = a;
            break;
        }
        if(a>b) swap(a,b);
        indexes[len++] = b;
    }
}

難しそうなところだけ簡単に説明しておくと、(N+L)/(L&-L)というのは、左端がLかつ自身が右の子であるようなノードインデックスです。

最終的にsegment treeに対する区間操作は次のように書けます。

void func(int L, int R){
    static int indexes[128], len;
    getIndexes(indexes, len, L, R);
    for(int i=len-1; i>=0; --i) propagate(indexes[i]);
    for(L+=N,R+=N;L<R;L>>=1,R>>=1){
        if(R&1) doSomething(--R);
        if(L&1) doSomething(L++);
    }
    for(int i=0; i<len; ++i) merge(indexes[i]);
}

遅延なしのタイプに比べてあからさまに不恰好ではありますが、これで一応遅延型segment treeの再帰を展開することができました。

それから、実装次第ではmergeはしばしば省略できます。

それ以外のsegment tree

普通のsegment treeや遅延型segment tree以外にも、動的segment treeや永続segment treeなどの応用があります。

これらは子へのリンクや担当する区間に関する情報を陽に持つ点で普通のsegment treeとは異なります。この再帰を取り除いて高速化するのは難しいです。書いたこと無い方は一度動的segment treeを書いておくことをお勧めします。平衡二分探索木を書くのも平衡させる為の操作を除けばそんなに変わらないし、永続化も変更加えるときにコピーとるだけです。ただしiwiさんのスライドで紹介されている平衡二分探索木の実装は、葉のみに元データを乗せるタイプではなく、各ノードがある1点に関する情報とそのノードを根とする部分木(部分列に対応)全体の情報の2種類を保持しているという点でsegment treeとは若干異なります。

省メモリ版(ネタ)

以下Nが2のべきに限らないときのことを考えます。

1次元のsegment treeを普通に実装すると、元のデータサイズがNのとき最悪でおよそ長さ4*Nの配列が必要になります。この4というのが結構大きいのが気になります。これを減らすことを考えてみましょう。ただし子や親へのリンクは陽に持たないようにすることが前提です。

実は木の形を完全二分木に限定する必要は無くて、使う配列の長さは2*highest(N-1)+N個あれば足ります(例:蟻本の「Crane」)。要するにわざわざ配列の末尾に単位元を埋めこむ必要は無いというだけのことです。2*highest(N-1)+Nというのは最悪でおよそ3*Nだと思ってよいでしょう。

もっと減らすこともできます。

元のデータを2のべきの個数ごとに分解してそれぞれsegment treeを構成すると長さ2*Nの配列で足ります。気分的には平方分割に近いですね。各操作での計算量もO(log N)と変わりありません。

もっとも、そこまで空間を節約したいなら時間を犠牲にして平方分割(長さN+sqrt(N)で良い)を使うのが実用的でしょうけど。

おわり

去年書いたときは「来年はLPとグラフについて書きたいなー」と思っていたんですが今年は不勉強でした。書くネタがまだ決まってない方は是非ご検討ください。私は大喜びします。

2013-03-13

立命館合宿2013Day2

メモ。

  • 立命館合宿企画者さまとAOJの管理者さまには大変お世話になりました。
  • コンテスト参加者のみなさまと、かなり無理なスケジュールを押し付けてしまったスタッフのlyoz君とfura2君と、インフラ用意してくれたhasi君と、それからついでに自分もお疲れさまでした。
  • 解説 http://www.slideshare.net/oupc/tag/ritscamp13day2
  • 問題文の不備やミスジャッジは今のところ見つかっておらずよかった。一安心だし結構誇らしい。
  • ICPCを意識したコンテストなのでもうちょっと実装よりにしてよかったかも。全体的にアルゴリズム寄りでグラフが多くなってしまった。
  • 序盤の4問には特に思い入れないけど、それ以外の問題はどれも結構気に入っているし思い入れもある。
  • 立命館合宿は夏合宿よりも修行的空気が薄いと勝手に思っていたので、たくさんAC出してもらったほうが気分いいよね、と易しめの問題を序盤に置いといた。参加者のレベル幅が大きいというのもある。でも易しすぎると達成感との兼ね合いもあるので難しい。
  • 難易度調整に関しては自分はやっぱりダメだった。fura2君がかなり正確に難易度把握できていて流石だった。
  • 今回もいくつか使われなかった問題が出た。
    • 重いだけでアルゴリズム的には普通な問題。
    • 完全に知識(ライブラリ)だけで頭使わずに解けてしまう問題。
    • そこそこ面白いけど、元ネタになった問題に類似しすぎている問題。
    • 面白いし好きだけど、残念ながら他のより良い問題とジャンルが被ってしまった問題。
    • 面白いと思ったけど、想定解法が撃墜されてしまった問題。
  • 解説スライド作るのが下手すぎる…。
A:回文数、B:括弧、J:Cube、D:Goto
  • この辺は適当。
  • 回文数は誰でも解けるように。
  • 括弧はちょっとだけ考える実装軽い問題ということで作った。詰まるチームもあるかもなあ、と思っていたけど意外と簡単だったらしい。
  • CubeはPCを遊ばせないようにするため実装寄り。アルゴ寄りのセットという自覚はあったのでPCに触ることすらない、という状況を避けたかった。
  • Gotoは易しめのアルゴ寄り問題ということで。
F:GCD
  • スライドするパートが微妙に難しいので、Oneより難しいと思っていた。
  • 実際は序盤4問以外で最も多く解かれていた。自分としては意外だったけどfura2君は正確にそれを予想していて流石。
I:One
  • IntegralのI。
  • 「数値積分いいよね」+「円とか直線じゃない幾何いいよね」ということで出したい問題だった。
  • 放物線だと不定積分が(幸か不幸か)計算できるので、そっちに引きずられるチーム多そうだと思っていた。
  • しかし放物線以外の山っぽい関数だと交点の計算でニュートン法とか二分探索とか要求することになり難易度上がりすぎるので仕方なくそのまま。
  • 実際にはほとんどのチームが厳密計算していた。
  • 「曲線の公式知らないと解けないのは微妙」という話をfura2君がしていたけど、「FFTとか互除法とかポリアとか数学だけど出てるからいいんじゃない?」と私が言ってそのまま出題された。
L:Trip
  • 作業締切り3~4日前になって、私が突然用意されていた1問を「既出の問題と似すぎていてつまんない」と切り捨てて慌てて作った。
  • Mirskyの定理がDilworthの定理の双対で綺麗&頑張れば気づけるのでこれで作ることにした。
  • 最長路求めさせるだけだと面白くないので、最長路のクリティカルな辺を求めさせるようにした。結果的にいい感じの難易度に収まってよかった。
  • 半順序集合の言葉を使って問題文表記したかったけど、あまりに不親切なので適当な設定を付けて出題した。問題文長くて不備が不安だったので何度もチェックした。
C:さんぽ
  • 最初はO(n^2*MAX_V)のタイプのナップサックに対応する問題が提案されていた。
  • 個数制限付きナップサックに対応させた方がコーナーケース出てきて面白いと思ったのでそっちに変更に。
E:replace
  • アドホック枠で提案。
  • 提案当時永続データ構造にハマっていて、全部が同じものを参照していたら1箇所書き換えるだけで全部に変更が適用されるの使えそうだなあ、というアイデアから。
  • そのアイデアだけなら簡単だけど、経路圧縮しないと出力でTLEするのは盲点になりやすいと思っていた。
  • 実際、経路圧縮せずにTLEしていた解答は多かった。
  • fura2君と自分で難易度評価に最も差があった問題だけど、実際のAC数を見るとやっぱりfura2君が正しかった。
  • スタックオーバーフローで引っかかっていたチームが多くて微妙に申し訳ない気分になった。
  • アルファベットサイズが小さいことを利用してる人が結構いて興味深かった(本質的には変わらないけど自分では思いつかなかった)。
K:K-th
  • 最初は単に数え上げる問題だった。
  • DPでO(n*A)だなあと思っていたら、ただの2項係数であることに気づいた。
  • 列の問題について、何かの判定ができるときは機械的に辞書順最小求めさせる問題が作れる。
  • それと同じように、数え上げができるときは辞書順K番目が機械的に導かれた。
G:魔方陣
  • 最終防衛レベルの問題という話を聞いていたけど、偏角ソートで区間分割すれば割と単純に解けることが発覚。
  • とはいえそれでも十分難しい。
H:1
  • 最小カットにはまっていた時期に作った。
  • 区間和を累積和に置き換えるテクニック+二部グラフの片方を反転させるテクニックを要求する問題を作ろうと思ったらかなり自然に生まれた。
  • 「問題がシンプル+ぱっと見ではグラフっぽくない+二部グラフであることも一瞬で見えるほどじゃない」という点はすごく気に入っていた。
  • 部分点を設定することができたならw≦6とかで出題したかった。このビットDPも結構面白い。
その他全般的に
  • それなりに経験値得られるセットになったのではないかなあ、と自賛してみる。
  • 去年のOUPC2012はトリッキーというか、飛び道具っぽい問題が多かったけど今年のセットは真面目っぽい。
  • 問題文は各作題者に任せた。
  • 自分担当の分については、今回も短い問題文にした。
  • 問題がシンプルなのに解法は本質的な複雑さを持っている、とか結構好きだし、何より短い方が題意が正確に伝わりやすいし不備がないかのチェックもしやすい。
  • とはいえ、本番では長い問題文を正確に読み取る技術も要求されることがあるので、その練習にならないというのは問題がある。
  • 制約は余裕を持ったサイズに。
  • ジャッジ解は大体制限時間の1/20以下で通るように設定している。流石に20倍も遅い解答の保証まではしない…。
  • スタックオーバーフローで落とすのはあまり好きじゃない(全く本質と関係ないくせにスタック使って展開するのが面倒だから)。
  • なのでLはそれを避けられるようにしている。
  • Eは避けるの難しく、とはいえ10^5というのは微妙なサイズで、書き方や言語で通ったり通らなかったりになる。それは嫌だったので3*10^5にして言語の差によらず一貫して落とすことにした。
  • 余った問題どう処理しようかな…。
追記
  • L問題で、「DAGであると書いてほしかった」という意見を見かけたのだけど、ちゃんと書いてあったような…。有向グラフであることも、閉路が存在しないことも明確に述べていたのだけれど。
  • エスパーしてみると、もしかしたら『「入次数が高々1とは限らない」と明記しろ』ということを主張していたのかもしれない。それならまあ。

2013-01-07

POJ-1854 : Evil Straw Warts Live

問題概要

長さL(<8000)の文字列が与えられる。隣り合う2文字をスワップして回文になるようにしたい。必要なスワップの最小回数を求める問題。回文にできないのであれば指摘する。

解法

奇数回現れる文字が2個以上あれば不可。それ以外のときは、以下のような手順で最小コストの回文が得られる(未証明)。

  • 最小のスワップ回数で、前半と後半で出現する文字の頻度が一致するように移動する。
  • 後半の文字列のみを最小回数で動かして回文になるようにする。

前半部分はやるだけ。後半は、分割統治で解ける。すなわち、文字列を前半と後半に分けて出現回数が一致するようにスワップを繰り返せばよい。

続きを読む

2012-12-08

GCJ2008 WF E: The Year of Code Jam

蟻本の一番最後に載っている問題。

最終的には蟻本と同じになるのだけど、前回の記事で書いた方法でより機械的に解いてみる。

まず前段階として、問題のサイズはそんな大きくないし、基本的には?の部分を開催するかどうかという2択から選ぶのだから最小カットで行けそうだと信じることが前提。部分問題に落とすのも辛そうなのでDPも上手く行かなそうだし…。

方針

x[i] = {i番目の日にコンテストを開く?1:0}

としてみる(とても自然)。

今回は最大化の問題なので、例によって損害を最小化する問題だと考える。基本的には毎日コンテストを開いて幸福度4を得られたものだと考えてみる。

このとき、最小化すべき損害の式(目的関数)は次のようになる。長くなるので4つに分ける。

  • sum f(x[i])*0 + f(1-x[i])*4

コンテストを開かなかったら損害4が発生する。

  • sum_{i,jは隣接している} f(x[i]+x[j]-1)*2

x[i]=x[j]=1のときは2の損害を受ける。

x[i]=1のときinfペナルティを受けると思えば良い。

x[i]=0のときinfペナルティを受けると思えば良い。

ここまではx[i]を上の様に定義したら勝手に出てくる。

さて、2つ目の式ではfの中に差分でないf(x[i]+x[j]-1)が出ている。このままでは最小カットにならないので、この形の常套手段としてx[j]=1-x[j]と置き換えてみる。つまり、二部グラフの片側に属する頂点に対しては

x[i] = {i番目の日にコンテストを開く?0:1}

と入れ替えることにする。f(x[i]+x[j]-1)と書いている部分の、iとjは二部グラフのことなる成分に属しているので今回はこれでfの中身を全部差分にできる。後は1,3,4つ目の目的関数についても二部グラフの片方についてx[i]と1-x[i]を入れ替えてやれば良い。

ということで、この問題で二部グラフの片側について0,1を入れ替えるのは極めて自然で、特別な発想を要するものではないことであったことがわかった(もちろん実際にコンテスト中に気づけるかは別問題だけど、少なくとも冷静な状態だとそんな突飛ではない)。

結局、x[i](=x[i]-0)か1-x[i]かx[i]-x[j]という差分の形を作ることを目標にすればよいだけだった。

続きを読む

LPっぽいのと最小カット

様々な問題をLPやその双対を駆使して解きまくっているwataさんが格好良すぎるので、ちょっといくつかの最小カットの問題を解き直してみた。

私はLPにも最大流にも詳しくないので、完全ユニモジュラとか言われても「成り立ってることを祈りましょう」くらいしか言えないし、どこがLPなんだよ!と言われてもまともに答えられる自信はないです。

基本形

x[i]は0または1の値をとり、x[s]=1,x[t]=0とする。関数f(x)=x>0?1:0と定義したとき、sum f(x[i]-x[j])*c[i][j]の最小化問題でかけるもの。ただしc[i][j]>=0。具体的にグラフを構成するにはiからjへ容量c[i][j]の辺を張れば良い。ほげほげしてはいけない、みたいな制約はc[i][j]=infだと思えば良い。

例題:Dual Core CPU (蟻本に載ってる)

x[i] = {モジュールiをAで実行する?1:0}とおく。このとき以下を最小化する。

sum_{i in [1..N]} (f(x[i])*A[i] + f(1-x[i])*B[i])

+ sum_{i in [1..M]} ( f(x[a[i] ]-x[b[i] ])*w[i] + f(x[b[i] ]-x[a[i] ])*w[i] )

ここで、

  • f(x[i])=f(x[i]-0)=f(x[i]-x[t])
  • f(1-x[i])=f(x[s]-x[i])

でかつ全ての係数が非負なので、

sum_{i in [1..N]} (f(x[i]-x[t])*A[i] + f(x[s]-x[i])*B[i])

+ sum_{i in [1..M]} ( f(x[a[i] ]-x[b[i] ])*w[i] + f(x[b[i] ]-x[a[i] ])*w[i] )

これは最小カットのLPとなっている。

具体的にグラフを構成するには、

  • 頂点iから頂点tへ容量A[i]の辺を張る。
  • 頂点sから頂点iへ容量B[i]の辺を張る。
  • 頂点a[i]からb[i]へ容量w[i]の辺を張る。
  • 頂点b[i]からa[i]へ容量w[i]の辺を張る。

とすればよい。

例題:GreenWarfare (SRM 465)

x[i] = {基地iを破壊する?1:0}

y[i] = {補給所iを破壊する?1:0}

CB[i]=基地iを破壊するのに必要なコスト

CP[i]=補給所iを破壊するのに必要なコスト

問題を素直に読むと、次を最小化する問題らしい。

sum_{i in [1..B]} f(x[i])*CB[i] + sum_{i in [1..P]} f(y[i])*CP[i]

+ sum_{基地iと補給所jの距離がR以下} f(1-(x[i]+y[j]))*inf

ここでf(1-(x[i]+y[j]))という式が出てきて困る。そこで、z[i]=1-y[i]と置き換えて上の式を書き直してみる。

sum_{i in [1..B]} f(x[i])*CB[i] + sum_{i in [1..P]} f(1-z[i])*CP[i]

+ sum_{基地iと補給所jの距離がR以下} f(z[j]-x[i])*inf

Dual Core CPUと同じように次のように書き換えれば終わりとなる。

sum_{i in [1..B]} f(x[i]-x[t])*CB[i] + sum_{i in [1..P]} f(x[s]-z[i])*CP[i]

+ sum_{基地iと補給所jの距離がR以下} f(z[j]-x[i])*inf

Komakiさんの例題0

今度は最大化問題なので、損害の最小化という風に考える。例えば本当は1個のゴミを処理するのに300円貰えたはずなのに、と考えると利益は300*3 - 損害となる。この場合の損害は、A,B,Cを燃やした場合の損害はそれぞれ300-50=250、300-60=240, 300-130=170。A,B,Cを埋めた場合の損害はどれも300-100=200となる。

x[A]={Aを燃やした?1:0}

などとおく。このとき以下の損害を最小化する。

f(x[A])*250+f(x[B])*240+f(x[C])*170+f(1-x[A])*200+f(1-x[B])*200+f(1-x[C])*200

+f(x[B]-x[C])*inf + f(x[C]-x[B])*inf

お馴染みの方法でf(x[A])=f(x[A]-x[t]), f(1-x[A])=f(x[s]-x[A])などと置き換えれば良い。

Komakiさんの演習0

本当は1個のゴミを処理する毎に600円貰えたはずだと考える。このとき利益は600*4-損害となる。

さっきと同じように式を立てると、次の最小化を考えていることになる。

f(x[A])*300+f(x[B])*200+f(x[C])*100+f(x[D])*0

+ f(1-x[A])*150+ f(1-x[B])*150 + f(1-x[C])*150 + f(1-x[D])*150

+ f(x[A]-x[B])*inf + f(x[A]-x[C])*inf + f(x[D]-x[A])*inf

後はやっぱり同じ。

Komakiさんの例題1

やっぱり損害の最小化。最初、各本毎に400円ずつ貰えるものだと考えて400*3-損害が答となる。

x[A]={Aを売った?1:0}

などとすると最小化すべき損害の式は次のようになる。

f(x[A])*500 + f(x[B])*100 + f(x[C])*0

+ f(1-x[A])*400 + f(1-x[B])*400 + f(1-x[C])*400

+ f(x[A]-x[B])*140 + f(x[B]-x[A])*140 + f(x[B]+x[C]-1)*30

今度はf(x[B]+x[C]-1)が出てきて困る。そこでx[C]=1-x[C]と置き換えると、

f(x[A])*500 + f(x[B])*100 + f(1-x[C])*0

+ f(1-x[A])*400 + f(1-x[B])*400 + f(x[C])*400

+ f(x[A]-x[B])*140 + f(x[B]-x[A])*140 + f(x[B]-x[C])*30

まとめ

「してはいけない」という制約はinfを係数に持つ項を目的関数に加える。コストは全部非負。

大体パターンが見えてくる。

  • x[i]=1のときコストが発生。
    • 目的関数にf(x[i]-x[t])*(コスト)を追加。
  • x[i]=0のときにコストが発生。
    • 目的関数にf(x[s]-x[i])*(コスト)を追加。
  • x[i]>x[j]のときにコストが発生。
    • 目的関数にf(x[i]-x[j])*(コスト)を追加。
  • x[i]!=x[j]のときにコストが発生(x[i]+x[j]=1と読み替えることもできる)。
    • x[i]>x[j]またはx[i]<x[j]のときにコストが発生と読み替える。</li>
  • x[i]=x[j]=0のときにコストが発生。
    • 目的関数にf(1-(x[i]+x[j]))*(コスト)を追加。
  • x[i]=x[j]=1のときにコストが発生。
    • 目的関数にf(x[i]+x[j]-1)*(コスト)を追加。

fの中は必ず2項の差分になってなくてはならず、そうなってない場合はx[j]=1-x[j]などで置き換える。このとき他の所で困らない保証はない(例えば2部グラフだと上手くいくことが多いが)。

これで全部上手く行くのかは分からないけど、例えばThe Year of Code Jam(蟻本の最後に載ってる)なんかはこの方針だと大分見えやすくなる気がした。

この記事の信憑性はゼロなので、間違いなどがあれば指摘して貰えると私は喜びます。

次は最小費用流に行きたい所だけど、その前に最小費用循環流勉強するべきなんだろうか。

Connection: close