続：『燃やす埋める』と『ProjectSelectionProblem』

http://tokoharuland.hateblo.jp/entry/2017/11/12/234636の続きです。
煽り気味な記事を書いたのは反省中です。気を悪くされた方がいましたら申し訳ありません。
こういうのは無駄に人の心を煽っても仕方なくて、ACできたら正義なのでどちらを選んでも問題はない、と考えた方がよかったかと思います。
また、前回の記事で抜けていた点として燃やす埋めるは最小化問題で、ProjectSelectionProblemは最大化というところも大きな違いでした。これは先ほど少しだけ追記しました。

ところで、今日は続きの話題を書きます。

『燃やす埋める』と『ProjectSelectionProblem』https://t.co/IxDVDXDP1o
話題になってますね。近頃は３つに分けるテクニックなども出てきていますけれども、これも対応可能なのでしょうか？
— 古寺いろは@競プロ応援アカウント (@codera_iroha) 2017年11月13日

いろはちゃんから上のような疑問をいただきました。

答えはできます、が、従来と比べて思考量が減るかは判断できないのでどっちでもいい気がします、というところです。

3つに分けるタイプの問題？

いろはちゃんの問題ですが、要するに次の問題だと認識しています。

これと関連して問題を1つ。「i番目のものを埋めるとxi円、燃やすとyi円貰えます(xi,yi>0)が、何もしないということもできます。i番目のものを埋めてj番目のものを燃やすのは駄目というペアがいくつか与えられます。もらえるお金を最大化してください」さて、どうやってグラフを作りますか？
— ＳＫＹ/sky58 (@skyaozora) 2017年11月13日

これの解法ですが、まず2N個のProjectを用意します。
次にはじめのN個には次の意味を持たせます
B（ベース）にいる <=> iは何もしない
Aにいる <=> iを燃やす

残りのN個には次の意味を持たせます
B(ベース)にいる <=> i を埋める
Aにいる <=> iは何もしない

このとき、禁止制約は『iを燃やすかつiを埋める』、と、『iを燃やすかつjを埋める』という形の制約になります。
この条件は結局『iを燃やすならばjは何もしない』とすれば回避でき、これはProjectの世界で『iをAにおけば、(j+N)はAに置かないといけない = 罰金INF』ということなので、めでたくProjectSelectionで書けました。

総コストについてですが、まず最初B(ベース)にいることを考えるため、埋める利得の総和を事前に足しておきます。
次に、ProjectSelectionProblemの答えにおける総和部分はBから見てAのスコアが相対的によいプロジェクトでのスコアの総和なので、これは結局燃やす利得の総和です。
最後に、ProjectSelectionProblemの答えにおけるmaxflowの値を引けば、これがもともと知りたかった3つに分けるタイプの問題の答えになります。

結局反転は登場せざるを得ないし、3択を2択にするのがトリッキーなので、そこのややこしさは回避できないでしょう。また、できるグラフは従来の考え方と大差ないはずです。
ただ、もともと最大化問題のフレームワークなので、minとmaxがごっちゃになるリスクは減るんじゃないかとは思います。

そう考えると、最小化問題だと燃やす埋めるで考える方がやりやすいのか、気になります。意見などありましたらお寄せください。

今日のまとめ

前回の記事のごめんなさい
3つに分ける問題も扱えます

2017-11-12

『燃やす埋める』と『ProjectSelectionProblem』

(UPD 11/15)
下の記事を書くにあたってやらかしたこととか、
返ってきた辛辣な反応を見て、いろいろ言いたくなったんですが、
自分の過ちがどんどん浮き彫りになった気がします。それはまた今度書きます。

個人的にPSP経由の解法はカットが苦手な人にはオススメだと思うので、
そういう人はぜひ試してほしいです。
次記事とか次々記事あたりは面白いんじゃないでしょうか。

- - -

こういうツイートをした。

『昨日のARCに関してなんですが、個人的には、『燃やす埋める』という概念はそろそろ消え去るべきだと思っています。なぜかというとProjectSelectionの形そのものを覚えれば瞬殺だからです。だからみんな http://tokoharu.github.io/tokoharupage/docs/formularization.pdf のp7とかwikipediaのページを読んでほしい』

