CodeForces Round#380 Div2
鬱
http://codeforces.com/contest/738
A
なんか普通に数える。
#include <bits/stdc++.h> using namespace std; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin >> n; string s; cin >> s; string ans = ""; for(int i = 0; i < n; ){ bool ok = [&]() { if(i >= n - 2) return true; if(s.substr(i, 3) != "ogo") return true; i = i + 3; for(int j = i; j < n - 1; j += 2) { if(s.substr(j, 2) == "go") i = j + 2; else break; } return false; }(); if(ok) { ans += s[i]; ++i; } else { ans += "***"; } } cout << ans << endl; return 0; }
B
累積和
int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n, m; cin >> n >> m; vector<vector<int>> fld(n, vector<int>(m, 0)); for(auto& v : fld) for(int& x : v) cin >> x; auto yoko = fld, tate = fld; for(int i : in(n)) { for(int j : in(m - 1)) yoko[i][j + 1] += yoko[i][j]; } for(int j : in(m)) { for(int i : in(n - 1)) tate[i + 1][j] += tate[i][j]; } int cnt = 0; for(int i : in(n)) for(int j : in(m)) { if(fld[i][j]) continue; if(i > 0) if(tate[i - 1][j] > 0) ++cnt; if(j > 0) if(yoko[i][j - 1] > 0) ++cnt; if(n - 1 > i) if(tate[n - 1][j] - tate[i][j] > 0) ++cnt; if(m - 1 > j) if(yoko[i][m - 1] - yoko[i][j] > 0) ++cnt; } cout << cnt << endl; return 0; }
C
二分探索。
そもそもtが無理ゲーのとき(二分探索して、rの値が最初に設定した上限になる場合)の対応を忘れていて落ちた。
このくらいpretestに入れろよ、とは思うけど仕方ないね。
4行追加しただけで通って鬱になった。
#include <bits/stdc++.h> using namespace std; using i64 = long long; const i64 INF = 1e18; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); i64 n, k, s, t; cin >> n >> k >> s >> t; vector<pair<i64, i64>> cars(n); for(auto& p : cars) cin >> p.first >> p.second; vector<i64> gas(k + 1); for(int i : in(k)) cin >> gas[i]; gas.back() = s; sort(gas.begin(), gas.end()); i64 l = -1LL, r = s * 3; while(r - l > 1LL) { i64 mid = (l + r) / 2LL; bool ok = [&]() { i64 before = 0LL, sum = 0LL; const i64 can_use = mid; for(auto cur : gas) { i64 dist = cur - before; if(dist > can_use) return false; if(can_use >= dist * 2) { sum += dist; before = cur; continue; } i64 diff = can_use - dist; sum += diff + (dist - diff) * 2LL; before = cur; } return sum <= t; }(); if(ok) r = mid; else l = mid; } if(r == s * 3) { cout << -1 << endl; return 0; } i64 ans = INF; for(auto p : cars) { if(p.second >= r) ans = min(ans, p.first); } cout << (ans == INF ? -1 : ans) << endl; return 0; }
D
とりあえず左から貪欲に置いて、あとは鳩の巣原理。
普通に解けなかった。
#include <bits/stdc++.h> using namespace std; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n, num, len, m; cin >> n >> num >> len >> m; string s; cin >> s; s += '1'; vector<int> blocks; int start = 0; bool in_range = false; for(int i : in(n + 1)) { if(s[i] == '1') { if(in_range == true) { in_range = false; int length = i - start; for(int k : in(length / len)) blocks.emplace_back(start + k * len); } } else { if(in_range == false) { in_range = true; start = i; } } } vector<int> ans; for(int i : in((int)(blocks.size()) - (num - 1))) ans.emplace_back(blocks[i] + (len - 1)); cout << ans.size() << endl; for(auto x : ans) cout << x + 1 << ' '; cout << endl; return 0; }
Dはちょっと難しいけどまあ普通に解けなきゃいけない感じだし、Cを落とすのはキツイなあ。
なんかこどふぉ久々すぎてコーナーケースに対する勘が鈍っていた感じがあり、険しい。