SRM 643 Div2 - tshitaの備忘録Ⅱ

結果

oxx 1080 -> 1075

今年最後のSRMはツライ結果だった．
来年も色を上げれるように頑張りたい．

[Easy: TheKingsArmyDiv2 ]

解法

Happyなソルジャーの数が0なら隣り合う2人のソルジャーをHappyにする必要がある．
Happyなソルジャーの隣り合う組が1つでも存在するならHappyにする必要はない．
それ以外，すなわち，Happyなソルジャー数が1以上でHappyなソルジャーの隣り合う組が存在しない場合は，Happyなソルジャーの隣の1人をHappyにすれば良いので1．

ソースコード

const int dx[] = {0, 1, 0, -1};
const int dy[] = {-1, 0, 1, 0};

class TheKingsArmyDiv2 {
public:
    int getNumber(vector <string> state) {
        const int H = state.size();
        const int W = state[0].size();
        int cnt_h = 0;

        for (int i = 0; i < H; ++i) {
            for (int j = 0; j < W; ++j) {
                if (state[i][j] == 'H') {
                    ++cnt_h;
                    for (int d = 0; d < 4; ++d) {
                        int x = dx[d] + j;
                        int y = dy[d] + i;
                        if (x < 0 || y < 0 || x >= W || y >= H)
                            continue;

                        if (state[y][x] == 'H')
                            return 0;
                    }
                }
            }
        }

        return (cnt_h == 0) ? 2 : 1;
    }
};

[Medium: TheKingsFactorization ]

解法

primesの要素数をS，求める答えを $\{a_{i}\}_{i=0,...,M-1}$ とする．
このとき，
$N = a_{0} \times a_{1} \times \cdots \times a_{M-3} \times a_{M-2} \times a_{M-1}$
となる．
また，便宜上 $2 \times (S - 1) = M - 2$ とする．

初めに，Nをprimesの要素で割ると，Nの値は
$N = a_{1} \times a_{3} \times \cdots \times a_{M-3} \times a_{M-1}$
となる．
この時， $a_{M-3} \le 10^6$ となっている．
もし， $a_{M-3} > 10^6$ ならば， $N \ge a_{M-3} \times a_{M-2} \times a_{M-1} > 10^6 \times 10^6 \times 10^6 = 10^{18}$ となり $N \le 10^{18}$ であることに矛盾する．

Nを $10^6$ 以下の素数で素因数分解しながらNをその素因数で割っていく．
$a_{M-1} > 10^6$ ならばNの値は1ではないが，残りの素因数は $a_{M-1}$ はNとなっている．
最後に，求めた素因数をソートして返す．

ソースコード

const int MAX_N = 1e6 + 10;

class TheKingsFactorization {
    int  prime[MAX_N];

public:
    vector<long long> getVector(long long N, vector<long long> primes) {
        int size = primes.size();
        int p = SieveOfEratosthenes(MAX_N);

        for (int i = 0; i < size; ++i)
            N /= primes[i];

        for (int i = 0; i < p; ++i) {
            if (N == 1)
                break;
            while (N % prime[i] == 0) {
                N /= prime[i];
                primes.push_back(prime[i]);
            }
        }

        if (N != 1)
            primes.push_back(N);

        sort(primes.begin(), primes.end());

        return primes;
    }

    int SieveOfEratosthenes(int n) {
        int p = 0;
        bool is_prime[MAX_N + 1];

        for (int i = 0; i <= n; ++i)
            is_prime[i] = true;
        is_prime[0] = is_prime[1] = false;

        for (int i = 2; i <= n; ++i)
            if (is_prime[i]) {
                prime[p++] = i;
                for (int j = 2 * i; j <= n; j += i)
                    is_prime[j] = false;
            }

        return p;
    }

};

[Hard: TheKingsTree ]

解法

説明する程理解してないので後で．

class TheKingsTree {
    int dp[52][52][52];
    vector<int> tree[51];

public:
    int getNumber(vector <int> parent) {
        int N = parent.size();

        for (int i = 0; i < N; ++i)
            tree[parent[i]].push_back(i + 1);

        memset(dp, -1, sizeof(dp));

        return Rec(0, 0, 0);
    }

    int Rec(int v, int red, int green) {
        if (dp[v][red][green] != -1)
            return dp[v][red][green];

        // select red
        int cost1 = red + 1;
        for (int i = 0; i < tree[v].size(); ++i)
            cost1 += Rec(tree[v][i], red + 1, green);

        // select green
        int cost2 = green + 1;
        for (int i = 0; i < tree[v].size(); ++i)
            cost2 += Rec(tree[v][i], red, green + 1);

        return dp[v][red][green] = min(cost1, cost2);
    }

};