SRM 661 Div 1 Easy

TopCoder 素数

さらっとだけ備忘録。

  1. N以下の全ての素数を調べる。
  2. その素数の累乗数表を持つ
  3. [2]のうち、N以下で最大のもの * 2を返す。

N以下の最大の素数の累乗数をxとする。 xの2倍がN以下であると仮定する。

ベルトラン＝チェビシェフの定理（今知った）より、

「自然数 n ≥ 2 に対して、n < p ≤ 2n を満たす素数 p が存在する」
ベルトランの仮説

x < p <= 2x <= Nとなる素数pが存在するので、xはN以下の最大の素数の累乗数ではない。

と言えるということなのかな。

lower_boundについて

C++メモなど 
#include <iostream>
#include <string>

using namespace std;

int a[5] = {10, 20, 20, 40, 60};

int main()
{
    cout << lower_bound(a, a + 5, 0) - a << endl; # 0
    cout << lower_bound(a, a + 5, 20) - a << endl; # 1
    cout << lower_bound(a, a + 5, 100) - a << endl; # 5

    cout << lower_bound(a, a + 5, 40) - a << endl; # 3
    cout << lower_bound(a, a + 5, 50) - a << endl; # 4
}

AtCoder Typical Contest 001 参加

コンテスト AtCoder

A: 深さ優先探索 - AtCoder Typical Contest 001 | AtCoder

B: Union Find - AtCoder Typical Contest 001 | AtCoder

C: 高速フーリエ変換 - AtCoder Typical Contest 001 | AtCoder

Cの高速フーリエ変換だけ分からなかった。。高速フーリエ変換ちゃんと勉強しよっと。。

A: 深さ優先探索

int H, W;
string mp[505] = {};
bool used[505][505] = {};
 
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

void solve(int x, int y) {
    used[x][y] = 1;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (0 <= nx && nx < H && 0 <= ny && ny < W) {
            if (!used[nx][ny]) {
                solve(nx, ny);
            }
        }
    }
}

int main() {
    cin >> H >> W;
    for (int i = 0; i < H; i++) {
        cin >> mp[i];
    }
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (mp[i][j] == '#') {
                used[i][j] = 1;
            }
        }
    }
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (mp[i][j] == 's') {
                solve(i, j);
            }
        }
    }
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (mp[i][j] == 'g') {
                if (used[i][j]) {
                    cout << "Yes" << endl;
                } else {
                    cout << "No" << endl;
                }
            }
        }
    }
    return 0;
}

B: Union Find

struct UF {
    vector<int> parent, rank;
 
    UF(int n) {
        parent.resize(n); rank.resize(n);
        for (int i = 0; i < n; i++) { parent[i] = i; rank[i] = 1; }
    }
 
    bool same(int x, int y) {
        return (find_root(x) == find_root(y));
    }
 
    int find_root(int x){
        if (parent[x] != x) parent[x] = find_root(parent[x]);
        return parent[x];
    }
 
    void connect(int x, int y){
        int rx = find_root(x), ry = find_root(y);
        if (rx == ry) return;
        if (rank[rx] > rank[ry]) { parent[ry] = rx; rank[rx] += rank[ry]; }
        if (rank[rx] <= rank[ry]) { parent[rx] = ry; rank[ry] += rank[rx]; }
    }
};
 
 
int main() {
    int N, Q;
    cin >> N >> Q;
    UF uf(N);
    for (int i = 0; i < Q; i++) {
        int p, a, b;
        cin >> p >> a >> b;
        if (p) {
            if (uf.same(a, b)) {
                cout << "Yes" << endl;
            } else {
                cout << "No" << endl;
            }
        } else {
            uf.connect(a, b);
        }
    }
    return 0;
}

yukicoder no.221/222/223 参加

コンテスト yukicoder

初yukicoder参加。

  1. No.221 犯罪都市 - yukicoder
  2. No.222 引き算と足し算 - yukicoder
  3. No.223 1マス指定の魔方陣 - yukicoder

1,2はただの実装。3は分からなくてそのまま時間切れとなってしまった。

犯罪都市

int main() {
    int N; cin >> N;
    N *= 100;
    double total = 1000*1000;
    double normal = total - N;
    double arrested = N * 0.99 + normal * 0.01;
    cout << normal / arrested << endl;
    return 0;
}

引き算と足し算

字句解析のように実装したが、yukicoderはLL使えるようなのでそっちでやりゃよかった...。こういう問題初めてなので謎にC++で頑張ってしまった。

int main() {
    string s;
    cin >> s;
    string x="", y="";
    int i = 0;
    if (s[i] == '-'){
        x+='-';
        i++;
    }
    if (s[i] == '+'){
        i++;
    }
    while (s[i] != '-' && s[i] != '+'){
        x += s[i];
        i++;
    }
    char op = s[i];
    i++;
    if (s[i] == '-'){
        y+='-';
        i++;
    }
    if (s[i] == '+') {
        i++;
    }
    while (i < s.size()) {
        y += s[i];
        i++;
    }
    stringstream ss(x);
    int xi; ss >> xi;
    stringstream ss2(y);
    int yi; ss2 >> yi;
    if (op == '-') cout << xi + yi << endl;
    else  if (op == '+') cout << xi - yi << endl;
    return 0;
}

Combinatorial - Longest Increasing Subsequence

DP AOJ

最長増加部分列 | 動的計画法 | Aizu Online Judge

int a[1000*100+5] = {};

int main() {
    int n;
    cin >> n;
    fill(a, a + 1000*100+5, 1000*1000*1000*2);
    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        *(lower_bound(a, a + 1000*100+5, t)) = t;
    }
    cout << lower_bound(a, a + 1000*100+5, 1000*1000*1000*2) - a << endl;

    return 0;
}

Combinatorial - Knapsack Problem

DP AOJ

Knapsack Problem | Aizu Online Judge

Combinatorial - 0-1 Knapsack Problem - アルゴリズムのメモ帳 とほぼ同じ問題。

続けて解いたので、ちょっとずるして上で解いたものを再利用した。

int main() {
    int N, W; cin >> N >> W;
    int v[105], w[105];
    for (int i = 0; i < N; i++) cin >> v[i] >> w[i];
    int dp[105][10005];
    memset(dp, -1, sizeof(dp));
    int res = 0;
    dp[0][0] = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= W; j++) {
            int k = j - w[i];
            if (k >= 0 && dp[i][k] >= 0) {
                dp[i + 1][j] = max(dp[i][j], dp[i][k] + v[i]);
            }

            if (k >= 0 && dp[i + 1][k] >= 0) {
                dp[i + 1][j] = max(dp[i + 1][j], dp[i + 1][k] + v[i]);
            }

            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
            res = max(res, dp[i + 1][j]);
        }
    }

    printf("%d\n", res);
    return 0;
}