Bondo416さんのモノグサプログラミングコンテスト2022(AtCoder Beginner Contest 238)での成績:2117位
— ボンド@競プロ (@bond_cmprog) February 5, 2022
パフォーマンス:1076相当
レーティング:1590→1548 (-42) :(#AtCoder #モノグサプログラミングコンテスト2022(ABC238) https://t.co/hrF1qjAoc3
A - Exponential or Quadratic
$ n \geq 60 $ のとき、必ず成り立つので $ n = \min(n, 60) $ として比較を行う
void solve(){ ll n; cin >> n; ll N = n * n; ll two = 1LL << (min(n, 60LL)); if(two > N) cout << "Yes" << endl; else cout << "No" << endl; }
B - Pizza
実際に切れ込みの入る位置を求めたあと、その間の角度の最大を求める
void solve(){ int N; cin >> N; vector<int> A(N); REP(i,N) cin >> A[i]; set<int> st; int cur = 0; st.insert(0); st.insert(360); REP(i,N){ cur += A[i]; cur %= 360; st.insert(cur); } int dir = 0; int ans = 0; for(auto x : st){ chmax(ans, x - cur); cur = x; } cout << ans << endl; }
C - digitnum
$ i $ 桁の数字ごとに分けて考える
それぞれの桁数ごとで考えると、その和は等差数列になるのでその総和が答え
void solve(){ ll N; cin >> N; ll cur = 9; ll pre = 1; mint ans = 0; REP(i,18){ if(N <= cur){ cur = N; } mint n = cur - pre + 1; ans += n * (n + 1) / 2; if(N <= cur) break; cur = 10 * cur + 9; pre *= 10; } cout << ans << endl; }
D - AND and SUM
$ x + y = 2(x \& y) + x \oplus y $ であるので、$ s - 2a = x \oplus y $ となりこれを満たす $ (x, y) $ が存在すればいい
これは $ s - 2a \geq 0 $ かつ $ (s - 2a) \& a = 0 $ を満たせばいい
void solve(){ ll a, s; cin >> a >> s; ll n = s - 2 * a; if(n >= 0 and (n & a) == 0) cout << "Yes" << endl; else cout << "No" << endl; }
E - Range Sums
$ a $ の累積和 $ b $ を考える
各クエリは $ b_{r} - b_{l - 1} $ と言い換えることができ、片方がわかっていればもう片方の値もわかるのでこの二頂点を連結にするとクエリと考える
そうすると、$ b $ の要素を頂点として考えると、$ b_0 $ から $ b_N $ にたどり着ければ良いことになる
よって各クエリに対してUnionFindなどで頂点を連結させ、$ b_0 $ と $ b_N $ が連結かどうかを判定すればいい
void solve(){ int N, Q; cin >> N >> Q; UnionFind uf(N+1); REP(i,Q){ int l, r; cin >> l >> r; uf.unite(--l, r); } cout << (uf.issame(0, N) ? "Yes" : "No") << endl; }
F - Two Exams
$ dp[i][j][k] := i $ 番目まで見た時に、$ j $ 人選び、選んでいない人の中で最小の順位が $ k $ のときの選び方の場合の数としてDPを行う
void solve(){ int N, K; cin >> N >> K; vector<int> P(N), Q(N); REP(i,N){ cin >> P[i]; --P[i]; } REP(i,N){ cin >> Q[i]; --Q[i]; } vector<int> idx(N); iota(ALL(idx), 0); sort(ALL(idx), [&](int a, int b){ return P[a] < P[b]; }); vector dp(K+10, vector<mint>(N+10)); dp[0][N] = 1; for(auto i : idx){ vector nxt(K+10, vector<mint>(N+10)); REP(x,K+1) REP(y,N+1){ if(Q[i] < y) nxt[x+1][y] += dp[x][y]; nxt[x][min(y, (ll)Q[i])] += dp[x][y]; } swap(nxt, dp); } mint ans = 0; REP(i,N+1) ans += dp[K][i]; cout << ans << endl; }