Hatena::Grouptopcoder

ぷろこんメモ用紙

 | 

2011-02-02

SRM496 Div1

00:04

青くなってしまったのでなんとしてでもレーティングを上げたい回。

ox- +50 277.23pts / 196th

1415→1516とまさかの黄色復帰。やったー!

250 ColoredStrokes

平面上に、水平方向に赤い線、垂直方向に青い線を引く。交点は緑になる。最終的な盤面が与えられるので、最小で何本の線を引くとこの盤面を作れるか。

RとGが水平方向に連続している限りは一本線を引けばいいので、その数をカウント。このとき、GにぶつかったらBに置換しておく。

次に垂直方向でBの本数を数えればおしまい。Div1Easyにしては簡単。

struct ColoredStrokes {
    int getLeast(vector <string> picture) {
        int H = picture.size();
        int W = picture[0].size();

        int cnt = 0;
        for(int r = 0; r < H; ++r) {
            bool on = false;
            for(int c = 0; c < W; ++c) {
                if(picture[r][c] == 'R' || picture[r][c] == 'G') {
                    on = true;
                    if(picture[r][c] == 'G') picture[r][c] = 'B';
                }
                else {
                    if(on) ++cnt;
                    on = false;
                }
            }
            if(on) ++cnt;
        }

        for(int c = 0; c < W; ++c) {
            bool on = false;
            for(int r = 0; r < H; ++r) {
                if(picture[r][c] == 'B') {
                    on = true;
                }
                else {
                    if(on) ++cnt;
                    on = false;
                }
            }
            if(on) ++cnt;
        }
        return cnt;
    }
};    

500 OneDimensionalBalls

一次元の直線上に点がいくつかあり、全ての点は同じ速さで運動している(向きは正も負もある)。ある瞬間に点の位置を記録し、点の数を適当に増やしてから一定時間後にもう一度点の位置を記録した。このとき、二つの記録から、最初の点が二番目の点のどれと対応するかを割り出したい。ありえるパターン数を答えよ。

最初の点と二番目の点の各ペアに対して移動距離を求め、同じ移動距離の中から適当に組み合わせを選べばいいんだなー、と理解。でも普通にやると50*50マスで50Queenを解く感じになってむりぽ……。

ちょっと考えて、一行で選べる場所は高々2マスであることに気づく。これならdfsでなんとかなるんじゃないか?と思って実装。しかし、なるべくどの点についても候補が2マスになるようにデータを作って食わせるとTLE。よく考えると250DFSになるから確かに無理っぽい。

それなら、ということで過去に使われた点を記録してキャッシュを取ってみる。これもだめ。

こんな感じでいろいろ定数倍高速化を試してると、最後2分くらいで自分の使ってたデータには1.8秒くらいで答えを返すのができた。もうこれでいいやーとSubmit。そのあと少しデータを変えて試してみたらあえなくTLEだった。

正攻法だと、候補がダブってる点をひとまとめにして扱い、二部マッチングのパターン数を数えるらしい。しかも、今回はグラフの性質上、左の個数と右の個数から簡単にパターン数が計算できる。これを全部かけ算すればおしまい。

以下、Practiceで通したコード。

struct OneDimensionalBalls {
    int getroot(int i, vector<int> &roots) {
        if(roots[i] == i) return i;
        else return (roots[i] = getroot(roots[i], roots));
    }

    bool unite(int i, int j, vector<int> &roots, vector<int> &levels) {
        i = getroot(i, roots);
        j = getroot(j, roots);
        if(i == j) return false;

        if(levels[i] < levels[j]) {
            roots[i] = j;
        }
        else {
            roots[j] = i;
            if(levels[i] == levels[j]) ++levels[i];
        }
        return true;
    }

    long long countValidGuesses(vector <int> firstPicture, vector <int> secondPicture) {
        int N = firstPicture.size();
        int M = secondPicture.size();
        vector<vector<int> > v(N, vector<int>(M));

        for(int i = 0; i < N; ++i) {
            for(int j = 0; j < M; ++j) {
                v[i][j] = abs(firstPicture[i]-secondPicture[j]);
            }
        }

        long long ans = 0;
        set<int> d_history;
        for(int i = 0; i < M; ++i) {
            int d = v[0][i];
            if(d == 0) continue;
            if(d_history.count(d) > 0) continue;
            d_history.insert(d);

            vector<int> roots(N), levels(N, 0);
            vector<set<int> > to(N);
            for(int i = 0; i < N; ++i) roots[i] = i;

            for(int j = 0; j < M; ++j) {
                vector<int> samegrp;
                for(int k = 0; k < N; ++k) {
                    if(v[k][j] == d) {
                        samegrp.push_back(k);
                        to[k].insert(j);
                    }
                }
                for(int k = 1; k < samegrp.size(); ++k) unite(samegrp[0], samegrp[k], roots, levels);
            }
            vector<bool> used(N, false);
            long long sum = 1;
            for(int j = 0; j < N; ++j) {
                if(used[j]) continue;
                set<int> tonodes;
                int fromcnt = 0;
                int linkcnt = 0;
                for(int k = j; k < N; ++k) {
                    if(getroot(j, roots) == getroot(k, roots)) {
                        linkcnt += to[k].size();
                        tonodes.insert(to[k].begin(), to[k].end());
                        fromcnt++;
                        used[k] = true;
                    }
                }
                //パターン数を計算
                if(fromcnt > tonodes.size()) sum *= 0;
                else if(fromcnt == tonodes.size()) {
                    if(linkcnt < tonodes.size()*2) sum *= 1;
                    else sum *= 2;
                }
                else sum *= tonodes.size();
            }
            ans += sum;
        }

        return ans;
    }
};

Challenge Phase

自分とほぼ同じDFSを書いていた人がいたのでTLEで撃墜。もうひとり怪しげなのがいたけど、コード読んでるうちに落とされてしまった。他にも二人いたけど迷って結局チャレンジせず。どっちもSystem Testで落ちていたので攻めればよかった……

 |