珍しく腹が立ってしまったから煽りっぽい感じで言ったので、少し落ち着き目でこれに対する色々を書いておきます。

そもそもこれらは何なのか。

結局のところ、最小カットに帰着して最大流のグラフに変換する際に楽をするツールというイメージです。

ProjectSelectionProblem

https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem#Project_selection_problem

次の問題が与えられます。
N 個の要素がある。最初どの頂点も集合 B に属しているが、これを集合 A に移すことで利益を最大化したい。要素 i が A に属する時には利得 p_i を得るという情報が与えられる。さらに 3 つ組の列 (xj, yj, zj) が与えられ、これは xj が A に属し、かつ yj が B に属していた時に zj(≥ 0) だけ損失をすることを意味する。得られる利得の最大値を答えよ。

この問題に対する解は　(∑(v∈V) max(0, pv) ) − maxflow(s, t)で求めることができる。ただし、 maxflow(s, t) とは、

1. 要素に対応する点の他に，新しく s, t の頂点を導入した N + 2 頂点のグラフの上に、
2. pv > 0 であれば s から v に容量 pv の辺を張り、
3. pv < 0 であれば v から t に容量 −pv の辺を張り、
4. xj から yj に容量 zj の辺を張ったときの、
5. s-t 間の最大流の値

である。

燃やす埋める

最小カットを使って「燃やす埋める問題」を解く

診断人さんの資料が現状一番詳しい気がしています。(最近の記事を読んでいないので良いのがあれば教えてください)

違いは？

これら二つのテクから構築されるグラフはほとんど同じようなものです（実際、「ならば」の制約を言い換える操作は同じことをしています）。
違いは集合の扱いで、ProjectSelectionProblem では「集合Aに入った方が集合Bに入れるよりどれくらいお得か？」という量を持ちます。

一方で、『燃やす埋める』というテクでは集合Aに入るときのコストと集合Bに入るコストを両方持ちます。（コストだからこちらは最小化問題ですね）

『燃やす埋める』という概念に消え去ってほしい理由

燃やす埋めるタイプそのままが出てきたときに何も考えずに変換テクを使えるのは強いです。そういう意味でこの概念は消える必要は無いし、しばらく残り続ける言葉だと思います。

しかし、私はProjectSelectionProblemの方にメジャーにはなってほしいと感じます。端的に言ってそちらの方が洗練されていると思うからです。

相対的なコストで考えるほうが考えやすい

Aに属したときのコスト、Bに属したときのコスト、と分けるのは個人的にとてもややこしいと感じます。燃やす埋めるの直接適用が可能であればよいですが、たいていの場合、ベースケースに所属させておいて、そこから見たときの相対利得を考察する方がずっと楽だと思います。

ローカルネームすぎる

この界隈、ローカルネームが流行ることが多いです。たいていの場合はその周辺にちゃんとした名前が無いからつけられているという認識ですが、今回はProjectSelectionProblemがすぐ近くにいるのに名付けられているので、なんだかなぁと思います。

変なハマり方をしにくい

例えば、ARC85で出た問題ではこういうハマり方をしている方がいました。

最小カットは考えたけど当然のように負辺が登場してやめた
— 最高の夏というよりほかの季節が厳しい (@maroon_kuri) 2017年11月11日

この問題はProjectSelectionProblemのフレームワークに自然に落ちる上、できるグラフに負辺が登場しません。何も考えてないのにこういうハマり方を回避できるのは地味にお得だと思いませんか？

まとめ

~~燃やす埋めるには緩やかに滅んでほしいと思います~~

2017-06-24

AGC 016 C (+/- Rectangle) と Farkas' lemma

AGC 016 Cを考えていると気づいたことがあるので、紹介します。

まず、AGCの問題文 : C: +/- Rectangle - AtCoder Grand Contest 016 | AtCoder
この問題は要するに、局所的には負にしつつ、全体は正にする、というような気分のような問題です。
私も結局よくわからず、最後は答えを見てなるほど～～、と言っていました。

