マラソンの感想
Competitive Programming Advent Calendar 2014の記事です。
自分はかつてTopCoder Marathon Matchに参加していた時期があったのですが、今回はその感想を書きます。
続きを読む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の親のindex | i/2 |
| iの子のindex | i*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を行う必要があります。
******************************** ******************************** ********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とグラフについて書きたいなー」と思っていたんですが今年は不勉強でした。書くネタがまだ決まってない方は是非ご検討ください。私は大喜びします。
立命館合宿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
L:Trip
- 作業締切り3~4日前になって、私が突然用意されていた1問を「既出の問題と似すぎていてつまんない」と切り捨てて慌てて作った。
- Mirskyの定理がDilworthの定理の双対で綺麗＆頑張れば気づけるのでこれで作ることにした。
- 最長路求めさせるだけだと面白くないので、最長路のクリティカルな辺を求めさせるようにした。結果的にいい感じの難易度に収まってよかった。
- 半順序集合の言葉を使って問題文表記したかったけど、あまりに不親切なので適当な設定を付けて出題した。問題文長くて不備が不安だったので何度もチェックした。
C:さんぽ
- 最初はO(n^2*MAX_V)のタイプのナップサックに対応する問題が提案されていた。
- 個数制限付きナップサックに対応させた方がコーナーケース出てきて面白いと思ったのでそっちに変更に。
E:replace
- アドホック枠で提案。
- 提案当時永続データ構造にハマっていて、全部が同じものを参照していたら1箇所書き換えるだけで全部に変更が適用されるの使えそうだなあ、というアイデアから。
- そのアイデアだけなら簡単だけど、経路圧縮しないと出力でTLEするのは盲点になりやすいと思っていた。
- 実際、経路圧縮せずにTLEしていた解答は多かった。
- fura2君と自分で難易度評価に最も差があった問題だけど、実際のAC数を見るとやっぱりfura2君が正しかった。
- スタックオーバーフローで引っかかっていたチームが多くて微妙に申し訳ない気分になった。
- アルファベットサイズが小さいことを利用してる人が結構いて興味深かった（本質的には変わらないけど自分では思いつかなかった）。
K:K-th
H:1
- 最小カットにはまっていた時期に作った。
- 区間和を累積和に置き換えるテクニック+二部グラフの片方を反転させるテクニックを要求する問題を作ろうと思ったらかなり自然に生まれた。
- 「問題がシンプル+ぱっと見ではグラフっぽくない+二部グラフであることも一瞬で見えるほどじゃない」という点はすごく気に入っていた。
- 部分点を設定することができたならw≦6とかで出題したかった。このビットDPも結構面白い。
その他全般的に
- それなりに経験値得られるセットになったのではないかなあ、と自賛してみる。
- 去年のOUPC2012はトリッキーというか、飛び道具っぽい問題が多かったけど今年のセットは真面目っぽい。
- 問題文は各作題者に任せた。
- 自分担当の分については、今回も短い問題文にした。
- 問題がシンプルなのに解法は本質的な複雑さを持っている、とか結構好きだし、何より短い方が題意が正確に伝わりやすいし不備がないかのチェックもしやすい。
- とはいえ、本番では長い問題文を正確に読み取る技術も要求されることがあるので、その練習にならないというのは問題がある。
- 制約は余裕を持ったサイズに。
- ジャッジ解は大体制限時間の1/20以下で通るように設定している。流石に20倍も遅い解答の保証まではしない…。
- スタックオーバーフローで落とすのはあまり好きじゃない(全く本質と関係ないくせにスタック使って展開するのが面倒だから)。
- なのでLはそれを避けられるようにしている。
- Eは避けるの難しく、とはいえ10^5というのは微妙なサイズで、書き方や言語で通ったり通らなかったりになる。それは嫌だったので3*10^5にして言語の差によらず一貫して落とすことにした。
- 余った問題どう処理しようかな…。
追記
- L問題で、「DAGであると書いてほしかった」という意見を見かけたのだけど、ちゃんと書いてあったような…。有向グラフであることも、閉路が存在しないことも明確に述べていたのだけれど。
- エスパーしてみると、もしかしたら『「入次数が高々1とは限らない」と明記しろ』ということを主張していたのかもしれない。それならまあ。
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の損害を受ける。
- sum_{i日目はコンテストが無いと確定している} f(x[i])*inf
x[i]=1のときinfのペナルティを受けると思えば良い。
- sum_{i日目はコンテストが有ると確定している} f(1-x[i])*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[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(蟻本の最後に載ってる)なんかはこの方針だと大分見えやすくなる気がした。
この記事の信憑性はゼロなので、間違いなどがあれば指摘して貰えると私は喜びます。
次は最小費用流に行きたい所だけど、その前に最小費用循環流勉強するべきなんだろうか。
プログラミングコンテストを開いたときの話
Competitive Programming Advent Calendar Div2012の12月4日分の記事です。
私はこの1年でいくつかのプログラミングコンテストに主催者寄りの立場で関わって来ました。具体的には、
- OUPC
- HBPC
- SuperCon
- Autumn Fest
- JAG主催のコンテストのいくつか
などです。今回はコンテストを開催する側としての個人的な経験を中心に書こうと思います。ただしSuperConは色々特殊なので除きます。またOUPCについては既に書いているのでそれとは重ならないようなことを書きます。最初はどうやってコンテストを開くか具体的なマニュアルを作るつもりで書く気でいたのですが、挫折しました。最近はコンテスト開催経験者も増えていますし、文字通りプロであるAtCoderという会社もあるので詳しい手順が知りたい方はその辺りを当たってみるとよいと思います。記事全体は長いですが後半は特に読む必要のないメモを貼り付けただけなので気楽に読んでください。
ジャッジシステム
コンテストを開催するにあたってどこのジャッジシステムを使うか選ぶ必要がありました。とはいえ選択肢はAtCoderかAOJの2択という感じでした。どちらで開催したときもシステムの人に丁寧な対応をしてもらったので、どちらでやっても困ることはありませんでした。AtCoderの方は部分点とか傾斜配点が使えたりhtmlがその場で直接いじれるのが便利でしたね。
時間や配点
5時間のフルセットだと長すぎてダレるとか後半の面白い問題はほとんど見てもらえないとかになりがちなので、2~3時間のコンテストにすることも検討したほうがよいです。
Autumn Festでは配点を好き勝手にいじりました。配点に傾斜を付けた方がより難しい(=面白い)問題に取り組んで貰えるという期待があったからです。
解答や入力の作成
最低限必要になるのがジャッジ解、入力生成器、入力検証器と(必要なら)出力検証器です。前二つは文字通りのもので、入力検証器は生成器よって作られた入力が仕様を満たしているかチェックするプログラムで、出力検証器は出力結果が正答かどうかをdiffで判定できないときにチェックするためのプログラムです。
ジャッジ解をつくるときは、「最大サイズだとTLEするけど愚直にやっているからほぼ確実に合ってるであろう解答」とかを別に用意しておくと便利です。
入力生成器は言うまでもなく重要なものです。嘘解法を確実に落とすのは難しいことですが、しかしやっぱりなるべくならちゃんと撃墜しておきたいものです。数え上げとかは適当に作っても嘘解法は大抵落とせるのですが、最適化系の問題だと撃墜はかなり難しい場合があります。また、テストケースの数はあまり多くなりすぎないように注意します。
入力検証器は、基本的にはtestlib.hとかの信頼できる道具を使うと楽に書けることが多いのですが、時には元の問題よりはるかに難しいものになってしまうこともあります。「ただし入力には矛盾がないことが保証されている」とか「与えられる座標が10^-6変化しても答は変わらない」とかの但し書きがあると大抵元の問題よりも難しい問題を解くことになってしまいます。
出力検証器も、小数の誤差判定くらいならtestlib.hとかに揃っているので楽ですがちゃんと誤解答を用意しておかないと何を投げてもACになってしまうとかの事故が起こるので危険です。
余力があるときは別の言語や解法で解答プログラムを書いたり、想定される嘘解答を作っておいてちゃんと撃墜できるかどうか試したりします。
問題の準備
コンテストの目的に合わせて作る問題の傾向は意識的に変えていました。
OUPCはICPC合宿に提供されるものなので実装量を増やす方向の工夫をちょこちょこ加えました。ICPCの訓練と言うのであれば問題設定もちゃんとダルい感じにしようかとも考えたのですが、ごめんなさい。そこは譲れませんでした。一貫性がないですね。ほぼ全ての作業をふたりだけでやっていたので問題文長くするとチェックが大変になって不具合が起きやすくなるという事情もあったんです…(もちろん後付けの理由です)。
Autumn Festのときは娯楽感を出したかったので修行っぽさを極力排して問題設定も解法もシンプルで実装量の少ない問題を多く選んだつもりです(解答が1行で書けたり、BNFが単純だったり)。
コンテストの最初の方に配置されるeasyな問題は大抵後回しにしていました。不足しているジャンルの調整とかが容易にできるからです。
コンテストの開催日が近づくにつれて自分で作った問題の難易度評価はよく分らなくなっていきます。
あと、アルゴリズムドリブンで問題作るのってそのアルゴリズムに対して理解を深める効果があると思います。物事を人に説明することによって理解が深まるという現象はよく知られていますが、それと似たようなものでしょう。
個人的な嗜好の話
私は自分が解いて面白いと感じられる問題を(なるべく)出題したいと思っています。問題を作ってみると自分の好みがよく分かるようになりました。
シンプルな設定やアイデアの問題が好きです。SRMの問題とか綺麗にまとまっていることが多いなーと思います。聞いたこともないような定理とかを使うタイプの知識ゲーも結構好きです。
一方、いたるところで見かけるような典型な問題はあまり考えていてわくわくしません。複雑な設定の問題もあまり好きではありません(解法があまりに鮮やかな場合は別ですが)。
くどいようですが、以上のことはあくまで私個人の嗜好の話でしかありません。新規参加者は増え続けているのだからそちら向けに典型問題を出題するのは真っ当ですし、複雑な設定や長い問題文を正確に読み取って本質を抽出することだって技術が要求されるひとつのジャンルであるし、実装力を問う問題が出題されるのは当然だと思っています。好き嫌いと良し悪しは別問題です。
コンテストを開く目的
コンテストを一度開くことに決めたら折角なので参加者には楽しんでもらいたいしそうなるような努力をしますが、私の場合それ自体がコンテストを開く動機になっているわけではありません。問題を作る作業が面白く、折角作ってみたのだから人に解いてもらいたいというのが主な目的です。
ただしAutumn Festを開いたのには別の目的がありました。uwiさん、tomerunさんという非学生コーダーの方にコンテストの開催を経験してもらいたかったのです。大学毎に主催するコンテストだけではなく、個人や有志による単発コンテストがもっと増えて欲しいという願望がありました。
コンテストを開くデメリット
コンテストを開催するにはもちろん時間と労力がかかります。
また作業する人間が増えるとマネジメントする人の労力も増えてしまいます(私は主に負担を増やしてしまう側です。ごめんなさい)。
問題考えたり入力データ用意したりするのはたしかに実力向上に繋がると思いますが、準備にかけた時間を問題を解くのに充てた方がより実力付いたのでは?と言われると私は反論することができません。
まとめ
コンテストが増えるのは基本的に誰にとっても嬉しいことだと思うので、みなさまぜひコンテストを開きましょう。
最近は全体的にコンテストのレベルが上がっていますが、もっと易しめのコンテストが増えても良いと思います(上位常連な人たちには退屈かもしれませんが、別にそこをターゲットにする必要はないので)。
以下はおまけです。
問題を作るときのネタのメモ
既存の問題の拡張、改変
- ネタは山ほどあるけど、良い計算量の解法を探すのは大変。
- 列の問題をを木に拡張したりするのはお宝いっぱい。
- 連続と離散を切り替えるとか。
逆問題、復元系、ロシアゲー
- ネタはいっぱい。でもやっぱりいい感じの解法を作るのは大変。
幾何
- ICPCの訓練っぽいセットにしたいなら必要になる。
- 双対変換使うのはそんなに多くない。
- 解き方によって実装量が激しく変わったりするのは非常に良い。
シミュレーションとかの実装ゲー
- 工夫すれば簡単になる、みたいなのがあって欲しい。
有名な教科書の練習問題
- ほぼそのまま出されている例も世の中にはたくさんある。結構参考になる。
貪欲
- 流行のマトロイドとか?
- その方面の知識はないし、なんだかんだで狙って作るのは難しそう。
分割統治
- マージする部分が最難であることが多いので、そこから考えるのが楽?
- 好きなジャンルなので頑張ってひねり出したい。
データ構造、クエリ処理
- 列に対して、区間へ一様に何かしたり質問を飛ばしたりするsegment treeな問題はお腹いっぱいな感がある。
- 正直この手の問題はよほど工夫しないと目新しい部分が出せない。今や遅延更新すら常識となりつつあるので(言い過ぎ)。
- 巡回シフトや反転とかが加わると平衡二分木になってよい?
- リアクティブでクエリ先読みを防ぐことができるようになったので出す側の自由度は広まった。
- meldable priority queue使う問題出したい…。→つい先日UTPCで出た。
- 連結リストとかも滅多に見ない。
- queue(幅優先探索以外)
- stack(all nearest smaller values以外)
- 永続データ構造。
グラフ
探索
- 結構何でもあり。
- BBとか反復深化とか両側探索とか。
- 推定値をちゃんと考えないと通らないようにするとか。
- ゲーム木探索ならαβとか。
数学
数え上げ
動的計画法
- 適当に問題作ったらよくでてくる。
- 状態の取り方が面白ければ何でもOK。
- 変な半順序が入ると希少性アップ。
- ただのビットDPだと希少性ないけど、計算量や状態数が3^nなのはそこそこ希少。
- そこから高速ゼータ変換まで発展すれば素晴らしい。
- 自然に状態考えて、自然に漸化式がでてきたのを自然に実装したら解けたみたいなのはちょっと抵抗がある。
- 累積和や(RMQ|スライド最小値)で計算量落とすのももはや作業感が強い。
- Monge性とかあると嬉しい。
- 期待値の線形性は使い古されたネタで典型だとは思うけれどなぜか許せてしまう。完全にえこひいきです。
確率的アルゴリズム
output sensitive
- 有名なのは平面走査で線分の交点を列挙するのとか。
- コンテストであまり見かけないの何でだろう?
- 制約の与え方が綺麗ではない、というのは多少感じられるけど気になるほどのことではない気が。
埋め込み、圧縮
数値解析
- 微分方程式とか。
- ロバストなアルゴリズムとか。
- 単にBigDecimal使うだけで回避できるようなのはちょっと違う。
- 精度保証がひたすら辛い。
- 多分不人気。
- 数が小さい所ではDPとかで厳密解を求めてサイズが大きくなったら近似式使うような問題は狙い目。
