ABCDEの5完2ペナで1025位とかなり良かったです。2ペナ分で大体100~200程度順位を落としているのでそこは反省かな。また、今回から(ルールの範疇で)GitHub Copilotを導入してみましたが、イディオム的な入力が簡単に済ませられるので中々便利...と思いつつ、急に10行ぐらい実装しだすのがかなり厄介だなぁと感じています。この辺を制御できる方法があればよいのですが。 # A - aaaadaa 言われたとおりにリプレイスすれば良いです。Stringでやる方法がありそうな気もしましたが、思いつかなかったのでcharの配列をmapで置換するシンプルな方法を取りました。 [提出](https://atcoder.jp/contests/abc384/submissions/60719491) ```rust use proconio::{input, marker::Chars}; fn main() { input!{ n: usize, c: char, d: char, s: Chars, } let ans = s.iter().map(|&s| if s == c { s } else { d }).collect::(); println!("{}", ans); } ``` # B - ARC Division 高橋くんのレーティングを管理しながら愚直に分岐を書けば良いです。分岐の条件をTypoしており、サンプルが合わねぇ！となって4分ぐらい消費した気がします。勿体ない。 [提出](https://atcoder.jp/contests/abc384/submissions/60729721) ```python n, r = map(int, input().split()) v = [map(int, input().split()) for _ in range(n)] for d, a in v: if d == 1: if r >= 1600 and r <= 2799: r += a else: if r <= 2399 and r >= 1200: r += a print(r) ``` ここで少し詰まってしまったことをこのあとのC, D問題に引きずってしまったので、序盤安定は大事だなぁと改めて思いました。最近は緑〜青diffの問題を中心に精進をしているので、この難易度帯を素早く丁寧に解くというのがおざなりになっているのかもしれません。 # C - Perfect Standings 問題は大きく2つのパートに分けられて、ある人が何点を取ったという組を列挙するパートと、順位に応じて並べ替えるパートです。前者はbit全探索でスコアと名前を一緒に生成するのが良いと思います。後者は言語依存ですが、Rustでは`(Reverse(score), name)`のタプルをキーにしてソートすれば達成できます。 [提出](https://atcoder.jp/contests/abc384/submissions/60735843) ```rust use std::cmp::Reverse; use itertools::Itertools; use proconio::input; fn main() { input!{ v: [u64; 5], } let sv = ["A", "B", "C", "D", "E"]; let mut ans = vec![]; for i in 1..=1<<5 { let mut sum = 0; let mut name = String::new(); for j in 0..5 { if i >> j & 1 == 1 { sum += v[j]; name.push_str(sv[j]); } } if name.len() == 0 { continue; } ans.push((sum, name)); } println!("{}", ans.iter().sorted_by_key(|(s, n)| (Reverse(s), n)).map(|(_, name)| name).join(" ")); } ``` この問題をやり始めたときは本当にテンパっており、「0, 1の組を全列挙するのってどうやるんだっけ！？！？！」となっておりました。水色コーダーさん？ # D - Repeated Sequence 例えば入力例1では、和が42となる連続する部分列として ``` 8 4 | 3 8 4 | 3 8 4 | 3 8 4 ``` が挙げられていますが、間に入っている$A$の要素が全て含まれるような部分は常に$3+8+4=15$です。復元は求められていないので和が常に同じ部分は無視することにして、この問題を次のように言い換えても問題なさそうです。 ## 言い換え長さ$N$の数列$A$を2回繰り返した数列$B$がある。数列$B$の空でない連続する部分列のうち、和が$S$を$\text{sum}(A)$で割ったあまりとなるものが存在するか判定せよ。この問題は尺取り法で$O(N)$で求められます。よってこの問題が解けました。 [提出](https://atcoder.jp/contests/abc384/submissions/60742405) ```rust use proconio::input; fn main() { input!{ n: usize, s: u64, mut a: [u64; n], } let s = s % a.iter().sum::(); for i in 0..n { a.push(a[i]); } let mut sum = 0; let mut r = 0; let mut l = 0; while r < a.len() { if sum == s { println!("Yes"); return; } if sum < s { sum += a[r]; r += 1; } else { sum -= a[l]; l += 1; } } while l < a.len() { if sum == s { println!("Yes"); return; } sum -= a[l]; l += 1; } println!("No"); } ``` 色々実装をミスったり、2回繰り返すのを忘れていたりなどボロボロの状態で1回提出してペナを喰らいました... # E - Takahashi is Slime 2 スライムを吸収したときに強くなる量はスライムを吸収する順に寄りません。また、一度吸収可能になったスライムは、以降どのタイミングでも吸収することができます。よって、「今隣接しているスライムのうち、最も弱いスライムを吸収する」という貪欲法が有効です。隣接するスライムを優先度付きキューによって管理することで、この問題を$O(HW\log{(HW)})$で解くことができます。 [提出](https://atcoder.jp/contests/abc384/submissions/60749184) ```rust use std::{cmp::Reverse, collections::BinaryHeap}; use proconio::{input, marker::Usize1}; fn main() { input!{ h: usize, w: usize, x: u128, p: Usize1, q: Usize1, v: [[u128; w]; h], } let mut strng = v[p][q]; let mut seen = vec![vec![false; w]; h]; seen[p][q] = true; let mut pq = BinaryHeap::new(); for r in 0..4 { let ni = p.wrapping_add(DI[r]); let nj = q.wrapping_add(DJ[r]); if ni < h && nj < w { seen[ni][nj] = true; pq.push((Reverse(v[ni][nj]), ni, nj)); } } while let Some((Reverse(c), i, j)) = pq.pop() { if strng <= c * x { continue; } strng += c; for r in 0..4 { let ni = i.wrapping_add(DI[r]); let nj = j.wrapping_add(DJ[r]); if ni < h && nj < w && !seen[ni][nj] { seen[ni][nj] = true; pq.push((Reverse(v[ni][nj]), ni, nj)); } } } println!("{}", strng); } ``` 隣接するスライムが吸収可能であるかを判定する際に、割り算を移行して楽しようとすると最大で$X\times \text{Max}(S_{i, j}) = 10^{21}$となり、符号なし64bit整数ではオーバーフローしてしまうという罠に引っかかり1ペナしました...。悪意あるだろ、これ --- 結果を見るとかなり良さそうに見える(実際に良かった)回ではあったものの、振り返ってみるとまだまだ反省点が多いです。まぁ勝てているので良いのですが、rating 1280にもなってくると5完早解きがずっと求められていくということなので、そう考えるとまだまだ精進が足りてないですね。

ABC384