接着剤の精進日記

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

AtCoder Beginner Contest 240（ABC240）

AtCoderBeginnerContest AtCoderBeginnerContest240 ABC ABC240

atcoder.jp

A - Edge Checker

$ a + 1 = b $、もしくは $ a = 1 $ かつ $ b = 10 $ のときYes

提出コード

void solve(){
    int a, b;
    cin >> a >> b;
    if(a + 1 == b or (a == 1 and b == 10)) cout << "Yes" << endl;
    else cout << "No" << endl;
}

B - Count Distinct Integers

setで種類数を数える

提出コード

void solve(){
    int N;
    cin >> N;
    set<int> st;
    REP(i,N){
        int a;
        cin >> a;
        st.insert(a);
    }
    cout << st.size() << endl;
}

C - Jumping Takahashi

$ dp[i][j] := i $ 回目までに $ j $ にたどり着けるかどうかでDPをする

提出コード

void solve(){
    int N, X;
    cin >> N >> X;
    vector<int> dp(101010);
    dp[0] = 1;
    REP(i,N){
        int a, b;
        cin >> a >> b;
        vector<int> nxt(101010);
        REP(j,101010) if(dp[j]){
            if(j + a < 101010) nxt[j+a] = 1;
            if(j + b < 101010) nxt[j+b] = 1;
        }
        swap(dp, nxt);
    }
    cout << (dp[X] ? "Yes" : "No") << endl;
}

D - Strange Balls

stackでボールに書かれた総数とその並んでいる個数の情報を持ってシミュレートをする

提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    vector<pair<int, int>> v;
    int sum = 0;
    REP(i,N){
        if(v.empty()){
            v.emplace_back(A[i], 1);
            sum += 1;
        }
        else{
            if(v.back().first == A[i]){
                if(v.back().second + 1 >= A[i]){
                    sum -= v.back().second;
                    v.pop_back();
                }
                else{
                    v.back().second++;
                    sum++;
                }
            }
            else{
                v.emplace_back(A[i], 1);
                sum++;
            }
        }
        cout << sum << endl;
    }
}

E - Ranges on Tree

葉同士はお互いに独立になっているのでそれぞれ別の数字を割り当てる必要がある
それ以外の頂点では、部分木に含まれる葉に割り当てた数字のminとmaxを求めればいい

提出コード