では次にFarkas' lemmaを見てみます。
Farkas' lemma - Wikipedia
これはリンクにある問題2つのうち、必ずどちらか一方のみに解がある、というなかなか面白い補題です。

この式の2番の方に着目してみましょう。 ${y=-y'}$ として ${y'}$ で式を立てれば不等号の向きが入れ替わります。

さてこの式、AGCの方の問題とほぼ同じではないですか？

${b}$ を要素がすべて1のベクトルすれば ${b^T y' > 0}$ は正にする制約だし、
${A}$ 側も、適切に設定すれば局所的に負にする制約にできます。

じゃぁこのとき、1式はどうなるのか。これは各小長方形1つに変数が1つ対応して、これが ${x}$ になります。
${b}$ はマス1個に対応して、どの要素も1。 ${Ax}$ は小長方形の重み ${x}$ をそれが含む各マスに足しこむ操作とみなせます。

ここまでわかれば、1式が解をもつかどうかはすぐにわかり、 ${H}$ が ${h}$ の倍数かつ ${W}$ が ${w}$ の倍数であることが必要十分になります。
すると、2式が解を持たないための条件はこの条件だとわかるのです。

ということで、解が存在する・しないの判定は、このようなアプローチで見つかることがわかりました。（やったね！）

AGCの問題を解こうと思うと、ここからさらに構成する必要があるのですが、
このアプローチだけだと少し厳しそうに見えます。
というのも、Farkas' lemmaのアプローチで解 ${y'}$ を構成しようと思うと、
分離超平面を構成する必要があります。
これを今回の大きさの行列に適用するのはしんどいので、特別な性質があればよいのですが、
ぱっとはわかりませんでした。

誰かわかる人がいれば教えてください。

2017-04-13

JOI春合宿2017 Day1 手持ち花火（Sparklers）の別解と上位問題の解法

こんにちは。今回はタイトル通りのことについて気づいたので紹介していこうと思います。
一応注意をしておくとネタバレを含むので、見たくない人は見ないでください。
また、この記事を書くにあたってsnukeさんに多大な助言をいただきました。この場で感謝します。

この問題の詳細はこちらをどうぞ。
JOI 2016/2017 春季トレーニング合宿課題

読み進めるとわかりますが、一部想定解法は上記にある解説ページがベースになっています。
また、のちのちSegmentTreeが現れますが、かなりざっくりとした説明ですので、SegmentTreeを知らないと読めないと思います。

問題文

まずはこの問題の問題文を整理するところから始めます。

${N}$ 人の人が一直線上に並んでおり、それぞれの人が一つずつ花火を持っている。
それぞれの花火に火はついていない。
${K}$ 番目の人は時刻 ${0}$ に自分の花火に着火する。
花火を持っている人と花火を持っていない人が同じ時刻に同じ場所にいれば花火を持っていない人に花火を着火することができる。ただし、同時刻・同場所にいても花火を着火させないこともできる。
それぞれの花火は着火後 ${T}$ 秒で消えてしまう。
それぞれの人の花火は1度までしか着火できない。
次のことができる各人の移動速度の上限 ${s}$ として最小のものを求めよ : 時刻 ${0}$ より適切にそれぞれの人を移動させることによって、それぞれの人の花火が一度点火される。

整理

入力は ${N,K,T}$ と各人の時刻0での位置 ${x[i]}$
出力は最小の移動速度の上限 ${s}$

重要な制約

${N \leq 10^5}$

解法

基本的にはスライドを参照すればよいが、ここで簡単におさらいする。

記法 : 以下 ${x[i]}$ の最大値を ${U}$ とする。

${O(N^2 \log U)}$ 時間解法

まずは二分探索したいので、移動速度の上限 ${s}$ を決め打ち、ある上限速度 ${s}$ ですべての花火が点火されるかを判定する問題を解くことにする。この問題もそれなりに難しく、正当性を確かめるのに少し苦労はするが、次のような結果を得る。

