https://atcoder.jp/contests/abc203atcoder.jp
Bondo416さんのAtCoder Beginner Contest 203(Sponsored by Panasonic)での成績:812位
— ボンド@競プロ (@bond_cmprog) May 30, 2021
パフォーマンス:1565相当
レーティング:1457→1468 (+11) :)#AtCoder #ABC203(SponsoredbyPanasonic) https://t.co/6DSu35tZbT
A - Chinchirorin
$ a = b $、$ b = c $、$ a = c $ のどれかを満たせばその残りを、そうでないなら0
を出力
提出コード
void solve(){ int a, b, c; cin >> a >> b >> c; if(a == b) cout << c << endl; else if(b == c) cout << a << endl; else if(a == c) cout << b << endl; else cout << 0 << endl; }
B - AtCoder Condominium
実際に全部加算していき、その総和を出力
提出コード
void solve(){ int N, K; cin >> N >> K; int sum = 0; for(int i=1;i<=N;i++){ for(int j=1;j<=K;j++) sum += 100 * i + j; } cout << sum << endl; }
C - Friends and Travel costs
$ A $ の昇順に村を訪れる事ができるかどうかを実際にシミュレートする
提出コード
void solve(){ int N, K; cin >> N >> K; map<ll, ll> mp; REP(i,N){ ll A, B; cin >> A >> B; cmp.add(A); mp[A] += B; } ll res = K; ll cur = 0; for(auto [k, v] : mp){ if(res < k - cur){ cur += res; res = 0; break; } else{ res += v; res -= (k - cur); cur = k; } } if(res > 0) cur += res; cout << cur << endl; }
D - Pond
難しい
ある整数 $ x $ 以下の整数が $ \lceil \frac{K ^ 2}{2} \rceil $ 以上を満たすもののうち、最小の $ x $ が中央値になり、二分探索で求めることが出来る
$ K \times K $ の区画に対して、$ x $ 以下の整数は $ 1 $ 、そうでないものは $ 0 $ とした総和を高速に求めることができればいい
これは、二次元累積和を用いることで各区画 $ \mathcal{O}(1) $ で求めることができ、全体で $ \mathcal
{O}(N^2 \log (\max(A_i))) $ で解くことが出来る
提出コード
void solve(){ ll N, K; cin >> N >> K; vector<vector<ll>> A(N, vector<ll>(N)); REP(i,N) REP(j,N) cin >> A[i][j]; auto check = [&](int m){ vector<vector<ll>> cum(N + 1, vector<ll>(N + 1)); REP(i,N) REP(j,N) cum[i+1][j+1] = cum[i][j+1] + cum[i+1][j] - cum[i][j] + (A[i][j] <= m); for(int i=K;i<=N;i++) for(int j=K;j<=N;j++){ if(cum[i][j] - cum[i][j-K] - cum[i-K][j] + cum[i-K][j-K] >= (K * K + 1) / 2) return true; } return false; }; ll l = -1, r = 2*INF; while(r - l > 1){ ll m = (l + r) >> 1; if(check(m)) r = m; else l = m; } cout << r << endl; }
E - White Pawn
今、操作1のみを行ったときに移動できる列の番号をsetで管理をする
操作2、3が行えるのは黒のポーンがある場所のみなので、行の昇順に黒のポーンがある行ごとに操作を行えばいい
操作によって増える要素集合をadd、減る要素集合をdelとしたときに、黒のポーンがある行を見終わったあとに、管理しているsetにaddを追加し、delを削除すればいい
最後まで操作を行ったときのsetのsizeが答え
提出コード
void solve(){ int N, M; cin >> N >> M; map<int, vector<int>> mp; REP(i,M){ int X, Y; cin >> X >> Y; mp[X].emplace_back(Y); } set<int> st; st.insert(N); for(auto [k, v] : mp){ set<int> add, del; for(auto y : v){ if(st.count(y - 1)) add.insert(y); if(st.count(y + 1)) add.insert(y); if(st.count(y) and !st.count(y-1) and !st.count(y+1)) del.insert(y); } for(auto &y : add) st.insert(y); for(auto &y : del) st.erase(y); } cout << st.size() << endl; }