void solve(){
    int N;
    cin >> N;
    vector<vector<int>> g(N);
    REP(i,N-1){
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    vector<pair<int, int>> dp(N, {INF, 0});
    int leaf = 1;
    auto dfs = [&](auto && self, int v, int par=-1, int mi=INF, int ma=0) -> pair<int, int>{
        bool is_leaf = true;
        for(auto nv : g[v]){
            if(nv == par) continue;
            auto [a, b] = self(self, nv, v, mi, ma);
            chmin(dp[v].first, a);
            chmax(dp[v].second, b);
            is_leaf = false;
        }
        if(is_leaf){
            dp[v].first = leaf;
            dp[v].second = leaf;
            leaf++;
        }
        return dp[v];
    };
    dfs(dfs, 0);
    for(auto [a, b] : dp) cout << a << " " << b << endl;
}

AtCoder Beginner Contest 239（ABC239）

AtCoderBeginnerContest AtCoderBeginnerContest239 ABC ABC239

atcoder.jp

A - Horizon

問題文の数式をそのまま求める

提出コード

void solve(){
    ll x;
    cin >> x;
    printf("%.12lf\n", sqrt(x * (x + 12800000)));
}

B - Integer Division

負の数のときの処理に気をつける

提出コード

void solve(){
    ll X;
    cin >> X;
    cout << floor_div(X, 10) << endl;
}

C - Knight Fork

問題文の図にある通り、あり得る箇所は $ (x1, y1) $ の周り8通りと $ (x2, y2) $ の周り8通りなのでこれを全探索し、一致する座標があるかどうかを判定する

提出コード

void solve(){
    ll x1, x2, y1, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
    int dy[8] = {2, 1, -1, -2,  2, 1, -1, -2};
    bool ok = false;
    REP(i,8){
        ll nx1 = x1 + dx[i];
        ll ny1 = y1 + dy[i];
        REP(j,8){
            ll nx2 = x2 + dx[j];
            ll ny2 = y2 + dy[j];
            if(nx1 == nx2 and ny1 == ny2) ok = true;
        }
    }
    cout << (ok ? "Yes" : "No") << endl;
}

D - Prime Sum Game

高橋くんが選んだ数字に対し、青木くんが選べるどの数字を使っても素数にできないとき、高橋くんはその数を選べばいい
そのような数字がないときは青木くんが必ず勝つ

提出コード

void solve(){
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    SieveOfEratosthenes<int> sieve(222);
    bool ok = false;
    for(int i=A;i<=B;i++){
        bool ok2 = true;
        for(int j=C;j<=D;j++){
            if(sieve.is_prime[i+j]) ok2 = false;
        }
        ok |= ok2;
    }
    cout << (ok ? "Takahashi" : "Aoki") << endl;
}

E - Subtree K-th Max

ある頂点において、その頂点の部分木に含まれる頂点に書かれている数字の大きい順に20個求めればいい
DFSをし、葉のほうから順に上位20件の数字を更新していけばいい

提出コード

void solve(){
    int N, Q;
    cin >> N >> Q;
    vector<ll> X(N);
    REP(i,N) cin >> X[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<multiset<int>> dp(N);
    REP(i,N) dp[i].insert(X[i]);
    vector<int> idx(N);
    iota(ALL(idx), 0);
    auto dfs = [&](auto && self, int v, int par) -> void{
        for(auto nv : g[v]){
            if(nv == par) continue;
            self(self, nv, v);
            for(auto &x : dp[nv]){
                if(dp[v].size() < 20) dp[v].insert(x);
                else{
                    dp[v].insert(x);
                    dp[v].erase(dp[v].begin());
                }
            }
        }
        return;
    };
    dfs(dfs, 0, -1);

    REP(i,Q){
        int v, k;
        cin >> v >> k;
        --v, --k;
        for(auto itr=dp[v].rbegin();itr!=dp[v].rend();itr++){
            if(k == 0){
                cout << *itr << endl;
                break;
            }
            k--;
        }
    }
}

F - Construct Highway

$ \sum D_i = 2(N-1) $ の時の場合を考える
連結成分ごとに残りいくつの辺を繋げることができるかを管理する
このとき、残り2以上の連結成分があれば残り1の連結成分との辺を結んでいく
最終的に残り1の連結成分がちょうど2つ残っていれば条件を満たす木を構築することができる

提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<int> D(N);
    REP(i,N) cin >> D[i];
    UnionFind uf(N);
    REP(i,M){
        int a, b;
        cin >> a >> b;
        --a, --b;
        D[a]--, D[b]--;
        uf.unite(a, b);
    }
    vector<vector<int>> v(N);
    REP(i,N){
        if(D[i] < 0){
            cout << -1 << endl;
            return;
        }
        REP(j,D[i]) v[uf.root(i)].emplace_back(i);
    }
    vector<int> cnt1;
    vector<vector<int>> cnt2;
    REP(i,N){
        if(v[i].size() == 1) cnt1.emplace_back(v[i][0]);
        else if(v[i].size() > 1) cnt2.emplace_back(v[i]);
    }
    vector<pair<int, int>> ans;
    for(auto vec : cnt2){
        REP(i,(int)vec.size()-1){
            if(cnt1.empty()){
                cout << -1 << endl;
                return;
            }
            uf.unite(vec[i], cnt1.back());
            ans.emplace_back(vec[i], cnt1.back());
            cnt1.pop_back();
        }
        cnt1.emplace_back(vec.back());
    }
    if(cnt1.size() != 2){
        cout << -1 << endl;
        return;
    }
    uf.unite(cnt1[0], cnt1[1]);
    ans.emplace_back(cnt1[0], cnt1[1]);
    if(uf.size(0) != N){
        cout << -1 << endl;
        return;
    }
    for(auto [a, b] : ans) cout << a+1 << " " << b+1 << endl;
}

AtCoder Beginner Contest 238（ABC238）

AtCoderBeginnerContest AtCoderBeginnerContest238 ABC ABC238

atcoder.jp

A - Exponential or Quadratic

$ n \geq 60 $ のとき、必ず成り立つので $ n = \min(n, 60) $ として比較を行う

提出コード

void solve(){
    ll n;
    cin >> n;
    ll N = n * n;
    ll two = 1LL << (min(n, 60LL));
    if(two > N) cout << "Yes" << endl;
    else cout << "No" << endl;
}

B - Pizza

実際に切れ込みの入る位置を求めたあと、その間の角度の最大を求める

提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    set<int> st;
    int cur = 0;
    st.insert(0);
    st.insert(360);
    REP(i,N){
        cur += A[i];
        cur %= 360;
        st.insert(cur);
    }
    int dir = 0;
    int ans = 0;
    for(auto x : st){
        chmax(ans, x - cur);
        cur = x;
    }
    cout << ans << endl;
}

