とこはるのまとめ

多分考えたことがまとまっているはずです。きっと。おそらく。

TCO2017 Semifinal2 500 RatingProgressAward

前回の続きです。

前回はいろはちゃんの疑問に答えたつもりでしたが、聞いてみたところ違った問題のことを指していて、表題の問題だったようです。
link :TopCoder Statistics - Problem Statement
今回もProjectSelectionProblemを経由して解いていきたいと思います。

問題概要

  • 授業をN課程とります。
  • 順番は任意でよいですが、1課程ずつ順番に受講しなければなりません。
  • 課程b[i]を受講するためには、すでに課程a[i]を修了している必要があります。
  • 最初のレーティングは1200です。
  • 課程iを受けるとratingが += change[i]だけ変動します。
  • k個の課程受けた直後のratingをv[k]とします。k=0なら初期値です。
  • このとき、Rating Progress を max( { v[i] - v[j] | i > j } )と定めます。
  • 受講する課程の順番をうまく選ぶことでRating Progressのありうる最大値を求めよ。

解法

問題の言いかえ

この問題はある種のProjectSelectionProblemっぽくみえます。「ぽい」と表現した理由は、次のような問題に言い換えてProjectを定めることはできるものの、ProjectSelectionProblemのフレームワークに適用できない形だからです。

ProjectをN個用意し、それぞれのProjectは proj[i]=0,1,2のように3値をとれるものとします。
このとき、a[i]からb[i]に到達可能ならproj[a[i]] >= proj[b[i]]を満たさなければならないとき、
proj[k]==1となるProject kに関して、change[k]の総和を最大化せよ。

これをどうにかProjectSelectionProblemに適用しようと思っても、「ならば」の制約がうまく入らないためどうにもうまくいかなさそうです。この「ならば」がうまくいかないのは1,2の間の「ならば」と0,1の間の「ならば」が共存できないことに由来しそうなので、この二つの制約を分離することをこれから考えていきます。

Projectの定義

その結果、次のような2N個のProjectを作ってみることにします。

最初のN個 :

  • B(ベース)に属する <=> 0に属する
  • Aに属する <=> 1,2に属する

残りのN個 :

  • B(ベース)に属する <=> 0,1に属する
  • Aに属する <=> 2に属する

ただし、それぞれの種類のProjectで、最初からi番目が課程iに対応するものとします。

最後に得たい答えの求め方

このとき、どうすれば1に属する利得を計算できるかですが、最初のN個でAに属するProjectと、残りのN個でBに属するProjectのchangeの総和を足し、最後にchange[i]の総和で引けばよいです。(ちょっとトリッキーですね)

制約

次に制約を考えます。考える制約は二種類です。

  • 課程の順序制約

これはb[i]がAに属すればa[i]がAに属す制約でよさそうです。だからフロー用グラフにb[i]からa[i]に∞容量の辺を張ります。この制約はどちらの種類でも共通です。

  • 2つのプロジェクトの整合性制約

本来1つのProjectと扱いたいものを2つのProjectに分離しました。ここの整合性がとれていなければいけません。具体的には、前者でBに属し、後者でAに属している場合に0かつ2に属して矛盾となるためこれを避けたいです。したがって、後者のプロジェクトがAに属している場合に前者のプロジェクトはAに属している必要があります。だから N + b[i] からa[i]に∞容量の辺を張るような感じになります。

利得

次にProjectSelectionProblemの構成要素として利得があるのでこれを考えます。

これはBに属しているときから見た、Aに属したときの相対的利得になります。
最初のN個はBにいるときにchangeをカウントせず、Aにいるときにchangeをカウントしたいです。だから最初のN個の利得pはchangeそのままです。
一方、後のN個はBにいるときにchangeをカウントし、Aにいるときにchangeをカウントしません。だから後のN個の利得pは正負が反転して-changeになります。

ここまでで最大流のグラフを作り終えることができました。

最大流を除いた部分の整理

最後に、最大流の外側で計算する部分について整理します。

  • ProjectSelectionProblem内部での総和部分

これは利得のうち、正であるものの総和なので、 abs(change[i])の総和になります。

  • ProjectSelectionProblemのBに所属させる際に発生する利得。

これは後者のProjectで発生します。これはchange[i]の総和です。

  • ProjectSelectionProblem外部でもともと解きたい問題の答えを得る。

これは以前説明した通り、change[i]の総和を引きます。

これら3つを合計することで、 abs(change[i])の総和を事前計算しておけばよく、結局 sum(abs(change[i])) - maxflow(s,t) が答えになります。

コード

以上のまとめとして、ACしたコードの一部を載せます。max_flowのライブラリを持っていると仮定し、add_edge(v,u,c)はフローを流したいグラフに対してvからuへ容量cの辺を張ることを指します。

int RatingProgressAward::maximalProgress
(vector <int> change, vector <int> a, vector <int> b) {
  int N = change.size();
  int ans = 0;
  int s = 2 * N, t = s + 1;
  for(int i=0; i<N; i++) {
    ans += abs(change[i]);
    add_edge(i+N, i, INF);
    if(change[i] > 0) {
      add_edge(s, i, change[i]);
      add_edge(N+i, t, change[i]);
    }
    else {
      add_edge(s, N+i, -change[i]);
      add_edge(i, t, -change[i]);
    }
  }
  int M = a.size();
  for(int i=0; i<M; i++) {
    add_edge(b[i], a[i], INF);
    add_edge(N + b[i], N + a[i], INF);
  }
  int ret = max_flow (s,t);
  return ans - ret;
}

個人的には割ときれいなグラフだと思っています。

本番でACされたコードを貼っておきます(要Login)。
tourist https://community.topcoder.com/stat?c=problem_solution&rm=330662&rd=17017&pm=14719&cr=22263204
ikatanic https://community.topcoder.com/stat?c=problem_solution&rm=330662&rd=17017&pm=14719&cr=22711754

全く違いますね。ちゃんと読めていないのでわからないですが、もっと簡単な考え方もあるのかもしれません。何かご存知の方がいらっしゃれば教えていただけると幸いです。

コメント

こうして出されてみると難問でしたが、考察の流れを考えれば拡張が容易にできそうにも見えます。
というのも、今回は 2 > 1 > 0にわけた領域のうち、それぞれの利得の重みを0,1,0としたような問題でしたが、これはp,q,rみたく係数をつけて一般化できそうに見えます(本当にできるか未チェック)。
こういう想像が働くようないい感じの解が得られて割と満足です。

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

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

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

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

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

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

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

これの解法ですが、まず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つに分ける問題も扱えます

『燃やす埋める』と『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で出た問題ではこういうハマり方をしている方がいました。

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

まとめ

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

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'}を構成しようと思うと、
分離超平面を構成する必要があります。
これを今回の大きさの行列に適用するのはしんどいので、特別な性質があればよいのですが、
ぱっとはわかりませんでした。

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

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 : 次の図のような配置はありえない。
f:id:tokoharu-sakura:20170410224338p:plain

証明は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)}に到達可能であることが言える。
特に、下図の赤印のような関係になっていることが言える。

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

この証明は性質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はより上位の問題に拡張できました。やったね!

競プロと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さんは言わずもがなで、どんなネタを提供してくれるのか楽しみです。

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されているため、
ジャッジケースにはこういうコーナーケースは入っていないのだと思われます。
今後、類題が出題される、もしくは類題を出題するときには気をつけたいところです。