2023-03-01から1ヶ月間の記事一覧

アルゴリズムと数学 042

https://atcoder.jp/contests/math-and-algorithm/tasks/abc172_dよくある和の順番を変えるやつですね。約数の問題では特に多いです。とおくと、とおくと、となります。 これでも十分速いですが、dが大きいところではが同じものが多いので、これをまとめると…

アルゴリズムと数学 041

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_al出勤時間と退勤時間をマージしてソートしておくと、そのあとは線形時間で時刻ごとの人数が得られます。 // Convenience Store 2 #![allow(non_snake_case)] ///////////////////…

アルゴリズムと数学 040

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_ak西の端から累積の距離を計算しておくだけですね。 // Travel #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = </t:>…

アルゴリズムと数学 039(2)

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_ajふつうに二分木を作ろうと思って書いたものの、コンパイラが通らずに苦労していたのですが、Bingに書かせてみたらちょっと違うものができてきたもののコンパイラが通るので、こ…

AtCoder Beginner Contest 295 D

https://atcoder.jp/contests/abc295/tasks/abc295_d左から見ていって、各数字の出現回数の偶奇が同じなら、その区間は各数字が偶数回出現していることになります。 // Three Days Ago #![allow(non_snake_case)] //////////////////// library ////////////…

アルゴリズムと数学 039

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_ajセグメント木を使うとVecの操作だけで済むので簡単ですね。 // Snowy Days #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { le</t:>…

AtCoder Beginner Contest 294 D

https://atcoder.jp/contests/abc294/tasks/abc294_dBTreeSetを使えば簡単で、呼ばれていない人のsetと呼ばれたけど受付に行っていない人のsetを作ればよいです。 ただ、 let e = not_called.iter().next().unwrap(); not_called.remove(e); だとcannot borr…

AtCoder Beginner Contest 293 D

https://atcoder.jp/contests/abc293/tasks/abc293_dグラフを作って隣接ノードが2つずつあればループになっています。 ただ、問題なのはノードが2つの連結成分です。1と2を連結すると、 {1: [2], 2: [1]}となりますが、反対側を結んだ時に強引に、 {1: [2, 2…

アルゴリズムと数学 038

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_aiあらかじめ累積を計算しておくだけですね。 // How Many Guests? #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut lin</t:>…

アルゴリズムと数学 037

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_ahなかなか通らなくて、仕方なくPythonで書いたらあっさり通って、それをまねしてみた。 2つの線分が平行なら、4点が同一直線上になければならなくて、それを射影して領域が重なっ…

AtCoder Beginner Contest 292 D

https://atcoder.jp/contests/abc292/tasks/abc292_dグラフを連結成分に分解します。 このときグラフをHashMap>で表すと、Vecの要素数がエッジの数の2倍になるのですが、自分へのエッジは二重に数えていないので、その分をカウントしないといけません。 // U…

AtCoder Beginner Contest 291 D

https://atcoder.jp/contests/abc291/tasks/abc291_d単なるDPですね。 ギリギリi32で足ります。 // Flip Cards #![allow(non_snake_case)] const D: i32 = 998244353; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = S</t:>…