C - digitnum

$ i $ 桁の数字ごとに分けて考える
それぞれの桁数ごとで考えると、その和は等差数列になるのでその総和が答え

提出コード

void solve(){
    ll N;
    cin >> N;
    ll cur = 9;
    ll pre = 1;
    mint ans = 0;
    REP(i,18){
        if(N <= cur){
            cur = N;
        }
        mint n = cur - pre + 1;
        ans += n * (n + 1) / 2;
        if(N <= cur) break;
        cur = 10 * cur + 9;
        pre *= 10;
    }
    cout << ans << endl;
}

D - AND and SUM

$ x + y = 2(x \& y) + x \oplus y $ であるので、$ s - 2a = x \oplus y $ となりこれを満たす $ (x, y) $ が存在すればいい
これは $ s - 2a \geq 0 $ かつ $ (s - 2a) \& a = 0 $ を満たせばいい

提出コード

void solve(){
    ll a, s;
    cin >> a >> s;
    ll n = s - 2 * a;
    if(n >= 0 and (n & a) == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}

E - Range Sums

$ a $ の累積和 $ b $ を考える
各クエリは $ b_{r} - b_{l - 1} $ と言い換えることができ、片方がわかっていればもう片方の値もわかるのでこの二頂点を連結にするとクエリと考える
そうすると、$ b $ の要素を頂点として考えると、$ b_0 $ から $ b_N $ にたどり着ければ良いことになる
よって各クエリに対してUnionFindなどで頂点を連結させ、$ b_0 $ と $ b_N $ が連結かどうかを判定すればいい

提出コード

void solve(){
    int N, Q;
    cin >> N >> Q;
    UnionFind uf(N+1);
    REP(i,Q){
        int l, r;
        cin >> l >> r;
        uf.unite(--l, r);
    }
    cout << (uf.issame(0, N) ? "Yes" : "No") << endl;
}

F - Two Exams

$ dp[i][j][k] := i $ 番目まで見た時に、$ j $ 人選び、選んでいない人の中で最小の順位が $ k $ のときの選び方の場合の数としてDPを行う

提出コード

void solve(){
    int N, K;
    cin >> N >> K;
    vector<int> P(N), Q(N);
    REP(i,N){
        cin >> P[i];
        --P[i];
    }
    REP(i,N){
        cin >> Q[i];
        --Q[i];
    }
    vector<int> idx(N);
    iota(ALL(idx), 0);
    sort(ALL(idx), [&](int a, int b){
        return P[a] < P[b];
    });
    vector dp(K+10, vector<mint>(N+10));
    dp[0][N] = 1;
    for(auto i : idx){
        vector nxt(K+10, vector<mint>(N+10));
        REP(x,K+1) REP(y,N+1){
            if(Q[i] < y) nxt[x+1][y] += dp[x][y];
            nxt[x][min(y, (ll)Q[i])] += dp[x][y];
        }
        swap(nxt, dp);
    }
    mint ans = 0;
    REP(i,N+1) ans += dp[K][i];
    cout << ans << endl;
}

AtCoder Beginner Contest 237（ABC237）

AtCoderBeginnerContest AtCoderBeginnerContest237 ABC ABC237

atcoder.jp

A - Not Overflow

実際に比較する

提出コード

void solve(){
    ll N;
    cin >> N;
    const ll lower = -(1LL << 31);
    const ll upper = 1LL << 31;
    if(lower <= N and N < upper) cout << "Yes" << endl;
    else cout << "No" << endl;
}

B - Matrix Transposition

$ B_{i,j} = A_{j,i} $ となるのでこれを出力する

提出コード

void solve(){
    int H, W;
    cin >> H >> W;
    vector<vector<int>> mat(H, vector<int>(W));
    REP(i,H) REP(j,W) cin >> mat[i][j];
    REP(i,W){
        REP(j,H) cout << mat[j][i] << " ";
        cout << endl;
    }
}

C - kasaka

先頭と末尾の a が一致している間それらを削除し、削除後の文字列 $ T $ を考える
この時点で回文ならばYes
そうでない場合、$ T $ の末尾の aの数だけ先頭にaを追加し、その文字列が回文ならばYes、そうでないならNoとなる

提出コード

void solve(){
    string S;
    cin >> S;
    int N = S.size();
    int cnt = 0;
    REP(i,N){
        if(S[i] == 'a' and S[N-i-1] == 'a') cnt++;
        else break;
    }
    string T = "";
    for(int i = cnt;i < N - cnt;i++) T += S[i];
    string U = T;
    reverse(ALL(U));
    if(T == U){
        cout << "Yes" << endl;
        return;
    }
    int cnt2 = 0;
    for(int i=(int)T.size()-1;i>=0;i--){
        if(T[i] == 'a') cnt2++;
        else break;
    }
    U = string(cnt2, 'a') + T;
    string V = U;
    reverse(ALL(V));
    if(U == V) cout << "Yes" << endl;
    else cout << "No" << endl;

D - LR insertion

$ i $ の左側にある数と右側にある数を配列で管理をする
$ i $ を挿入する際には、$ i $ の挿入する位置の左にある数と右にある数のみなので、挿入するたびにその分を更新していく

提出コード

void solve(){
    int N;
    cin >> N;
    string S;
    cin >> S;
    vector<pair<int, int>> vp(N+1, {-1, -1});
    REP(i,N){
        char c = S[i];
        if(c == 'L'){
            int l = vp[i].first;
            if(l == -1){
                vp[i].first = i+1;
                vp[i+1].second = i;
            }
            else{
                vp[i+1].first = l;
                vp[i+1].second = i;
                vp[l].second = i+1;
                vp[i].first = i+1;
            }
        }
        else{
            int r = vp[i].second;
            if(r == -1){
                vp[i].second = i+1;
                vp[i+1].first = i;
            }
            else{
                vp[i+1].second = r;
                vp[i+1].first = i;
                vp[r].first = i+1;
                vp[i].second = i+1;
            }
        }
    }
    int start = -1;
    REP(i,N+1) if(vp[i].first == -1) start = i;
    int nxt = start;
    while(nxt != -1){
        cout << nxt << " ";
        nxt = vp[nxt].second;
    }
    cout << endl;
}

E - Skiing

楽しさの $ -1 $ 倍したものをコストとしたグラフでのダイクストラを行うことを考える
このグラフ上では、$ H_i \lt H_j $ のとき、コストは $ H_i - H_j \lt 0 $ と負になる場合がある
そのため、ポテンシャルを用いてダイクストラを適用できるようにする
$ i \rightarrow j $ に移動するときのコストを元のコスト $ c $ を用いて $ c’ = c + (H_i - H_j) $ とすると、$ H_i \gt H_j $ のとき、$ i \rightarrow j $ の辺はコスト $ 0 $、 $ j \rightarrow i $ の辺はコスト $ H_i - H_j $ となるので負の辺がないこのグラフ上でダイクストラを行う

提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<ll> H(N);
    REP(i,N) cin >> H[i];
    vector<vector<int>> g(N);
    REP(i,M){
        int u, v;
        cin >> u >> v;
        g[--u].emplace_back(--v);
        g[v].emplace_back(u);
    }
    priority_queue<LP, vector<LP>, greater<LP>> pq;
    vector<ll> dist(N, LINF);
    dist[0] = 0;
    pq.emplace(0, 0);
    while(!pq.empty()){
        auto [d, v] = pq.top(); pq.pop();
        if(d < dist[v]) continue;
        for(auto nv : g[v]){
            ll nxt = max(H[nv] - H[v], 0LL);
            if(chmin(dist[nv], dist[v] + nxt)){
                pq.emplace(dist[nv], nv);
            }
        }
    }
    ll ans = 0;
    REP(i,N) chmax(ans, H[0] - H[i] - dist[i]);
    cout << ans << endl;
}

F - |LIS| = 3

長さ3のLISを求める際のDP配列をキーとしてDPを行えばよい
$ dp[i][j][k][l] := i $ まで見た時に、長さ1、2、3の増加部分列の右端になるものの最小値がそれぞれ$ j, k, l $ のときの数列の個数としてDPを行う

提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector dp(N+1, vector(M+1, vector(M+1, vector<mint>(M+1, 0))));
    dp[0][M][M][M] = 1;
    REP(i,N) REP(j,M+1) REP(k,M+1) REP(l,M+1){
        REP(x,M){
            if(x <= j) dp[i+1][x][k][l] += dp[i][j][k][l];
            else if(x <= k) dp[i+1][j][x][l] += dp[i][j][k][l];
            else if(x <= l) dp[i+1][j][k][x] += dp[i][j][k][l];
        }
    }
    mint ans = 0;
    REP(i,M) REP(j,i+1,M) REP(k,j+1,M) ans += dp[N][i][j][k];
    cout << ans << endl;
}

