https://projecteuler.net/problem=12ふつうに三角数を素因数分解しても十分速いです。 しかし、素因数分解の指数だけで約数の個数は決まるので、約数の個数が条件より大きい指数だけ考えれば速いです。 素因数分解を とすると、約数の個数は、 となります。…

https://atcoder.jp/contests/abc335/tasks/abc335_gとなる最小のpをaの周期と呼ぶことにします。 だから、周期はP-1の約数になります。なので、P-1から割っていって1になる最小の約数を求めればよいですが、もうちょっと効率のよい方法がある気がするんです…

https://atcoder.jp/contests/abc335/tasks/abc335_e繋がっている同じ値のノードは結合してグラフにします。そうすればあとはDPになります。 // Non-Decreasing Colorful Path #![allow(non_snake_case)] use std::cmp::max; use std::collections::HashMap;…

https://atcoder.jp/contests/abc335/tasks/abc335_d例にあるようにらせん状にたどればよいです。 // Loong and Takahashi #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); s</t:>…

https://atcoder.jp/contests/typical90/tasks/typical90_qある線分に対し、Lが小さい線分でその線分が交わるものを数えます。その線分をとすると、となります。線分の集合(L, R)をLでソートします。そうして、BITを用意してに1を加えていきます。そして、そ…

https://projecteuler.net/problem=11どうもグローバルで定数を定義するのができないみたいで、mainの中にstr_tableを書いたらうまくいきました。 あとは、splitも使えてそんなに難しくないです。 from math import max import sys struct Matrix: var a: Dy…

https://atcoder.jp/contests/typical90/tasks/typical90_pA, B, Cの中で一番大きいものが何個使うか固定して、残りで一番少ない個数を調べます。 // Gravy Jobs #![allow(non_snake_case)] use std::cmp::min; //////////////////// library //////////////…

https://projecteuler.net/problem=10エラトステネスの篩をするだけですね。 from math import max, sqrt import sys fn make_prime_table(N: Int) -> DynamicVector[Int]: let a = DTypePointer[DType.bool].alloc(N+1) for i in range(N+1): a.store(i, Tr…

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辺の間隔（＝長さ）を一定とすると、辺をずらすとどこかで移動量の最小値がありますが、片方の辺を端からずらしていくと移動量が下に凸になるので、両方の辺を合わせても下に凸になります。なので、領域を…

https://atcoder.jp/contests/abc330/tasks/abc330_e連続する範囲を葉にする木を作ればいいですが、実装が大変です。ですが、範囲にOrderingの各Traitを実装すればBTreeSetを使えます。範囲が重なれば等しい、そうでなければ大小ということにします。 // Cou…

https://atcoder.jp/contests/abc330/tasks/abc330_d縦横でoの数を数えておきます。 // Counting Ls #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_</t:>…

https://atcoder.jp/contests/typical90/tasks/typical90_l典型的なUnion-Findを使う問題ですね。 色々な型に対応できるようにUnion-Findの構造体を頑張って書いてみました。 // Gravy Jobs #![allow(non_snake_case)] use std::collections::HashMap; use s…

https://projecteuler.net/problem=6べた書きするだけですね。 # e006.mojo import sys fn f(N: Int) -> Int: var s = 0 var s2 = 0 for n in range(1, N+1): s += n s2 += n*n return s*s - s2 fn main() raises: let args = sys.argv() let N = atol(args[…

https://atcoder.jp/contests/typical90/tasks/typical90_k単なるDPですが、よくあるパターンで終わりの日でソートします。 // Gravy Jobs #![allow(non_snake_case)] use std::cmp::max; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T</t:>…

https://projecteuler.net/problem=5gcdが使えますね。 # e005.mojo from math import gcd import sys fn lcm(n: Int, m: Int) -> Int: return n // gcd(n, m) * m fn f(N: Int) -> Int: var m: Int = 1 for n in range(1, N+1): m = lcm(m, n) return m fn …