接着剤の精進日記

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

京セラプログラミングコンテスト2021(AtCoder Beginner Contest 200)

atcoder.jp

A - Century

$ \lceil \frac{N}{100} \rceil $ を出力
提出コード

void solve(){
    int N;
    cin >> N;
    cout << ceil_div(N, 100) << endl;
}

B - 200th ABC-200

問題文のとおりにシミュレートする
提出コード

void solve(){
    ll N, K;
    cin >> N >> K;
    REP(i,K){
        if(N % 200 == 0) N /= 200;
        else N = N * 1000 + 200;
    }
    cout << N << endl;
}

C - Ringo's Favorite Numbers 2

すでに見た $ A_i \pmod{200} $ の値をmapなどで管理し、今見ている $ A_j $ に対応する余りの個数を答えに加算していく
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    sort(A.rbegin(), A.rend());
    map<int, int> mp;
    ll ans = 0;
    REP(i,N){
        ll rem = A[i] % 200;
        ans += mp[(rem - 200 + 200)%200];
        mp[rem]++;
    }
    cout << ans << endl;
}

D - Happy Birthday! 2

$ N \leq 8 $ のとき、数列の選び方は $ 2^8 - 1 = 255 \lt 200 $ となり、鳩ノ巣原理から答えが必ず存在する
$ N \gt 8 $ の場合、bit全探索で全探索することが出来るので、$ N = \min(N, 8) $ としてbit全探索を行えばいい
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,N) cin >> A[i];

    vector<vector<int>> v(200);
    REP(i,1<<min(N, 8)){
        vector<int> t;
        int sum = 0;
        REP(j, min(N, 8)) if(i >> j & 1){
            sum = (sum + A[j]) % 200;
            t.emplace_back(j+1);
        }
        if(!v[sum].empty()){
            cout << "Yes" << endl;
            cout << v[sum].size() << " ";
            for(auto x : v[sum]) cout << x << " ";
            cout << endl;
            cout << t.size() << " ";
            for(auto x : t) cout << x << " ";
            cout << endl;
            return;
        }
        v[sum] = t;
    }
    cout << "No" << endl;
}

ZONeエナジー プログラミングコンテスト “HELLO SPACE”

atcoder.jp

A - UFO襲来

全探索で判定する
提出コード

void solve(){
    string S;
    cin >> S;
    int ans = 0;
    REP(i,9){
        if(S.substr(i, 4) == "ZONe") ans++;
    }
    cout << ans << endl;
}

B - 友好の印

むずかしい
$ i $ 番目の遮蔽物に対してUFOが見えるギリギリの高さを求める
これは $ i $ 番目遮蔽物とUFOの傾きを求めてその直線の切片を求めればいい
傾きは $ \frac{D - d_i}{H - h_i} $ となり、切片は $ h_i - d_i \frac{D - d_i}{H-h} $ となる
すべての遮蔽物に対しこれを求め、その最大が答え
提出コード

void solve(){
    int N;
    double D, H;
    cin >> N >> D >> H;
    double ans = 0;
    REP(i,N){
        double d, h;
        cin >> d >> h;
        double dx = D - d;
        double dh = H - h;
        double p = dh / dx;
        double c = h - p * d;
        chmax(ans, c);
    }
    printf("%.12lf\n", ans);
}

C - MAD TEAM

むずかしい
答えを決め打つ二分探索をする
ある整数 $ x $ が答えになるかどうかを考えるとそれぞれの能力値は$ x $ 以上なら1、そうでないなら0として状態を圧縮できる
そうするとすべての状態数は$ 2^5 = 32 $ 通りになるので、この中から3組選ぶ組み合わせを全探索しても十分に間に合う
提出コード

void solve(){
    int N;
    cin >> N;
    vector abcde(N, vector(5, 0LL));
    REP(i,N) REP(j,5) cin >> abcde[i][j];

    auto check = [&](int x) -> bool{
        set<int> st;
        REP(i,N){
            int bit = 0;
            REP(j,5) if(abcde[i][j] >= x) bit |= (1 << j);
            st.insert(bit);
        }
        bool ok = false;
        for(auto a : st) for(auto b : st) for(auto c : st){
            if((a | b | c) == ((1 << 5) - 1)) ok = true;
        }
        return ok;
    };

    int l = 0, r = INF + 10;
    while(r - l > 1){
        int m = (l + r) >> 1;
        if(check(m)) l = m;
        else r = m;
    }
    cout << l << endl;
}

D - 宇宙人からのメッセージ

