途中までかなりあやしかったものの，なんとか5完に漕ぎ着けました... # A - Equally 場合分けとしてありうるのは5通りなので、全部書きます。 [提出](https://atcoder.jp/contests/abc385/submissions/60939941) ```python a, b, c = map(int, input().split()) if a + b == c or a + c == b or b + c == a or a == b == c: print("Yes") else: print("No") ``` [[ABC384]]からGitHub Copilotを使っていますが、こういうときに補完をいい感じにしてくれるので見た目の割には書くのに苦労していません。 # B - Santa Claus 1 移動の処理は言われたとおりに頑張るとして、一度通った家を重複して数えないように一度通ったマスをdfs/bfsでやるような要領で管理すればよいです。 [提出](https://atcoder.jp/contests/abc385/submissions/60951948) ```python di = [0, 1, 0, -1, 1, 1, -1, -1] dj = [1, 0, -1, 0, 1, -1, 1, -1] dc = 'RDLU' h, w, i, j = map(int, input().split()) s = [input() for _ in range(h)] t = input() seen = [[False] * w for _ in range(h)] ans = 0 i -= 1 j -= 1 for c in t: for r in range(4): if dc[r] != c: continue ni, nj = i + di[r], j + dj[r] if ni < 0 or h <= ni or nj < 0 or w <= nj or s[ni][nj] == '#': break if not seen[ni][nj] and s[ni][nj] == "@": ans += 1 seen[ni][nj] = True i, j = ni, nj break print(i + 1, j + 1, ans) ``` D問題でも思いましたが、終わったときの場所を出力させる問題というのはまた珍しいなぁなどと思いました。どういう意図なんだろう？特に深い理由はないんかな # C - Illuminate Buildings 開始点のビルと、電飾で飾るビルの間隔を決めると選ぶことができるビルの数が求まります。よって、これらを全探索すればよいです。多分調和級数の和なので$O(N^2\log{N})$ぐらいで間に合います。証明はAC(は？) [提出](https://atcoder.jp/contests/abc385/submissions/60959132) ```rust use proconio::{input, marker::Usize1}; fn main() { input!{ n: usize, h: [Usize1; n], } let mut ans = 1; for i in 0..n { for steps in 1.. { if i + steps >= n { break; } let mut tmp = 1; let mut k = steps; while i + k < n { if h[i + k] == h[i] { tmp += 1; k += steps; } else { break; } } ans.chmax(tmp); } } println!("{}", ans); } ``` # D - Santa Claus 2 $x = x_i, y = y_i$であるような家の列を`map>`で持ちます。各移動に対して、その移動で通過する家のうち最小・最大のものがlogで求めることができるので、そのような家を取得→重複を防ぐために削除を繰り返せばよいです。とくに、削除をすることで取得される家の数は最大で$N$個なので、全体で$O(N\log N + M)$でシミュレートすることができます。できるんですが、実装がとにかく辛いです。 [提出](https://atcoder.jp/contests/abc385/submissions/60984798) ```cpp #define int long long #define rep(i, n) for (int i = 0; i < (int)(n); i++) void solve() { int n, m; int si, sj; cin >> n >> m >> si >> sj; vector> home; rep(i, n) { int x, y; cin >> x >> y; home.push_back({x, y}); } vector> move; rep(i, m) { char c; int d; cin >> c >> d; move.push_back({c, d}); } map> home_i; map> home_j; rep(i, n) { home_i[home[i].first].insert(home[i].second); home_j[home[i].second].insert(home[i].first); } int ans = 0; int now_i = si; int now_j = sj; rep(i, m) { char c = move[i].first; int d = move[i].second; if (c == 'L') { int target = now_i - d; auto itr = home_j[now_j].lower_bound(target); if (itr == home_j[now_j].end()) { now_i = target; continue; } else { while(itr != home_j[now_j].end() && *itr <= now_i) { ans++; home_i[*itr].erase(now_j); itr = home_j[now_j].erase(itr); } now_i = target; } } else if (c == 'R') { int target = now_i + d; auto itr = home_j[now_j].lower_bound(now_i); if (itr == home_j[now_j].end()) { now_i = target; } else { while(itr != home_j[now_j].end() && *itr <= target) { ans++; home_i[*itr].erase(now_j); itr = home_j[now_j].erase(itr); } now_i = target; } } else if (c == 'U') { int target = now_j + d; auto itr = home_i[now_i].lower_bound(now_j); if (itr == home_i[now_i].end()) { now_j = target; } else { while(itr != home_i[now_i].end() && *itr <= target) { ans++; home_j[*itr].erase(now_i); itr = home_i[now_i].erase(itr); } now_j = target; } } else if (c == 'D') { int target = now_j - d; auto itr = home_i[now_i].lower_bound(target); if (itr == home_i[now_i].end()) { now_j = target; } else { while(itr != home_i[now_i].end() && *itr <= now_j) { ans++; home_j[*itr].erase(now_i); itr = home_i[now_i].erase(itr); } now_j = target; } } } cout << now_i << " " << now_j << " " << ans << endl; } ``` 　Rustはループをしながら削除、というような操作は所有権の問題で辛い(実際どうなるかはわからないけど、辛い予感がした)のでC++を選択しましたが、C++のイテレータの仕様周りでとにかく躓きました。C++難しいよ〜 # E - Snowflake Tree 以降、$x, y$は問題文で述べられている「ユ木」を生成する際に選ぶ値を指します。削除する頂点数の最小化ではなく、残す頂点数の最大化を考えます。根を一つ決めると、$x$については考える必要がなく$y$のみに着目すればよいです。また、$y$の候補としてありうるのは根と隣接する頂点(以降は公式解説と合わせて"一層目の頂点"と呼びます)が持つ部分木の数です[^1]。これを大きい方から全探索すると、一層目の頂点のうち部分木の数が大きいほうから$k$番目の部分木の個数を$y$として採用するとき、残る頂点の数は$1 + k \times (y + 1)$[^2]と$O(1)$で求めることができるので、全体で$O(N\log{N})$でこの問題を解くことができます。 [提出](https://atcoder.jp/contests/abc385/submissions/60983251) ```rust use proconio::{input, marker::Usize1}; fn main() { input! { n: usize, edges: [(Usize1, Usize1); n - 1], } let mut g = vec![vec![]; n]; for (u, v) in edges { g[u].push(v); g[v].push(u); } let mut deg = vec![0; n]; for i in 0..n { deg[i] = g[i].len(); } let mut m_size = 1; for v in 0..n { let mut lc: Vec = g[v] .iter() .map(|&u| deg[u] - 1) .collect(); lc.sort_unstable_by(|a, b| b.cmp(a)); let d = lc.len(); let mut tmp = 1; for k in 1..=d { let y = lc[k - 1]; let size = 1 + k * (1 + y); if size > tmp { tmp = size; } } if tmp > m_size { m_size = tmp; } } let ans = n - m_size; println!("{}", ans); } ``` [^1]: 例えば一層目の部分木の個数が3, 3, 1となっていた場合に、$y=2$を選ぶぐらいなら$y=3$を選んだほうが無駄な削除が減るので [^2]: 根の数(1つ) + 根の部分木の1つあたりの大きさ(y+1) × 根の部分木の個数(k個) --- 本当にギリギリのところでDとEを通せたことで勝利しましたが、1300↑とそろそろ自分の適正レートから上振れしているなぁと感じるぐらいのレート帯になってきました。しばらくはレートの維持が目標になってきそうです。

ABC385