かなり問題セットと運に助けられた感のある回でしたが、ともあれ残り45秒でFを通したことでABCDFの5完・青perfでの再入水を果たしました。 # A - Humidifier 1 $T_i \leq 100$と小さいので、1秒ずつシミュレーションすれば良いです。問題文からは加湿器から水が抜けるタイミング(水が入っていない状態から水を入れたときの処理順)がわからなかったのでclarを投げようか10秒ぐらい迷いました。まぁサンプルから読み取ったのでいいかなぁみたいな。 [提出](https://atcoder.jp/contests/abc383/submissions/60504341) ```rust use proconio::input; fn main() { input!{ n: usize, v: [(usize, u64); n], } let mut t = 0; let mut i = 0; let mut l = 0; while i < n { if l != 0 { l -= 1; } if t == v[i].0 { l += v[i].1; i += 1; } t += 1; } println!("{l}"); } ``` # B - Humidifier 2 $H \leq 10, W \leq 10$と小さいので、加湿器2つをどこに配置するかと、その配置に対して加湿されるマスの個数を$O((HW)^3)$で全探索することができます。$(10\times10)^3 = 10^6$程度なのでこれは十分高速です。 [提出](https://atcoder.jp/contests/abc383/submissions/60508768) ```rust use cps::chlibs::ChLibs; use itertools::iproduct; use proconio::{input, marker::Chars}; fn main() { input!{ h: usize, w: usize, d: usize, s: [Chars; h], } let mut ans = 0; for (ai, aj) in iproduct!(0..h, 0..w) { if s[ai][aj] == '#' { continue; } for (bi, bj) in iproduct!(0..h, 0..w) { if ai == bi && aj == bj { continue; } if s[bi][bj] == '#' { continue; } let mut cnt = 0; for (i, j) in iproduct!(0..h, 0..w) { if s[i][j] == '#' { continue; } let dist = (ai.abs_diff(i) + aj.abs_diff(j)).min(bi.abs_diff(i) + bj.abs_diff(j)); if dist <= d { cnt += 1; } } ans.chmax(cnt); } } println!("{ans}"); } ``` # C - Humidifier 3 複数始点でBFSをすればよいです。$O(HW)$ [提出](https://atcoder.jp/contests/abc383/submissions/60511999) ```rust use std::collections::VecDeque; use cps::consts::{DI, DJ}; use itertools::iproduct; use proconio::{input, marker::Chars}; fn main() { input!{ h: usize, w: usize, d: u64, s: [Chars; h], } let inf = 1u64 << 60; let mut seen = vec![vec![inf; w]; h]; let mut que = VecDeque::new(); for (i, j) in iproduct!(0..h, 0..w) { if s[i][j] == 'H' { que.push_back((i, j)); seen[i][j] = 0; } } while let Some((pi, pj)) = que.pop_front() { for r in 0..4 { let ni = pi.wrapping_add(DI[r]); let nj = pj.wrapping_add(DJ[r]); if ni < h && nj < w && s[ni][nj] == '.' && seen[ni][nj] == inf { seen[ni][nj] = seen[pi][pj] + 1; que.push_back((ni, nj)); } } } println!("{}", seen.iter().flatten().filter(|&cnt| *cnt <= d).count()); } ``` Twitterで少し話題にされていましたが、複数始点の場合も開始点の処理が少し違うだけで普通のBFSとやることは同じなので、そのあたりを押さえておけば苦労せずに通せるんじゃないかなぁと思います。実装を楽にしたり、ライブラリに丸投げできるという点では加湿器があるマスに対して超頂点を導入するのもありだと思いますが、まぁそこまでしなくてもという気持ち。 # D - 9 Divisors こんなの何か良い性質あるだろ！と言いながら"numbers that has nine divisor"で調べると一番上にまったく同じ問題とその解答コード([Count number of integers less than or equal to N which has exactly 9 divisors](https://www.geeksforgeeks.org/count-number-of-integers-less-than-or-equal-to-n-which-has-exactly-9-divisors/))が出てくるので、オーバーフロー対策だけして投げるとACしました。 ...ということでコンテストは全く考察をせずに終えたのですが、ブログではちゃんと考えようと思います。ある値$K$を素数$P_i$と正整数$a_i$を用いて$K=\prod {P_i}^{a_i}$と表したとき$\prod a_i+1$ですから、これが9となるような$a$の組としてあり得るものは$a=(2, 2), (8)$の2つです。つまり、 (1) $p^2q^2 \leq N$であるような素数の組$(p, q) (p < q)$の個数を数えよ (2) $p^8 \leq N$であるような素数$p$の個数を数えよという部分問題を解くことでこの問題が解けます。いずれについても最大で$\sqrt{N}$までの素数を考えれば良いので、事前に列挙しておきます[^1]。(1)について、ある$p$に対して$q^2 \leq \frac{N}{p^2}, p < q$を満たす$q$の個数を数えればよく、これは列挙した素数列に対して二分探索することで高速に計算可能です。(2)については素数1つずつに対して判定をすれば良いです。これで部分問題が解けたので、この問題を解くことができました。 [提出](https://atcoder.jp/contests/abc383/submissions/60558252) ```rust use cps::prime::create_primes; use num_integer::Roots; use proconio::input; fn main() { input!{ n: usize } let half_n = n.sqrt(); let v = create_primes(half_n+1); let mut ans :usize = 0; let n = n as u64; for &vi in v.iter() { let val = vi.pow(8); if val > n { break; } ans += 1; } for i in 0..v.len() { let p = v[i].pow(2); let max_q = n / p; // v[j]^2 がmax_q以下である最大 // -> v[j]^2がmax_q+1以上である最小 let idx = v.binary_search_by_key(&(&max_q+1), |vi| vi.pow(2)).unwrap_or_else(|x|x); if i < idx { ans += idx - i - 1; } else { break; } } println!("{ans}"); } ``` [^1]: $N \leq 10^{12}$なので、列挙される素数の個数は$10^6$未満であり、実際にはもっと少ないです。 # E - Sum of Max Matching (upsolve) 考察はそれなりにできていたものの、証明なしに実装するのが怖くてFに行きました。後から解説をみたら考えていたとおりで合っており、悲しい[^2]。 [^2]: 結果論だけを言うと、Fを通したことでABCDEの5完勢よりも良い順位を取れたのでこの判断は功を奏したと言えるが、4完に終わった可能性も十分にあった実験をすると、使われる辺は[[最小全域木]]に含まれる辺であることが分かります(できるだけ重みが小さい辺を通って行きたいので)。全体のコストを小さくしたいというようなことを考えると、自然に次のような貪欲法が考えられます: クラスカル法を用いて最小全域木を構築する。新たに辺を追加したとき、同じ集合に属する頂点間で、Aに含まれる頂点とBに含まれる頂点でペアが作れるようになったならそのペアを採用する(このときの$f$の値は追加した辺の重みとなる)。一見すると嘘貪欲っぽい[^3]ですが、この貪欲によって最適解を得られます。証明はわからないんですが、気持ち的にはクラスカル法で結合時の重みがだんだん大きくなっていく→その時点でそのペアを採用しなければ後からより大きいコストでペアを作ることになって損、という感じだと思います。[提出](https://atcoder.jp/contests/abc383/submissions/60559108) ```rust use cps::unionfind::UnionFind; use itertools::Itertools; use proconio::{input, marker::Usize1}; fn main() { input!{ n: usize, m: usize, k: usize, e: [(Usize1, Usize1, u64); m], a: [Usize1; k], b: [Usize1; k], } let mut ans = 0; let f = |x: &(u64, u64), y: &(u64, u64)| { let a = x.0 + y.0; let b = x.1 + y.1; if a > b { (a - b, 0) } else { (0, b - a) } }; let mut uf = UnionFind::new(n, f); let va = a.iter().fold(vec![0; n], |mut v, &ai| { v[ai]+=1; v }); let vb = b.iter().fold(vec![0; n], |mut v, &ai| { v[ai]+=1; v }); for i in 0..n { uf.insert_data(i, (va[i], vb[i])); } for &(u, v, w) in e.iter().sorted_unstable_by_key(|v| v.2) { if uf.same(u, v) { continue; } let (pa, pb) = uf.get_data(u).copied().unwrap(); let (qa, qb) = uf.get_data(v).copied().unwrap(); let val = (pa+qa).min(pb+qb); ans += val * w; uf.merge(u, v); } println!("{}", ans); ``` [^3]: 私はこの気持ちになったので「うーん、わからん！ｗ」となって諦めました # F - Diversity まず、商品$i$が色$i$であるという仮定を置く(つまり、すべての商品が違う色である)と、`dp[i][j] := 色iまで考えたときに、j円払って得られる満足度の最大値`とする動的計画法が有効です。空間は$NX$で遷移は商品の色を$i+1$値段を$p$, 効用を$u$として`dp[i+1][j+p] = max(dp[i+1][j+p], dp[i][j] + u + K)`と、買わない場合の`dp[i+1][j] = max(dp[i+1][j], dp[i][j])` の2通りで$O(1)$なので、この仮定の上では$O(NX)$で解けることが分かります。さて、元の問題に立ち返ります。色が違うもの同士は先の遷移で解けるので、同じ色同士の遷移を考えましょう。とはいえこれは単純で、同じ色の商品を扱っている間は$i$を固定して`dp[i+1][j+p] = max(dp[i+1][j+p], dp[i+1][j] + u)`という遷移を付ければ良いです。よって、全体で$O(NX)$でこの問題が解けました。実装は一般にnextDPと呼ばれるテクを用いて行うとバグらせにくいと思います。 [提出](https://atcoder.jp/contests/abc383/submissions/60544137) ```rust use cps::chlibs::ChLibs; use proconio::{input, marker::Usize1}; fn main() { input!{ n: usize, x: usize, k: i64, mut items: [(usize, i64, Usize1); n], } let items = items.iter() .fold(vec![vec![]; n], |mut v, &(p, u, c)| { v[c].push((p, u)); v }); let inf :i64 = -1; let mut dp =vec![vec![inf; x+1]; 2]; let mut cur = 0; dp[cur][0] = 0; for v in items.iter() { if v.is_empty() { continue; } let nxt = 1 - cur; for &(p, u) in v.iter() { for i in (0..=x).rev() { if dp[cur][i] != inf { // 買わない let val = dp[cur][i]; dp[nxt][i].chmax(val); } if i + p > x { continue; } // cur -> nxt (k) if dp[cur][i] != inf { let val = dp[cur][i] + u + k; dp[nxt][i+p].chmax(val); } // nxt -> nxt if dp[nxt][i] != inf { let val = dp[nxt][i] + u; dp[nxt][i+p].chmax(val); } } } dp[cur].fill(inf); cur = nxt; } println!("{}", dp[cur].iter().max().unwrap()); } ```

ABC383