tokizo

競技プログラミングの備忘録や日記

ABC135

結果

3完(13:39)
Rated 1006/4450

f:id:fawula:20190728102026p:plain
コンテストURL

所感

A: 一瞬焦った (A問題に1mmでも思考を要する問題が置かれるとビビる)

B: 久しぶりにB問題っぽいB問題が出た気がする
ソートして変化点を計算,2以下ならOK

C: バグらせて時間を溶かした これくらいならB問題くらいの速度で解かなければと自戒

D: DPだということは分かったが何もできず

レート

f:id:fawula:20190728102629p:plain

HackerRank Journey to the Moon

気持ちが良い問題だった
問題リンク

問題概要

N人の宇宙飛行士がいます
P個のペアが渡されます
ペアは同じ国籍同士の宇宙飛行士の番号です
N人の中から,国籍が違う宇宙飛行士のペアはいくつあるか

解説

同じ国籍どうしの宇宙飛行士をDFSやUnionFindでグループを作ります
例えばAグループに3人,Bグループに4人いるとすると,Aグループ3人それぞれに対しBグループの4人がペアになりうるので生成できるペア数は12となります

愚直に二重for分でペア数を掛けていくと,時間がかかるのは予想できます

そこで,ひとまずN人から2人を選ぶ組み合わせの総数を出します
そこから同じグループから2人を選ぶ組み合わせの数をグループごとに見ていき引いていけば,答えが求まります

イメージは余事象的な感じですかね?

コード(C++14)

#include <bits/stdc++.h>
using namespace std;

struct UnionFind{
    vector<long long> par;
    UnionFind(long long N) : par(N){
        for(long long i = 0; i < N; i++){
            par[i] = -1;
        }
    }
    long long root(long long x){
        if(par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    void unite(long long x, long long y){
        long long rx = root(x);
        long long ry = root(y);
        if(rx == ry) return;
        else{
            if(par[rx] > par[ry]) swap(rx, ry);
            par[rx] += par[ry];
            par[ry] = rx;
       }
    }
    bool same(long long x, long long y){
        return root(x) == root(y);
    }
    void check(){
        for(auto x : par){
            cout << x << " ";
        }
        cout << endl;
    }
};

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    long long n, p;
    cin >> n >> p;
    UnionFind uf(n);
    while(p--){
        long long a, b;
        cin >> a >> b;
        uf.unite(a, b);
    }

    map<long long, long long> mp;
    for(long long i = 0; i < n; i++){
        long long r = uf.root(i);
        mp[r] = -uf.par[r];
    }

    vector<long long> B;
    for(auto x : mp){
        B.push_back(x.second);
    }

    long long bs = B.size();
    long long ans = n * (n - 1) / 2;
    for(long long i = 0; i < bs; i++){
        ans -= B[i] * (B[i] - 1) / 2;
    }

    cout << ans << endl;

    return 0;
}

ABC134

結果

3完(10:10)
Rated 2109/4713

f:id:fawula:20190721163150p:plain

コンテストURL

所感

A: 問題文の通りに実装を行う

B: 一人の監視員で (d * 2 + 1) の範囲をカバーするので、Nを(d * 2 + 1) で割る(切り上げ)

C: 数列Aの最大値が2以上含む場合はすべて最大値,そうでないなら最大値の箇所だけ2番目の最大値を出力

D: 解けなかった…
2019/07/21解いた
提出URL

#include <bits/stdc++.h>
using namespace std;

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    vector<int> A(n + 1);
    for(int i = 0; i < n; i++){
        cin >> A[i + 1];
    }

    int m = 0;
    for(int i = n; i > 0; i--){
        for(int j = i + i; j <= n; j += i){
            A[i] ^= A[j];
        }
        if(A[i]) m++;
    }

    cout << m << endl;
    for(int i = 1; i <= n; i++){
        if(A[i]) cout << i << ' ';
    }

    return 0;
}

xorが使えるところ,前から後ろに見ていくのが大事
エラトステネスの篩みたいにn * 対数時間な感じでいい感じになる

まとめ

f:id:fawula:20190721163659j:plain

う〜ん…

ABC131

結果

4完 (3WA)
Rated内2484位 (Aの提出者4930人)
 f:id:fawula:20190623111142p:plain

コンテストURL

