久しぶりにやらかして冷えた〜
A - Poor
A、B、Cの中なら一番難しかった(読解力さん…)
最初ソートしてa[0] == a[1] && a[0] != a[2]でよし!wをやってWA
それはそうなんですよね、C解いた後戻ってきてsetを使った
提出コード
int main(){ cin.tie(0); ios::sync_with_stdio(false); set<int> st; REP(i,3){ int a; cin >> a; st.insert(a); } if(st.size() == 2) cout << "Yes" << endl; else cout << "No" << endl; }
B - Papers, Please
これも読解力?
言われたとおり偶数についてだけチェックする
提出コード
int main(){ cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; vector<int> A(N); REP(i,N) cin >> A[i]; string ans = "APPROVED"; REP(i,N){ if(A[i] % 2 == 0){ if(A[i] % 3 == 0 || A[i] % 5 == 0) continue; else ans = "DENIED"; } } cout << ans << endl; }
C - Poll
慣れているとこれが一番早く解けそう
mapとかで出現回数を持っておいて、最大のものをvectorとかに入れてソートする
本番vectorに入れた後ソートしたけどmapでやってるからソートいらないよね
提出コード
int main(){ cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; map<string, int> mp; int ma = 0; REP(i,N){ string s; cin >> s; mp[s]++; chmax(ma, mp[s]); } vector<string> ans; for(auto x : mp){ if(x.second == ma) ans.push_back(x.first); } sort(ans.begin(), ans.end()); REP(i,ans.size()) cout << ans[i] << endl; }
D - Pairs
ぱっと見にぶたんとかでやりそうな雰囲気
負の数と交じるので処理が面倒くさそうだなあとなり一旦Eを見に行きEのほうが解けそうだったので結局本番中解かずに終わり
まだ実装してないので実装したらコード貼ります
[追記]
提出コード
int main(){ cin.tie(0); ios::sync_with_stdio(false); ll N, K; cin >> N >> K; vector<ll> A(N); REP(i,N) cin >> A[i]; sort(A.begin(), A.end()); auto f = [&](ll tar, ll a) -> ll{ ll l = -1, r = N; while(r - l > 1){ ll m = (r + l) >> 1; if(a * A[m] <= tar){ if(a < 0) r = m; else l = m; } else{ if(a < 0) l = m; else r = m; } } if(a < 0) return N - r; else return r; }; ll l = -LINF, r = LINF; while(r - l > 1){ ll m = (l + r) >> 1; ll cnt = 0; REP(i,N){ cnt += f(m, A[i]); if(A[i] * A[i] <= m) cnt--; } if(cnt / 2 >= K) r = m; else l = m; } cout << r << endl; }
E - Payment
取り敢えず桁ごとに独立で考える
その桁が5以下ならそのまま使って、6以上なら一桁繰り上げてお釣りを貰ったほうが良さそう
実装する、WA
実はこれだけじゃ不十分で、ある桁が5の時次の位が5以上かどうかで場合分けがもう一つ必要
本番中は、貪欲じゃ解けないじゃんってなってDPも書いてたんだけど結局遷移を間違えて通せなかった
提出コード(貪欲解)
int main(){ cin.tie(0); ios::sync_with_stdio(false); string S; cin >> S; int ans = 0; bool flg = false; reverse(S.begin(), S.end()); int N = S.size(); int cur = 0; REP(i,N){ int a = S[i] - '0'; a += cur; if(a < 5){ ans += a; cur = 0; } else if(a > 5){ ans += 10 - a; cur = 1; } if(a == 5){ if(i < N - 1 && S[i+1] - '0' >= 5){ ans += 10 - a; cur = 1; } else{ ans += a; cur = 0; } } //cout << ans << endl; } if(cur > 0) ans++; cout << ans << endl; }
int dp[1010101][2]; int main(){ cin.tie(0); ios::sync_with_stdio(false); string S; cin >> S; int ans = 0; reverse(S.begin(), S.end()); int N = S.size(); REP(i,1010101) dp[i][0] = dp[i][1] = INF; dp[0][0] = 0; REP(i,N){ int a = S[i] - '0'; chmin(dp[i+1][0], min(dp[i][0], dp[i][1]) + a); chmin(dp[i+1][1], min(dp[i][0] + 11 - a, dp[i][1] + 9 - a)); } cout << min(dp[N][0], dp[N][1]) << endl; }
F - Perils in Parallel
読んでさえいなかったんだけど難しかったらしい?
おわりに
AtCoderのレート最近連続して上がってたしまあ、下がることもあるよね
ただ、内容があんまりよくないのが駄目かなあ
Eみたいな問題初手DPで殴れるようにしたいね