WARush

SRMの結果とか、解けた問題のコードを書いていきます

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の日記

全員が!
f:id:Ekaing:20130601003300j:plain
Receiveするまで!
f:id:Ekaing:20130601010440j:plain
僕は!
f:id:Ekaing:20130601003342j:plain
叫ぶのを!
f:id:Ekaing:20130601003356j:plain
やめ!
f:id:Ekaing:20130601003410j:plain
ない!
f:id:Ekaing:20130601003422j:plain
というわけで、Receiveする人を左右に伸ばしていく感じになります。

誰が叫べば全員がReceiveしたことになるでしょうか?左側は、最も左の t と同じかさらに左のsを持つものが、右側は、最も右の s と同じかさらに右のtを持つものが叫べばそれぞれよい事になります。
f:id:Ekaing:20130601003926j:plain


ここで問題です。Receiveした人が下図のような時に一体誰に叫ばせればいいのでしょうか?
f:id:Ekaing:20130601003628j:plain

答えはこんな感じで
f:id:Ekaing:20130601003645j:plain
f:id:Ekaing:20130601003700j:plain
最も左または右に伸ばせる人に頼めばよいのです。

よって、あらかじめ次誰に頼むよリストを作っておいてから、それぞれの人で叫ぶ回数を数えていけばよいです。
誰に頼むよリスト(左判)
f:id:Ekaing:20130601004211j:plain
誰に頼むよリスト(右判)
f:id:Ekaing:20130601004333j:plain

ところで、まだ目標に届いていないのに、一番左へ(または右へ)伸ばせるのが自分自身だった場合、これは全員にReceiveさせることが無理なので、-1を返せばよいです。
f:id:Ekaing:20130601004538p:plain


これでOKかと思いきや下図の場合を考えてみてください。
f:id:Ekaing:20130601004621p:plain
右と左でそれぞれ違う人に叫んでもらうと2回かかりますが、
一番上の人に頼めば1発でやってくれる訳です。

つまり、自分自身をすっぽり覆う人がいた場合、説明したセオリーが通じない可能性がでてきます。しかし、最初の一回だけ、すっぽり覆う人を試して、後はセオリー通りやればよいです。なぜなら、自分自身以外をすっぽり覆っているやつがあっても、それはソイツがただ単により左に(または右に)伸ばせる人になるだけだからです。
f:id:Ekaing:20130601005210p:plain

自分を含んで入れ子になっていたら、範囲を大きいほうをとればいいだけです。
f:id:Ekaing:20130601005423p:plain


つまり、最初に一回だけ、自分をすっぽり含んでるやつを全部試せば良いと言う事です。なので、まずセオリー通りに全員試しておいて、すっぽり含んでいるやつを試すときはそれに+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;
    }
};