まず、 ${L \leq K \leq R}$ となる ${L,R}$ を用意する。
このとき、区間 ${[L,R]}$ に入るすべての人に花火をつけるためには ${(x[R] - x[L]) / (R - L) \leq 2sT}$ である必要がある。

逆にこれを達成するためには、 ${L=R=K}$ からはじめて( ${L}$ をデクリメント) or ( ${R}$ をインクリメント)のどちらかの操作を繰り返し、上記式を常に達成できれば良い。

つまり、すべての ${L,R}$ について ${(x[R] - x[L]) / (R-L) \leq 2sT}$ をチェックし、その結果をoxを用いてグリッドに書き込めば、
そのグリッドの左下から右上まで oのみを使って到達できるかどうかを判定する問題になる（下図参照）。

f:id:tokoharu-sakura:20170410224334p:plain

これで ${O(N^2 \log U)}$ 時間で計算できることがわかる。

${O(N \log U)}$ 時間解法（解説スライドにおける想定解法）

上記の解法に工夫を加えて ${O(N)}$ 程度に落とすために、まずは式変形をして、
${x[R] - 2sTR \leq x[L] - 2sTL}$ とする。
この式は非常に都合がよく、 ${X[i] := x[i] - 2sTi}$ とおけば
${X[R] \leq X[L]}$ で判定可能である。

これを眺めるとうまい性質がわかる（らしい）ので、それを用いると貪欲的に解けるという主張になる。
（あとはスライドを読んでください）

別解

ここからは考えた別解について説明していきます。
その際、書き込んだoxの性質についてみていきます。

oxの並び方の観察

まず、次の性質が簡単に示せます。

性質1 : 次の図のような配置はありえない。

証明はXを用いれば簡単にできる。
oxが書き込まれる条件を思い出せば
${X[j_2] \leq X[i_2]}$ ,
${X[j_1] \leq X[i_1]}$ ,
${X[i_1] < X[j_2],}$
${X[i_2] < X[j_1]}$ が得られる。
これらをすべて足せば ${0< 0}$ が現れるため矛盾する。

次に、ある種貪欲的に進めてうまくいくことを示す。
そのために次の性質2を示す。

性質2 : まず、到達可能性を定義しておく。 ${(L,R)=(l,r)}$ に到達可能であるとは、 ${(L,R)=(K,K)}$ より始めて ${L}$ をデクリメントもしくは ${R}$ をインクリメントを続けて、x印を通らずに ${(L,R)=(l,r)}$ に到達できることと定義する。
仮に、 ${(L,R)=(i,j)}$ が到達可能かつ、 ${(L,R)=(i,j+1)}$ が到達不可能であるとし、さらに ${i}$ より小さい ${t}$ に対して ${(L,R)=(t,j+1)}$ にo印であったとする。この ${t}$ は最小(図で考えると一番上)のものをとることにする。
このとき ${(L,R)=(t,j+1)}$ に到達可能であることが言える。
特に、下図の赤印のような関係になっていることが言える。

この証明は性質1を用いればできる。つまり、図の赤o印の箇所を ${(i_2,j_1)}$ とおき、 ${j_2=j+1}$ とおく。 ${i_1}$ は ${(i_1,j_1)}$ がo印になっているようにとる。
このとき、性質1より

ox
xo

のような位置関係は禁止されているが、
上記のように ${i_1,i_2,j_1,j_2}$ を定めれば

ox
?o

のような位置関係になっていることがわかる。
性質1より'?'はo印にしかなりえない。
これを繰り返せば赤印のような箇所にo印をつけることができるため、
結局 ${(t,j+1)}$ も到達可能であることがわかる。

アルゴリズム

さて、以上の性質2を使えば、次のような遷移をして右上マスに到達すればOKであることがわかる。

最初は ${(L,R) = (K,K)}$ とする

o印である限り、 ${L}$ を減らす(上へ進む)

Rをひとつ増やす。

もしoであれば上記のように ${L}$ をできるだけ減らす

そうでなければ ${L}$ を増やして(つまり下に進んで)o印が書かれている箇所を見つける(性質2より、これをみつければ必ず ${(K,K)}$ から到達可能。)