所感

A: 隣り合う文字列が同じところがあった場合'BAD'

B: 指定した数列を作り、総和から絶対値が一番小さいものを引く

C: 包除原理
コーナーケース

1 1 1 1

に注意(30分溶かした)

D: Cで悩んでて味変がてら見たら秒で解けた
priority_queueに突っ込んだ

もう死にかけよ!!
f:id:fawula:20190623112016p:plain

ABC126-D: Even Relation

問題概要

問題ページへのリンク

N頂点の木がある。頂点ui, vi間の辺の長さはwiとする
同じ色に塗られた任意の2頂点間について、その距離が偶数になることを満たすように各頂点に色を塗る
そのような塗り分け方を1つ見つけて出力せよ

考察

偶数同士、奇数同士の辺でつながっている頂点をそれぞれ別の色で塗りたいが偶数同士だからといって一意に色が定まるわけではない

なんとなく根から各頂点までの距離の累積和の偶奇を取ることにした
以下のような入力を考える

8
1 2 1
1 3 3
3 4 2
3 5 2
5 6 6
5 7 7
7 8 5

図にすると以下のようになる
f:id:fawula:20190520110614j:plain

頂点1を根とし、各頂点までの距離の累積和を取ると以下のようになる
f:id:fawula:20190520111610p:plain

各頂点までの距離の累積和が直前までの累積和と偶奇が同じだったら今までの色、違ったら別の色で塗る
f:id:fawula:20190520111647p:plain

コード

dfsの引数preは前回訪れた頂点で、後戻りさせないようにしている

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, long long> P; // {to, cost}

int n;
const int N = 100010;
vector<P> G[N];
vector<int> Color(N);

void dfs(int now, int pre, int color, long long acost){ // accumulate_cost
    Color[now] = color; 
    for(int i = 0; i < G[now].size(); i++){
        P p = G[now][i];
        if(p.first == pre) continue;
        long long to_acost = p.second + acost;
        if(to_acost % 2 == acost % 2 ) dfs(p.first, now, color, to_acost);
        else dfs(p.first, now, (color == 1 ? 0 : 1), to_acost);
    }
}


int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> n;
    for(int i = 0; i < n - 1; i++){
        int a, b;
        long long c;
        cin >> a >> b >> c;
        a--; b--;
        G[a].push_back({b, c});
        G[b].push_back({a, c});
    }
    
    Color.resize(n);
    
    dfs(0, -1, 1, 0);

    for(int i = 0; i < n; i++){
        cout << Color[i] << endl;
    }

    return 0;
}

実際のコードへのリンク

ABC126-D: Even Relation 供養

Dに一時間以上費やすも解けず蒸発
とりあえずめっちゃ書いたので供養
ACコードではない

#include <bits/stdc++.h>
using namespace std;

long long const N = 100010;

long long n;
struct edge {
    long long cost, to;
};
vector<edge> G[N];

vector<bool> F(N); // true: even
vector<bool> Check(N);

void dfs(long long now, bool fst, int od){ // syokai?, odd?
    Check[now] = true;
    if(fst){
        for(long long i = 0; i < G[now].size(); i++){
            
        }
    }else
        for(long long i = 0; i < G[now].size(); i++){

        }
    }
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> n;
    for(long long i = 0; i < n - 1; i++){
        long long u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        G[u].push_back({w, v});
        G[v].push_back({w, u});
    }

    for(long long i = 0; i < n; i++){
        if(Check[i]) continue;
        dfs(i, true, -1);
    }

    return 0;
}
#include <bits/stdc++.h>
using namespace std;

long long const N = 100010;

long long n;
struct edge {
    long long cost, to;
};
vector<edge> G[N];

vector<bool> BF(N);
vector<bool> Check(N);