AtCoder Beginner Contest 236（ABC236）

AtCoderBeginnerContest AtCoderBeginnerContest236 ABC ABC236

atcoder.jp

A - chukodai

$ a, $ 文字目と $ b $ 文字目をswap

提出コード

void solve(){
    string S;
    cin >> S;
    int a, b;
    cin >> a >> b;
    --a, --b;
    swap(S[a], S[b]);
    cout << S << endl;
}

B - Who is missing?

それぞれの数をカウントして $ A_i = 3 $ なる $ i $ を出力

提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,4*N-1){
        int a;
        cin >> a;
        A[--a]++;
    }
    REP(i,N) if(A[i] == 3) cout << i + 1 << endl;
}

C - Route Map

$ S_i $ が $ T_j $ に出現するかどうかをmapなどで管理する

提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<string> S(N), T(M);
    map<string, bool> mp;
    REP(i,N){
        cin >> S[i];
        mp[S[i]] = false;
    }
    REP(i,M){
        cin >> T[i];
        mp[T[i]] = true;
    }
    REP(i,N) cout << (mp[S[i]] ? "Yes" : "No") << endl;
}

D - Dance

探索順を工夫することで全探索できる
$ i $ 番目のペアを作成する時に、まだペアに使っていないもののうち、一番左のものを使用することにする
そうすると状態数は最大で $ 15 \times 13 \times \dots \times 1 = 2027025 $ となり全探索で十分に間に合う

