ABC141
所要時間
- 30分ABC3完答,Cで一回WA,D問お手上げ
解答メモ
A
- Weathering with you.
#include <bits/stdc++.h> #define REP(i, x) for (int i = 0; i < (int)(x); i++) #define ALL(x) (x).begin(), (x).end() typedef long long ll; using namespace std; int main() { cin.tie(0); ios::sync_with_stdio(false); string S; cin >> S; if(S == "Sunny"){ cout << "Cloudy" << endl; }else if(S == "Cloudy") { cout << "Rainy" << endl; }else{ cout << "Sunny" << endl; } return 0; }
B
- そのまま解く
#include <bits/stdc++.h> #define REP(i, x) for (int i = 0; i < (int)(x); i++) #define ALL(x) (x).begin(), (x).end() typedef long long ll; using namespace std; int main() { cin.tie(0); ios::sync_with_stdio(false); string S; cin >> S; bool result = true; // odd for(int i=0; i < S.length(); i+=2){ if(!(S[i] == 'R' || S[i] == 'U' || S[i] == 'D')){ result = false; } } if(!result){ cout << "No" << endl; return 0; } if(S.length() == 1){ cout << "Yes" << endl; return 0; } // even for(int i=1; i < S.length(); i+=2){ if(!(S[i] == 'L' || S[i] == 'U' || S[i] == 'D')){ result = false; } } if(result){ cout << "Yes" << endl; }else{ cout << "No" << endl; } return 0; }
C
- 問題を
もし1問も解答できなかった場合の最終スコアはK-Q
と考えると,K-Qに正答できた問題数を足して1以上ならOK
と読み替えられるので で解ける - 一回なぜかWA食らったが,
if(score[i] + K - Q > 0)
でオーバーフローしたためと考えられる(全部 long longで宣言するように修正しただけでACになった)
#include <bits/stdc++.h> #define REP(i, x) for (int i = 0; i < (int)(x); i++) #define ALL(x) (x).begin(), (x).end() typedef long long ll; using namespace std; int main() { cin.tie(0); ios::sync_with_stdio(false); ll N, Q, K; cin >> N >> K >> Q; ll score[100001]; REP(i, N+1) {score[i] = 0;} int tmp_a; REP(i, Q) { cin >> tmp_a; ++score[tmp_a]; } for(long i=1; i<=N; ++i){ if(score[i] + K - Q > 0){ cout << "Yes" << endl; }else{ cout << "No" << endl; } } return 0; }
D
- 以下が分からなかった
- どういう戦略で割引券を使うのが最適か
- 値段でソートして一番高いやつから多く使って行けばいいんじゃね?と思って実装してみたが違った
- どういう戦略で割引券を使うのが最適か
解説PDF
- 以下が分からなかった
- 最初の定理については何となく分かる
- は毎回の除算で小数点以下を切り捨てているので雰囲気は分かる
- しかしこの定理に基づいてどう実装するか?priority_queueの使い方知らないマン
- 以下が分からなかった
解説動画 youtu.be
- めちゃくちゃわかりやすくて感動した.↑の定理はたしかに2進数で考えると「そりゃそうやな」と腑に落ちる(けど数学的に証明できないと使うのは怖い).
- 普通に考えれば「その時点で一番高いものを半額にしていけばよい」というのは確かにそうなのでそう解けば良かったが,↑の定理が思いつかないと厳しいか,あるいは「このような定理が成り立つ.知らんけど.」で,一か八かでこの方針で解くことになりそうではある.D問題解けた人はどうやって導いたんだこれ?
アライグマ「ABC141を解いて90分全完+4WAで80位相当だったのだ。C問題は、毎回ポイントの変化を計算しなくても、ラウンドが終わったときのポイントは「K-Q+正解数」になるからすぐ計算できるのだ。D問題は、金額が高い方から貪欲に券を1枚ずつ使うのだ」
— 競技プログラミングをするフレンズ (@kyopro_friends) September 16, 2019
- みんな大して苦労せずに解いてるところを見るに,競プロ勢にとってはこの程度の問題は普通なのかもしれない...
ともかくpriority_queue使えないと同様の問題で詰むのがよくわかったので,使い方と時間計算量をちゃんと調べておく必要がある
解説見て書いた解答
- priority_queueの時間計算量は,
push
とpop
は,top
はらしい - よって時間計算量は
- priority_queueの時間計算量は,
#include <bits/stdc++.h> #define REP(i, x) for (int i = 0; i < (int)(x); i++) #define ALL(x) (x).begin(), (x).end() typedef long long ll; using namespace std; int main() { cin.tie(0); ios::sync_with_stdio(false); int N, M; priority_queue<ll> A; ll tmp_a; cin >> N >> M; REP(i, N) { cin >> tmp_a; A.push(tmp_a); } REP(i, M) { tmp_a = A.top(); A.pop(); A.push(floor(tmp_a / 2)); } ll result = 0; REP(i, N){ result += A.top(); A.pop(); } cout << result << endl; return 0; }