ちょい冷え
— ボンド@競プロ (@bond_cmprog) December 13, 2020
Bondo416さんのAtCoder Beginner Contest 185での成績：1030位
パフォーマンス：1447相当
レーティング：1501→1495 (-6) :(#AtCoder #ABC185 https://t.co/KXWAcGGx4A
A - ABC Preparation
$ min(A_1, A_2, A_3, A_4) $を出力
提出コード
void solve(){ int mi = 101; REP(i,4){ int a; cin >> a; chmin(mi, a); } cout << mi << endl; }
B - Smartphone Addiction
実際にシミュレートをし、途中で0以下になればNo
提出コード
void solve(){ ll N, M, T; cin >> N >> M >> T; vector<ll> A(M), B(M); REP(i,M) cin >> A[i] >> B[i]; ll cur = N; ll pre = 0; REP(i,M){ cur -= (A[i] - pre); if(cur <= 0){ cout << "No" << endl; return; } cur = min(N, cur + B[i] - A[i]); pre = B[i]; // dump(cur); } cur -= T - pre; if(cur > 0) cout << "Yes" << endl; else cout << "No" << endl; }
C - Duodecim Ferra
$ dp[i][j] := i $個目まで見たときの長さの総和が$ j $のときの場合の数としてDPをする
想定解は$ _{L - 1} C _{11} $に等しい、気づかなかった
提出コード
void solve(){ int L; cin >> L; vector dp(13, vector<ll>(222)); dp[0][0] = 1; REP(i,12){ REP(j,222){ // i本目を何cmで切るか for(int k=1;k<=189;k++){ if(j + k > L) continue; if(dp[i][j] == 0) continue; dp[i+1][j+k] += dp[i][j]; } } } ll ans = 0; cout << dp[12][L] << endl; }
D - Stamp
連続した白色の区間の長さが最小の部分がネックになるのでその長さを$ mi $とする
白色の区間の長さを$ k $とするとその区間は$ \lceil \frac{k}{mi} \rceil $回操作を行う必要があるので、その総和が答え
マス$ A $に$ 0, N+1 $を追加すると実装が少し楽
提出コード
void solve(){ ll N, M; cin >> N >> M; vector<ll> A(M); REP(i,M) cin >> A[i]; if(M == 0){ cout << 1 << endl; return; } if(N == M){ cout << 0 << endl; return; } ll mi = LINF; A.emplace_back(0); A.emplace_back(N+1); ll sz = A.size(); sort(A.begin(), A.end()); REP(i,sz-1){ if(A[i+1] - A[i] - 1 == 0) continue; chmin(mi, A[i+1] - A[i] - 1); // dump(mi); } ll ans = 0; REP(i,sz-1){ ans += (A[i+1] - A[i] - 1 + mi - 1) / mi; } cout << ans << endl; }
E - Sequence Matching
$ dp[i][j] := A $を $ i $文字目まで、$ B $を $ j $文字目まで見たときの$ x + y $の最小としてDPをする
これは編集距離と同様のことをやっている（本番中全然気づかなかった）
提出コード
void solve(){ int N, M; cin >> N >> M; vector<int> A(N), B(M); REP(i,N) cin >> A[i]; REP(j,M) cin >> B[j]; vector dp(N+1, vector(M+1, 0)); REP(i,N+1) dp[i][0] = i; REP(j,M+1) dp[0][j] = j; for(int i=1;i<=N;i++) for(int j=1;j<=M;j++){ dp[i][j] = min({dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + (A[i-1] != B[j-1])}); } cout << dp[N][M] << endl; }
F - Range Xor Query
XORの区間和と一点更新はBITかセグ木に載せられるのでどちらかを使えばいい
本番中はセグ木を使った
提出コード
void solve(){ int N, Q; cin >> N >> Q; SegTree<long long> seg(N, [](long long a, long long b) { return a ^ b; }, 0); vector<long long> A(N); for (int i = 0; i < N; ++i) { cin >> A[i]; seg.set(i, A[i]); } seg.build(); REP(i,Q){ ll T, X, Y; cin >> T >> X >> Y; X--; if(T == 1){ ll x = seg.get(X, X+1); seg.update(X, x ^ Y); } else{ cout << seg.get(X, Y) << endl; } // seg.print(); } }
