アルゴリズムと数学 013

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_mナイーブに素因数分解して、あとは分割統治法的に約数を列挙します。 // Divisor Enumeration #![allow(non_snake_case)] //////////////////// library //////////////////// fn…

アルゴリズムと数学 012

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_lミラー・ラビンを実装する余裕がないので、2から割っておきます。 // Primality Test #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() </t:>…

アルゴリズムと数学 007

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_g包除原理ですね。これを使うために最小公倍数が要ります。 // Number of Multiples 1 #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() </t:>…

AtCoder Beginner Contest 286 D

https://atcoder.jp/contests/abc286/tasks/abc286_d和を状態としたDPですね。 // Money in Hand #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_lin</t:>…

アルゴリズムと数学 004

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_d整数を3つではなく一般化しました。積にsumのようなものはないですが、foldが使えますね。 // Product of 3 Integers #![allow(non_snake_case)] //////////////////// library /…

アルゴリズムと数学 003

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_cVecはIteratorにするとsumが使えます。 // Sum of N Integers #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = </t:>…

アルゴリズムと数学 001

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_aこれから、アルゴリズムと数学 演習問題集を解いていきます。https://atcoder.jp/contests/math-and-algorithm // Print 5+N #![allow(non_snake_case)] //////////////////// li…

AtCoder Beginner Contest 285 D

https://atcoder.jp/contests/abc285/tasks/abc285_d(S, T)をエッジとしてグラフにします。それがループを含まないか調べます。少し前に連結成分に分けるコードを書いたので、連結成分に分けて、それぞれの成分が木になっているかを調べます。 // Change Use…

AtCoder Beginner Contest 265 D

https://atcoder.jp/contests/abc265/tasks/abc265_d各解はしゃくとり法で求められるので、その解をたどっていきます。 // Iroha and Haiku (New ABC Edition) #![allow(non_snake_case)] use std::collections::HashMap; //////////////////// library ////…

AtCoder Beginner Contest 266 D

https://atcoder.jp/contests/abc266/tasks/abc266_d各すぬけ君が現れる時刻に各穴での最大値を記憶していけばよいですね。 穴の数が固定なので、ここでは配列を使っています。 定数はこんな感じに定義します。 const M: usize = 5; 配列はこう初期化します…

AtCoder Beginner Contest 267 D

https://atcoder.jp/contests/abc267/tasks/abc267_d各Aに対して部分列の長さごとに最大値を求めればよいです。 // Index × A(Not Continuous ver.) #![allow(non_snake_case)] use std::cmp::{min, max}; //////////////////// library ///////////////////…

AtCoder Beginner Contest 284 D

https://atcoder.jp/contests/abc284/tasks/abc284_dまでにpかqのどちらかで割り切れます。 qで割り切れたら、を計算します。の計算はニュートン法的に、 , を収束するまで繰り返します。 // Happy New Year 2023 #![allow(non_snake_case)] ///////////////…

AtCoder Beginner Contest 268 D

https://atcoder.jp/contests/abc268/tasks/abc268_dSの間にアンダースコアを挟みますが、例えば、Sが4個で合わせて11文字だったら、最大5個のアンダースコアを3つに分配することになります。これは意外と簡単です。最初は、 1 1 1これに1ずつ加えていけばよ…

AtCoder Beginner Contest 269 D

https://atcoder.jp/contests/abc269/tasks/abc269_dグラフを連結成分に分けます。グラフの表現にはHashMapを使います。Vecでも表せるのですが、連結成分に分けるとなると効率が悪くなります。実際には分ける必要は無いのですが、後で使うために分けるコード…

AtCoder Beginner Contest 270 D

https://atcoder.jp/contests/abc270/tasks/abc270_d残りの石の数に対して、どちらも最善を尽くしたとき、先番がいくつ取れるかをDPにします。 ふつうにtake_whileが使えますね。 // Stones #![allow(non_snake_case)] //////////////////// library ///////…

AtCoder Beginner Contest 271 D

https://atcoder.jp/contests/abc271/tasks/abc271_dカードの組と和でDPすればいいです。この時、1歩前の和を記録しておくとDPが終わった後にtrace backできて文字列を作ることができます。 後ろから追加していくので、あとから逆順の文字列にします。 // Fl…

AtCoder Beginner Contest 282 D

