Bondo416さんのAtCoder Beginner Contest 223での成績：311位
— ボンド@競プロ (@bond_cmprog) October 17, 2021
パフォーマンス：1841相当
レーティング：1530→1565 (+35) :)#AtCoder #ABC223 https://t.co/9Cdi8IySZI
A - Exact Price
$ X > 0 $ かつ $ X \equiv 0 \pmod{100} $ ならば Yes
void solve(){ int X; cin >> X; if(X == 0){ cout << "No" << endl; return; } cout << (X % 100 == 0 ? "Yes" : "No") << endl; }
B - String Shifting
どちらか一方に $ N $ 回シフトし続ければすべて列挙できる
列挙した文字列のなかで辞書順最小と最大のものを出力する
void solve(){ string S; cin >> S; set<string> st; int N = S.size(); REP(i,2*N){ string T = S; char c = T.back(); T.pop_back(); string U = c + T; st.insert(U); S = U; } cout << *st.begin() << endl; cout << *st.rbegin() << endl; }
C - Doukasen
左右からの導火線の火がぶつかる時刻 $ t $ を求める
これは二分探索で求められる（が、$ t = \frac{1}{2} \sum _{i=1} ^N \frac{A_i}{B_i} $ で求められる、天才？）
あとは、左右のどちらかからシミュレートで時刻 $ t $ における左端からの距離を求めればいい
void solve(){ int N; cin >> N; vector<int> A(N), B(N); REP(i,N) cin >> A[i] >> B[i]; ll sum = accumulate(ALL(A), 0LL); auto check = [&](double m) -> bool{ double l = 0; double r = sum; { double rest = m; REP(i,N){ double need = (double)A[i] / B[i]; if(need > rest){ l += B[i] * rest; rest = 0; } else{ l += A[i]; rest -= need; } if(rest <= 0) break; } } { double rest = m; for(int i=N-1;i>=0;i--){ double need = (double)A[i] / B[i]; if(need > rest){ r -= B[i] * rest; rest = 0; } else{ r -= A[i]; rest -= need; } if(rest <= 0) break; } } if(l >= r) return true; return false; }; double l = 0, r = LINF; REP(i,100){ double m = (l + r) / 2; if(check(m)) r = m; else l = m; } double ans = 0.0; REP(i,N){ double need = (double)A[i] / B[i]; if(need > r){ ans += r * B[i]; break; } else{ ans += A[i]; r -= need; } } printf("%.12lf\n", ans); }
D - Restricted Permutation
基本的にはトポロジカル順序を出力すればいい
ただし、そのままqueueを使うのではなく、priority_queueで今取り出せるもののうち最小の頂点を取り出せるようにする
void solve(){ int N, M; cin >> N >> M; vector<vector<int>> g(N); StronglyConnectedComponents scc(N); REP(i,M){ int a, b; cin >> a >> b; --a, --b; g[a].emplace_back(b); scc.make_edge(a, b); } scc.solve(); if(scc.getSize() != N){ cout << -1 << endl; return; } auto order = topologicalSort(g); for(int x : order) cout << x + 1 << " "; cout << endl; }
E - Placing Rectangles
AtCoder Beginner Contest 062 C - Chocolate Barの解説の通りに分けることを考えればいい
上図のA, B, Cの割り当て方をnext_permutationで全探索をする
void solve(){ ll W, H, A, B, C; cin >> W >> H >> A >> B >> C; vector<ll> rec(3); rec[0] = A; rec[1] = B; rec[2] = C; vector<int> idx(3); iota(ALL(idx), 0); bool ok = false; do{ { ll h1 = ceil_div(rec[idx[0]], W); // 横 ll h2 = ceil_div(rec[idx[1]], W); ll h3 = ceil_div(rec[idx[2]], W); if(h1 + h2 + h3 <= H) ok = true; // 縦 ll h = H - h1; ll w2 = ceil_div(rec[idx[1]], h); ll w3 = ceil_div(rec[idx[2]], h); if(h > 0 and w2 + w3 <= W) ok = true; } { ll w1 = ceil_div(rec[idx[0]], H); // 横 ll w2 = ceil_div(rec[idx[1]], H); ll w3 = ceil_div(rec[idx[2]], H); if(w1 + w2 + w3 <= W) ok = true; // 縦 ll w = W - w1; ll h2 = ceil_div(rec[idx[1]], w); ll h3 = ceil_div(rec[idx[2]], w); if(w > 0 and h2 + h3 <= H) ok = true; } }while(next_permutation(ALL(idx))); cout << (ok ? "Yes" : "No") << endl; }
F - Parenthesis Checking
( のとき +1、)のとき-1として累積和（$ cum $ )を考える
区間 $ [l, r] $ が正しい括弧列になる条件は以下の2つを満たしていればいい
$ 1. \; cum_{l - 1} = cum_{r}$
$ 2. \; min_{i = l - 1} ^r cum_{i} \geq cum_{l - 1} $
2点 $ l - 1, r - 1 $ をswapするときは、$ l \leq x \leq N $ と $ r \leq x \leq N $ の範囲に影響するので、その差分更新をする
void solve(){ int N, Q; string s; cin >> N >> Q >> s; vector<S> cum(N+1); REP(i,N) cum[i+1] = cum[i] + (s[i] == '(' ? 1 : -1); lazy_segtree<S, op, e, F, mapping, composition, id> seg(cum); while(Q--){ int q, l, r; cin >> q >> l >> r; if(q == 1){ if(s[l-1] == '(') seg.apply(l, N+1, -1); else seg.apply(l, N+1, 1); if(s[r-1] == '(') seg.apply(r, N+1, -1); else seg.apply(r, N+1, 1); swap(s[l-1], s[r-1]); if(s[l-1] == '(') seg.apply(l, N+1, 1); else seg.apply(l, N+1, -1); if(s[r-1] == '(') seg.apply(r, N+1, 1); else seg.apply(r, N+1, -1); } else{ bool ok = true; int base = seg.prod(l-1, l); if(base != seg.prod(r, r+1)) ok = false; if(seg.prod(l-1, r+1) < base) ok = false; cout << (ok ? "Yes" : "No") << endl; } } }
