SRM580 Div1 Medium 「ShoutterDiv1」
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12576
訳
新入生であるウサギ達はウナギクラブに入った。このグループには誰一人、知り合いはいなかった。昨日、初めてウサギ達はクラブに参加した。あなたはintのsとtが与えられる。s[i]はi番目のウサギがクラブに顔を出した時間であり、t[i]はi番目のウサギがクラブを立ち去った時間である。
それぞれのウサギのペアは、同じ時間にクラブにいれば、お互いを知る事になり、彼らは"Shoutter"というソーシャルネットワークサービスで友達登録をする。瞬間に一緒にいることになったケースでもこれは当てはまる。(例えば、一匹がクラブに入り、一匹がその瞬間クラブを出た場合でも)
"Shoutter"にて、そのユーザーは短いメッセージをいつでも叫ぶことができる。その叫びは友達であれば読むことができる。友達は叫びを再投稿する事ができ、再投稿した人の友達は叫んだ人の友達でなくとも、その叫びを読むことができる。その時、彼らはさらに再投稿する事ができ、それは続いていく。
叫びは好きなだけ再投稿する事ができる。ウサギが叫びを複数回再投稿したいときは、別々に行わなくてはならない。
今日、ウサギたちは各自、"Shoutter"で自己紹介を投稿した。各ウサギは他全てのウサギ(現在友達でないものも含め)の自己紹介を読みたい。最小何回の再投稿が必要なのかを計算し、返せ。もし不可能であれば-1を返せ。
あなたはString s1000, s100, s10, s1が与えられる。全てのs1000を連結し、S1000とせよ。s100, s10, s1についても同じように連結しS100, S10, S1とせよ。i番目の文字はi番目のウサギに対応する。具体的にはS1000[i] + S100[i] + S10[i] + S1[i]と連結しそれを整数に変換する。例えば、S1000[4]='0', S100[4]='1', S10[4]='4', and S1[4]='7'であれば4番目のウサギのクラブに入った時間は("0147") = 147となる。t1000, t100, t10, t1についても同じようにせよ。
制約
1 <= ウサギの数 <= 2500
0 <= ウサギが部屋に入った時間、出た時間 <= 9999
考えた事(アホゥ)
ウサギが50匹か~。じゃあワーシャルフロイドしてそれの一番最長のやつ-1でいいんじゃないかなぁ(マジ謎)。
あれ?ウサギは実は2500匹か~。じゃあトポロジカル順序にして2部グラフで最大流とかかなぁ(もっと謎)
という具合に悪い方向に深みにはまっていった・・・普通のグラフから考えが抜け出せなくなってギブアップ
解法(スライド風)
コチラを参考にしましたm(_ _)m
TopCoder SRM 580 Div1 Medium ShoutterDiv1 - simezi_tanの日記
全員が!
Receiveするまで!
僕は!
叫ぶのを!
やめ!
ない!
というわけで、Receiveする人を左右に伸ばしていく感じになります。
誰が叫べば全員がReceiveしたことになるでしょうか?左側は、最も左の t と同じかさらに左のsを持つものが、右側は、最も右の s と同じかさらに右のtを持つものが叫べばそれぞれよい事になります。
ここで問題です。Receiveした人が下図のような時に一体誰に叫ばせればいいのでしょうか?
答えはこんな感じで
最も左または右に伸ばせる人に頼めばよいのです。
よって、あらかじめ次誰に頼むよリストを作っておいてから、それぞれの人で叫ぶ回数を数えていけばよいです。
誰に頼むよリスト(左判)
誰に頼むよリスト(右判)
ところで、まだ目標に届いていないのに、一番左へ(または右へ)伸ばせるのが自分自身だった場合、これは全員にReceiveさせることが無理なので、-1を返せばよいです。
これでOKかと思いきや下図の場合を考えてみてください。
右と左でそれぞれ違う人に叫んでもらうと2回かかりますが、
一番上の人に頼めば1発でやってくれる訳です。
つまり、自分自身をすっぽり覆う人がいた場合、説明したセオリーが通じない可能性がでてきます。しかし、最初の一回だけ、すっぽり覆う人を試して、後はセオリー通りやればよいです。なぜなら、自分自身以外をすっぽり覆っているやつがあっても、それはソイツがただ単により左に(または右に)伸ばせる人になるだけだからです。
自分を含んで入れ子になっていたら、範囲を大きいほうをとればいいだけです。
つまり、最初に一回だけ、自分をすっぽり含んでるやつを全部試せば良いと言う事です。なので、まずセオリー通りに全員試しておいて、すっぽり含んでいるやつを試すときはそれに+1すればよいです。それらの最小値をとっていけば答えとなります。
ソースコード
int N; int s[2550], t[2550]; int L[2550], R[2550]; // L[i] i番目の人から1番左に伸ばせる人 Rは右 int max_s, min_t; // 最大のsと最小のt class ShoutterDiv1 { public: int count(vector <string> s1000, vector <string> s100, vector <string> s10, vector <string> s1, vector <string> t1000, vector <string> t100, vector <string> t10, vector <string> t1){ // 連結 N = s1.size(); string S1000, S100, S10, S1, T1000, T100, T10, T1; for( int i = 0; i < N; i++ ){ S1000 += s1000[i]; S100 += s100[i]; S10 += s10[i]; S1 += s1[i]; T1000 += t1000[i]; T100 += t100[i]; T10 += t10[i]; T1 += t1[i]; } // s, t初期化 N = S1.length(); max_s = -1, min_t = 10000; for( int i = 0; i < N; i++ ){ s[i] = (S1000[i] - '0') * 1000 + (S100[i] - '0') * 100 + (S10[i] - '0') * 10 + (S1[i] - '0'); t[i] = (T1000[i] - '0') * 1000 + (T100[i] - '0') * 100 + (T10[i] - '0') * 10 + (T1[i] - '0'); max_s = max( max_s, s[i] ); min_t = min( min_t, t[i] ); } // L, R初期化 for( int i = 0; i < N; i++ ){ int s_i = i, s_v = s[i], t_i = i, t_v = t[i]; for( int j = 0; j < N; j++ ){ if( t[i] < s[j] || t[j] < s[i] ) continue; // 重なってない if( s[j] < s_v ){ s_i = j; s_v = s[j]; } if( t[j] > t_v ){ t_i = j; t_v = t[j]; } } L[i] = s_i; R[i] = t_i; } // セオリー通りにとりあえずやる int res[2550] = {0}; // res[i] i番目の自己紹介が全員にいきわたるまでの最小リシャウト回数 for( int i = 0; i < N; i++ ){ int l = i, r = i; // 左方向に while( min_t < s[l] ){ if( l == L[l] ) return -1; // つながってない l = L[l]; res[i]++; } // 右方向に while( t[r] < max_s ){ if( r == R[r] ) return -1; // つながってない r = R[r]; res[i]++; } } // 覆ってるやつを使ってみる for( int i = 0; i < N; i++ ){ for( int j = 0; j < N; j++ ){ if( s[j] < s[i] && t[i] < t[j] ){ res[i] = min( res[i], res[j] + 1 ); } } } // 集計 int ans = 0; for( int i = 0; i < N; i++ ){ ans += res[i]; } return ans; } };