https://atcoder.jp/contests/typical90/tasks/typical90_oこれは、アルゴリズムと数学 101と同じ問題です。

https://projecteuler.net/problem=9直角三角形の各辺の長さは、 と表せて、周囲の長さLは、となるので、L/2を3つの整数の積にすれば簡単にl, m, nを求められます。ただ、一般的には2つの約数に分解して、片方をさらに2つの約数に分解しますが、そうすると分…

https://atcoder.jp/contests/typical90/tasks/typical90_n小学生と通う小学校を同じ並びにすればよいです。 // We Used to Sing a Song Together #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut l</t:>…

https://atcoder.jp/contests/abc334/tasks/abc334_fDPですが、状態が今いる位置と持っているプレゼント数なので、状態数がO(NK)なので間に合いません。しかし、スタートに戻る以外は次に移るので同じ値を足すだけです。また、スタートに戻るのは各状態から…

https://atcoder.jp/contests/abc334/tasks/abc334_dRをソートして累積和を求めておいて二分探索ですね。 // Reindeer and Sleigh #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::n</t:>…

https://projecteuler.net/problem=8毎回13個の数字を掛け算すればよいですが、もう少し頑張れば計算量を減らせます。0が13個の間に何個あるのかと最後の0のあと積を記憶しておけばよいです。 # e008.mojo import sys struct ProductGenerator: var L: Int v…

https://atcoder.jp/contests/typical90/tasks/typical90_m1とNと両方からダイクストラをやればよいです。 // Passing #![allow(non_snake_case)] use std::collections::BinaryHeap; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { l</t:>…

https://atcoder.jp/contests/abc333/tasks/abc333_g分母がN以下で実数rに最も近い分数を最良近似と言います。これは連分数と結びついています。 例えば、0.45を連分数で表すと、 となります。これは次のように求められます。 の逆数を取るとで、この整数部…

https://atcoder.jp/contests/abc333/tasks/abc333_fN個の中でiが最後まで残る確率をと書くと、1回動かすと、なので、最初の式のに最後の式を代入して、という処理を次々していけば、となるので、が求まって、他の確率も求まります。 // Takahashi Quest #![…

https://atcoder.jp/contests/abc333/tasks/abc333_eタイプが違うと独立に考えられます。タイプトごとに、逆向きに、符号も逆にして考えます。トータルで負になるときだけ、パスします。 // Takahashi Quest #![allow(non_snake_case)] use std::cmp::max; /…

https://atcoder.jp/contests/abc333/tasks/abc333_d1を含むエッジを除いてUnion-Findを構築します。そうしたとき、一番点の数の大きな木以外を足すと求める値になります。 // Erase Leaves #![allow(non_snake_case)] use std::cmp::max; /////////////////…

https://atcoder.jp/contests/abc332/tasks/abc332_d行と列の順列は独立なので、それぞれの順列と隣同士の互換がどれだけ要るかを計算しておけば、あとはしらみつぶしです。 // Swapping Puzzle #![allow(non_snake_case)] use std::collections::{HashMap, …

https://atcoder.jp/contests/abc331/tasks/abc331_ePriorityQueueを使って、合計が多い組み合わせから列挙していきます。 // Set Meal #![allow(non_snake_case)] use std::collections::{BinaryHeap, HashSet}; //////////////////// library ////////////…

https://atcoder.jp/contests/abc331/tasks/abc331_d二次元累積和を使うと高速にエリア内の黒の個数を求めることができます。 // Tile Pattern #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line</t:>…

https://projecteuler.net/problem=7配列にはいろいろな種類があるようです。ここでは2種類を使います。 Pointerはallocateして最後にfreeするというCで領域確保するのと同じものです。恐ろしいですね。 DynamicVectorはpush_backして要素を追加できるので、…

https://atcoder.jp/contests/abc330/tasks/abc330_f辺の間隔（＝長さ）を一定とすると、辺をずらすとどこかで移動量の最小値がありますが、片方の辺を端からずらしていくと移動量が下に凸になるので、両方の辺を合わせても下に凸になります。なので、領域を…