提出コード

void solve(){
    int N;
    cin >> N;
    vector<vector<int>> A(2*N, vector<int>(2*N));
    REP(i,2*N) REP(j,i+1,2*N) cin >> A[i][j];
    ll ans = 0;
    auto dfs = [&](auto && self, vector<pair<int, int>> v, vector<bool> used) -> void{
        if(v.size() == N){
            ll sum = 0;
            for(auto [a, b] : v) sum ^= A[a][b];
            chmax(ans, sum);
            return;
        }
        int l = 0;
        REP(i,2*N) if(!used[i]){
            l = i;
            break;
        }
        used[l] = true;
        REP(i,2*N) if(!used[i]){
            v.emplace_back(l, i);
            used[i] = true;
            self(self, v, used);
            used[i] = false;
            v.pop_back();
        }
        used[l] = false;
        return;
    };
    vector<pair<int, int>> v;
    vector<bool> used(2*N);
    dfs(dfs, v, used);
    cout << ans << endl;
}

E - Average and Median

平均値の最大と、中央値の最大に対しそれぞれ二分探索を行う
平均値の最大の場合、平均値を $ m $ とすると、予め $ A_i = A_i - m $ とした状態で選んだものの総和が $ 0 $ 以上であれば条件を満たす
よって、上記をDPで求めながら平均値の最大を二分探索で求める
中央値も同様に、

