接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 198（ABC198）

AtCoder Beginner Contest 198（ABC198）

AtCoderBeginnerContest AtCoderBeginnerContest198 ABC ABC198

atcoder.jp

A - Div

$ (1, N-1), (2, N-2), ..., (N-1, 1) $ のようになるので $ N-1 $ を出力
提出コード

void solve(){
    int N;
    cin >> N;
    cout << N-1 << endl;
}

B - Palindrome with leading zeros

文字列で受け取って、文字列の先頭に0を $ i (0 \leq i \leq 9) $ 個つけたときに回分になるかどうかを判定すればいい
提出コード

void solve(){
    string N;
    cin >> N;
    int n = N.size();
    REP(i,20){
        if(i > 0) N = '0' + N;
        bool ok = true;
        REP(j,(i+n)/2){
            if(N[j] != N[(i+n)-j-1]) ok = false;
        }
        if(ok){
            cout << "Yes" << endl;
            return;
        }
    }
    cout << "No" << endl;
}

C - Compass Walking

$ (X, Y) $ までの距離を $ d $ とすると、$ d = R $ のときは $ 1 $ 回で移動できる
また、$ d <= 2R $ のときは $ 2 $ 回移動が必要となる
それ以外の場合、$ d \leq R x $ となるような最小の $ x $ が答えとなる
答えの範囲が多く見積もっても $ 2 \times 10^5 $ くらいには収まるので愚直にループを回して確認すればいい
整数で扱いたいので両辺を二乗して考える
提出コード

void solve(){
    ll R, X, Y;
    cin >> R >> X >> Y;

    if(R*R == X*X + Y*Y) cout << 1 << endl;
    else if(R*R*4 >= X*X + Y*Y) cout << 2 << endl;
    else{
        for(ll i=3;i<202020;i++){
            if(R*R*i*i >= X*X + Y*Y){
                cout << i << endl;
                return;
            }
        }
    }
}

D - Send More Money

$ S_1, S_2, S_3 $ に出現する文字の個数が10を超えたときは条件に違反するのでUNSOLVABLEとなるのでそれ以外の場合で考える
各文字に$ 0, 1, ..., 9 $ のどれを割り当てるかをnext_permutationで全探索をする
leading zero に気をつけて条件を満たす割り当て方があればそれを出力し、なければUNSOLVABLEを出力
文字は座圧をしておくとちょっと楽
提出コード

void solve(){
    string S1, S2, S3;
    cin >> S1 >> S2 >> S3;
    set<int> st;
    Compress<int> cmp;
    for(auto c : S1){
        st.insert(c);
        cmp.add(c-'a');
    }
    for(auto c : S2){
        st.insert(c);
        cmp.add(c-'a');
    }
    for(auto c : S3){
        st.insert(c);
        cmp.add(c-'a');
    }
    cmp.build();
    int n = cmp.size();
    if(st.size() > 10){
        cout << "UNSOLVABLE" << endl;
        return;
    }
    vector<int> num(10);
    iota(num.begin(), num.end(), 0);
    do{
        // dump(num);
        string s1 = S1;
        string s2 = S2;
        string s3 = S3;
        REP(i,s1.size()) s1[i] = char(num[cmp.get(s1[i]-'a')] + '0');
        REP(i,s2.size()) s2[i] = char(num[cmp.get(s2[i]-'a')] + '0');
        REP(i,s3.size()) s3[i] = char(num[cmp.get(s3[i]-'a')] + '0');
        if(s1[0] == '0' or s2[0] == '0' or s3[0] == '0') continue;
        ll sum1 = 0, sum2 = 0, sum3 = 0;
        REP(i,s1.size()) sum1 = sum1 * 10 + (s1[i] - '0');
        REP(i,s2.size()) sum2 = sum2 * 10 + (s2[i] - '0');
        REP(i,s3.size()) sum3 = sum3 * 10 + (s3[i] - '0');
        if(sum1 + sum2 == sum3){
            cout << s1 << endl;
            cout << s2 << endl;
            cout << s3 << endl;
            return;
        }
    }while(next_permutation(num.begin(), num.end()));
    cout << "UNSOLVABLE" << endl;
}

E - Unique Color

頂点 $ 1 $ からのパスなので今見ているパスに出現している色の個数を管理しながらdfsをすればいい
行きがけに今の頂点の色を加算し、帰りがけにその頂点の色を取り除く操作をしながらよい頂点を判定していけばいい
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> C(N);
    REP(i,N) cin >> C[i];
    vector<vector<int>> g(N);
    REP(i,N-1){
        int a, b;
        cin >> a >> b;
        --a, --b;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    vector<int> ans;
    auto dfs = [&](auto && self, int v, int par, multiset<int> & st) -> void{
        if(st.find(C[v]) == st.end()){
            ans.emplace_back(v+1);
        }
        st.insert(C[v]);
        for(auto nv : g[v]){
            if(nv == par) continue;
            self(self, nv, v, st);
        }
        st.erase(st.find(C[v]));
    };
    multiset<int> st;
    dfs(dfs, 0, -1, st);
    sort(ans.begin(), ans.end());
    for(auto x : ans) cout << x << endl;
}