struct UnionFind{
    vector<long long> par;
    UnionFind(int NN) : par(NN){
        for(long long i = 0; i < NN; i++){
            par[i] = -1;
        }
    }
    long long root(int x){
        if(par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    void unite(long long x, long long y){
        long long rx = root(x);
        long long ry = root(y);
        if(rx == ry) return;
        else{
            if(par[rx] > par[ry]) swap(rx, ry);
            par[rx] += par[ry];
            par[ry] = rx;
       }
    }
    bool same(int x, int y){
        return root(x) == root(y);
    }
    void check(){
        for(auto x : par){
            cout << x << " ";
        }
        cout << endl;
    }
};

void dfs_first(long long now){
    // BF[now] = true;
    Check[now] = true;
    long long gs = 0; // gusu_count
    for(long long i = 0; i < G[now].size(); i++){
        edge e = G[now][i];
        if(e.cost % 2 == 0) gs++;
    }
    if(gs * 2 == (long long)G[now].size()){
        for(long long i = 0; i < G[now].size(); i++){
            edge e = G[now][i];
            BF[e.to] = false;
            Check[e.to] = true;
        }
    }else{
        if(gs > (long long)G[now].size() / 2){
            BF[now] = true;
            for(long long i = 0; i < G[now].size(); i++){
                edge e = G[now][i];
                if(e.cost % 2 == 0){
                    BF[e.to] = true;
                }else{
                    BF[e.to] = false;
                }
                Check[e.to] = true;
            }
        }else{
            BF[now] = false;
            for(long long i = 0; i < G[now].size(); i++){
                edge e = G[now][i];
                if(e.cost % 2 == 0){
                    BF[e.to] = true;
                }else{
                    BF[e.to] = false;
                }
                Check[e.to] = true;
            }
        }
    }
}

void dfs_second(long long now){
    long long bc = 0; // brack_count
    long long wc = 0; // white_count
    for(long long i = 0; i < G[now].size(); i++){
        edge e = G[now][i];
        if(Check[e.to]){
            if(BF[e.to]) bc++;
            else wc++;
        }
    }
    if(bc > 0 and wc == 0){
        for(long long i = 0; i < G[now].size(); i++){
            if()
        }
    }else{

    }

}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> n;
    for(long long i = 0; i < n - 1; i++){
        long long u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        G[u].push_back({w, v});
        G[v].push_back({w, u});
    }

    bool fff = true; // first?
    for(long long i = 0; i < n; i++){
        if(Check[i]) continue;
        if(G[i].size() >= 2){
            if(fff){
                dfs_first(i);
                fff = false;
            }else{
                // dfs_other?
            }
        }
    }

    return 0;
}
#include <bits/stdc++.h>
using namespace std;

long long const N = 100010;

long long n;
struct edge {
    long long cost, to;
};
vector<edge> G[N];

vector<bool> BF(N);
vector<bool> C(N);
vector<bool> Color(N);

struct UnionFind{
    vector<long long> par;
    UnionFind(int NN) : par(NN){
        for(long long i = 0; i < NN; i++){
            par[i] = -1;
        }
    }
    long long root(int x){
        if(par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    void unite(long long x, long long y){
        long long rx = root(x);
        long long ry = root(y);
        if(rx == ry) return;
        else{
            if(par[rx] > par[ry]) swap(rx, ry);
            par[rx] += par[ry];
            par[ry] = rx;
       }
    }
    bool same(int x, int y){
        return root(x) == root(y);
    }
    void check(){
        for(auto x : par){
            cout << x << " ";
        }
        cout << endl;
    }
};

void dfs1(long long now, UnionFind &uf, map<long long, bool> &mp){
    C[now] = true;
    long long gc = 0; // gusu_count
    for(long long i = 0; i < G[now].size(); i++){
        edge e = G[now][i];
        if(e.to % 2 == 0) gc++;
    }
    if(gc >= (long long)G[now].size() / 2){
        for(long long i = 0; i < G[now].size(); i++){
            edge e = G[now][i];
            if(e.cost % 2 == 0){
                uf.unite(now, e.to);
                C[e.to] = true;
            }
        }
        mp[uf.root(now)] = true;
    }else{
        for(long long i = 0; i < G[now].size(); i++){
            edge e = G[now][i];
            if(e.cost % 2 != 0){
                uf.unite(now, e.to);
                C[e.to] = true;
            }
        }
        mp[uf.root(now)] = false;
    }
}

void dfs2(long long now, UnionFind &uf, map<long long, bool> &mp){
    // long long gc1 = 0, oc1 = 0; // guusuu_counst
    C[now] = true;
    long long cnt = 0;
    for(long long i = 0; i < G[now].size(); i++){
        edge e = G[now][i];
        if(C[e.to]){
            if(mp[uf.root(e.to)]){
                if(e.cost % 2 == 0){
                    uf.unite(now, e.to);
                    C[e.to] = true;
                }else{
                    mp[e.to] = false;
                    C[e.to] = true;
                }
            }else{
                if(e.cost % 2 != 0){
                    uf.unite(now, e.to);
                    C[e.to] = true;
                }else{
                    mp[e.to] = true;
                    C[e.to] = true;
                }
            }
        }else{
            cnt++;
        }
    }
    if(cnt == G[now].size()){
        dfs1(now, uf, mp);
    }
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> n;
    for(long long i = 0; i < n - 1; i++){
        long long u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        G[u].push_back({w, v});
        G[v].push_back({w, u});
    }

    map<long long, bool> mp; // true -> gusu
    UnionFind uf(n);

    bool ff = true;
    for(long long i = 0; i < n; i++){
        if(G[i].size() >= 2){
            if(ff){
                dfs1(i, uf, mp);
                ff = false;
            }else{
                if(C[i]) continue;
                dfs2(i, uf, mp);
            }
        }
    }
    for(auto x : mp){
        cout << x.first << ' ' << x.second << endl;
    }

    return 0;
}

CPSCO2019 Session1-C: Coins

問題概要

問題リンク

1, 10, 100, ..., 109, 5, 50, 500, ..., 5 * 109円硬貨がある
スーパーでN種類の果物が1つずつ、それぞれA0,A1, ..., An-1円で売られている

N種類の果物のうち、K個買う時の合計金額をちょうど支払うために必要な硬貨の枚数の最小値を求めよ
ただし、硬貨の数は限りなく多いとする

考察

たくさんの硬貨…? Strange Bankか? と思ったが、大きい硬貨から順番に払っていけば最小の硬貨枚数となるので別問題であると分かった(Strange Bankだと13円の場合、12円以下で大きい値の硬貨から貪欲に削っていくと、9円と1円と1円と1 円の硬貨の4枚となる。しかし6円と6円と1円の3枚が最小の硬貨枚数となる)

硬貨の最小枚数を考える前に、K個の果物を選ぶ方法を考える
nCkを列挙してやれば良いのは分かるが実装方法が分からない…
例えば N = 5, K = 3の場合,{A[0], A[1], A[2]}, {A[0], A[1], A[3]}, {A[0], A[1], A[4]}, ...と順々に列挙する必要がある

順々…?列挙…? …深さ優先探索!!!!!!!!!
AOJ-整数の和が頭に浮かんだ

f:id:fawula:20190509170508p:plain

↑こんなイメージで探索していき、遷移数がKになったときの合計金額を、持っている合計金額以下の硬貨で徐々に減らしていき、硬貨枚数をカウントしてすべての遷移後の硬貨枚数の最小値が答え

うまく説明できなくてアレですが、いけるとこまでいくぜ〜感で探索するイメージです

コード

#include <bits/stdc++.h>
using namespace std;

long long n, k, ans = 1e9;
long long A[35];

vector<long long> Coin;

void dfs(long long now, long long cnt, long long total){
    if(cnt == k){
        long long cc = 0; // coin_count
        for(long long i = 0; i < Coin.size(); i++){
            if(Coin[i] > total) continue;
            while(total - Coin[i] >= 0){
                cc++;
                total -= Coin[i];
            }
        }
        ans = min(ans, cc);
    }else{
        for(long long i = 0; i < n; i++){
            if(now + 1 + i < n){
                dfs(now + 1 + i, cnt + 1, total + A[now + i + 1]);
            }
        }
    }
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> n >> k;
    for(long long i = 0; i < n; i++){
        cin >> A[i];
    }

    for(long long i = 0; i < 9; i++){
        Coin.push_back((long long)pow(10, i));
        Coin.push_back((long long)(5 * pow(10, i)));
    }

    sort(Coin.rbegin(), Coin.rend());

    for(long long i = 0; i < n; i++){
        dfs(i, 1, A[i]);
    }

    cout << ans << endl;

    return 0;
}

atcoder.jp

宣伝

cp-categorizeというサイトに自分で解いた競プロの問題を勝手にジャンル分けしています。深さ優先探索の問題は地道に解いているのでそこそこの問題量があります。ぜひサイトを覗いてみてください!