Bondo416さんのAtCoder Beginner Contest 174での成績:452位
— ボンド@競プロ (@bond_cmprog) August 2, 2020
パフォーマンス:1868相当
レーティング:1254→1332 (+78) :)#AtCoder #ABC174 https://t.co/cQbROlgNR9
A - Air Conditioner
なら"Yes"、そうでなければ"No"
提出コード
void solve(){ int X; cin >> X; if(X >= 30) cout << "Yes" << endl; else cout << "No" << endl; }
B - Distance
ルートを外してあげてならカウントしていく
提出コード
void solve(){ ll N, D; cin >> N >> D; int cnt = 0; REP(i,N){ ll x, y; cin >> x >> y; x *= x, y *= y; if(x + y <= D * D) cnt++; } cout << cnt << endl; }
C - Repsept
難しい
Kが偶数のときは絶対作れないのでそれ以外を考えてみる
愚直に求めていくことを考えると、割り算の要領で先頭からmodを取っていく
その時、mod K が0になればその桁を出力する
コンテスト中は厳密な証明出来なかったのでK桁目まで見れば十分そうだなーで投げちゃった
解説にちゃんと証明が載っていたので読みます
提出コード
void solve(){ int K; cin >> K; int cur = 0; REP(i,K+1){ cur = cur * 10 + 7; cur %= K; if(cur == 0){ cout << i + 1 << endl; return; } } cout << -1 << endl; }
D - Alter Altar
これも結構考えちゃったんだけど茶色difficultyらしくてびっくり
最終的な状態を考えると、
RR...RWW...W
WW...W
RR...R
のどれかになっていればいい
これを達成するには一番左にあるWと一番右にあるRをswapすることを繰り返していけばいい
提出コード
void solve(){ int N; cin >> N; vector<int> R, W; REP(i,N){ char c; cin >> c; if(c == 'R') R.emplace_back(i); else W.emplace_back(i); } if(size(R) == 0 or size(W) == 0){ cout << 0 << endl; return; } sort(R.rbegin(), R.rend()); int r = 0; int ans = 0; REP(i, size(W)){ if(W[i] < R[r]){ ans++; if(size(R) > r) r++; } if(size(R) == r) break; } cout << ans << endl; }
E - Logs
最大値の最小化はにぶたん(素振り)
操作を行った後の丸太の長さの最大値をにできるかどうか、という判定問題を考える
長さの丸太を長さで分割していくことを考えると回切る必要がある
そのため、この合計回数がK回以内なら達成でき、そうでないなら達成できない
あとは、このについて二分探索をするとこの問題を解くことができる
提出コード
void solve(){ ll N, K, ma = 0; cin >> N >> K; vector<ll> A(N); REP(i,N){ cin >> A[i]; chmax(ma, A[i]); } auto check = [&](ll x) -> ll{ if(x == 0) return LINF; ll cnt = 0; REP(i,N) cnt += (A[i] + x - 1)/ x - 1; return cnt; }; ll l = 0, r = ma+1; while(r - l > 1){ ll m = (r + l) >> 1; if(check(m) <= K) r = m; else l = m; } cout << l+1 << endl; }
F - Range Set Query
以下の記事を読んだ記憶があったので「区間 種類数」みたいにググるとHitする
hama-du-competitive.hatenablog.com
その後に類題でググってるとけんちょんさんの記事があったのでそれをペタりました
drken1215.hatenablog.com
典型らしいのでちゃんと中身理解しておきたいね
提出コード
void solve(){ int N, Q; cin >> N >> Q; vector<int> a(N); REP(i,N) cin >> a[i]; vector<int> lefts(Q), rights(Q), ids(Q); REP(i,Q){ cin >> lefts[i] >> rights[i]; --lefts[i]; ids[i] = i; } sort(ids.begin(), ids.end(), [&](int i, int j) { return rights[i] < rights[j];}); BIT<int> bit(N+10); vector<int> prev(505050, -1); vector<int> res(Q); int r = 0; for (auto i : ids) { for (; r < rights[i]; ++r) { bit.add(prev[a[r]]+2, r+2, 1); prev[a[r]] = r; } int tmp = bit.sum(lefts[i]+1, lefts[i]+2); res[i] = max(res[i], tmp); } for (int i = 0; i < Q; ++i) cout << res[i] << endl; }