$$ A_i = \left\{ \begin{array}{c} 1 (A_i \geq m) \\ -1 (A_i \lt m) \end{array} \right. $$ とした状態で選んだものの総和が0より大きいとき条件を満たすので同様に求める

提出コード

void solve(){
    ll N;
    cin >> N;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    {
        auto f = [&](long double m) -> bool{
            vector<long double> dp(N, -LINF);
            dp[0] = A[0] - m;
            dp[1] = A[1] - m;
            REP(i,N){
                if(i + 1 < N) chmax(dp[i+1], dp[i] + A[i+1] - m);
                if(i + 2 < N) chmax(dp[i+2], dp[i] + A[i+2] - m);
            }
            return max(dp[N-2], dp[N-1]) >= 0.0 ? true : false;
        };
        long double l = 0, r = LINF;
        REP(i,200){
            long double m = (l + r) / 2;
            if(f(m)) l = m;
            else r = m;
        }
        printf("%.12Lf\n", l);
    }
    {
        auto f = [&](ll m) -> bool{
            vector<ll> dp(N+1, -INF);
            dp[0] = (A[0] >= m ? 1 : -1);
            dp[1] = (A[1] >= m ? 1 : -1);
            REP(i,N){
                if(i + 1 < N) chmax(dp[i+1], dp[i] + (A[i+1] >= m ? 1 : -1));
                if(i + 2 < N) chmax(dp[i+2], dp[i] + (A[i+2] >= m ? 1 : -1));
            }
            return max(dp[N-1], dp[N-2]) > 0 ? true : false;
        };
        ll l = 0, r = LINF;
        while(r - l > 1){
            ll m = (l + r) >> 1;
            if(f(m)) l = m;
            else r = m;
        }
        printf("%d\n", l);
    }
}

F - Spices

$ c_i $ の昇順にソートした状態で、xorの基底を求める
$ i $ が基底に追加される場合、答えに$ c_i $ を加算する

提出コード

void solve(){
    int N;
    cin >> N;
    vector<LP> v;
    REP(i,(1<<N) - 1){
        int c;
        cin >> c;
        v.emplace_back(c, i+1);
    }
    sort(ALL(v));
    ll ans = 0;
    vector<ll> bases;
    for(auto [c, val] : v){
        for(auto base : bases) chmin(val, val ^ base);
        if(val > 0){
            ans += c;
            bases.emplace_back(val);
        }
    }
    cout << ans << endl;
}