Bondo416さんのSOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)での成績：1107位
— ボンド@競プロ (@bond_cmprog) February 20, 2021
パフォーマンス：1514相当
レーティング：1529→1527 (-2) :(#AtCoder #SOMPOHDプログラミングコンテスト2021(ABC192) https://t.co/mL2T2m3a8J
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; }