https://atcoder.jp/contests/abc282/tasks/abc282_d連結成分に分けて、隣り合うノードを白と黒に塗り分けます。塗り分けられなかったら二部グラフではありません。そして、連結成分の中と連結成分の間にエッジをいくつ作れるかを数えます。 // Make Biparti…

AtCoder Beginner Contest 276 D

https://atcoder.jp/contests/abc276/tasks/abc276_dAのgcdにAの各要素が何回割ってたどり着くかをカウントします。 reduceって無いんですね。foldだとgcdはちょっと面倒ですよね。 // Divide by 2 or 3 #![allow(non_snake_case)] fn read<T: std::str::FromStr>() -> T { let mut</t:>…

AtCoder Beginner Contest 277 D

https://atcoder.jp/contests/abc277/tasks/abc277_dAをソートして、グループ化します。あとは最初と最後がくっつくかですね。 // Takahashi's Solitaire #![allow(non_snake_case)] fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_</t:>…

AtCoder Beginner Contest 281 D

https://atcoder.jp/contests/abc281/tasks/abc281_dキーが個数と和のDの剰余、値を和の最大値とするDPですね。 // All Assign Point Add #![allow(non_snake_case)] use std::collections::HashMap; fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::i</t:>…

AtCoder Beginner Contest 278 D

https://atcoder.jp/contests/abc278/tasks/abc278_dHashMapを使えば簡単ですね。 // All Assign Point Add #![allow(non_snake_case)] use std::collections::HashMap; fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mut li</t:>…

AtCoder Beginner Contest 279 D(2)

https://atcoder.jp/contests/abc279/tasks/abc279_d微分を使わなくても、3点の区間を倍々にしていって、3点の中で真ん中が一番時間が短ければ、そこから真ん中が一番時間が短い状態をキープしつつ区間を縮小していきます。 // Freefall #![allow(non_snake_…

AtCoder Beginner Contest 279 D

https://atcoder.jp/contests/abc279/tasks/abc279_d微分して0になる点から、前後を調べます。ただし、1より小さくなってはいけません。 // Freefall #![allow(non_snake_case)] fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line</t:>…

AtCoder Beginner Contest 280 D

https://atcoder.jp/contests/abc280/tasks/abc280_d素因数分解すれば、あとは素数ごとに計算すればよいですね。 素数ごとに条件を満たす最小の倍数を求める部分はもっと効率のいい方法があると思いますが、素因数分解に比べれば十分に速いですね。 // Facto…

AtCoder Beginner Contest 272 D(2)

https://atcoder.jp/contests/abc272/tasks/abc272_d素因数分解さえできれば、移動できるステップを高速に求められます。そのために、GaussIntという構造体を作りました。 デバッグのためにfmtというメソッドを作って複素数を出力できるようにしましたが、そ…

AtCoder Beginner Contest 272 D

https://atcoder.jp/contests/abc272/tasks/abc272_dどこへ進めるかはナイーブに実装しても十分に間に合いますね。 何歩で行けるかはQueueを使えばよいですが、RustではVecDequeというcollectionを使うようです。 // Root M Leaper #![allow(non_snake_case)…

AtCoder Beginner Contest 273 D

https://atcoder.jp/contests/abc273/tasks/abc273_dこれも行と列で分けて考えることができます。 壁の座標を各行、各列で格納します。 その際に二分探索をするのでソートしますが、HashMapの中のVecをどうソートしていいのか分からなかったので、新たにHash…

AtCoder Beginner Contest 274 D

https://atcoder.jp/contests/abc274/tasks/abc274_dx軸とy軸で分けて考えればよいです。 あと、flattenがちゃんとあるんですね。 // Robot Arms 2 #![allow(non_snake_case)] use std::collections::HashSet; fn read<T: std::str::FromStr>() -> T { let mut line = String::new(</t:>…

AtCoder Beginner Contest 275 D(3)

https://atcoder.jp/contests/abc275/tasks/abc275_dmemoizeというcrateを使えば簡単です。 ただ、AtCoderでは使えないようです。 // Yet Another Recursive Function #![allow(non_snake_case)] use memoize::memoize; fn read<T: std::str::FromStr>() -> T { let mut line = Str</t:>…

AtCoder Beginner Contest 275 D(2)

https://atcoder.jp/contests/abc275/tasks/abc275_d構造体にメモを置けばそんなに気持ち悪くないと思います。 // Yet Another Recursive Function #![allow(non_snake_case)] use std::collections::HashMap; fn read<T: std::str::FromStr>() -> T { let mut line = String::new(</t:>…