Codeforces #26

1416pts / 185位でレーティングは1549→1593。微増。

A Almost Prime

1〜Nで素因数をちょうど2つだけ持つ数の個数を求める問題。書くだけ。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<bool> is_prime(3001, true);
    vector<int> primes;

    primes.push_back(2);
    for(int i = 3; i < 3001; i += 2) {
        if(is_prime[i]) {
            for(int j = i*2; j < 3001; j += i) {
                is_prime[j] = false;
            }
            primes.push_back(i);
        }
    }

    int N;
    cin >> N;

    int cnt = 0;
    for(int i = 1; i <= N; ++i) {
        int pcnt = 0;
        int num = i;
        for(int j = 0; j < primes.size(); ++j) {
            if(primes[j] > num) break;
            if(num % primes[j] == 0) {
                while(num % primes[j] == 0) num /= primes[j];
                if(++pcnt > 2) break;
            }
        }
        if(pcnt == 2) ++cnt;
    }

    cout << cnt << endl;
    return 0;
}

B Regular Bracket Sequence

カッコの列が与えられるので、適当に文字を削除してmatchedにする問題。少し悩んだけど、先頭から見ていってunmatchedになる閉じカッコと最後まで閉じなかった開きカッコを削除すればOK。

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    int open = 0;
    string str;
    cin >> str;

    int len = str.size();
    for(int i = 0; i < str.size(); ++i) {
        if(str[i] == '(') {
            ++open;
        }
        else if(str[i] == ')') {
            if(open == 0) --len;
            else --open;
        }
    }
    len -= open;
    cout << len << endl;

    return 0;
}

C Parquet

Parquetなる物で長方形の部屋の床を敷き詰める方法を出力する問題。1x2と2x1と2x2のParquetがそれぞれ何枚か与えられるので、敷き詰められれば方法を、無理ならIMPOSSIBLEを出力する。
とりあえず部屋の面積が奇数ならアウト。偶数の時は、縦か横の長さを見てどっちかが奇数なら、一列を1x2か2x1で敷き詰めて偶数x偶数の敷き詰めに還元する。例えば5x4だとすると、横一列に1x2を敷き詰めて4x4敷き詰めにする。もしもここで1x2が十分になければ、残りの2x1と2x2では縦方向は2ずつしか消費できず、5の長さを敷き詰められないのでIMPOSSIBLE。
偶数x偶数になったら、1x2や2x1は二つずつ組み合わせて2x2にして、2x2だけの敷き詰めとして解く。1x2や2x1が1枚しかなければスルー。これで最後まで置けないのならIMPOSSIBLE。
・・・というのを考えたけど、コンテスト中は通らなかった。必死でデバッグして、最後2分で1x2と2x1の敷き詰め方を逆に実装してたことが判明。必死で修正するも間に合わず・・・。
Practiceで出したら通った。うがー。

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    int n, m, a, b, c;
    cin >> n >> m >> a >> b >> c;

    vector<vector<int> > field(n, vector<int>(m, 0));
    int rem = n*m;

    if(n*m % 2 == 1) goto IMPOSSIBLE;
    if(n*m > 2*a + 2*b + 4*c) goto IMPOSSIBLE;

    if(n % 2 == 1) {
        for(int i = 0; i < m; i += 2) {
            if(a == 0) goto IMPOSSIBLE;
            --a;
            field[n-1][i] = field[n-1][i+1] = (i%4)+10;
        }
        --n;
        rem -= m;
    }
    else if(m % 2 == 1) {
        for(int i = 0; i < n; i += 2) {
            if(b == 0) goto IMPOSSIBLE;
            --b;
            field[i][m-1] = field[i+1][m-1] = (i%4)+10;
        }
        --m;
        rem -= n;
    }
    
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            if(field[i][j] != 0) continue;
            vector<bool> used(10, false);
            if(i > 0) used[field[i-1][j]] = true;
            if(i > 0 && j < m-1) used[field[i-1][j+1]] = true;
            if(j > 0) used[field[i][j-1]] = true;
            if(i < n-1 && j > 0) used[field[i+1][j-1]] = true;
            
            int pos = 1;
            int num1, num2;
            while(used[pos]) ++pos;
            num1 = pos++;
            while(used[pos]) ++pos;
            num2 = pos;

            if(b >= 2) {
                field[i][j] = field[i+1][j] = num1;
                field[i][j+1] = field[i+1][j+1] = num2;
                b -= 2;
            }
            else if(a >= 2) {
                field[i][j] = field[i][j+1] = num1;
                field[i+1][j] = field[i+1][j+1] = num2;
                a -= 2;
            }
            else if(c >= 1) {
                field[i][j] = field[i][j+1] = field[i+1][j] = field[i+1][j+1] = num1;
                c -= 1;
            }
            else goto IMPOSSIBLE;
        }
    }

    for(int i = 0; i < field.size(); ++i) {
        for(int j = 0; j < field[i].size(); ++j) {
            cout << char('a'+field[i][j]);
        }
        cout << endl;
    }
    goto END;

IMPOSSIBLE:
    cout << "IMPOSSIBLE" << endl;

END:
    return 0;
}

D Tickets

E Multithreading

解いてない。Dは嫌いな確率問題。Eはよくわからない。