ABC174 参加記録
ググり力、灯台下暗しと言ったところでした。
レートは冷えたけど、学びもありました。Eまでは悪くないペースだったと思うけど...
A問題
こう言う問題で秒単位で時間を削るなら3項目演算子使うべきなんだろうけど素直にif文を書いてしまった。いや別にいいんだけど...
#include<bits/stdc++.h> using namespace std; using ll = long long; #define REP(i,n) for(int i = 0;i < n;i++) int main(void){ cin.tie(0); ios::sync_with_stdio(false); int x;cin >> x; if(x >= 30)cout << "Yes" << '\n'; else cout << "No" << '\n'; }
B問題
最初入力が実数だと勘違いして(誤読1)誤差大丈夫かなEPS
用意しないといけないやつかと思った
流石にB問題だし誤差大丈夫だろと思ってたらそもそも整数だった
#include<bits/stdc++.h> using namespace std; using ll = long long; #define REP(i,n) for(int i = 0;i < n;i++) int main(void){ cin.tie(0); ios::sync_with_stdio(false); int ans = 0; int n;cin >> n; ll d;cin >> d; REP(i,n){ ll x,y;cin >> x >> y; if(x*x+y*y <= d*d)ans++; } cout << ans << '\n'; }
C問題
Mで割ったあまりの周期は高々Mとかになるやつ。最初M%2==0で-1
とかやってたら案の定TLEした。うるうる
int main(void){ cin.tie(0); ios::sync_with_stdio(false); ll k;cin >> k; if(k % 2 == 0){ cout << -1 << '\n'; return 0; } ll ten = 1; ll tmp = 0; int cnt = 1; for(int i = 0;i < 1e7;i++){ ll add = (7 * ten) % k; tmp = (tmp + add) % k; ten = (ten * 10) % k; if(tmp == 0){ cout << cnt << '\n'; return 0; } cnt++; } cout << -1 << '\n'; }
D問題
隣接swapだと勘違いして(誤読2)時間を溶かしていた。 Rを全部左に詰めるから、最初の入力で(Rの個数をMとする)、[0,M)の範囲にあるRは動かさなくていいことに注意するとO(N)で計算できる
int main(void){ cin.tie(0); ios::sync_with_stdio(false); ll n;cin >> n; string s;cin >> s; ll ans = 0; ll cnt = 0; REP(i,n)cnt += (s[i] == 'R'); REP(i,n){ ans += (i >= cnt && s[i] == 'R'); } cout << ans << '\n'; }
E問題
一目見て二分探索だと気づいたので書いて通す。これはすぐできた
ll n,k; ll a[maxn]; void read(){ cin >> n >> k; REP(i,n)cin >> a[i]; } bool func(int x){ ll cnt = 0; REP(i,n){ cnt += ((a[i] + x - 1) / x) - 1; } return cnt <= k; } int main(void){ cin.tie(0); ios::sync_with_stdio(false); read(); int l = 0,r = 1e9 + 1; while(l + 1 != r){ int mid = (l + r)/2; // can all len <= mid ? if(func(mid))r = mid; else l = mid; } cout << r << '\n'; }
F問題
fastestが2分を切っているのを見て、データ構造かライブラリか超有名知識なんだろうと察しをつけ、色々とググろうとしたけどダメだった。と言うか、格好つけて英単語を並べて英語の記事を探そうとしてた。普通に日本語の記事に本質があった...(TODO:通したらリンクを貼る)
まとめ
青になって初めてのrated。レートはとかしてしまったけど、データ構造系の有名知識も身につけていかないといけないなと感じ、教訓になった。また頑張ります。 夏休みが近いので、夏休みになったらCFのばちゃとかをたくさんやりたい。1ヶ月しかないと言うか将来のこともやんなきゃいけないけど。