AtCoder Regular Contest 134
AtCoder Regular Contest 134 です。
バーチャル参加をしました。ペナ込みで 3完 60:23 でした。
A - Bridge and Sheets
橋に$N$ 枚のシートが敷かれていて、後何枚追加したら橋を全部覆えますか？という問題。
一番端から1枚目のシートの間を覆うには～、1枚目から2枚目の間は～って考えて行ったら良いです。 最後に敷いたシートの右端を計算して持っておけば、$a_i$ から引けば間の距離が分かります。後は $w$ で切り上げ除算します。
fn main() { input! { n : usize, l : usize, w : usize, mut a : [usize; n] } a.push(l); let mut pre = 0; let mut ans = 0; for a in a { let c = (a.saturating_sub(pre)+w-1)/w; ans += c; pre = a + w; } println!("{}", ans); }
B - Reserve or Reverse
問題文の理解をするのに時間かかりました… $S_0$ と $S_N$ をスワップ、 $S_1$ と $S_{n-1}$ をスワップみたいな感じで外側からスワップしていって辞書順最小にしてください。という問題。
辞書順最小にするには、最も小さい文字を手前に持ってくるようにしたら良いです。
そのためには、各文字の index を先に求めておいて、できるだけ後ろの a を前に持ってきて後ろ側をどこまで使ったか覚えておくみたいなことをしたら良いです。
fn main() { input! { n : usize, mut s : Chars } let mut index = vec![vec![]; 26]; for (i, &c) in s.iter().enumerate() { let c = (c as u8 - b'a') as usize; index[c].push(i); } let mut now = n; for (i, c) in s.clone().into_iter().enumerate() { let c = (c as u8 - b'a') as usize; 'e: for j in 0..c { while let Some(x) = index[j].pop() { if i <= x && x <= now { s.swap(i, x); now = x; break 'e } } } } println!("{}", s.iter().join("")); }
C - The Majority
難しい…
箱に $1$ が 0個では過半数が満たされないため、まず $1$ を箱に1個ずつ入れた状態から考えます。 このとき、箱は過半数であるという条件は満たされているので、他の番号が書かれたボールを入れるときに一緒に $1$ のボールを入れたら条件は満たされたままになります。 そのため、 $1$ が書かれたボールは、 $1$以外のボールの数 + 箱の数（$K$）以上である必要があります。
次に、$1$ 以外のボールを箱に振り分ける組合せを考えます。これは、それぞれの数字に対して箱に振り分ける組合せを考えたら良いので、良い感じにします（重複組合せ）。
後は、余った $1$ のボールを振り分ける方法をかけたら良いです。
今回は、入力される値が大きく、$K$が小さいので毎回組合せを計算します。
fn main() { input! { n : usize, k : usize, a : [usize; n] } const MOD : usize = 998_244_353; let sum = a.iter().skip(1).sum::<usize>(); if a[0].saturating_sub(k) < sum { println!("0"); return; } let mut ans = 1; for &a in a.iter().skip(1) { ans *= nCr(a + k - 1, k - 1, MOD); ans %= MOD; } ans *= nCr(a[0]-sum-k+k-1, k-1, MOD); ans %= MOD; println!("{}", ans); }
D - Concatenate Subsequences
よく分かりませんでした。 E 以降は見てません。
まとめ
バーチャル参加でしたが、まぁまぁの成績だったと思います。
AtCoder Beginner Contest 236
はい． AtCoder Beginner Contest 236 です。
Unrated 参加しました。
4完 41:56 でした（1ペナ込み）
A - chukodai
問題文の通り、 $a$ 文字目と $b$ 文字目を入れ替えて出力します。
fn main() { input! { mut s : Chars, a : Usize1, b : Usize1 } s.swap(a, b); println!("{}", s.into_iter().join("")); }
B - Who is missing?
$1$ から$N$ までのカードが 4 枚ずつあって、そのうちの1枚が抜かれているのでそれを求める問題。
抜かれていなかったら、 $1$ から $N$ までの総和の $4$倍がカード全部の合計になっているので、残っているカードの和を引いたら抜かれているカードが分かります。
fn main() { input! { n : usize, a : [usize; 4*n-1] } let sum = a.into_iter().sum::<usize>(); println!("{}", n*(n+1)/2*4 - sum); }
C - Route Map
$S_i$ が $T_j$ の中にありますか？という問題。
$T$ の集合を Set などに乗せると存在判定が早くできるため、そうしたら愚直に判定できる。
fn main() { input! { n : usize, m : usize, s : [String; n], t : [String; m] } let t : FxHashSet<_> = t.into_iter().collect(); println!("{}", s.into_iter().map(|s| if t.contains(&s) {"Yes"} else {"No"}).join("\n")); }
D - Dance
「愚直に探索できるだろ！」をしたら TLE しました。（このミス何回するんだろう…） DFSするときに片方の INDEX は最小のものに固定しないと計算量が大変なことになります。
最初に見つけた !used なやつを使ったら break したら良いです。
fn main() { input! { n : usize } let mut a = vec![vec![0; 2*n]; 2*n]; for i in 0..2*n { input! { aa : [usize; 2*n-1-i] } for j in 0..2*n-1-i { a[i][i+j+1] = aa[j]; a[i+j+1][i] = aa[j]; } } let mut used = vec![false; 2*n]; let ans = dfs(0, n, &mut used, &a); println!("{}", ans); } fn dfs(s:usize, n:usize, used:&mut Vec<bool>, a:&Vec<Vec<usize>>) -> usize { if used.iter().all(|&f| f) { return s; } let mut res = 0; for i in 0..2*n { if used[i] { continue } used[i] = true; for j in i+1..2*n { if used[j] { continue } used[j] = true; res = res.max(dfs(s ^ a[i][j], n, used, a)); used[j] = false; } used[i] = false; break } res }
E - Average and Median
なんで解けなかったんだろう…？ 二分探索するのは分かったんだけど判定で迷ってました。
二分探索で平均の目標を決めて、 $A_i$ から引いておけばどれくらい目標値と離れているか分かるので、後は取る/取らないで条件を考慮しながら和の最大値を求めるDPをしたら良いです。
中央値も同じ感じで、目標値以上かどうかを判定して同じ感じで数を数えたら良いです。
fn main() { input! { n : usize, a : [i64; n] } let ave = { let mut l = 0.0; let mut r = 1_000_000_001.0; for _ in 0..100 { let m = (l+r) / 2.0; let b = a.iter().map(|&i| i as f64 - m).collect_vec(); let mut dp : Vec<Vec<f64>> = vec![vec![0.0; n+1]; 2]; for i in 1..=n { dp[0][i] = dp[1][i-1]; // 取らない dp[1][i] = dp[0][i-1].max(dp[1][i-1]) + b[i-1]; // 取る } if dp[0][n].max(dp[1][n]) < 0. { r = m } else { l = m } } l }; let med = { let mut l = 0; let mut r = 1_000_000_001; while l+1 < r { let mut m = (l+r) / 2; let b = a.iter().map(|&i| if i>=m {1} else {-1}).collect_vec(); let mut dp = vec![vec![0; n+1]; 2]; for i in 1..=n { dp[0][i] = dp[1][i-1]; // 取らない dp[1][i] = dp[0][i-1].max(dp[1][i-1]) + b[i-1]; // 取る } if dp[0][n].max(dp[1][n]) <= 0 { r = m } else { l = m } } l }; println!("{}\n{}", ave, med); }
F - Spices
XOR の基底だろうな～って思いながら考えていたんですが、 E で時間を使ってしまってあんまり時間がなかったです…
これは得意側な問題なので見た瞬間解けても良かった気がします…
安い方から使いたいので、$c_i$ の昇順に処理します。 ある $c_i$ を採用するかどうか考えたときに、今まで採用したスパイスから作れるものであれば採用する必要がありません。
小さい順に、基底かどうかチェックしつつ採用するかどうかを決めたら良いです（参考）。
fn main() { input! { n : usize, c : [usize; (1<<n)-1] } let c = c.into_iter().enumerate().map(|(i,c)| (c,i+1)).sorted().collect_vec(); let mut ans = 0; let mut base = vec![]; for (c, mut i) in c { for &b in base.iter() { i = i.min(b ^ i); } if i == 0 { continue } base.push(i); ans += c; } println!("{}", ans); }
G - Good Vertices
見てません
Ex - Distinct Multiples
見てません
まとめ
E,F は解けたな～って感じですね…
AtCoder Beginner Contest 215
はい． AtCoder Beginner Contest 215 です。
バーチャル参加をしました。 5完 52:58 でした。
A - Your First Judge
問題文の通り Hello,World! と一致するか判定したら良いですね。
fn main() { input! { s: String } let ans = s == "Hello,World!"; println!("{}", if ans {"AC"} else {"WA"}); }
B - log2(N)
$2 ^ k \leq N$ となる最大の $k$ を求める問題。 制約が$N \leq 10^{18}$ なので最大でどれくらいになるか考えて見ます。 $\log_2(10^{18})$ は $60$ 以下なので、愚直に求めても良さそうです。愚直に $2$ の累乗を計算していって超えないギリギリを求めます。
fn main() { input! { n : u64 } let mut ans = 0; { let mut tmp = 1; while tmp * 2 <= n { tmp *= 2; ans+=1; } } println!("{}", ans); }
C - One More aab aba baa
苦労しました… $N \leq 8$ なので全探索して良いんですが、 Rust の （Itertools の） permutations を使うと、重複が出るので焦っていました。 よく考えると、重複削除してソートされた奴から $K$ 番目のやつを出力したら良いです…
C++ でも next_permutation とかを使って列挙したらいけると思います。
fn main() { input! { mut s : Chars, k : usize } let n = s.len(); let mut ans = s.iter().permutations(n) .map(|p| p.iter().join("")).collect_vec(); ans.sort(); ans.dedup(); println!("{}", ans[k-1]); }
D - Coprime 2
難しくないですか？ 僕は苦手です。 最大公約数が $1$ である必要があるので、素因数分解が使えそうです。 $10^{5}$ 以下の素数はそんなに多くないので、素因数分解してそこに現れる倍数を消していく。 既に消されている素数はスキップする。とすると良さそうです。
fn main() { input! { n : usize, m : usize, a : [usize; n] } // 素因数分解用のテーブルを用意 let mut amax = *a.iter().max().unwrap(); let mut sieve = (0..=amax).collect_vec(); for i in 2..=amax { if sieve[i] != i { continue } for j in ((i*i)..=amax).step(i) { sieve[j] = i; } } let mut ans : BTreeSet<usize> = (1..=m).collect(); for &ai in a.iter() { let mut ai = ai; let mut p = HashSet::new(); while ai != 1 { p.insert(sieve[ai]); ai /= sieve[ai]; } // a_i を素因数分解 // 現れる素数の倍数を答え候補から削除 for pi in p.into_iter() { if !ans.contains(&pi) { continue } // 既になければスキップ for i in (pi..=m).step(pi as usize) { ans.remove(&i); } } } println!("{}", ans.len()); println!("{}", ans.iter().join("\n")); }
E - Chain Contestant
D よりこちらの方が（考察は）簡単に思えました。 AAC ～ AJC まで 10種類しかなくて、同じ種類のコンテストは連続でしか参加できないため、今までどこに訪れたか・最後に参加したコンテスト分かれば良さそうです。 そういう状態を持った DP をします。
dp[i][j][k] : i番目の文字まで使って、j のビットが立っている所は訪れていて、 k というコンテストを最後に参加した場合の数。
i 番目の文字を使うというのがめんどくさいので、 dp と next というテーブルを使って遷移しています。
next[x][1<<x] += 1 をしているのは、その部分からコンテストに出始めたところを考えています。
後は、 j >> x & 1 == 1 で j の状態は既に x が使われているかを判定していて、既に使われているなら最後に参加したコンテスト k が x と同じでないといません。
その判定をして continue しています。
後は、 j という状態から x を使ったという状態に行きたいので j | (1<<x) に遷移させます
fn main() { input! { n : usize, s : Bytes } let mut s : Vec<usize> = s.iter().map(|&c| (c - b'A') as usize).collect(); // 0..9 に変換しておく let mut dp = vec![vec![0_u64; 1<<10]; 10]; const MOD : u64 = 998244353; for x in s.into_iter() { let mut next = dp.clone(); next[x][1<<x] += 1; // ここから参加し始める for j in (0..(1<<10)) { for k in 0..10 { if j>>x&1 == 1 && x!=k { continue } // xを使っているなら、最後が x じゃないとダメ next[x][j | (1<<x)] += dp[k][j]; next[x][j | (1<<x)] %= MOD; }} dp = next; } let mut ans = 0; for i in 0..(1<<10) { for j in 0..10 { ans += dp[j][i]; ans %= MOD }} println!("{}", ans) }
F - Dist Max 2
見ました。 二分探索っぽいんですが、判定が書けません。
G - Colorful Candies 2
見てません。
H - Cabbage Master
見てません。
まとめ
参加してたら、 1600パフォくらいだったっぽいです？ C,E の実装詰まった感があるので、その辺かな～ F も解きたいけどね。
AtCoder Beginner Contest 210
はい． AtCoder Beginner Contest 210 です。
バーチャル参加をしました。ペナ込みで 5完 70:13 でした。
A - Cabbages
$Y < X$ が保証されているので、 $X$円で買って、安くなる分引けば良いです。
$N$ が $A$ よりも小さい場合があるので、引き算で求めるときに負にならないように気をつけましょう。
fn main() { input! { n : i64, a : i64, x : i64, y : i64 } println!("{}", x * n - 0.max(n - a) * (x - y) ) }
B - Bouzu Mekuri
左から見ていって、 1 が来たらどちらかの負けなのでそこから後ろは関係ありません。
交互にカードを食べるので、 1 が来るまでの偶奇が大切です。 take_while で前半から連続する 0 の個数を取って偶奇で判定します。
fn main() { input! { n : usize, s : Chars } println!("{}", if s.iter().take_while(|&&c| c == '0').count() % 2 == 0 {"Takahashi"} else {"Aoki"} ) }
C - Colorful Candies
$K$ が固定なので、最初に $K$ 個の区間を取って、後は１つずつ区間をずらして求めていけば良いです。右側を１つ伸ばして左側を１つ縮める感じですね。
このとき、見ている区間に現れる種類のそれぞれの個数が分かれば、 $0$ 個の状態から $1$ 個以上になったら種類数が増えるし、 $1$ 個以上の状態から $0$ 個になれば種類数が減ったことが分かります。
今回は、 $ 1 \leq C_i \leq 10^{9} $ と種類数が多いので、 HashMap みたいなものを使うか座標圧縮をして配列で持つなどをしましょう。
fn main() { input! { n : usize, k : usize, c : [Usize1; n] } let mut cnt = 0; let mut mp = HashMap::new(); // 初期化：最初の k 個の区間を求めておく for &ci in c.iter().take(k) { let t = mp.entry(ci).or_insert(0); if *t == 0 { cnt += 1; } *t += 1; } let mut ans= cnt; // 区間をずらして見ていく for i in k..n { { // 左端を消す let t = mp.entry(c[i-k]).or_insert(0); *t -= 1; if *t == 0 { cnt -= 1; } } { // 右端を追加する let t = mp.entry(c[i]).or_insert(0); if *t == 0 { cnt += 1; } *t += 1; } ans = ans.max(cnt); } println!("{}", ans); }
D - National Railway
難しい…
適当に $2$ 箇所選んで駅を建てたときのコストを最小化してくださいという問題。
１点（$A _ {i,j}$）を決めたときに、そこよりも左上とのペアにするときの（ $A_{i,j}$ を除く）コストが分かれば良いので、DP っぽく移動するたびに $c$ を足しつつ最小コストを求めつつ答えを求めます。
これを、左上・右上・左下・右下の４方向からやれば良いです（対称になるのでうまく２方向からやれば良さそう）。
fn main() { input! { h : usize, w : usize, c : usize, a : [[usize; w]; h] } let mut ans = std::usize::MAX; let mut lu = vec![vec![std::usize::MAX; w]; h]; for i in 0..h { for j in 0..w { if i > 0 { lu[i][j] = lu[i][j].min(lu[i-1][j] + c); } if j > 0 { lu[i][j] = lu[i][j].min(lu[i][j-1] + c); } if i!=0 || j!=0 { ans = ans.min(lu[i][j] + a[i][j]); } lu[i][j] = lu[i][j].min(a[i][j]); } } let mut ru = vec![vec![std::usize::MAX; w]; h]; for i in 0..h { for j in (0..w).rev() { if i > 0 { ru[i][j] = ru[i][j].min(ru[i-1][j] + c); } if j+1 < w { ru[i][j] = ru[i][j].min(ru[i][j+1] + c); } if i!=0 || j!=w-1 { ans = ans.min(ru[i][j] + a[i][j]); } ru[i][j] = ru[i][j].min(a[i][j]); } } let mut ld = vec![vec![std::usize::MAX; w]; h]; for i in (0..h).rev() { for j in 0..w { if i+1 < h { ld[i][j] = ld[i][j].min(ld[i+1][j] + c); } if j > 0 { ld[i][j] = ld[i][j].min(ld[i][j-1] + c); } if i!=h-1 || j!=0 { ans = ans.min(ld[i][j] + a[i][j]); } ld[i][j] = ld[i][j].min(a[i][j]); } } let mut rd = vec![vec![std::usize::MAX; w]; h]; for i in (0..h).rev() { for j in (0..w).rev() { if i+1 < h { rd[i][j] = rd[i][j].min(rd[i+1][j] + c); } if j+1 < w { rd[i][j] = rd[i][j].min(rd[i][j+1] + c); } if i!=h-1 || j!=w-1 { ans = ans.min(rd[i][j] + a[i][j]); } rd[i][j] = rd[i][j].min(a[i][j]); } } println!("{}", ans); }
E - Ring MST
明らかに最小全域木なので、最小全域木に思いを馳せます。しかし、$N$ が大きいので最小全域木を素直に求めることはできません。
そこで、コストが小さい順に処理をしていくことを考えます。
コストが小さい順に見ているので、今見ているやつをできるだけ使いたいです。
ある $(a, c)$ の組を考えたとき、好きに $x$ を決めて $x + a$ との間に辺が張れるので張れるだけ張ります。
例えば、$N = 6, A = 2$ だったら、 0 のノードからたどり着けるだけ張ったら以下のようになりますね。
1 からたどり着けるところにも全部張ってみましょう。
こんな感じで２つのグループに分かれました。 このとき $4 + A$ をしても $\mod 6$ で 0 に戻ってきてしまいます。 $5 + A$ も同様に 1 に戻りますね。
そのため、 $N = 6, A = 2$ のとき最大限辺を張っても２グループにしか分けられません。では、$N = 7, A = 2$ のときはどうでしょう？
結論から言うと、全部つなげることができます。以下のように $6 + A$ をしたときにズレてすべてが繋がります。
では、 $N, A$ が与えられたときに、 これが何個に分かれるか知りたいです。
ある $x$ を $A$ ずつずらしていったものが同じグループに属します。そして、最終的なグループ数は $\gcd(A, N)$ になります。
その最終的なグループ数にするための操作回数ですが、１回につき１つのノードをグループに加えることができるので、$N - \gcd(A, N)$ で求められます。
fn main() { input! { mut n : usize, m : usize, mut ac : [(usize, usize); m] } ac.sort_by_key(|&(_,c)| c); let mut ans = 0; for &(a, c) in ac.iter() { let gcd = gcd(n, a); if gcd >= n { continue } ans += c * (n - gcd); n = gcd; } println!("{}", match n { 1 => ans as i64, _ => -1, }); }
まとめ
バーチャル参加しました。 F は眠くて見ていません。
もう少しやる気が出たら ABC 復活します。
AtCoder Beginner Contest 205
はい． AtCoder Beginner Contest 205 です
ずっと書いてなかったので、その間にいろいろありました｡ 最近は Rust で競プロをしているので、 Rust で書いて行きます（特殊な書き方はしてないので多分読めるはず…）｡
当日は参加できなかったので、バーチャル参加をしました｡ ABCDE の5完でした｡ E は数式をガチャガチャしてたら通ったので、説明はできません… その後で F をやったら割とすんなり通せました｡
A - kcal
100mL で $A$ kcal なので、 1 mL あたりは 100 で割れば求まりますね｡ それが $B$ mL あるので それとかけたら答えです｡
fn main() { input! { a : f64, b : f64 } println!("{}", b * (a / 100.)); }
B - Permutation Check
ソートして、 $1, 2, \cdots, N$ と比較しても良いんですが、$1 \leq A _ i \leq N$ なので 並びかえて $1, 2, \cdots, N$ にできないは被りがあるときです｡
ソートして、重複削除してその長さを $N$ と比較したら良いです｡
fn main() { input! { n : usize, mut a : [i64; n] } a.sort(); a.dedup(); // 重複削除 println!("{}", if a.len() == n {"Yes"} else {"No"}); }
C - POW
まず、$A, B$ が正のときだけを考えます｡ $A ^ C$ と $B ^ C$ の肩に乗っている値は同じなので、 $A$ と $B$ の比較をしたら良いですね｡
では、負のときはどうでしょう｡
負数を奇数回かけると負、偶数回かけると正になるので、 の偶奇で場合分けをしたら良さそうです｡
$C$ が偶数のときは、 $A, B$ の絶対値を取ってあげると、そのまま比較できます｡
fn main() { input! { mut a : i64, mut b : i64, c : i64, } if c % 2 == 0 { a = a.abs(); b = b.abs(); } println!("{}", match a.cmp(&b) { Ordering::Equal => "=", Ordering::Less => "<", Ordering::Greater => ">" }); }
なんか $A ^ { C \% 2 + 2 }$ と $B ^ { C \% 2 + 2 }$ を比較する天才方法もあるみたいです｡
D - Kth Excluded
$A_i$ に含まれない正整数のうち、小さい方から $K$ 番目を直接求めるのは難しそうです｡ そこで、「$B$ 以下の値のうち、 $A_i$ に含まれない正整数はいくつありますか？」ということを考えます｡
これは、 $1$ から $B$ の $B$ 個の整数のうち、 $B$ 以下の $A_i$ の個数を引けばすぐに求められます（$A$ が並んでいるなら lower_bound などで効率的に求められます）｡
また、 $B$ を増やせば この個数は単調増加するので二分探索で個数が $K$ 個以下 になるギリギリの $B$ を探せば良さそうです｡
fn main() { input! { n : usize, q : usize, a : [i64; n], k : [i64; q] } for k in k { println!("{}", calc(&a, k)); } } fn calc(a : &Vec<i64>, k : i64) -> i64 { let mut l = -1; let mut r : i64 = 2_000_000_000_000_000_000; while l+1 < r { let m = (l+r) / 2; let index = a.lower_bound(&m) as i64; if k < (m - index) { r = m } else { l = m } } l }
E - White and Black Balls
数式をガチャガチャして、途中でカタラン数っぽいなとなって、カタラン数の求め方からガチャガチャしてたら通りました｡
説明できることはありません…
fn main() { input! { n : i64, m : i64, k : i64 } if n > m + k as i64 { println!("0"); return } const MOD : i64 = 1_000_000_007; let comb = Combination::new(2_500_000, MOD); let n = n as i64; let m = m as i64; let mut ans = comb.nCk(n+m, m) - comb.nCk(n+m, m+k+1) + MOD; println!("{}", ans % MOD); }
F - Grid and Tokens
あふれ出るフロー感を感じました｡ $i$ 番目の人の要望が2つあって、どこのマス目を使うかみたいなものを考えるとマッチングに見えます｡
$s$ を始点、 $t$ を終点として考察します｡
初期方針として、$r$ を取るパートを考えて、 s --> i --> r --> t のようなグラフを書きたくなったんですが、
s --> i --> r --> c --> t とはできないので、 「$i$ 番目の人」というのを間にいれる方針で考えます｡
s --> r --> i --> c --> t みたいなグラフにします｡$r$ と $c$ はそれぞれ、 $s, t$ に繋げば良いですね｡
そして、r --> i と i --> c は要望通りに繋ぎます｡
ただし、入る線と出る線が同じノードに入ると、 $i$ 番目の人を諦めたときに他の $r$ からの線（もしくは $c$ の線）も切らないといけなくなってしまうので、
頂点を増やして入と出を分けます｡
フローのライブラリは Rust で作ってなかったので、rust-lang-ja/ac-library-rs からお借りしました｡
fn main() { input! { h : usize, w : usize, n : usize, abcd : [(Usize1, Usize1, Usize1, Usize1); n] } let mut mf = MfGraph::new(450); let s = 440; let t = 441; for i in 0..h { mf.add_edge(s, i, 1); } for i in 0..w { mf.add_edge(h+i, t, 1); } for (id, &(a,b,c,d)) in abcd.iter().enumerate() { mf.add_edge(h + w + id, h + w + n + id, 1); for i in a..=c { mf.add_edge(i, h + w + id, 1); } for i in b..=d { mf.add_edge(h+w+n+id, h+i, 1); } } println!("{}", mf.flow(s, t)); }
まとめ
久しぶりに記事を書いたので雰囲気が思い出せませんでした｡
E,F はあんまり自信がないです｡間違ってたらごめんなさい｡
早く青になりたいです｡
AtCoder Beginner Contest 191
はい． AtCoder Beginner Contest 191 です
久しぶりにブログを書きます。
ABE の3完でした。 C は問題文の意味が理解できなかったです…
全部解き直ししたのでまとめておききます。
A - Vanishing Pitch
が、消えている
秒後から
秒後までの間に入っていたら打つことができません。
等速直線運動をするので、
秒後に進んでいる距離は、
ですね。
も同様に求められるので、適当に判定します。
int main() { int v, t, s, d; cin >> v >> t >> s >> d; if (v*t <= d && d <= v*s) { cout << "No" << endl; } else { cout << "Yes" << endl; } }
B - Remove It
と等しいものだけ出力しなければ良いです。
AtCoder のジャッジではスペースや改行を区別らしいので適当に
continue しても良いのですが、削除して出力してみました。
int main() { int n, x; cin >> n >> x; vector a(n, 0); for (int i=0; i<n; i++) cin >> a[i]; a.erase(remove_if(a.begin(), a.end(), [&](const int& a){return a==x;}), a.end()); for (int i=0; i<a.size(); i++) { cout << a[i] << (i+1==a.size()? "" : " "); } cout << endl; }
こんな感じでも通ります。
int main() { int n, x; cin >> n >> x; vector a(n, 0); for (int i=0; i<n; i++) cin >> a[i]; for (const auto& ai : a) { if (ai == x) continue; cout << ai << endl; } }
C - Digital Graffiti
本番中に問題文の意味が理解できませんでした… 本番中は凸多角形しか頭にありませんでした。凹多角形も含まれるんですね。
正方形をいくつか塗りつぶした図形があるので、それが何角形か判定してくださいというものです。
以下の図は8角形です。
角は尖っているところかへこんでいるところなので、以下のように 4マス見て黒が1つか3つの所を数えます。
向きが変わっても白い部分をベースに周りの4つを確かめたら良いので、全部探索します。
int main() { int h, w; cin >> h >> w; vector<string> s(h); for (int i=0; i<h; i++) cin >> s[i]; vector dx = { -1, 0, -1, 0}; vector dy = { -1, -1, 0, 0}; int ans = 0; for (int i=1; i<h; i++) { for (int j=1; j<w; j++) { int cnt = 0; for (int k=0; k<4; k++) { if (s[i+dy[k]][j+dx[k]] == '#') cnt++; } if (cnt == 1 || cnt == 3) ans++; } } cout << ans << endl; }
D - Circle Lattice Points
あの…難しくないですか？
本番中には、 x を（ループを回して）決め打ちして y 座標を上下求めたらその間にある整数の個数を求めることができるなーと考えていました。 しかし、円の方程式しか出てこなくてどうやって求めるんだ…ってなっていました。
x座標と円の半径が分かっているので、三平方の定理で求めるらしいです。 それが分かっていても、実装が大変… 誤差が大変なのでまず、全値を 10000 倍とかして計算します。 y座標を求めて、良い感じに整数に丸めなければなりません。苦手です。
int main() { long double tx, ty, tr; cin >> tx >> ty >> tr; long d = 10000; long x = round(tx * d); long y = round(ty * d); long r = round(tr * d); long xl = (x-r > 0)? (x-r+d-1)/d*d : (x-r)/d*d; long xu = (x+r < 0)? (x+r-d+1)/d*d : (x+r)/d*d; long ans = 0; for (long i=xl; i<=xu; i+=d) { long t = r*r - (x-i)*(x-i); long yd = sqrt(t) - 1; while ((yd+1)*(yd+1) <= t) yd++; long yu = (y+yd < 0)? (y+yd-d+1)/d : (y+yd)/d; long yl = (y-yd > 0)? (y-yd+d-1)/d : (y-yd)/d; if (yu < yl) continue; ans += abs(yu - yl) + 1; } cout << ans << endl; }
E - Come Back Quickly
癒やしですか…？こういうの好きです。
とかなり小さいので各頂点からダイクストラしても間に合いそうです。
ここである頂点i から出発して i に戻ってきたときの処理がめんどくさいんですが、距離を保存する配列を1つ余分に持っておいて、そこにためていけば良いです。
using P = pair<long, long>; vector<long> dijkstra(long n, long s, vector<vector<P>> g) { vector<long> d(n+1,INT_MAX); priority_queue<P, vector<P>,greater<>> q; q.emplace(0,s); d[s] = 0; while (! q.empty()) { const auto [cost, u] = q.top(); q.pop(); if (d[u] < cost) continue; for (auto [e, c] : g[u]) { if (e == s) { d[n] = min(d[n], d[u] + c); } else if (d[e] > d[u] + c) { d[e] = d[u] + c; q.emplace( d[e], e); } } } return d; } int main() { int n, m; cin >> n >> m; vector g(n, vector<P>()); for (int i=0; i<m; i++) { int a, b, c; cin >> a >> b >> c; a--; b--; g[a].emplace_back(b, c); } for (int i=0; i<n; i++) { const auto dist = dijkstra(n, i, g); if (dist[n] < INT_MAX) cout << dist[n] << endl; else cout << -1 << endl; } }
F - GCD or MIN
min を取るので、 の最小値以下の値じゃなければ、残らないということはすぐに分かったのですがその後どうするんだーとなりました。
gcd を取るため、残る候補としては の約数どれかです。
その約数を作れるかどうかは、その値を約数に持つ値同士の gcd を取ればその値を作れるか分かります。
そしてその約数を持つもの同士の gcd はどうやっても その約数未満にはならないです。
そこで、 の約数を求めつつ、同じ約数を持つ値と gcd を取って map などにためていきます。
そして map にある key と value が一致するものだけが、
から 1つ以上の要素を選んで gcd で作れる値です。
その値のうち min(A) 以下となるものを数えたら答えです。
int main() { int n; cin >> n; vector a(n, 0); for (int i=0; i<n; i++) cin >> a[i]; int amin = *min_element(a.begin(), a.end()); unordered_map<int, int> mp; for (const auto& ai : a) { for (int i=1; i*i<=ai; i++) { if (ai%i == 0) { mp[i] = mp[i]? gcd(mp[i], ai) : ai; mp[ai/i] = mp[ai/i]? gcd(mp[ai/i], ai) : ai; } } } long ans = 0; for (const auto& [i, j] : mp) if (i<=amin && i==j) ans++; cout << ans << endl; }
まとめ
この回は全完も狙えた気がするので、ちょっと残念です。 最近は ABC あんまり成績良くないので、全完狙えるような回はもっとがんばりたいですね。
レートは下がらなかったのでよし！
ABC174 F - Range Set Query
ABC174 に出たときに、 F だけ解けずに居たので復習。
解説AC → 考察し直し → AC しました。
問題
問題文
ある数列が与えられるので、その数列の 番目から
番目までの間にある数の種類数を答えて下さいという問題。
解説AC
考察してもよく分からなかったので、まずeditorial を見ました。がよく分からず…
次に、解説動画 を見ました。 同じ数同士の距離を考えて、2次元で平面走査するというのは分かったのですが、実装できるほど腑に落ちませんでした。
そこで、もう一度考察してみました。
考察
あるクエリ を考えるときに、
から右側のうち、現れる数を数えれば良いです。
そこで、数列 を後ろから良い感じに処理していけば良さそうです（
に注目して前からでも良いです）。
数列の長さと対応した配列を用意して、 までで、各数の一番左にある数だけに 1、重複していたら 0 を入れてその和を求めることで、数が何種類あるか数えることができます。
例えば、サンプル2の
2 5 6 5 2 1 7 9 7 2
という数列を考えます。後ろから考えていくので、以下のように重複（有効）判定を更新していきます。
まず、2 は最初なので、重複は無くて数える対象ですね。
次の7,9 も同様です。
そして、次の7 では既に7 があるので先に処理した7を0 にしておきます。
このとき、 のようなクエリを処理するときは、矢印の範囲の和を取れば良いです。
の範囲には 3 種類の数がありますね。
このように、後ろから配列の更新とその場所が左端になるクエリの処理を同時にやっていくと良い感じに処理できます。
もちろん配列で の和を愚直に取ると、計算量が大きくなってしまうため、セグ木やBITなどで処理します。そうすると、
で計算できます。
何度か修正して、ソースコードとしては以下のようになりました。
最初の提出はこんな感じ
using int64 = long long; using P = pair<int, int>; using TP = tuple<int, int, int>; class BIT { const int n; vector<int64> d; public: BIT(int _n=0) : n(_n), d(n+1, 0) {} void add(int i, const int64 x=1) { for (i++; i <= n; i += i&-i) d[i] += x; } int64 sum(int i) { int64 x = 0; for (i++; i; i -= i&-i) x += d[i]; return x; } }; int main() { int n, q; cin >> n >> q; vector c(n+1, 0); for (int i=1; i<=n; i++) cin >> c[i]; vector<TP> lr; lr.emplace_back(-1, -1, -1); for (int i=1; i<=q; i++) { int l, r; cin >> l >> r; lr.emplace_back(l, r, i); } sort(lr.begin(), lr.end()); unordered_map<int, int> pre; BIT bit(n+1); vector ans(q+1, -1); for (int i=n; i>=1; i--) { if (pre[c[i]] > 0) bit.add(pre[c[i]], -1); bit.add(i, 1); pre[c[i]] = i; while(get<0>(lr.back()) == i) { const auto [l, r, j] = lr.back(); lr.pop_back(); ans[j] = bit.sum(r); } } for (int i=1; i<=q; i++) cout << ans[i] << endl; }
感想
典型らしく、Diffも水とすごく高いわけじゃなかったんですが 難しくないですか…？