もしそのようなo印がなければ失敗。最初に定めた制限速度 ${s}$ では不可能であることがわかる。

最後に ${(L,R)=(1,N)}$ に到達すればOK

要するに、各 ${R=r}$ に対して到達可能な ${(L,R)=(l,r)}$ である ${l}$ のうち最小のもの（一番上にあるもの）を求めていることになる。

単純に進めるだけでは時間計算量の上界は ${O(N^2)}$ であるが、 ${N^2}$ 回程度の移動回数を必要とするような入力はこのアルゴリズムに気づかなければ構成が難しい。
ということで最悪で ${O(N^2)}$ 時間かかるコードを実装して提出してみたが、春合宿で用意されたデータセットすべてに正答することができた。

改良アルゴリズム

さて、改良できそうな箇所は最も近いx印の場所を求めたり最も近いo印の場所を求めることである。

これは次のようなアルゴリズムで実現可能である。
都合上片方のケースのみで考えるが、問題は次のように言い換えるとわかりやすい。

「配列 ${X}$ とインデックス ${i}$ が与えられる。ただし ${X[R] \leq X[i]}$ であるとする。
${i}$ より小さい ${j}$ のうち、 ${X[R] > X[j]}$ となるような最大の ${j}$ を求めよ。」

これは次のようなデータ構造を持てばできる。
例えば最小値を持つRMQを用いて二分探索のようなことをする。
まず ${O(\log N)}$ 個くらいの調べたい範囲を持ってきて、それぞれの最小値を調べる。
これらの中ではじめて最小値が ${X[R]}$ を下回る箇所を持ってくる。
この範囲で、segment tree上で二分探索をすればできる。
これは1クエリあたり ${O(\log N)}$ 時間で計算できる。

この解法から現れる上位問題

さて、ここまででtokoharuの考えた別解を紹介しましたが、想定解法のアルゴリズムをちゃんと理解している人であれば想定解法の方が好ましいと考えるかと思います。なぜなら想定解法の方が（たぶん）シンプルにほぼ線形時間アルゴリズムを構築できるからです。

とはいえ、この別解からは面白いことがわかります。
それはSparklersの上位問題が解けてしまうからです。

ここで上位問題の問題文を記述することにします。強調した部分以外は同じ文章になります。

${N}$ 人の人が一直線上に並んでおり、それぞれの人が一つずつ花火を持っている。
それぞれの花火に火はついていない。
誰か一人が時刻 ${0}$ に自分の花火に着火する。
花火を持っている人と花火を持っていない人が同じ時刻に同じ場所にいれば花火を持っていない人に花火を着火することができる。ただし、同時刻・同場所にいても花火を着火させないこともできる。
それぞれの花火は着火後 ${T}$ 秒で消えてしまう。
それぞれの人の花火は1度までしか着火できない。
次のことができる各人の移動速度の上限 ${s}$ として最小のものを求めよ : 時刻 ${0}$ より適切にそれぞれの人を移動させることによって、それぞれの人の花火が一度点火される。

太文字で強調した通り、 ${K}$ が消えてしまい、スタートが誰でも良くなってしまい、難易度が上がります。
しかし別解と同様の方針で考えればこの問題でも解くことが可能です。

これを確かめるために、もう一度「性質1」と「性質2」を確認してみます。
よく考えるとこの二つの性質は図を180度回転しても成立することがわかります。
つまり、性質2で出てきた到達可能性について ${(L,R)=(1,N)}$ を始点としても同様の性質が成り立つことがわかります。

これがわかると、次の図のような到達可能性を調べればよいことがわかります。
f:id:tokoharu-sakura:20170411005130p:plain

この180度回転バージョンでは、各 ${R=r}$ について、到達可能な ${(L,R)=(l,r)}$ の中で最大のl（一番下のo印）を求めることになります。
そして、これが ${l=r}$ となるグリッドに到達すればOKということになります。

まとめ

Sparklersはより上位の問題に拡張できました。やったね！

2016-12-07

