AtCoder Beginner Contest 166（ABC166）

水色で3完の人がいるらしいですよ、誰でしょうね

にゃーん
Bondo416さんのAtCoder Beginner Contest 166での成績：5314位
パフォーマンス：654相当
レーティング：1386→1331 (-55) :(#AtCoder https://t.co/EfreAMOstW
— ボンド@競プロ (@bond_cmprog) 2020年5月3日

A - A?C

言われてるとおりにやる
提出コード

void solve(){
    string S;
    cin >> S;
    if(S == "ABC") cout << "ARC" << endl;
    else cout << "ABC" << endl;
}

B - Trick or Treat

ぱっと見で問題がよくわからなかった
お菓子をもらっている人をカウントすればいい
提出コード

void solve(){
    int N, K;
    cin >> N >> K;
    vector<int> cnt(N);
    REP(i,K){
        int d;
        cin >> d;
        REP(j,d){
            int a;
            cin >> a;
            --a;
            cnt[a]++;
        }
    }
    int ans = 0;
    REP(i,N) if(cnt[i] == 0) ans++;
    cout << ans << endl;
}

C - Peaks

一本の道を通っての部分読み飛ばしててUnionFind貼ってサンプル合わなくて気づいた
各頂点の隣接リストを見れば良いね

提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<int> H(N);
    REP(i,N) cin >> H[i];
    vector<vector<int>> G(N);
    REP(i,M){
        int a, b;
        cin >> a >> b;
        --a, --b;
        G[a].emplace_back(b);
        G[b].emplace_back(a);
    }
    int ans = 0;
    REP(i,N){
        int ma = H[i];
        bool ok = true;
        for(auto nv : G[i]){
            if(H[nv] >= ma){
                ok = false;
                break;
            }
        }
        if(ok) ans++;
    }
    cout << ans << endl;
}

D - I hate Factorization

これ難しいんですけど
1000くらいまで全探索すれば良さそうなのはぱっとわかって
そこから何故かBをO(1)で求めようとして沼った
微分を使うと4乗オーダーで見積もりが出来るらしいですよ（考えもしなかった）
Bも全探索すればいいですね、はい…
提出コード

void solve(){
    ll X;
    cin >> X;
    for(ll i=1;i<=2e3;i++){
        for(ll j=-2e3;j<=2e3;j++){
            if(i*i*i*i*i - j*j*j*j*j == X){
                cout << i << " " << j << endl;
                return;
            }
        }
    }
}

E - This Message Will Self-Destruct in 5s

これ緑difficultyまじ？壊れる
条件を考えると $i + A_i = j - A_j$ になるものを探せばいい
そのため左辺のものと右辺のものをmapなどで管理しておけば
後は先頭から見ていくいつものやつ
D解けなくて焦ってたのもあるけどこれ解けないのはだめだねーINF回見てるやつ
提出コード

void solve(){
    int N;
    cin >> N;
    map<ll, ll> L, R;
    ll ans = 0;
    REP(i,N){
        ll A;
        cin >> A;
        ans += L[i-A];
        ans += R[i+A];
        L[i+A]++;
        R[i-A]++;
    }
    cout << ans << endl;
}

まだ解いてないんだけどぱっと見後ろから貪欲とかそういう系に見える
大体の場合でYESにできそうだから、出来ないときの場合分けを考えるやつっぽい
全探索でも出来るらしい
うまくいくやつは雑にやってもNまで探索すればいいので間に合う
だめなときが問題になるけど、ダメな奴は基本的には早い段階で枝刈りされるので大丈夫なるパターン
なのでNに近い段階で駄目なパターンが多く見つかるというケースは少なくなりそう
だめになる時というのが、A+B+Cの値が小さい時になるけどA+B+Cが小さいときは最適に選ばないといけないことが増えて、状態数が小さくなり、その状態で駄目になるというのは早い段階で枝刈りされるという感じなのかな
提出コード

void solve(){
    int N, A, B, C;
    cin >> N >> A >> B >> C;
    vector<string> vs(N);
    REP(i,N) cin >> vs[i];
    string ans;
    auto dfs = [&](auto && self, int cur, int a, int b, int c) -> bool{
        if(cur == N) return true;

        if(vs[cur] == "AB"){
            if(a == 0 && b == 0) return false;
            if(0 < a && self(self, cur+1, a-1, b+1, c)){
                ans.push_back('B');
                return true;
            }
            if(0 < b && self(self, cur+1, a+1, b-1, c)){
                ans.push_back('A');
                return true;
            }
            return false;
        }

        if(vs[cur] == "AC"){
            if(a == 0 && c == 0) return false;
            if(0 < a && self(self, cur+1, a-1, b, c+1)){
                ans.push_back('C');
                return true;
            }
            if(0 < c && self(self, cur+1, a+1, b, c-1)){
                ans.push_back('A');
                return true;
            }
            return false;
        }

        if(vs[cur] == "BC"){
            if(b == 0 && c == 0) return false;
            if(0 < b && self(self, cur+1, a, b-1, c+1)){
                ans.push_back('C');
                return true;
            }
            if(0 < c && self(self, cur+1, a, b+1, c-1)){
                ans.push_back('B');
                return true;
            }
            return false;
        }
        return false;
    };

    dfs(dfs, 0, A, B, C);
    reverse(ans.begin(), ans.end());
    if(ans.size() < N) cout << "No" << endl;
    else{
        cout << "Yes" << endl;
        for(auto x : ans) cout << x << endl;
    }
}

おわりに

ここ3, 4回くらいの問題ほんと解けない
Dに数学置かれると辛くなりがち

接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。