TCO2017 Semifinal2 500 RatingProgressAward
(UPD 12/24) 説明に誤りがあったので修正。
前回の続きです。
前回はいろはちゃんの疑問に答えたつもりでしたが、聞いてみたところ違った問題のことを指していて、表題の問題だったようです。
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 + i から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みたく係数をつけて一般化できそうに見えます(本当にできるか未チェック)。
こういう想像が働くようないい感じの解が得られて割と満足です。