文字列を実際に反転させる代わりに今反転しているかどうかのフラグをもたせる
反転しているときに文字列を追加するときは文字列の先頭に、そうでないなら後ろに追加する
追加が終わったあとに反転フラグが立っていれば文字列をreverseさせる
最後に、stackなどで同じ文字が隣り合っていればその部分を消していき残った文字列を出力する
提出コード

void solve(){
    string S;
    cin >> S;
    int x = 0;
    deque<char> dq;
    for(char c : S){
        if(c == 'R') x = 1 - x;
        else{
            if(x == 0) dq.push_back(c);
            else dq.push_front(c);
        }
    }
    string tmp;
    while(!dq.empty()){
        tmp += dq.front();
        dq.pop_front();
    }
    if(x) reverse(tmp.begin(), tmp.end());
    string ans = "";
    for(char c : tmp){
        if(ans == "") ans += c;
        else{
            if(ans.back() == c) ans.pop_back();
            else ans += c;
        }
    }
    cout << ans << endl;
}

E - 潜入

愚直で通しちゃった
想定解は4つ目の操作を行っている途中かどうかの頂点を増やしてあげてそのグラフ上でダイクストラをすればいい
提出コード

void solve(){
    int R, C;
    cin >> R >> C;
    vector<vector<ll>> A(R+1, vector<ll>(C+1));
    vector<vector<ll>> B(R+1, vector<ll>(C+1));
    REP(i,R) REP(j,C-1) cin >> A[i+1][j+1];
    REP(i,R-1) REP(j,C) cin >> B[i+1][j+1];
    vector dist(R+1, vector(C+1, LINF));
    priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<tuple<ll, int, int>>> pq;
    pq.emplace(0, 1, 1);
    dist[1][1] = 0;
    while(!pq.empty()){
        auto [d, nr, nc] = pq.top(); pq.pop();
        if(dist[nr][nc] < d) continue;
        chmin(dist[nr][nc], d);
        if(nc < C){
            if(chmin(dist[nr][nc+1], A[nr][nc] + d)) pq.emplace(dist[nr][nc+1], nr, nc+1);
        }
        if(nc > 1){
            if(chmin(dist[nr][nc-1], A[nr][nc-1] + d)) pq.emplace(dist[nr][nc-1], nr, nc-1);
        }
        if(nr  < R){
            if(chmin(dist[nr+1][nc], B[nr][nc] + d)) pq.emplace(dist[nr+1][nc], nr+1, nc);
        }
        for(int i=1;i<nr;i++){
            if(chmin(dist[nr-i][nc], i + d + 1)) pq.emplace(dist[nr-i][nc], nr-i, nc);
        }
    }
    cout << dist[R][C] << endl;
}

AtCoder Beginner Contest 199(ABC199)

atcoder.jp

A - Square Inequality

オーバーフローなどの心配もないので素直に判定をする
提出コード

void solve(){
    ll A, B, C;
    cin >> A >> B >> C;
    if(A * A + B * B < C * C) cout << "Yes" << endl;
    else cout << "No" << endl;
}

B - Intersection

最終的な答えは $ \max(A) \leq x \leq \min(B) $ を満たす $ x $ の個数なので $ \max(0, \min(B) - \max(A) + 1) $ が答え
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N), B(N);
    REP(i,N) cin >> A[i];
    REP(i,N) cin >> B[i];
    int a = 0, b = INF;
    REP(i,N){
        chmax(a, A[i]);
        chmin(b, B[i]);
    }
    cout << max(0, b - a + 1) << endl;
}

C - IPFL

愚直に文字列を作り直したりすると間に合わないので少し工夫する必要がある
今どっちが先頭なのかをflagなどで持っておくと、swapを行うだけでいいので十分に間に合う
提出コード

void solve(){
    int N, Q;
    string S;
    cin >> N >> S >> Q;
    string s1 = S.substr(0, N);
    string s2 = S.substr(N, 2*N);
    int x = 0;
    REP(i,Q){
        int t, a, b;
        cin >> t >> a >> b;
        --a, --b;
        // dumps(i, a, b, x);
        if(t == 1){
            if(x == 0){
                if(a < N and b < N) swap(s1[a], s1[b]);
                else if(a < N and b >= N) swap(s1[a], s2[b-N]);
                else swap(s2[a-N], s2[b-N]);
            }
            else{
                if(a < N and b < N){
                    swap(s2[a], s2[b]);
                }
                else if(a < N and b >= N){
                    swap(s2[a], s1[b-N]);
                }
                else{
                    swap(s1[a-N], s1[b-N]);
                }
            }
        }
        else{
            x = 1 - x;
        }
    }
    if(x) cout << s2 << s1 << endl;
    else cout << s1 << s2 << endl;
}