競プロとLP双対まわりの話で最近知ったこと

こんにちは。tokoharuです。

これは
Competitive Programming （その2） Advent Calendar 2016 - Adventar
の12/7の記事です。

問題も稀にしか確認しなくなりましたが最近得た知見をここで報告・宣伝しておきます。少々マニアックな記事です。

概要

私のtwitter(鍵)を確認している人はご存知かもしれませんが、二年前に公開したドキュメントhttp://tokoharu.github.io/tokoharupage/docs/formularization.pdfを改訂しました。内容はフローとかLPとか双対とかそのあたりの話です。元々は自分だけ読めればよかったものを少しずつ他の人に読めるものに変えている途中なのでまだまだ読みにくいかもしれません。特にLPとかの話は情報系学科の人でも触りくらいしか知らないでしょうし...

それから最初のほうにLPを用いた細かな話をしているので挫折する方もいるかもしれませんが、Project Selectionあたりの話はちょっと毛色が異なるし、おそらくこのドキュメントで最も実用的な箇所なのでそこを読むのがよいと思います。

知見1（最小費用流問題の双対っぽい問題への対処）

LP双対をとって最小費用流問題に帰着させるような問題は双対という操作を覚えないといけないし、操作を間違えやすい意味で厳しい問題という印象でした。しかし、最近yosupoさんの力を借りることでいい感じに解釈して辺を張ることに成功したかと思います。
この考え方をマスターすれば、例えばHow to create a good game(AOJ-ICPC 1100点, 2016/12/6現在)の解法を紙を使わず頭の中だけで構築することも可能かと思います。

知見2（牛ゲーの罠）

書いた文章をもう一回読んだり検証したりして気づいたのですが、
AOJ0304はデータセットが甘いっぽいことに気づきました。
今後こういう問題を作るときはこういうケースを仕込んでおいてガンガン落としていきたいですね。
詳しくはこの記事をご覧ください :
tokoharuland.hateblo.jp

今後

最近はフローで解くと部分点でさらに深い洞察を踏まえることで高速なアルゴリズムを導く系統の問題が増えてきたような気がします。そういう問題は結局はフローの特殊ケースであるといえることもあり、こういうのもいずれ体系立てれたりしないかなぁと思ったりしますがそんなにちゃんと考えてないです。背後に何かいい感じのものがあったりしないかなぁ。

今年の JOI2016 春合宿「最悪の記者2」, KUPC2016 H「壁壁壁壁壁壁壁」なんかの問題はこの意味で非常に興味深いですし、作問者の方は素晴らしい問題をありがとうございます。この系統でいくとhttp://codeforces.com/contest/724/problem/Eもですね。この辺は深く理解したいですね。

次のアドベントカレンダー担当者

明日はskyさんとyosupoさんですね。

skyさんとは長い付き合いのはずなのにあまり話してない気がするのですが、
きっと彼の印象に残ってるイベントとぼくの印象に残っているイベントはかぶってる気がするので楽しみです。

yosupoさんは言わずもがなで、どんなネタを提供してくれるのか楽しみです。

2016-12-01

AOJ0304がコーナーケースを入れ損ねてるっぽい話

競プロとLPまわりの記事 :
github.com
をupdateしたくなったので色々整理しているとこういう話になっているっぽいことを確認しました。

まず、次のふたつのACされたコードを用意します。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1197971#1と
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1270321#1

これらに

5 4
1<=2-2
4>=3-2
5>=4-1
5>=3+4

の入力を与えるとき、前者はinf,後者は-1が出力されます。

入力に対する解説をすると、
始点1から到達不可能な点であっても負閉路が検出されるときは
validな配置が存在しないため-1になるべきということです。

それぞれのBellman-Ford法を眺めてみると、
前者の実装では始点以外INFで初期化をしてINFがあれば更新をしないのに対し、
後者の実装では始点以外INFで初期化をしたもののINFがあっても更新をしています。
この差が反映されて出力の差異が発生しています。

これらのコードが両方ACされているため、
ジャッジケースにはこういうコーナーケースは入っていないのだと思われます。
今後、類題が出題される、もしくは類題を出題するときには気をつけたいところです。

