あまり良くない勝ち方でしたが、とはいえ5完で勝ち。最近は連勝できているのでこの調子でレートを増やしたいです。 # A - 12435 埋め込むかどうかで少し迷いますが、5個は少し多いなーと思ったのでシミュレーションします。[url](https://atcoder.jp/contests/abc390/submissions/62022294) ```cpp #include using namespace std; #define rep(i,n) for (ll i=0;i> a[i]; rep(i, 4) { swap(a[i], a[i+1]); bool flag = true; rep(j, 5) { if (a[j] != j+1) flag = false; } if(flag) { cout << "Yes "; return; } swap(a[i], a[i+1]); } cout << "No "; } ``` # B - Geometric Sequence 等比数列ってなんでしたっけ(あの？)となったのでググります。1つめの比をベースとして、それと全て同じになっていることを判定すれば良さそうです。ただし、小数演算は誤差が怖いので $$ \begin{align} \frac{A_1}{A_0} &= \frac{A_{i+1}}{A_{i}} \\ A_1 \times A_{i} &= A_0 \times A_{i+1} \\ \end{align} $$ と式変形をして小数を用いずに判定すれば安全にACできます。[提出](https://atcoder.jp/contests/abc390/submissions/62030711) ```cpp #include using namespace std; using ll = long long; #define rep(i,n) for (ll i=0;i> n; ll a[n]; rep(i, n) cin >> a[i]; rep(i, n-1) { if (a[1] * a[i] != a[0] * a[i+1]) { cout << "No "; return; } } cout << "Yes "; } ``` また、言語によりますが、有理数ライブラリを利用するのも手かと思います。[有理数ライブラリ解(Rust)](https://atcoder.jp/contests/abc390/submissions/62198587) ```rust use itertools::Itertools; use num_rational::Ratio; use proconio::input; fn main() { input! { n: usize, a: [u64; n], } println!( "{}", if a.iter() .tuple_windows() .map(|(&a, &b)| Ratio::new(a, b)) .all_equal() { "Yes" } else { "No" } ); } ``` # C - Paint to make a rectangle 黒マスの内、最も右/左/下/上にあるもの場所を記録します。その内側にあるものは黒の領域で外側は白の領域となるので、内側の領域に白いマスが存在しないことを判定すればよいです。 [提出](https://atcoder.jp/contests/abc390/submissions/62042916) ```cpp void solve() { int h, w; cin >> h >> w; vector bd(h); rep(i, h) cin >> bd[i]; ll l=w, r=-1, u=h, d=-1; rep(i, h) rep(j, w) { if (bd[i][j] == '#') { chmin(l, j); chmin(u, i); chmax(r, j); chmax(d, i); } } if(l==w) { cout << "Yes "; return; } rep(i, h) rep(j, w) { if(bd[i][j] == '.') { if(l <= j && j <= r && u <= i && i <= d) { cout << "No "; return; } } } cout << "Yes "; } ``` # D - Stone XOR 見るからに全探索です。しかも、特に工夫のいらない全探索に見えます。というのも、うまくやることで省略できるという要素がなさそうで、しかも特にメモ化できる要素が無い[^memo]ので、再帰で全列挙すればよいです。[提出(1142ms)](https://atcoder.jp/contests/abc390/submissions/62052761) ```rust use std::collections::BTreeSet; use proconio::input; fn dfs(v: &mut Vec, i: usize, a: &Vec, ans: &mut BTreeSet) { if i == a.len() { ans.insert(v.iter().fold(0, |acc, &x| acc ^ x)); return; } for j in 0..v.len() { v[j] += a[i]; dfs(v, i + 1, a, ans); v[j] -= a[i]; } v.push(a[i]); dfs(v, i + 1, a, ans); v.pop(); } fn main() { input! { n: usize, a: [u64; n], } let mut ans = BTreeSet::new(); dfs(&mut Vec::new(), 0, &a, &mut ans); println!("{}", ans.len()); } ``` [^memo]: より厳密にはあるかもしれないが、メモ化したときのメモが一切利用されないようなケースが作れるなと思った計算量解析はせずにまぁ間に合うだろで投げましたが、このような区別できる要素を1つ以上のグループに分ける場合の数のことをベル数というらしいです[^wiki]。$i$番目のベル数を$B_i$と書くことにすると、計算量は$O(B_{N}\log{B_{N}})$となります。、$N=12$のとき、$B_{12}=4,213,597$であり$B_{12} \times \log{B_{12}} \risingdotseq 92,727,032$ですから、じつはかなりの定数倍勝負だったみたいです。特に、C++では`std::set`が実はあまり早くないこともありかなりの人が沼にハマったようでした。 [^wiki]: [ベル数 - Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%99%E3%83%AB%E6%95%B0) Rustでも、`BTreeSet`ではなく単に`Vec`に入れておいて、最後にsortしてdedupすることでより高速に解くことができました。[提出(Rust, 369ms)](https://atcoder.jp/contests/abc390/submissions/62199108) # E - Vitamin Balance まず、シンプルなdpが見えました。`dp[i][j][k] := カロリーi, ビタミン1がj, ビタミン2がkだけ接種したときのビタミン3としてあり得る最大値`としたい気持ちになりますが、困ったことにメモリが全然足りません。無限のメモリを使いたい。仕方がないので別の方針を考えます。よく見ると各食べ物はビタミンを1つしか持っていないので、それぞれについて「カロリーiだけ接種したときの接種ビタミンとしてあり得る最大値」とすれば、これは$O(NX)$で求めることができます。さらに、この結果を用いて、「カロリーを$X$以下だけ接種したときに、各ビタミンを$m$以上接種することは可能か？」を判定して二分探索をすることによって、$O(NX + N\log(\sum A))$でこの問題を解くことができます。なお、本番の私は何を考えたか毎回動的計画法をやり直す$O(NX\log(\sum A))$という実装をしました[^baka]が、ぎりぎり通ったのでOK。[提出(1653ms)](https://atcoder.jp/contests/abc390/submissions/62071072) ```rust use proconio::{input, marker::Usize1}; fn dp(key: i64, x: usize, v: &Vec<(i64, usize)>) -> usize { let mut dp = vec![-1; x + 1]; dp[0] = 0; for &(a, c) in v { for i in (0..x + 1).rev() { if i + c >= x + 1 { continue; } let val = dp[i] + a; dp[i + c].chmax(val); } } // key以上で最小のindex for (i, &xi) in dp.iter().enumerate() { if xi >= key { return i; } } return x + 1; } fn main() { input! { n: usize, x: usize, v: [(Usize1, i64, usize); n], } let v = v.iter().fold(vec![vec![]; 3], |mut v, &(i, a, c)| { v[i].push((a, c)); v }); let mut ok = 0; let mut ng = 1e18 as i64; while ng - ok > 1 { let mid = (ok + ng) / 2; let s = (0..3) .into_iter() .map(|i| { let res = dp(mid, x, &v[i]); res }) .sum::(); if s <= x { ok = mid; } else { ng = mid; } } println!("{}", ok); } ``` [^baka]: 一応頭の中で軽く計算して、全然間に合うなーと思いながら出したのでくっそ遅くてびっくりした # F - Double Sum 3 (Upsolve) 手も足も出ず。ある区間を削除する際に、できるだけ長い区間を削除したいです。具体的には、`3, 2, 4, 6, 7`が与えられたときは、$l=2, r=4$を選んで数列を`6, 7`とし、その後$l=6, r=7$を選ぶのが最適となります。ここで答えを求めることは難しいので、数え上げる対象を読み替えることにします。すべての操作を行った結果、$i=1, 2, \cdots, N$それぞれについて$l=A_i$として削除を行った回数を数え上げることができれば、この問題を解くことができます。ここで、操作において$l=A_i$として削除を行う条件を考えると、それは「対象の区間において$A_j = A_i - 1$なる$j$が存在しない」です。なぜなら、そのような$A_j$が存在するのであればそちらを左端として処理するほうが良いからです。逆に言うと、そのような$j$が出てくるまでの間は$l=A_i$として削除するのが最適となりますから、$ji$である$j$であって$A_j = A_i-1$を満たすような$j$のうち最も小さいものが高速にわかれば良く、これは二分探索などを用いることで対数時間で求めることができます。また、同じ区間を重複して数えてしまうケースがあるため、「削除する区間に同じ値が含まれる場合は最も左にある値を使う」というルールをつけ、上とのmaxをとることで重複を排除できます。以上より、この問題が$O(N\log N)$と十分高速に解くことができます。なお、実装が辛いなーと言いながら工夫をしていたら$O(N)$になっていました。。[提出](https://atcoder.jp/contests/abc390/submissions/62106239) ```rust use proconio::input; fn main() { input! { n: usize, a: [usize; n], } let mut v = vec![vec![]; n + 1]; let mut idxes = vec![None; n + 1]; for (i, &ai) in a.iter().enumerate() { v[ai].push(i); if idxes[ai].is_none() { idxes[ai] = Some(0); } } let mut ans = 0; let mut last_seen = vec![None; n + 1]; for (i, &ai) in a.iter().enumerate() { let mut l = if let Some(idx) = last_seen[ai - 1] { idx as i64 } else { -1 }; l = l.max(if let Some(idx) = last_seen[ai] { idx } else { -1 }); let r = if let Some(idx) = idxes[ai - 1] { v[ai - 1][idx] as i64 } else { n as i64 }; if idxes[ai].unwrap() + 1 == v[ai].len() { idxes[ai] = None; } else { idxes[ai] = Some(idxes[ai].unwrap() + 1); } last_seen[ai] = Some(i as i64); ans += (i as i64 - l) * (r - i as i64); } println!("{}", ans); } ```

ABC390