D - RGB Coloring 2

どの頂点をどの色で塗るかを全探索をすると$ \mathcal{O}(3^N) $ となり間に合わない
どの頂点を赤色で塗り、他の頂点を青と緑色で塗るかを考える
そうすると、赤色で塗った頂点以外の各連結成分が二部グラフになっていればよくその場合の数を数えればいい
そのため、どの頂点を赤色で塗るかをbit全探索をし、各連結成分ごとに二部グラフになっているかを判定する
二部グラフを満たす場合、グラフ全体の連結成分の個数を $ sz $、赤色で塗った頂点の個数を $ cnt $ とすると $ 2 ^ {sz - cnt} $ 通り答えに加算する
実際の実装では二部グラフ判定のために頂点数を拡張しているので $ 2 ^ {\frac{sz}{2} - cnt} $ となる
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<int> edge(N);
    REP(i,M){
        int a, b;
        cin >> a >> b;
        --a, --b;
        edge[a] |= (1 << b);
        edge[b] |= (1 << a);
    }
    ll ans = 0;
    REP(i,1<<N){
        int cnt = 0;
        bool ok = true;
        REP(j,N) if(i >> j & 1){
            if(i & edge[j]) ok = false;
            cnt++;
        }
        if(!ok) continue;
        UnionFind uf(2*N);
        int sz = 2 * N;
        REP(j,N) if(!(i >> j & 1)){
            for(int k=j+1;k<N;k++){
                if((edge[j] >> k & 1) and !((i >> k & 1))){
                    if(uf.unite(j, k + N)) sz--;
                    if(uf.unite(k, j + N)) sz--;
                }
            }
        }
        REP(i,N) if(uf.issame(i, i + N)) ok = false;
        if(ok) ans += 1 << (sz / 2 - cnt);

    }
    cout << ans << endl;
}

E - Permutation

$ dp[state] := $ すでに選んだ整数の状態が $ state $ かつ $ X_i \leq |state| $ であるような条件を満たしているときの場合の数としてbitDPを行う
$ x \notin state $ を満たす整数 $ x $ を追加する時、$ X_i = |state \cap x | $ を満たす $ i $ について、$ state \cap x $ に含まれる $ Y_i $ 以下の整数が $ Z_i $ 以下の場合DPの遷移が可能となる
そのため、上記の条件を満たすようなDP遷移を行ったときの $ dp[2^N -1 ] $ が最終的な答えとなる
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<int> X(M), Y(M), Z(M);
    REP(i,M) cin >> X[i] >> Y[i] >> Z[i];
    vector dp(1<<N, 0LL);
    dp[0] = 1;
    for(int i=1;i<(1<<N);i++){
        bool ok = true;
        REP(j,M){
            if(__builtin_popcount(i) != X[j]) continue;
            int cnt2 = 0;
            REP(k,Y[j]) if(i >> k & 1) cnt2++;
            if(cnt2 > Z[j]) ok = false;
        }
        if(!ok) continue;
        REP(j,N) if(i >> j & 1) dp[i] += dp[i^(1<<j)];
    }
    cout << dp[(1<<N)-1] << endl;;
}

第二回日本最強プログラマー学生選手権

atcoder.jp

A - Competition

$ \frac{Y}{X} \gt \frac{i}{Z} $ を満たすような値段 $ i $ が答え
よって分母を払って $ ZY \gt Xi $ を満たす最大の $ i $ を全探索する
提出コード

void solve(){
    int X, Y, Z;
    cin >> X >> Y >> Z;
    int ma = 0;
    REP(i,1010101){
        if(Z * Y > X * i) chmax(ma, i);
    }
    cout << ma << endl;
}

B - Xor of Sequences

$ A_i, B_i $ を $ i $ が $ A, B $ に含まれる個数とすると
$ A _i > 0 $ and $ B_i = 0 $ もしくは $ A_i = 0 $ and $ B_i > 0 $ を満たす $ i $を出力すればいい
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<int> A(1010), B(1010);
    REP(i,N){
        int a;
        cin >> a;
        A[a]++;
    }
    REP(i,M){
        int a;
        cin >> a;
        B[a]++;
    }
    vector<int> ans;
    REP(i,1010){
        if(A[i] > 0 and B[i] == 0) ans.emplace_back(i);
        if(B[i] > 0 and A[i] == 0) ans.emplace_back(i);
    }
    sort(ans.begin(), ans.end());
    REP(i,ans.size()) cout << ans[i] << " ";
    cout << endl;
}

C - Max GCD 2