2015-11-22

2015 JAG Regional J : Longest Shortest Path

原案出しました。
この問題は考察が非人道的ですが、壁を突破した後にたどり着く解法は美しいものです。

今回は感想や小話を書いたり、中の人の議論ページにあるのをちょっと編集して貼り付けます。

感想や小話

解法を知りたい人はもう少し下を眺めてください

提案直前

モチベーションとして、LP双対をとる問題を作りたかった
手本ポジションにHow to create a good gameという問題があるので、この問題と似たような状況で双対とって遊んでいれば面白そうなので遊ぼうとなる
できた
下記解法(1)が見えたのでとりあえずMi_Sawaさんに相談
確かに双対をとった結果は同じということを確認し、解法(2)とかで解けますねーみたいな話をされる
- これはちゃんと理解できていなかったのでとりあえずそっちはMi_Sawaさんに任せることにする
簡単な例題を解いて照合するうちに変数yが1/nばかりをとることに気づく。
これに沿って変形することで費用流一回で解けそうな何か(3)が錬成された
Mi_Sawaさんに投げるとしばらくしたら証明してくれた。さすが。

8月

とある日、だらだら5時とかまで起きてた
寝ようとしたらGCJ World Finalの現地にいるMi_SawaさんからD問題を読めとの連絡が来る
眠いけど読むとどうも今回のJ問題と非常に類似するとわかり目が覚めてくる
アイデアが同じだとほぼ類題になるので棄却の危機を感じる
と思って解説フェーズの動画を見るとよくわからん操作をしていて安心した

作問準備

C++では下記(1),(2),(3)の解法はAtCoder上で通った。それぞれ(5sec, 5sec, 0.1sec)
妙に辺数が多いのはSimplex法( algorithm/SimplexMethodLP.cc at master · spaghetti-source/algorithm · GitHub)が思いのほか高速だったため。
- M=1000程度でも下手すると通るのではぐらい速度。Simplex法恐ろしい
- という事情でM=2000.
- ここまでやるとようやく30秒では終わらなくなったので呪縛から逃れる。
その代償として、c,dの最大値を極限まで減らした。
- これはパス反復法の理論計算量を考えた時に、制約最大値を代入をしてもそこそこ信用できる程度の量にするため。
ちなみに代入すると4億でした。実際には0.1secで終了します。
- このギャップを埋める入力は良く知らないので詳しいことをご存知の方は教えてください。

終わった後の感想など

やーさんめっちゃ説明うまい。
- 「グッと睨むと」みたいなフレーズの選び方がうまいなぁと思った
なかなか解けないよね…とは思った。
- とはいえ解く可能性のあるチームは考えていて、
- 先述のGCJ-WF進出者のsemiexpはワンチャン行けるんじゃないの
- 直前にsigmaさんのHow to create a good gameを解いた記事を読んでいたので行けないかな
- とか思っていました
やっぱりこの解法(3)の直感的理解がわからん。なんやねんこれ
台湾はまさかの(3)で解いたので頭良すぎと思った
- 彼らにはそこまで理解できているのか
- もしかして何か論文かなんかあるとか？

議論ページの解法などまとめ

貪欲っぽいのを落とす入力

4 5 L 1 4
1 2 2 2
1 3 4 4
2 3 1 1
2 4 4 4
3 4 2 2

L=1の場合、最適値は6. 2->3の辺の長さを1増やす
L=2の場合、最適値は6+1/3. 1->2と3->4の辺の長さに1/3足して2->3に2/3足す
L=5の場合、最適値は7+1/4. 1->2と3->4の辺の長さに5/4足す

このように、ある辺を一旦増加させても、Lを増やせば減少させる方がよいケースがある。
なので、そのような仮定に基づくアルゴリズムは落とされる。

これをある程度突破できる嘘解法はある？

解法

この問題で求めたいのは max_x min (辺にxの距離を足したs-tパス長)。
とりあえずmin...に対して双対をとるといわゆる牛ゲーになり、全体としてmaxだけでかける

