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みたく係数をつけて一般化できそうに見えます（本当にできるか未チェック）。
こういう想像が働くようないい感じの解が得られて割と満足です。

とこはるのまとめ

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