難しい
$ i $ の倍数を考えたときに、 $ i $ の倍数が $ [A, B] $ の区間の中に2個以上存在すればいい
よって、$ 1 \leq i \lt B $ の範囲で $ i $ の倍数が2個以上あるもののなかで最大のものが答え
計算量は調和級数で $ \mathcal{O}(N \log N) $
提出コード

void solve(){
    int A, B;
    cin >> A >> B;
    int ma = 0;
    for(int i=1;i<B;i++){
        int cnt = 0;
        for(int j=i;j<=B;j+=i){
            if(A <= j) cnt++;
        }
        if(cnt >= 2) chmax(ma, i);
    }
    cout << ma << endl;
}

D - Nowhere P

$ A_1 $ には $ P - 1 $ 個好きに選べる
$ A_2 $ を考えると $ A_1 + A_2 \neq 0 \pmod P $ を満たせばいい
そのため、$ A_1 + A_2 = 0 \pmod P $ となるようなものは1通りしかなく、それ以降も同様なので $ (P-1)(P-2)^{N-1} $ が答え
提出コード

void solve(){
    int N, P;
    cin >> N >> P;
    cout << mint(P - 1) * modpow(mint(P-2), N-1) << endl;
}

F - Max Matrix

ある一点を変更したときの総和の変化は、その一点の変更による差分で計算できるので、総和を持ちながらクエリを処理したときの差分を計算する
クエリの先読みを行って座圧を行い、$ A, B $ に存在する整数の個数、整数ごとの和をそれぞれセグメント木で管理する
今、$ A_x $ を $ Y $ に変更したとすると$ A_x $ 以上の $ B $ に存在する整数の総和、$ A_x $ 未満の$ B $ に存在する整数の個数 $ cnt \times A_x $が答えから取り除かれる
その後、$ Y $ 以上の $ B $ に存在する整数の総和、$ Y $ 未満の$ B $ に存在する整数の個数 $ cnt \times Y $ が答えに加算される
$ B_x $ を $ Y $ に変更した場合も同様に差分更新を行い、各クエリごとにその答えを出力する
提出コード

void solve(){
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<int> A(N), B(M);
    Compress<ll> cmp;
    cmp.add(0);
    vector<int> T(Q), X(Q), Y(Q);
    REP(i,Q){
        cin >> T[i] >> X[i] >> Y[i];
        X[i]--;
        cmp.add(Y[i]);
    }
    cmp.build();
    int sz = cmp.size();
    segtree<S, op, e> sum_a(sz), sum_b(sz);
    segtree<S, op, e> cnt_a(sz), cnt_b(sz);
    cnt_a.set(0, N), cnt_b.set(0, M);
    ll ans = 0;
    REP(i,Q){
        int t = T[i], x = X[i], y = Y[i];
        if(t == 1){
            ans -= sum_b.prod(cmp.get(A[x]), sz);
            ans -= cnt_b.prod(0, cmp.get(A[x])) * A[x];
            ll tmp_cnt = cnt_a.get(cmp.get(A[x]));
            cnt_a.set(cmp.get(A[x]), tmp_cnt-1);
            ll tmp_sum = sum_a.get(cmp.get(A[x]));
            sum_a.set(cmp.get(A[x]), tmp_sum - A[x]);
            A[x] = y;
            ans += sum_b.prod(cmp.get(A[x]), sz);
            ans += cnt_b.prod(0, cmp.get(A[x])) * A[x];
            cnt_a.set(cmp.get(A[x]), cnt_a.get(cmp.get(A[x])) + 1);
            sum_a.set(cmp.get(A[x]), sum_a.get(cmp.get(A[x])) + A[x]);
        }
        else{
            ans -= sum_a.prod(cmp.get(B[x]), sz);
            ans -= cnt_a.prod(0, cmp.get(B[x])) * B[x];
            ll tmp_cnt = cnt_b.get(cmp.get(B[x]));
            cnt_b.set(cmp.get(B[x]), tmp_cnt-1);
            ll tmp_sum = sum_b.get(cmp.get(B[x]));
            sum_b.set(cmp.get(B[x]), tmp_sum - B[x]);
            B[x] = y;
            ans += sum_a.prod(cmp.get(B[x]), sz);
            ans += cnt_a.prod(0, cmp.get(B[x])) * B[x];
            cnt_b.set(cmp.get(B[x]), cnt_b.get(cmp.get(B[x])) + 1);
            sum_b.set(cmp.get(B[x]), sum_b.get(cmp.get(B[x])) + B[x]);
        }
        cout << ans << endl;
    }
}

AtCoder Beginner Contest 198(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;
}