Hatena::Grouptopcoder

ぷろこんメモ用紙

 | 

2011-02-20

Codeforces #56

22:55

春休みに突入したので久しぶりのCodeforces

oox-- 1340pts 233rd。

レーティング1695→1677。単調減少。

Cは解けてたのに変なバグ入れてしまった……。

A Where Are My Flakes?

問題開いて情報量なさそうなイラストが目に飛び込んできてちょっと戸惑う。実際関係なかった。

1列に並んでる箱のなかに当たりがあって、「〜より左」「〜より右」の形式のヒントが与えられるので、条件を満たす箱がいくつあるか数える問題。

箱の数は1000以下なので配列つくってシミュレーションするだけ。

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> v(N+1, 1);
    v[0] = 0;
    while(M--) {
        string to, the, dir, of;
        int idx;
        cin >> to >> the >> dir >> of >> idx;
        if(dir == "left") for(int i = idx; i <= N; ++i) v[i] = 0;
        else if(dir == "right") for(int i = 1; i <= idx; ++i) v[i] = 0;
    }
    int cnt = 0;
    for(int i = 0; i <= N; ++i) 
        if(v[i]) ++cnt;
    if(cnt == 0) cnt = -1;
    cout << cnt << endl;

    return 0;
}

B Serial Time!

問題文を理解するのに10分くらいかかる。

問題自体は単純で、3次元のグリッドを塗り潰して何マス塗れるか数えるだけ。問題のストーリーがどう絡んでるかはちゃんと把握してない。

inline bool inRange(int a, int x, int b) {
    return a <= x && x <= b;
}

int dfs(vector<vector<string> > &plate, int k, int r, int c) {
    const int d[][3] = { {-1, 0, 0}, {1, 0, 0}, {0, -1, 0}, {0, 1, 0}, {0, 0, -1}, {0, 0, 1} };

    int K = plate.size();
    int R = plate[0].size();
    int C = plate[0][0].size();
    int cnt = 0;
    for(int i = 0; i < 6; ++i) {
        int kk = k+d[i][0], rr = r+d[i][1], cc=c+d[i][2];
        if(inRange(0, kk, K-1) && inRange(0, rr, R-1) && inRange(0, cc, C-1) && plate[kk][rr][cc] == '.') {
            ++cnt;
            plate[kk][rr][cc] = '#';
            cnt += dfs(plate, kk, rr, cc);
        }
    }
    return cnt;
}

int main() {
    int K, N, M;
    cin >> K >> N >> M;
    vector<vector<string> > plate(K, vector<string>(N));

    for(int i = 0; i < K; ++i) {
        for(int j = 0; j < N; ++j) {
            cin >> plate[i][j];
        }
    }

    int R, C;
    cin >> R >> C;
    --R; --C;

    plate[0][R][C] = '#';
    cout << dfs(plate, 0, R, C)+1 << endl;

    return 0;
}

C Mushroom Strife

キノコの生えてる芝生と、それを繋ぐ道を描いた地図がある。道には両端の芝生に生えているキノコの数のGCDとLCMが書いてある。ある地図が与えられたとき、そのようなキノコの配置が有り得るか判定せよ。

GCDとLCMってことは掛け算して2数の積にしてからほげほげするんだろうなーとなんとなく予想がつく。で、ちょっと手で試してみると、一つの頂点の数が決まれば後はなし崩し的に決まっていくことがわかる。ということで、一つの頂点の数をどうやって決めるか。

ここでGCDとLCMが効いてくる。キノコの数は整数なので、GCDとLCMの約数になっているはず。しかしこの2数は最大で106と大きいため試し割りは無理なので、Project eulerでよくやる素因数分解から約数を求める手法を使う。

あとはハマリそうなコーナーケースを考える。

  • グラフが連結じゃないかもしれない→連結成分で分解してからそれぞれで答えがあるかチェックする
  • ループがあって、一周すると答えが合わないかもしれない→すでに埋めた頂点への道も見て、検算する
  • b=GCD*LCM/aが整数でも、GCD(a,b)が一致しないかもしれない(サンプル4がそのケース)→ちゃんと試す

書いた。サンプル通った。Wrong Answer on pretest5...

直らず時間切れ。

System test中にコードを見なおしてて気づく。素因数分解の割っていく条件、while(n%p==0)じゃなくてwhile(n%p)って書いてる!!!!これはひどい!

サンプルだと数が小さいので通ってしまうっぽい……。

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

