Bondo416さんのAtCoder Beginner Contest 260での成績：1115位
— ボンド@競プロ (@bond_cmprog) July 17, 2022
パフォーマンス：1437相当
レーティング：1418→1420 (+2) :)#AtCoder #ABC260 https://t.co/ClA0BW8LXV
A - A Unique Letter
文字ごとに出現数をカウントし、それが1のものを出力
void solve(){ vector<int> cnt(26); REP(i,3){ char c; cin >> c; cnt[c-'a']++; } REP(i,26) if(cnt[i] == 1){ cout << char(i + 'a') << endl; return; } cout << -1 << endl; }
B - Better Students Are Needed!
すでに合格した人は省いて残りの人を配列で管理をする
残った人の点数の降順、同じ点数なら受験番号の昇順にソートをし、それぞれの上限人数までを答えに入れる
void solve(){ int N, X, Y, Z; cin >> N >> X >> Y >> Z; vector<int> A(N), B(N); REP(i,N) cin >> A[i]; REP(i,N) cin >> B[i]; vector<int> ok(N); vector<int> ans; { vector<pair<int, int>> idx; REP(i,N) idx.emplace_back(-A[i], i); sort(ALL(idx)); REP(i,min(X, (int)idx.size())) { auto [a, id] = idx[i]; ok[id] = 1; ans.emplace_back(id); } } { vector<pair<int, int>> idx; REP(i,N) if(!ok[i]) idx.emplace_back(-B[i], i); sort(ALL(idx)); REP(i,min(Y, (int)idx.size())) { auto [a, id] = idx[i]; ok[id] = 1; ans.emplace_back(id); } } { vector<pair<int, int>> idx; REP(i,N) if(!ok[i]) idx.emplace_back(-A[i]-B[i], i); sort(ALL(idx)); REP(i,min(Z, (int)idx.size())) { auto [a, id] = idx[i]; ok[id] = 1; ans.emplace_back(id); } } sort(ALL(ans)); for(auto x : ans) cout << x+1 << endl; }
C - Changing Jewels
操作を行えるだけ行ってレベル1の青い宝石を作ればいいので、これを再帰関数などで求める
void solve(){ int N, X, Y; cin >> N >> X >> Y; ll ans = 0; auto dfs = [&](auto && self, ll red, ll blue, ll n) -> void { if(n == 1) { chmax(ans, blue); return; } ll r = red; ll b = blue + red * X; // n if(n >= 2) { r += b; ll bb = b * Y; // n-1 self(self, r, bb, n-1); } else chmax(ans, b); return; }; dfs(dfs, 1, 0, N); cout << ans << endl; }
D - Draw Your Cards
UnionFindの親を管理するように場に出ている山ごとにグループを管理する
場に見えているカードの番号をsetで管理し、カードを重ねる際にグループとsetを更新していく
void solve(){ int N, K; cin >> N >> K; vector<int> P(N); REP(i,N) { cin >> P[i]; --P[i]; } vector<int> group(N); // 番号 vector<vector<int>> pile(N); iota(ALL(group), 0); set<int> st; vector<int> ans(N, -1); REP(i,N){ int x = P[i]; auto itr = st.lower_bound(x); if(itr == st.end()) { pile[group[x]].emplace_back(x); st.insert(x); } else { int idx = *itr; group[x] = group[idx]; pile[group[x]].emplace_back(x); st.erase(idx); st.insert(x); } if(pile[group[x]].size() >= K) { for(auto y : pile[group[x]]) ans[y] = i + 1; st.erase(x); } } REP(i,N) cout << ans[i] << endl; }
E - At Least One
条件を満たす数列の連続部分列 $ 1 \leq l \lt r \ leq M $ をしゃくとり法で求める
$ [l, r] $ が条件を満たすとき、これに含まれる区間はすべて条件を満たすので、imos法で答えを加算していく
void solve(){ int N, M; cin >> N >> M; vector<vector<int>> v(M+10); REP(i,N) { int a, b; cin >> a >> b; v[a].emplace_back(i); v[b].emplace_back(i); } int cnt_zero = N; vector<int> cnt(N); vector<int> ans(M+10); int right = 1; REP(left, 1, M+1) { while(right <= M and cnt_zero != 0) { for(auto x : v[right]) { if(cnt[x] == 0) cnt_zero--; cnt[x]++; } right++; } if(cnt_zero != 0) continue; ans[right-left]++; ans[M+1-left+1]--; for(auto x : v[left]) { cnt[x]--; if(cnt[x] == 0) cnt_zero++; } } dump(ans); REP(i,1,M+1) { ans[i] += ans[i-1]; cout << ans[i] << " "; } cout << endl; }
F - Find 4-cycle
$ V_2 $ に含まれる頂点 $ (x, y) $ について、両方について隣接である $ V_1 $ の頂点が2つ見つかれば 4-cycleを含んでいることがわかる
$ V_2 $ の頂点対の組み合わせが $ T(T-1) $ 個であるため、鳩の巣原理から$ V_2 $ の頂点対に隣接している $ V_1 $ の頂点をメモしていき、すでにメモしている値ならばそれを 4-cycleとして出力することで実行時間以内で解くことができる
void solve(){ int N, M; cin >> N >> M; vector<vector<int>> v(M+10); REP(i,N) { int a, b; cin >> a >> b; v[a].emplace_back(i); v[b].emplace_back(i); } int cnt_zero = N; vector<int> cnt(N); vector<int> ans(M+10); int right = 1; REP(left, 1, M+1) { while(right <= M and cnt_zero != 0) { for(auto x : v[right]) { if(cnt[x] == 0) cnt_zero--; cnt[x]++; } right++; } if(cnt_zero != 0) continue; ans[right-left]++; ans[M+1-left+1]--; for(auto x : v[left]) { cnt[x]--; if(cnt[x] == 0) cnt_zero++; } } dump(ans); REP(i,1,M+1) { ans[i] += ans[i-1]; cout << ans[i] << " "; } cout << endl; }
