2023-01-02 ABC266 の F と ABC154 の A, B, C, D を解いた
ABC266 : AtCoder Beginner Contest 266 の F を解いた。
- F - Well-defined Path Queries on a Namori
https://atcoder.jp/contests/abc266/tasks/abc266_f
- 提出: https://atcoder.jp/contests/abc266/submissions/37675514
- 解説 AC
- N 頂点 N 辺の連結な単純無向グラフは、木に 1 つ辺を足したもの (なもりグラフ)
- 閉路が 1 個あり、その中の頂点から「足」 (木) が生えている構造
- ひとつの「足」の中の頂点 2 つならパスは 1 つ (Yes) 、そうでなければ閉路を通るので複数 (No) になる
- 辺の数 (次数) が 1 個の頂点から辺をたどって、たどった辺は削除し、辺を削除した頂点の辺の数が 1 個になれば……と続ける
- たどりながら Union-Find (Dsu) で連結して同じグループにしていく (「足」でまとめる)
- 各クエリに対して Union-Find で同じグループかを判定する
ABC154 : AtCoder Beginner Contest 154 の A, B, C, D を解いた。
- A - Remaining Balls
https://atcoder.jp/contests/abc154/tasks/abc154_a
- 提出: https://atcoder.jp/contests/abc154/submissions/37696630
UがSとTのどちらかを判定して一致する側 (AorB) を -1 する
- B - I miss you...
https://atcoder.jp/contests/abc154/tasks/abc154_b
- 提出: https://atcoder.jp/contests/abc154/submissions/37696639
"x".repeat(s.len())
- C - Distinct or Not
https://atcoder.jp/contests/abc154/tasks/abc154_c
- 提出: https://atcoder.jp/contests/abc154/submissions/37696664
a.iter().copied().collect::<HashSet<usize>>().len() == a.len()
- D - Dice in Line
https://atcoder.jp/contests/abc154/tasks/abc154_d
- 提出: https://atcoder.jp/contests/abc154/submissions/37696897
- 期待値が最大になる開始位置を調べる
- 連続する K 個の区間の
p_iの和が大きい箇所を探す - 繰り返して求めると間に合わないが連続しているので右端の p_l を引いて p_r を足してそこまでの最大を超えているかを確かめれば良い
- 期待値は 1 から p_i の等差数列の和を p_i で割ったものの総和を取れば良い
今日のコミット。