ABC190に参加しました
AtCoderのコンテストに参加した際の結果と考え方、反省点などを書いていきます。
コンテストページはこちら
解いた問題
A問題
問題の概要
高橋君と青木君が交互にアメを食べあうゲームを行います。
高橋君は個のアメ、青木君は個のアメを持っていて、
の時は高橋君が先に、の時は青木君が先にアメを食べ始めます。
先にアメが無くなるのはどちらでしょうか。
制約
- はまたはのいずれか
- 入力はすべて整数
どのように考えたか
処理分けが面倒くさいので、高橋君が選考になるようにしたい。
青木君のアメからを引いてあげると、高橋君が先行の場合何も起きず、後攻の場合のみ引かれるので青木君が先にアメを食べたことになる。
後は、高橋君が青木君より多くアメを持っていたら高橋君の勝ちで、そうでなければ青木君の勝ちになる。
結果
1発AC
・提出したコード
#include<bits/stdc++.h> #include<atcoder/all> #define rep(i, n) for (long long i = 0; i < (long long)(n); i++) #define REP(i,v,n) for(long long i = v; i <= (long long)(n); i++) #define rrep(i,n) for(long long i = n;0 <= (long long)(i); i--) #define RREP(i,n,v) for(long long i = n;v <= (long long)(i); i--) #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } using namespace std; using namespace atcoder; using ll = long long; using pi = pair<int, int>; ll pows(ll x, ll n) {ll ret = 1;while (n > 0) {if (n & 1) ret *= x;x *= x;n >>= 1;}return ret;} int main() { int a,b,c; cin >>a >> b>> c; b -= c; bool ans = false; if(b < a)ans =true; cout << ((ans)?"Takahashi":"Aoki") << endl; return 0; }
A問題にしては難しかったです
ACまでの時間
ACしたのはコンテスト開始から2分後です。
B問題
問題の概要
高橋君は種類の呪文を使うことができ、番目の呪文は詠唱が秒、威力が秒かかります。
詠唱がより小さく、威力がより大きい呪文は存在しますか?
制約
- 入力はすべて整数
どのように考えたか
入力を全て受け取り、一致したものがあるかを全て確認した
結果
1発AC
提出したコード
#include<bits/stdc++.h> #include<atcoder/all> #define rep(i, n) for (long long i = 0; i < (long long)(n); i++) #define REP(i,v,n) for(long long i = v; i <= (long long)(n); i++) #define rrep(i,n) for(long long i = n;0 <= (long long)(i); i--) #define RREP(i,n,v) for(long long i = n;v <= (long long)(i); i--) #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } using namespace std; using namespace atcoder; using ll = long long; using pi = pair<int, int>; ll pows(ll x, ll n) {ll ret = 1;while (n > 0) {if (n & 1) ret *= x;x *= x;n >>= 1;}return ret;} int main() { int n,s,d,x,y; cin >> n >> s >> d; bool ans = false; rep(i,n){ cin >> x >>y; if(x < s && d < y)ans = true; } cout << ((ans)?"Yes":"No") << endl; return 0; }
比較するだけだったから簡単だった
ACまでの時間
ACしたのはコンテスト開始から5分後です。
C問題
問題の概要
の番号がついた個の皿と、の番号がついた個の条件があります。
条件は皿と皿の両方にボールが一個以上置かれている時に満たします。
の番号がついた人の人がいて、人は皿か皿のどちらか一方にボールを置きます。
満たされる条件の最大個数を求めて下さい。
制約
- 入力はすべて整数
どのように考えたか
Nが小さいため、K人が皿の上にボールを置けるすべてのパターンを列挙するためにbit全探索を用いた
結果
1発AC
・提出したコード
#include<bits/stdc++.h> #include<atcoder/all> #define rep(i, n) for (long long i = 0; i < (long long)(n); i++) #define REP(i,v,n) for(long long i = v; i <= (long long)(n); i++) #define rrep(i,n) for(long long i = n;0 <= (long long)(i); i--) #define RREP(i,n,v) for(long long i = n;v <= (long long)(i); i--) #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } using namespace std; using namespace atcoder; using ll = long long; using pi = pair<int, int>; ll pows(ll x, ll n) {ll ret = 1;while (n > 0) {if (n & 1) ret *= x;x *= x;n >>= 1;}return ret;} int main() { int n,m,a,b,k,ans=0; cin >> n >> m; vector<pi>AB(m); rep(i,m)cin >>AB[i].first >> AB[i].second; cin >> k; vector<pi>hu(k); rep(i,k)cin >> hu[i].first >> hu[i].second; for(int bit = 0;bit <(1 << k);bit++){ vector<int>dish(n,0); rep(i,k){ auto [c,d] = hu[i]; c--,d--; if(bit & (1 << i))dish[c]++; else dish[d]++; } int tmp = 0; rep(i,m){ auto [e,f] = AB[i]; e--,f--; if(1 <= dish[e] && 1 <= dish[f])tmp++; } chmax(ans,tmp); } cout << ans << endl; return 0; }
久々のbit全探索でバグらせないか心配だったが、無事一発で通せてよかった
ACまでの時間
ACしたのはコンテスト開始から15分後。
結果
コンテスト結果
ABCの3完でした。
Cまでは早く解けたがD問題が解けず悔しかった
パフォーマンス、レーティング変動
今回のパフォーマンスは796、前回より50近く上がりました。
レーティングはそれに伴い+10の711となりました。
反省点
今回は特に緊張してパニックにはならずC問題まで順調に解けて、D問題は解けなかったですがそれまでは特に時間の無駄遣いはせずD問題に注力することができました。
ただ、等差数列の式変形や検索でD問題を解いたという人の話を聞き、そこも鍛えていかないとダメだなと感じました。
今のところレートは上昇し続けているので、このまま緑を目指したいです。