(P1)
max p_t - p_s
s.t. p_u - p_v <= d_e + x_e
sum c_e x_e <= L
x_e >= 0
さらに双対をとる
(P2)
min (sum d_e f_e) + y L
s.t. fはs->tに1流れるような流量保存則を満たす
c_e y - f_e >=0
f_e, y>=0
これでほぼ最小費用流の形が出る。

ここからいくつかの方針が考えられる。

(1) (P2)のyを固定したときの最適値をg(y)とおけば、
元の問題がLPであることを考慮すればg(y)は凸関数。
また、g(y)は最小費用流で求められる。 ~
最適解は0 < y <= 1に入ることを確認してから(これは証明の意味で。実際y=1であればもとの最短長に+Lする状況になるので、それは長すぎる。)三分探索をする。

(2)
ここの欄はMi_Sawaさんが書いてくれる予定です -> 詰めきったら (3) と同じになりました... (途中で考察を止めるといちおう少し違う形になるので書いておきます)
(P1)
max. p_t - p_s
s.t. p_u - p_v <= d_e + x_e
sum c_e x_e <= L
x_e >= 0

であった.

答えの値を T 以上にできるかで二分探索することにすると,

(P1')
max. 0
s.t. p_u - p_v <= d_e + x_e
sum c_e x_e <= L
p_s - p_t <= T
x_e >= 0

を得る. sum c_e x_e <= L を満たせるかで判定問題にすることにして,

(P1'')
max. -sum c_e x_e
s.t. p_u - p_v <= d_e + x_e ... 双対変数 f_e
p_s - p_t <= T ... 双対変数 α
x_e >= 0

と -L との大小を比較し, -L 以上な最大の T をとればよい.

双対をとると,

min. -αT + sum f_e d_e
s.t. f : s-t に α 流れるフロー
0 <= f <= c
0 <= α

だから, 容量 c, コスト d のグラフで, 単位流量あたりにコストが T 以下である間フローを流し,
(フローのコスト) - (フロー量)*T と -L との大小を比較すればよい.
この時の (flow, cost) は, CostPerformanceFlow の時の折れ線の折れている部分になる.

(flow, cost) な点で cost - flow * T を -L 以上にできるのは, T <= (cost + L) / flow のとき.
よって, 各点で min((cost+L)/flow, s-t shortest path) を取り, その max が答え.
さらに詰めると, 結局とこはるさんのと同じになる.

(3)
(P2)が出たところからさらに考察を進める。
yを 1/mで置き換え、f_eをf_e/mで置き換える。
これを整理すると
(P3)
min (sum d_e f_e + L) / m
s.t. fはs->tにm流れるように流量保存則を満たす
c_e >= f_e
f_e >= 0 , m > 0
f(m) := ((P3)の条件でのmin (sum d_e f_e + L) の値)とおけば
これはm流す最小費用流の最適値にLを足したものなので、区間で線形に増える。
したがって、f(m)が線形で増える区間[l,r]でf(m)=am+bであったとすると
f(m)/m = a + b/mより、最小値をとるとすれば端点(m=l,r)である(m=0はムシ)

なので、折れ線の端点のみの結果を見て比較すればよいので次をすればよい。

容量c, コストdの最小費用流に対する最短路反復法(Primal Dual)を走らせる
1反復ごとに(P3)の目的関数値をチェック
それらの最小値が答え

その他

この問題のおもしろいところは、

(3)の解法で出てくるグラフの容量は元のグラフのコストとなり、コストは元のグラフの距離となり、
逆のように感じるような設定になっているところ。

春コンのCost Performance Flowと似てる部分がそこそこある?
ぱっと見て最短路反復法と思える人はいるか？いるとすればどのくらい思いつきやすいか？

GCJ WF 2015 D にて類似の問題が出題されました(https://code.google.com/codejam/contest/5224486/dashboard#s=p3 )が、解説映像を見る限り少し違う方針に見える
公式analysisはまだ(9/15) : https://code.google.com/codejam/contests.html
準急さんが卒業してから出題するという説？