typedef long long LL;

vector<int> primes;

LL gcd(LL a, LL b) {
    if(b > a) return gcd(b, a);
    while(b) {
        LL mod = a % b;
        a = b;
        b = mod;
    }
    return a;
}

void gen_primes(int n) {
    vector<int> bit(n+1, 1);
    primes.push_back(2);
    int lim = sqrt(n)+1;
    for(int i = 3; i <= n; i += 2) {
        if(bit[i]) {
            primes.push_back(i);
            if(i > lim) continue;
            for(int j = i*i; j <= n; j += i) bit[j] = 0;
        }
    }
}

void prime_division(LL n, vector<pair<LL,LL> > &facts) {
    for(int i = 0; i < primes.size(); ++i) {
        int cnt = 0;
        int p = primes[i];
        while(n % p == 0) {
            cnt++;
            n /= p;
        }
        if(cnt) facts.push_back(make_pair(p, cnt));
        if(n == 1) break;
    }
    if(n > 1) facts.push_back(make_pair(n, 1));
}

void divisors(const vector<pair<LL,LL> > &facts, vector<LL> &divs) {
    divs.push_back(1);
    for(int i = 0; i < facts.size(); ++i) {
        vector<LL> tmp;
        LL p = facts[i].first;
        LL acc = p;
        for(LL j = 1; j <= facts[i].second; ++j) {
            for(int k = 0; k < divs.size(); ++k) tmp.push_back(divs[k]*acc);
            acc *= p;
        }
        divs.insert(divs.end(), tmp.begin(), tmp.end());
    }
}

bool find_mus(const vector<vector<pair<LL,LL> > > &v, const set<int> &cn, vector<LL> &table) {
    int N = v.size();
    int start = *cn.begin();
    int to = 0;
    for(to = 0; to < N; ++to) if(v[start][to].first != 0) break;
    LL pr = v[start][to].first * v[start][to].second;

    if(cn.size() == 1) return true;

    vector<pair<LL,LL> > facts;
    vector<LL> divs;
    prime_division(pr, facts);
    divisors(facts, divs);
    for(vector<LL>::iterator it = divs.begin(); it != divs.end(); ++it) {
        queue<int> q;
        vector<int> used(N, 0);
        q.push(start);
        table[start] = *it;
        used[start] = 1;
        bool found = true;
        while(!q.empty()) {
            int n = q.front();
            q.pop();
            for(int i = 0; i < N; ++i) {
                if(v[n][i].first != 0) {
                    LL pr = v[n][i].first*v[n][i].second;
                    if(pr % table[n] != 0) {
                        found = false;
                        goto next;
                    }
                    if(used[i] && table[i] != pr/table[n]) {
                        found = false;
                        goto next;
                    }
                    table[i] = pr / table[n];
                    if(gcd(table[i], table[n]) != v[n][i].first) {
                        found = false;
                        goto next;
                    }
                    if(!used[i]) q.push(i);
                    used[i] = 1;
                }
            }
        }
next:
        if(found) return true;
    }
    return false;
}

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<pair<LL, LL> > > v(N, vector<pair<LL,LL> >(N, make_pair(0, 0)));

    gen_primes(1000000);
    for(int i = 0; i < M; ++i) {
        int a, b;
        pair<LL,LL> p;
        cin >> a >> b >> p.first >> p.second;
        --a; --b;
        v[a][b] = v[b][a] = p;
    }

    vector<set<int> > connections;
    vector<int> used(N, 0);
    while(true) {
        set<int> s;
        queue<int> q;
        int start = 0;
        for(start = 0; start < N; ++start) if(!used[start]) break;
        if(start == N) break;
        q.push(start);
        used[start] = 1;
        while(!q.empty()) {
            int n = q.front();
            q.pop();
            s.insert(n);
            for(int i = 0; i < N; ++i) {
                if(!used[i] && v[n][i].first != 0) {
                    q.push(i);
                    used[i] = 1;
                }
            }
        }
        connections.push_back(s);
    }

    vector<LL> table(N, 1);
    bool found = true;
    for(int i = 0; i < connections.size(); ++i) {
        if(!find_mus(v, connections[i], table)) {
            found = false;
            break;
        }
    }
    if(found) {
        cout << "YES" << endl;
        for(int i = 0; i < N; ++i) cout << table[i] << " ";
        cout << endl;
    }
    else cout << "NO" << endl;

    return 0;
}
 |