AtCoder Beginner Contest 264
AtCoder Beginner Contest 264 です。
5完 120:12 （6ペナ + 30:00 ) 506位でした。 F 問題沼ったのがかなり悔しいです。これ初手提出の時点で解けているべき感じの問題だった…。
A - "atcoder".substr()
Rust で非常にめんどくさい問題…。頑張って実装します。
fn main() { input! { l : Usize1, r : usize } let atcoder = "atcoder".chars().collect_vec(); println!("{}", atcoder[l..r].iter().join("")); }
B - Nice Grid
一瞬、黒か白かの2次元配列を書きそうになったんですが、よく考えると一番近い壁までの距離の偶奇で白か黒か決まります。後は良い感じに。
fn main() { input! { r : Usize1, c : Usize1 } let f = r.min(14 - r).min( c.min(14 - c) ); println!("{}", if f % 2 == 0 {"black"} else {"white"}); }
C - Matrix Reducing
$H, W$ が小さいので、 $A$ のどの行・列を採用するか全探索します。本当は、探索範囲を絞った方が良いと思うんだけど、めんどくさいので本当に全探索。まぁ絞った方が良かったね（779ms）
itertools の combinations とか使って探索範囲をまともにしたら 19ms になった。
fn main() { input! { h1 : usize, w1 : usize, a : [[usize; w1]; h1], h2 : usize, w2 : usize, b : [[usize; w2]; h2] } let mut ok = false; 'e:for s1 in 1..(1<<h1) { for s2 in 1..(1<<w1) { let mut a2 = vec![]; for i in 0..h1 { if (s1 >> i) & 1 == 0 { continue } let mut t = vec![]; for j in 0..w1 { if (s2 >> j) & 1 == 0 { continue } t.push(a[i][j]); } a2.push(t); } if a2 == b { ok = true; break 'e;} } } println!("{}", if ok {"Yes"} else {"No"}); }
D - "redocta".swap(i,i+1)
"atcoder" の並び変えた文字列しか与えられないので、すごく雑なことをしても大体間に合います。転倒数とか考えたんですが、ライブラリとか無いので愚直に swap かけていきます。とりあえず 'a' を先頭に持ってくる、 't' を 2桁目に持ってくるという感じにします。
fn main() { input! { mut s : Chars } let atcoder = "atcoder".chars().collect_vec(); let n = atcoder.len(); let mut ans = 0; for i in 0..n { let mut index = s.iter().position(|&c| c == atcoder[i]).unwrap(); while index > i { s.swap(index - 1, index); ans += 1; index -= 1; } } println!("{}", ans); }
E - Blackout 2
連結成分の管理なので Union-Find を使いたくなります。切るという操作はめんどくさいので、クエリを逆向きにして繋ぐという操作をやっていきます。後は、発電所に繋がっているかどうかを考えれば良いんですが、適当に新しい頂点を作ってそこに全部発電所を繋いでおけば良いです（発電所の番号は隣り合っているので超頂点じゃなくても良かったです）。後はその頂点の連結成分 - (m + 1) をしたら発電所と繋がっている都市の数が分かります。
fn main() { input! { n : usize, m : usize, e : usize, edges : [(Usize1, Usize1); e], queries : [Usize1] } let mut cut = vec![false; e]; for q in queries.iter() { cut[*q] = true; } let mut uni = UnionFind::new(n + m + 1); let r = n + m; for i in n..n+m { uni.merge(r, i); } for (i, &(u, v)) in edges.iter().enumerate() { if cut[i] { continue } uni.merge(u, v); } let mut ans = Vec::with_capacity(queries.len()); for &x in queries.iter().rev() { ans.push(uni.size(r) - m - 1); uni.merge(edges[x].0, edges[x].1); } println!("{}", ans.iter().rev().join("\n")); }
F - Monochromatic Path
沼った。DP っぽいものは書いてたんだけど、なぜかダイクストラみたいにやっていたし、超絶雑な場合分けで実装ゴリゴリになってた…。うーむ…。
結局優先度付キューを普通のキューにして通したけど、まぁループでも書けるね。 これはもっと早く解けるべきですね。↓ のコードは修正版。
fn main() { input! { h : usize, w : usize, r : [usize; h], c : [usize; w], a : [Chars; h] } const MAX : usize = std::usize::MAX / 10; // const MAX : usize = 100; let mut dist = vec![vec![vec![vec![MAX; w]; h]; 2]; 2]; dist[0][0][0][0] = 0; dist[1][0][0][0] = r[0]; dist[0][1][0][0] = c[0]; dist[1][1][0][0] = r[0] + c[0]; let mut pq = VecDeque::new(); pq.push_back((Reverse(0), 0, 0, 0, 0)); pq.push_back((Reverse(r[0]), 1, 0, 0, 0)); pq.push_back((Reverse(c[0]), 0, 1, 0, 0)); pq.push_back((Reverse(r[0] + c[0]), 1, 1, 0, 0)); for y in 0..h { for x in 0..w { for f1 in 0..2 { for f2 in 0..2 { // → に移動 if x+1 < w { let ny = y; let nx = x + 1; if (f2 == 1 && a[y][x] != a[ny][nx]) || (f2 == 0 && a[y][x] == a[ny][nx]) { if dist[f1][0][ny][nx] > dist[f1][f2][y][x] { dist[f1][0][ny][nx] = dist[f1][f2][y][x]; } } else { if dist[f1][1][ny][nx] > dist[f1][f2][y][x] + c[x + 1] { dist[f1][1][ny][nx] = dist[f1][f2][y][x] + c[x + 1]; } } } // ↓ に移動 if y+1 < h { let ny = y + 1; let nx = x; if (f1 == 1 && a[y][x] != a[ny][nx]) || (f1 == 0 && a[y][x] == a[ny][nx]) { if dist[0][f2][ny][nx] > dist[f1][f2][y][x] { dist[0][f2][ny][nx] = dist[f1][f2][y][x]; } } else { if dist[1][f2][ny][nx] > dist[f1][f2][y][x] + r[y + 1] { dist[1][f2][ny][nx] = dist[f1][f2][y][x] + r[y + 1]; } } } }}}} let mut ans = std::usize::MAX; ans = ans.min(dist[0][0][h-1][w-1]); ans = ans.min(dist[0][1][h-1][w-1]); ans = ans.min(dist[1][0][h-1][w-1]); ans = ans.min(dist[1][1][h-1][w-1]); println!("{}", ans); }
G - String Fair
見てない。
Ex - Perfect Binary Tree
見てない。
まとめ
1806パフォ、 1604 → 1626(+22) とレートは上がったが、絶対に早く解けた F 沼ったのであんまり嬉しくないですね。うん。
AtCoder で青になりました
第三回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 262） で青になりました。ちなみにコンテスト当日が誕生日でした✌
簡単な自己紹介
- zeronosu77108 （もしくは Ryuki）という名前で活動しています。
- IT系、社会人3年目です。
- 競プロは ABC200～ Rust で参加しています（それ以前は C++ ）。
青になるまで
初めて水色になったのが 2020/06/21 なので、青になるのに約2年かかりました。 正直 2021年3月～辺りの青パフォラッシュで青になれると思って居たんですが、第二回日本最強プログラマー学生選手権 で惨敗してからかなり調子が崩れました。また、この頃からしばらく Diff が灰灰茶青（中位以上）青黄 や 灰灰灰茶黄黄 みたいな崖が多いコンテストが増え、灰～水の全員が早解き勝負みたいなコンテストが増えちょっとでも考察が遅れたりペナを出すと爆死するコンテストが増えていました。chokudaiさんとかは「解く速度で評価できるから良くない？」みたいなことを言っていましたが、参加する側からしたら面白くないです。そこで半年くらいお休みしていました。
復帰してから少しレートが下がったもののその後は調子が良くすぐ青にいけると思ったのですが、問題が発生します。新Writer の登場です。彼等は数学が得意なので、単純に数学的知識が必要な問題や普通のアルゴリズムに数学的要素が多い問題が増えた気がします（とは言え高校数学レベル…？）。僕は数式を書いて整理して考察するみたいなものがかなり苦手なので、正直「もうしばらく青になれないなぁ」と思っていました。この 第三回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 262） も 問題傾向を変えているという記事 が出ていたのと、前回の第二回冷えていたので、出ないか出ても Unrated にしようと思っていました。しかし、コンテスト直前になぜかいける気がして Rated 登録しました。おかげで誕生日のコンテストで青になることができました（これ冷えてたら最悪の誕生日だったな…）。
最近の精進
特にやってないです…。というか他のことが忙しくて何も手が回っていませんでした。もう少し時間を作りたい所です。一応コンテストに出て、コンテスト後にはコンテスト中に見ていた問題を解く位はしていました。コンテスト中に F を見ていたが、実は G が得意で（後からやってみると）解けたみたいなのが結構あったので、 最近は ABC - G の方が解いてる数多いかもしれません。
AtCoder Problems の情報
まぁ、凡人なので青になるまでにはぼちぼち解いてる方だと思います。最近の ARC とかはあんまり解いてないです。
Solved By zeronosu77108_ Topcoder: 0 Codeforces: 160 AtCoder: 1979 AOJ: 33 yukicoder: 261 library-checker: 18 Sum: 2451
勉強したアルゴリズム・データ構造
これ要ります？最近の ABC の感じだとダイクストラとセグ木、最大流があれば困らないんじゃないですかね。 個人的にはゲーム問題とか桁DPが好きです（最近あんまり出ないんだよなぁ…）。
これから
なんか身の回りに青になると辞める人がちょいちょい居るんですが、僕はまだレート上げたいと思っています。最近の ABC だと「あ～これ知ってる知識だったなぁ」みたいなのもあって（bitset 高速化とか…）、もっと色々引き出しやすくしたいです。後は↑にも書いたんですが、数式書いて整理するみたいなのが苦手なのでその辺ですね。 ARC の問題を解いたり、コドフォの問題を解いたりしたいなぁと思っています。
おわりに
誕生日プレゼント or 青記念プレゼントお待ちしています（？）
欲しい物リスト
AtCoder Beginner Contest 258
AtCoder Beginner Contest 258 です。
A - When?
60 を超えたら 1時間足されて、 60 を引いた余りが分に足されるので、 時間の方に $K$ を 60 で割って切り捨てた物、分の方に $K$ を 60 で割った余りを足してあげると良いです。後は、2桁 0 埋めして良い感じに出力。
fn main() { input! { k : usize } println!("{:02}:{:02}", 21 + k/60, k % 60); }
B - Number Box
B にしては難しくないですか？ 始点を決めて、8方向どっちに進む続けるか決めて $N-1$ 回進んでみると良いです。適当に剰余するといいんですが Rust だと負になったりするとめんどくさいので自分でリセット書きました。
fn main() { input! { n : usize, a : [Bytes; n] } let a = a.into_iter().map(|a| a.iter().map(|&a| (a - b'0') as usize).collect_vec()).collect_vec(); let mut ans = 0; for i in 0..n { for j in 0..n { for (dx, dy) in vec![(!0, !0), (1, !0), (!0, 1), (1, 1), (0, !0), (!0, 0), (1, 0), (0, 1)] { let mut y = i; let mut x = j; let mut now = a[y][x]; for _ in 0..n-1 { x = x.wrapping_add(dx); y = y.wrapping_add(dy); if n == x { x = 0; } if n == y { y = 0; } if n <= x { x = n-1; } if n <= y { y = n-1; } now = now*10 + a[y][x]; } ans = ans.max(now); } }} println!("{}", ans); }
C - Rotation
末尾の文字を 1文字削除、先頭に追加を繰り返すと1回につき 先頭の index が -1 される感じになります。
例えば、 abc に 2回操作すると bca になりますね。これは先頭の index が $0$ → $-1 (n-1)$ → $-2(n-2)$ という感じに遷移していると考えられます。そこから $X$ 文字は良い感じに足して剰余取ってあげると分かります。
fn main() { input! { n : usize, q : usize, s : Chars, queries : [(u8, Usize1); q] } let mut now = 0; let mut ans = vec![]; for (t, x) in queries { match t { 1 => { now += n - x - 1; now %= n; } 2 => { ans.push(s[(now + x) % n]); } _ => unreachable!() } } println!("{}", ans.iter().join("\n")); }
D - Trophy
1番から順番にしかプレイできないので、まぁ順番にクリアしていくことを考えます。 $i$ 番目のステージをクリアしたときに残りの $X - i$ 回をどうするか考えるんですが、 $i$ より前のステージを繰り返しクリアするのはその前の段階でやる方が最適なので考える必要がありません。よって、 $i$ 番目までクリアしたときは $i$ 番目を残りの $X - i$ 回クリアしたときの時間を求めてその最小値を求めたら良いです。
fn main() { input! { n : usize, mut x : usize, ab : [(usize, usize); n] } let mut ans = std::usize::MAX; let mut sum = 0; for (a, b) in ab { sum += a + b; x -= 1; ans = ans.min(sum + x * b); } println!("{}", ans); }
提出した瞬間に $x < n$ の場合にバグりそう～って思ったんですが、何故か AC しました。 よく考えたら $x$ を usize で受け取っていたのでめちゃくちゃでかい値になってどうにかなりました（？） 本来ならこう書くべきでした 提出。
E - Packing Potatoes
見てすぐここスタートにしたらどこまで行くかダブリングするか～って思いました。$\sum W_i$ よりも $X$ が大きい場合に注意して実装すると良いです…。この問題はもっと早く解けたなぁという感じ。
fn main() { input! { n : usize, q : usize, x : usize, w : [usize; n], k : [usize; q] } const LOG : usize = 40; let mut tab = vec![vec![0; n]; LOG+1]; let w = w.into_iter().cycle().take(2*n).collect_vec(); let mut csum = vec![0; w.len()+1]; for i in 0..w.len() { csum[i+1] = csum[i] + w[i]; } let c = (x-1) / csum[n]; let x = x % csum[n]; for i in 0..n { tab[0][i] = csum.lower_bound(&(csum[i] + x)) % n; } for i in 0..LOG { for j in 0..n { tab[i+1][j] = tab[i][tab[i][j]]; }} let mut ans = Vec::with_capacity(n); for k in k { let mut pref = 0; for i in 0..LOG { if (k-1) >> i & 1 == 1 { pref = tab[i][pref]; } } let now = tab[0][pref]; let c = if now <= pref { n - pref + now } else { now - pref } + c * n; ans.push(c); } println!("{}", ans.iter().join("\n")); }
F - Main Street
見た感じ苦手問題なので飛ばしました。
G - Triangle
コンテスト中に解けず…。
$ \mathcal {O} ( N ^ 3 ) $ 通りそうだなぁと思って出してみたんですが、 Rust では通らず…。 C++ なら通ったっぽい。 C++ で書けば良かった～～～。 $i, j \ (i < j)$ を決め打って考えたときに、 $i, j$ よりも頂点番号が大きい奴で両方に繋がっている奴を見つけたら良いです。愚直にやると $ \mathcal {O} ( N ^ 3 ) $ になるんですが、 bitset で管理すると64倍高速化できます。
うーん…。最近 bitset 使ってなかったから全然思い浮かばなかったなぁ。 $i, j$ を小さい順に考えると、良い感じに $k$ を求められないかとは考えていたんだけど、残念。
こういう問題、出しても良いけど問題としては面白くないなぁ……。
fn main() { input! { n : usize, a : [Bytes; n] } let mut g = vec![bitset_fixed::BitSet::new(n); n]; for i in 0..n { g[i] = bitset_fixed::BitSet::new(n); for j in i+1..n { if a[i][j] == b'0' { continue } g[i].set(j, true); } } let mut ans : usize = 0; for i in 0..n { for j in i+1..n { if a[i][j] == b'0' { continue } ans += (&g[i] & &g[j]).count_ones() as usize; }} println!("{}", ans); }
Ex - Odd Steps
見てない
まとめ
1591 パフォ。 レート 1549 → 1553(+4) 渋い… D まではかなり早かったのでその勢いを維持したかった……！
E で $K$ 番目まで入れたときにどこで終わるかすぐ求め終わって居たのに、その1個前とか謎の実装をし始めて沼ったのが良くなかった。その1個前は $K-1$番目を求めると良いんですよねぇ……
AtCoder Beginner Contest 255
AtCoder Beginner Contest 255 です。
A - You should output ARC, though this is ABC.
2行2列の行列が与えられるので、その $R$ 行 $C$ 列のものを出力して下さいという問題。2次元の配列で受け取りができれば簡単です。
fn main() { input! { r : Usize1, c : Usize1, a : [[i64; 2]; 2] } println!("{}", a[r][c]); }
B - Light It Up
$N$ 人それぞれ、明かりを持っている $K$ 人の最短距離の最大値が答えになります。
fn main() { input! { n : usize, k : usize, a : [Usize1; k], p : [(f64, f64); n] } let mut ans: f64 = 0.; for &(x1,y1) in p.iter() { let mut t = std::f64::MAX; for &i in a.iter() { t = t.min( hypot(x1 - p[i].0, y1 - p[i].1)); } ans = ans.max(t); } println!("{}", ans); }
C - ±1 Operation 1
算数をします。終わり。 上限よりも大きいか、下限よりも小さいなら上限か下限に合わせれば良いです。 間なら、そこから一番近い上側の要素か、下側の要素に合わせたら良いです。 僕の書き方だと、 $d=0$ で最初から一致しているときにバグるので場合分けしておきます。
fn main() { input! { mut x : i64, a : i64, d : i64, n : i64 } if d == 0 && a == x { println!("0"); return; } let min = a.min(a + d*(n-1)); let max = a.max(a + d*(n-1)); let ans; if max < x || x < min { ans = (x - (a+d*(n-1))).abs().min((x-a).abs()) } else { let p = x - a; let mut t = std::i64::MAX; if (min..=max).contains(&((p/d+1)*d+a)) { t = t.min(((p/d+1)*d+a - x).abs()); } if (min..=max).contains(&(p/d*d+a)) { t = t.min((x - p/d*d-a).abs()); } ans = t; } println!("{}", ans); }
D - ±1 Operation 2
こっちの方が（競プロチックで）僕にとっては簡単でした。 $X$ に揃えるとき、 $X$未満の要素数・ $X$ 未満の要素の総和、 $X$以上の要素数・ $X$ 以上の要素の総和が分かれば計算できます。$A$ をソートしておて $X$ がどこに入るか二分探索で求めてそこから良い感じにやれば良いです。累積和を取っておくと総和はすぐ求まります。
fn main() { input! { n : usize, q : usize, mut a : [usize; n], queries : [usize; q] } a.sort(); let mut csum = vec![0; n+1]; for i in 0..n { csum[i+1] = csum[i] + a[i]; } let mut ans = vec![]; for x in queries { let index = a.lower_bound(&x); let left = csum[index]; let leftc = index; let rightc = n - index; let right = csum[n] - csum[index]; ans.push(x*leftc - left + right - x*rightc); } println!("{}", ans.iter().join("\n")); }
E - Lucky Numbers
式を書くと $A _ 0$ を決めたら全部決まる事が分かります。 後は、 $A_0$ から求められるように累積和みたいなものを取っておいて、 $ A _ i$ を $X_j$ にするとき他の値がラッキーナンバーになっているかチェックしたら良いです。
よく考えたら、 $A _ i$ 要素を $X _ j$ にするときの $A _ 0$ を全部探索して、最も多い $A _ 0$ を採用したら良いので、$ M $ のループ 1個減らせる。 実装してみたが、O($ N M ^ 2 $) とそんなに変わらなかった。
fn main() { input! { n : usize, m : usize, s : [i64; n-1], x : [i64; m] } let y : FxHashSet<_> = x.iter().cloned().collect(); let mut csum = vec![0; n]; for i in 0..n-1 { csum[i+1] = csum[i] + if i%2==0 {s[i]} else {-s[i]} } let mut cnt1 = FxHashMap::default(); let mut cnt2 = FxHashMap::default(); for (i, &a) in csum.iter().enumerate() { if i%2 == 0 { *cnt1.entry(a).or_insert(0) += 1; } else { *cnt2.entry(a).or_insert(0) += 1; } } let mut ans = 0; for (i, &ai) in csum.iter().enumerate() { for &xj in x.iter() { // ai を xj にするための a_0 の値 let a0 = if i%2!=0 {ai - xj} else {xj - ai}; let mut t = 0; for &xp in x.iter() { let p = xp + a0; if let Some(&c) = cnt2.get(&p) { t += c; } let p = a0 - xp; if let Some(&c) = cnt1.get(&p) { t += c; } } chmax(&mut ans, t); } } println!("{}", ans); }
F - Pre-order and In-order /
E 解けねぇってパッと見たときに in-order の方が理解できなくて諦めたんだけど、よく読んだら意味が分かった。 なんか行きがけ順ベースで、通りがけが来たら〜って左右に振っていくと良さそうなんだけど、ちゃんと読んだのが終了2分前で何も間に合わず。
G - Constrained Nim /
コンテスト後にゲーム問題なら見れば良かった〜って思ったけど、解けず。 やりたいことは大体分かったが、うまく値を管理することができず…。
Ex - Range Harvest Query
見てない
まとめ
最近の ABC 苦手な問題ばっかりであんまり面白くないな…。
まぁ、苦手問 ２問もあってこの成績ならまだ良いか？ パフォ 1484 レート 1504 → 1502
AtCoder Beginner Contest 253
AtCoder Beginner Contest 253 です。
A - Median?
$a,b,c$ が与えられるので $b$ が中央値か？ と言う問題 a..=c の間に $b$ が含まれていると良い。
fn main() { input! { a : usize, b : usize, c : usize } println!("{}", if (a.min(c)..=c.max(a)).contains(&b) {"Yes"} else {"No"}); }
B - Distance Between Tokens
'o' の座標を求めて、x軸方向とy軸方向別々に距離を足したら良い。同じ記号なので少しめんどくさい。
fn main() { input! { h : usize, w : usize, s : [Chars; h] } let mut st = (0,0); let mut g = (0,0); let mut f = false; for i in 0..h { for j in 0..w { if s[i][j] == '-' {continue} if !f { st = (i,j); f=true;} else { g = (i,j); } }} println!("{}", st.0.max(g.0) - st.0.min(g.0) + st.1.max(g.1) - st.1.min(g.1)); }
C - Max - Min Query
$x$ を多重集合に入れたり、 $x$ を $c$ 個多重集合から消したりする（足りなかったら $0$ になるまで）。後、多重集合の max と min を求める。
問題はシンプルだが、データ構造がないとめんどくさい。 BTreeMultiSet を作っているので、それをはっつける。 $c$個削除は実装していなかったので、温かみのある実装をする。
流石に無いのは不便なので、コンテストあとに実装した（修正版）。
fn main() { input! { q : usize } let mut s = BtreeMultiSet::new(); for _ in 0..q { input! { t : u8 } match t { 1 => { input! { x : usize } s.add(x); } 2 => { input! { x : usize, c : usize } match s.set.get_mut(&x) { Some(xc) => { if *xc <= c { s.set.remove(&x); } else { *xc -= c; } } None => {}, } } 3 => { println!("{}", s.last().unwrap() - s.first().unwrap()); } _ => unreachable!() } } }
D - FizzBuzz Sum Hard
$N$ 以下の正整数のうち $A$の倍数でも $B$ の倍数でもないものの総和を求める問題。最初総和じゃなくて個数を求めて 「？？？」となっていた。
Rust を信じて (0..=n).step_by(a).sum::<usize>() などとするも TLE。 O(1) でやってくれ……！
仕方ないので、自分で式を書く。
fn main() { input! { n : usize, a : usize, b : usize } let mut ans = n * (n+1) / 2; ans -= (a + n/a*a) * (n/a) / 2; ans += (lcm(a,b) + n/lcm(a,b)*lcm(a,b)) * (n/lcm(a,b)) / 2; ans -= (b + n/b*b) * (n/b) / 2; println!("{}", ans); }
E - Distance Sequence
dp[i][j] i桁決まって、 $A _ i = j$ である場合の数とかをやれば良い。そのまま計算すると O(NMK) とかになってヤバそうなので、累積和取っておいて、 総和 - 満たさない範囲 とかをしたら良い。 $K = 0$ のときに注意
fn main() { input! { n : usize, m : usize, k : usize } if k == 0 { println!("{}", pow(m,n,MOD as usize)); return; } const MOD : i64 = 998_244_353; let mut dp = vec![1; m+1]; for _ in 1..n { let mut next = vec![0; m+1]; let mut csum = vec![0; m+2]; let mut sum = 0; for i in 1..=m { csum[i] = (csum[i-1] + dp[i]) % MOD; sum += dp[i]; sum %= MOD; } for i in 1..=m { next[i] = (sum + MOD - csum[m.min(i+k-1)] + csum[i.saturating_sub(k)]) % MOD; next[i] %= MOD; } dp = next.into_iter().map(|d| d % MOD).collect_vec(); } let mut ans = dp[1..].iter().fold(0, |acc,&v| (acc+v) % MOD) % MOD; println!("{}", ans); }
F - Operations on a Matrix
本番中解けなかった。クエリ平方分割しようとして沼った。
後半に考えていた、後ろからやって $i$ 行目を $x$ にする操作のときに良い感じに計算するやつ、結局時間が足りずに詰め切れなかったんだけど、コンテスト後にちゃんと書いたら通った。
3 のクエリが流れてきたときを $0$ として、良い感じにやると良い。
fn main() { input! { n : usize, m : usize, q : usize, } let mut queries = Vec::with_capacity(q); let mut bit = FenwickTree::<i64>::new(m+1); let mut cnt = 0; let mut nq = vec![vec![]; n]; for _ in 0..q { input! { t : u8 } match t { 1 => { input! { l:Usize1, r:usize, x:i64 } queries.push((t, l, r, x)); } 2 => { input! { i:Usize1, mut x:i64 } queries.push((t, i, 0, x)); } 3 => { input! { i:Usize1, j:Usize1 } queries.push((t, i, j, cnt)); cnt += 1; } _ => unreachable!() } } let mut ans = vec![0; cnt as usize]; for (t, l, r, x) in queries.into_iter().rev() { match t { 1 => { bit.add(l, x); bit.add(r, -x); } 2 => { let i = l; for (index, j) in nq[i].drain(..) { ans[index as usize] += x + bit.fold(j); } } 3 => { let (i, j) = (l,r); let index = x as usize; nq[i].push((index, j)); ans[index] -= bit.fold(j); } _ => unreachable!() } } for i in 0..n { for (index, i) in nq[i].drain(..) { ans[index as usize] += bit.fold(i); } } println!("{}", ans.iter().join("\n")); }
G - Swap Many Times
見てない。
Ex - We Love Forest
見てない
まとめ
微妙。 レート 1529 → 1530(+1)
Codeforces Round #748 (Div. 3)
Codeforces Round #748 (Div. 3) のバーチャル参加をしたのでまとめ。
A,B,C,D1,E の 5完。7ペナ。ペナが多くて良くないね。
A. Elections
他の候補者に勝つために、最低後何票必要ですか？という問題。 良い方針が思いつかないので、最大値が何個あるかで場合分けをする。
よく考えると、 a_ans = max(0, max(b, c) + 1 - a) とかで良い。
fn solve() { let a : Vec<usize> = input_vec(); let max = *a.iter().max().unwrap(); let mut cnt = a.iter().filter(|&&a| a==max).count(); if cnt == 3 { println!("{} {} {}", 1, 1, 1); } else if cnt == 2 { println!("{} {} {}", if a[0] == max {1} else {max-a[0]+1}, if a[1] == max {1} else {max-a[1]+1}, if a[2] == max {1} else {max-a[2]+1}, ) } else { println!("{} {} {}", if a[0] == max {0} else {max-a[0]+1}, if a[1] == max {0} else {max-a[1]+1}, if a[2] == max {0} else {max-a[2]+1}, ) } }
B. Make it Divisible by 25
正整数 $n$ が与えられるので、何文字か削除して 25 の倍数にして下さいという問題。
雑にどこか1文字を消すプログラムを書くも TLE。よく考えると、下位3桁くらい（本当は2桁で良いバチャ中は雑に考えてた）が 25 で割り切れたら良いので、削除するのは下位3桁のどれかだけで良い。念のため同じ値を入れないように BTree な Set に探索済みの値を入れておいた（こっちの方が効いたかも？）。
fn solve() { let n : usize = input(); let mut q = VecDeque::new(); q.push_back((n, 0)); let mut s = BTreeSet::new(); while let Some((n, i)) = q.pop_front() { if n % 25 == 0 { println!("{}", i); return; } if s.insert(n/10) { q.push_back((n/10, i+1)); } if s.insert(n/100*10 + n%10) { q.push_back((n/100*10 + n%10, i+1)); } if s.insert(n/1000*100 + n%100) { q.push_back((n/1000*100 + n%100, i+1)); } } }
C. Save More Mice
一直線上に猫1匹と、ネズミが $n$匹 居て $k$ に穴がある。ネズミを1匹だけ1進める・猫を1進めるを交互に繰り返して、ネズミを何匹穴に到達させられるかという問題（猫に追いつかれるとダメ）。
ネズミが先に移動するので、ネズミは猫が穴に到達するまでの $k$回の移動ができる。 よって穴に近い方からゴールさせていき $k$ 回以下となるギリギリを求めたら良い。
fn solve() { let (k, n) : (usize, usize) = input_t(); let mut x : Vec<usize> = input_vec(); x.sort(); x.reverse(); let mut ans = 0; let mut sum = 0; for x in x { if sum + (k - x) >= k { break } sum += (k - x); ans += 1; } println!("{}", ans); }
D1. All are Same
数列 $a$ が与えられる。ある $i$ を選んで $a_i = a_i - k$ をするのを繰り返して、 $a$ を全部同じ値にするとき、それを達成できる $k$ の最大値を求めて下さい。という問題。
操作回数 0回で済む場合は、 $k$ はどんな値でも良いので操作回数0を考えると最初から全部同じ場合である。全部同じ場合は -1 とする。それ以外のときを考える。
適当な $i,j$ を選んで、それらを1回で揃えるには $ \mid a _ i - a _ j \mid $ かかる。それを共通で良い感じにしたいので、 GCD を取れば良い。$n$ が小さいので、適当で良い。
fn solve() { let n : usize = input(); let a : Vec<i64> = input_vec(); if a.iter().filter(|&&b| a[0] == b).count() == n { println!("-1"); return; } let mut g = 0; for i in 0..n { for j in i+1..n { g = gcd(g, (a[i]-a[j]).abs()); }} println!("{}", g); }
D2. Half of Same
バチャ中は解けなかった。 揃えるやつを決めて、その差の絶対値で GCD を map で管理しながらやれば良いと思ったんだけどダメ…。これなんでダメなんだ…？（いくつかあるけどこんな感じ → WA （これ GCD が 0 になるやつの扱いがダメそうだな。））。
$n$ がそんなに多くないので、差の絶対値の約数を列挙してちゃんと数えて良い。
$a_i$ を決め打ちして、$a_i$ と同じやつは別で数えておく。後は、差を取って約数列挙カウントを愚直によやると良い。これも D1 と同様に、同じやつが $n/2$ 以上あったら -1 。
fn solve() { let n : usize = input(); let mut a : Vec<i64> = input_vec(); let mut cnt = BTreeMap::new(); for &a in a.iter() { *cnt.entry(a).or_insert(0) += 1; } let max = cnt.into_iter().map(|(_,c)| c).max().unwrap(); if max>=n/2 { println!("-1"); return; } let mut ans = 0; for &ai in a.iter() { let mut cnt = BTreeMap::new(); let mut c = 0; for &aj in a.iter() { if ai == aj { c+=1; continue } for d in f((ai - aj).abs()) { *cnt.entry(d).or_insert(0) += 1; } } for (g, j) in cnt { if j+c>=n/2 { ans=ans.max(g); }} } println!("{}", ans); } fn f(x: i64) -> Vec<i64> { let mut sqrt = 0.max((x as f64).sqrt() as i64 - 10); while (sqrt+1)*(sqrt+1) <= x { sqrt += 1; } let mut res = vec![]; for i in 1..=sqrt { if x % i != 0 { continue } res.push(i); if x/i != i { res.push(x/i); } } res }
【追記】
差の絶対値で GCD を map で個数を管理するやつダメだって言ったけどできました。 管理の仕方が悪くて、その GCD になる最大値を管理するべきでした…
fn solve() { let n : usize = input(); let a : Vec<i64> = input_vec(); let mut cnt = BTreeMap::new(); for &a in a.iter() { *cnt.entry(a).or_insert(0) += 1; } let max = cnt.into_iter().map(|(_,c)| c).max().unwrap(); if max >= n/2 { println!("-1"); return; } let mut ans = 0; for i in 0..n { let mut cnt = BTreeMap::new(); for j in 0..n { for (g, c) in cnt.clone() { let g = gcd(g, (a[i] - a[j]).abs()); let t = cnt.entry(g).or_insert(0); *t = (c+1).max(*t); } cnt.entry((a[i]-a[j]).abs()).or_insert(1); } for (g, c) in cnt { if c >= n/2 {ans=ans.max(g); }} } println!("{}", ans); }
E. Gardener and Tree
木が与えられるので、葉から消していくのを $k$ 回繰り返して残る頂点数を答えて下さいという問題。特に根が有るわけじゃないので、端っこから消えていく。
多始点の BFS みたいなことをしながら端っこを取り除くみたいなことを繰り返すと良い。何回目で取り除かれるかっていうのを入れていくと良いが、次数が $1$ になる（親だけ残る）タイミングだけ取り除かれるカウンターを更新する必要がある（4 WA）。
fn solve() { let (n, k) : (usize, usize) = input_t(); if n == 1 { println!("0"); return; } let mut g = vec![vec![]; n]; let mut cnt = vec![0; n]; for _ in 0..n-1 { let (mut a, mut b) : (usize, usize) = input_t(); a-=1; b-=1; g[a].push(b); g[b].push(a); cnt[a]+=1; cnt[b]+=1; } let mut d = vec![0; n]; let mut q = VecDeque::new(); let mut used = vec![false; n]; for i in 0..n { if cnt[i] == 1 { q.push_back(i); d[i]=1; used[i]=true;}} while let Some(v) = q.pop_front() { used[v] = true; for &u in g[v].iter() { if used[u] { continue } cnt[u] -= 1; if cnt[u] == 1 { q.push_back(u); d[u]=d[v]+1;} } } println!("{}", d.iter().filter(|&&d| d>k).count()); }
F. Red-Black Number
読んだけど解けてない
【2022/05/28 追記】
ネタバレ？を見つつ実装。
$N, A, B$ が小さいので、良い感じに DP をして、復元をする。
dp[i][j][k][l] $i$ 桁使って、$A$ で割った余りが $j$ 、$B$ で割った余りが $k$ 、赤（もしくは黒）が $l$ 桁 をして、復元する。そんなに遅くないようにかいたつもりなんだけど TL ギリギリだった。 $t$ がそんなに大きくないのでまとめて出力するようにしてもほぼ変わらず…。これ遅めの言語だと辛そう？ usize をたくさん持っているのが良くないのかね？
fn solve() { let (n, a, b) : (usize, usize, usize) = input_t3(); let x : Vec<_> = input::<String>().chars().collect(); let x = x.into_iter().map(|c| (c as u8 - b'0') as usize).collect::<Vec<_>>(); let mut dp = vec![vec![vec![vec![false; n+1]; b]; a]; n+1]; let mut pref = vec![vec![vec![vec![None; n+1]; b]; a]; n+1]; dp[0][0][0][0] = true; // dp for (i, c) in x.into_iter().enumerate() { for j in 0..a { for k in 0..b { for l in 0..n { if !dp[i][j][k][l] { continue } let d = dp[i][j][k][l]; if l+1 <= n { dp[i+1][(j*10 + c) % a][k][l+1] |= d; pref[i+1][(j*10 + c) % a][k][l+1] = Some((i,j,k,l)); } dp[i+1][j][(k*10 + c) % b][l] |= d; pref[i+1][j][(k*10 + c) % b][l] = Some((i,j,k,l)); }}} } // 赤と黒の桁の差が少なくなるところを探す let mut min = std::usize::MAX; let mut index = None; for i in 1..n { if !dp[n][0][0][i] { continue } let d = i.max(n-i) - i.min(n-i); if min >= d { min = d; index = Some(i); } } if index.is_none() { println!("-1"); return; } // 復元 let mut ans = Vec::with_capacity(n); let mut now = (n, 0, 0, index.unwrap()); while let Some(next) = pref[now.0][now.1][now.2][now.3] { ans.push(if now.3 == next.3 {'B'} else {'R'}); now = next; } println!("{}", ans.iter().rev().collect::<String>()); }
G. Changing Brackets
読んでない
まとめ
Codeforces Anytime は冷え。うーん、 D2 は解けるべきだったかもしれない。
[バーチャル参加] zeronosu77108_さんのCodeforces Round #748 (Div. 3)での結果は662位でした！ パフォーマンス：1645相当 レーティング：1707→1691 (-16) #CodeforcesAnytime https://codeforces-anytime.sonoapp.page/users/0RUV6NRz0XY7Jco7nDg0fjn4z3h2?cert=17
AtCoder Beginner Contest 252
AtCoder Beginner Contest 252 です。
6完ペナ込み 97:22 でした（5ペナ）。 6完したのに激渋なんですが…。
A - ASCII code
文字コードが与えられるので変換して出力します。
fn main() { input! { n : u8 } println!("{}", n as char); }
B - Takahashi's Failure
嫌いな食べ物のうち、1つでもおいしさ最大のものがあったら、嫌いな食べ物を食べる可能性があります。
先に $A$ の最大値を求めておいて、 $A_{B_i}$ が最大値と一致するか見たら良いです。
fn main() { input! { n : usize, k : usize, a : [usize; n], b : [Usize1; k] } let max = *a.iter().max().unwrap(); println!("{}", if b.iter().any(|&i| a[i] == max) {"Yes"} else {"No"}); }
C - Slot Strategy
どれか一つの数字に揃えたくて、最短で揃えたら何秒になりますか？っていう問題。
$N \leq 100$ と小さいので、一番近い奴にどんどん揃えていけば良いです。
fn main() { input! { n : usize, s : [Bytes; n] } let mut ans = std::usize::MAX; for i in 0..10 { // i に揃える let mut used = vec![false; n]; let mut tmp = 0; let mut now = 0; let mut a = 0; for k in 0..n { let mut min = std::usize::MAX; for (j, s) in s.iter().enumerate() { if used[j] { continue } let index = s.iter().position(|&c| (c-b'0') == i as u8).unwrap(); let t = if now%10 < index || k==0 && index==0 { index - now%10 } else { 10 - now%10 + index }; if t < min { min=t; a=j; } } now += min; used[a] = true; } ans = ans.min(now); } println!("{}", ans); }
D - Distinct Trio
異なるものを 3つ選ぶ方法を直接求めるのは難しそうです。よって、どれかが同じになるものを考えて、全体から引けば良さそうです。
$N$ 個の中から、3個を選ぶ組合せは、 ${} _ n \mathrm{C} _ 3$ なので、 $\frac{n \times (n-1) \times (n-2)}{3!} $ になります。
重複する場合を数えたいので、まず各数が何個あるのか数えます。ある数$i$が $c$個あるとき、 3個のうち $i$ が 2個選ばれる場合の数は、 ${} _ c \mathrm{C} _ 2 \times (n - c)$ です。 3個選ばれる場合は、 ${} _ c \mathrm{C} _ 3 $ です。よって、これらを引けば良いです。
fn main() { input! { n : usize, a : [usize; n] } let mut ans = n * (n-1) / 2 * (n-2) / 3; let mut mp = BTreeMap::new(); for &a in a.iter() { *mp.entry(a).or_insert(0) += 1; } for (_, &c) in mp.iter() { ans -= c * (c-1) / 2 * (n - c); ans -= c * (c-1) / 2 * (c-2) / 3; } println!("{}", ans); }
E - Road Reduction
都市1からの最短経路となる辺だけを残して最小全域木にしてくださいという問題。
ダイクストラして、その経路復元をしたら良いです。 ちゃんと復元するとめんどくさいので、頂点の最短距離が確定したときにそこに来るために使用した辺を保存していけば良いです。
最後の出力、辺の数で確認しなければいけないのに、頂点数でチェックしてペナりました。
fn main() { input! { n : usize, m : usize, edges : [(Usize1, Usize1, usize); m] } let mut g = vec![vec![]; n]; for (i, &(a,b,c)) in edges.iter().enumerate() { g[a].push((b,c,i)); g[b].push((a,c,i)); } let mut used = vec![false; m]; dijkstra(0, &g, &mut used); println!("{}", (1..=m).filter(|i| used[i-1]).join(" ")) } fn dijkstra<T>(s:usize, g:&Vec<Vec<(usize,T, usize)>>, used:&mut Vec<bool>) -> Vec<Option<T>> where T : Clone + Copy + num::Zero + std::ops::Add + std::cmp::Ord { let mut dist = vec![None; g.len()]; dist[s] = Some(std::cmp::Reverse(T::zero())); let mut pq = std::collections::BinaryHeap::from(vec![(std::cmp::Reverse(T::zero()), s, None)]); while let Some((std::cmp::Reverse(c),v, i)) = pq.pop() { if let Some(std::cmp::Reverse(d)) = *&dist[v] { if d < c { continue } if let Some(i) = i { used[i] = true; } for &(u, c, j) in g[v].iter() { if chmax(&mut dist[u], Some(std::cmp::Reverse(d + c))) { pq.push((dist[u].unwrap().into(), u, Some(j))); } } } } dist.into_iter().map(|d| match d {Some(std::cmp::Reverse(x)) => Some(x), _ => None}).collect() }
F - Bread
大きいやつを何度も切るのは嫌なので、良い感じに小さくしたいです。これは逆向きに考えて良くて、小さい方からマージしていけば良いです。
後は、 $L - \sum A_i$ の分を上手く考えれば良いです。$L - \sum A_i = 0$ のときは何もしなくて良くて、$L - \sum A_i > 0$ の時は、 $L - \sum A_i$ もどこかのタイミングで切り出してやらないといけないので、切る候補の中に追加します。 ← これに気付くのに時間かかりすぎた（4ペナ…）。
fn main() { input! { n : usize, l : usize, a : [usize; n] } let mut pq : BinaryHeap<_> = a.iter().map(|&a| Reverse(a)).collect(); let sum = a.iter().sum::<usize>(); if l != sum { pq.push(Reverse(l - sum)); } let mut ans = 0; while pq.len() > 1 { let Reverse(a) = pq.pop().unwrap(); let Reverse(b) = pq.pop().unwrap(); ans += a + b; pq.push(Reverse(a + b)); } println!("{}", ans ); }
G - Pre-Order
読んだけど解けてない。
Ex - K-th beautiful Necklace
読んでない。
まとめ
1689パフォ、 レート 1509 → 1529（+20）。 最近失敗しまくりだったので、まぁ増えたので良かったかな。
6完したのに、 1689パフォは渋い！
