接着剤の精進日記

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

トップ > AtCoderBeginnerContest > SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)

SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)

AtCoderBeginnerContest AtCoderBeginnerContest192 ABC ABC192

atcoder.jp

A - Star

今の値から次の100の倍数までの差を求めたいので $ 100 - x \% 100 $ を出力
提出コード

void solve(){
    int X;
    cin >> X;
    X %= 100;
    cout << 100 - X << endl;
}

B - uNrEaDaBlE sTrInG

問題文の条件を満たしているかどうかを判定すればいい
提出コード

void solve(){
    string s;
    cin >> s;
    bool ok = true;
    REP(i,s.size()){
        if(i % 2 == 0){
            if('a' <= s[i] and s[i] <= 'z'){}
            else ok = false;
        }
        else{
            if('A' <= s[i] and s[i] <= 'Z'){}
            else ok = false;
        }
    }
    cout << (ok ? "Yes" : "No") << endl;
}

C - Kaprekar Number

毎回愚直に求めても十分間に合うのでシミュレートすればいい
提出コード

void solve(){
    string N;
    int K;
    cin >> N >> K;
    vector<int> ans;
    set<string> st;
    auto num = [&](string s) -> int{
        int res = 0;
        REP(i,s.size()){
            res = res * 10 + (s[i] - '0');
        }
        return res;
    };
    string pre = N;
    while(K--){
        string cur = pre;
        sort(cur.rbegin(), cur.rend());
        ll g1 = num(cur);
        sort(cur.begin(), cur.end());
        ll g2 = num(cur);
        ll nxt = g1 - g2;
        string ns = "";
        if(nxt == 0) ns = '0';
        while(nxt > 0){
            ns += char('0' + nxt % 10);
            nxt /= 10;
        }
        reverse(ns.begin(), ns.end());
        pre = ns;
    }
    cout << pre << endl;
}

D - Base n

難しい
$ X $ を $ n $ 進法表記で表した数には単調性があるのでオーバーフローに気をつけながら二分探索をすればいい
ただし $ | X | = 1 $ のときは答えが 0 か 1 になるので場合分けが必要
提出コード

void solve(){
    string X;
    ll M;
    cin >> X >> M;
    int d = 0;
    reverse(X.begin(), X.end());
    for(auto x : X) chmax(d, x - '0');
    if(X.size() == 1){
        if(d > M) cout << 0 << endl;
        else cout << 1 << endl;
        return;
    }
    ll l = d, r = M+1;
    auto check = [&](ll x) -> bool{
        ll cur = 0;
        ll base = 1;
        REP(i,X.size()){
            if((X[i] - '0') > LINF / base){
                return false;
            }
            ll tmp = base * (X[i] - '0');
            if(cur > LINF - tmp){
                return false;
            }
            cur += tmp;
            if(base > LINF / x){
                if(i + 1 < X.size()) return false;
            }
            base *= x;
        }
        if(cur > M) return false;
        else return true;
    };

    while(r - l > 1){
        ll m = (r + l) >> 1;
        if(check(m)) l = m;
        else r = m;
    }

    cout << l - d << endl;
}

E - Train

鉄道 $ i $ を使って 時刻 $ d $ に $ A_i $ から $ B_i $ に移動するとき、最短で $ \lceil \frac{d}{K_i} \rceil \times K_i + T_i $ で着くことができる
上記をコストとしたダイクストラで解くことができる
提出コード

void solve(){
    int N, M, X, Y;
    cin >> N >> M >> X >> Y;
    --X, --Y;
    vector<vector<tuple<int, ll, ll>>> g(N);
    REP(i,M){
        int A, B, T, K;
        cin >> A >> B >> T >> K;
        g[--A].emplace_back(--B, T, K);
        g[B].emplace_back(A, T, K);
    }
    vector<ll> dist(N, LINF);
    dist[X] = 0;
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
    pq.emplace(0, X);
    while(!pq.empty()){
        auto [d, cur] = pq.top(); pq.pop();
        if(d > dist[cur]) continue;
        for(auto [nxt, t, k] : g[cur]){
            ll nxt_d = (d + k - 1) / k * k + t;
            if(chmin(dist[nxt], nxt_d)){
                pq.emplace(dist[nxt], nxt);
            }
        }
    }
    ll ans = dist[Y];
    if(dist[Y] == LINF) ans = -1;
    cout << ans << endl;
}

F - Potion

選ぶ個数 $ k $ を固定して考えると
$ dp[i][j][l] := i $ 番目まで見たときに $ j $ 個選んで総和が $ l \pmod{k} $ のときの最大値としてDPをする
$ dp[N][k][X\%k] \neq -1 $ のとき $ \frac{X - dp[N][k][X\%k]}{k} $ となるのですべての $ k $ について上記のDPを行えば $ \mathcal{O}(N^4) $ で解ける
提出コード

void solve(){
    int N;
    ll X;
    cin >> N >> X;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    ll ans = LINF;
    for(int k=1;k<=N;k++){
        vector dp(N+1, vector(N+1, vector(N+1, -1LL)));
        dp[0][0][0] = 0;
        REP(i,N){
            REP(j,N){
                REP(l,N){
                    if(dp[i][j][l] == -1) continue;
                    chmax(dp[i+1][j][l], dp[i][j][l]);
                    chmax(dp[i+1][j+1][(l+A[i])%k], dp[i][j][l] + A[i]);
                }
            }
        }
        if(dp[N][k][X%k] != -1) chmin(ans, (X - dp[N][k][X%k]) / k);
    }
    cout << ans << endl;
}