https://atcoder.jp/contests/abc368/tasks/abc368_dエッジからグラフを作って、それを木にして、ルートから辿ります。Vにあるノードをルートにすると間違いが無いです。 // Minimum Steiner Tree #![allow(non_snake_case)] use std::collections::HashSet;…

https://projecteuler.net/problem=59何を言っているのかわからない問題文ですが、キーが3文字と言っているので、キーがABCなら、1文字目と4文字目と…はAがキーで、2文字目と5文字目と…はBがキーで、などとなるのでしょう。そして、各グループで一番多いコー…

https://projecteuler.net/problem=58右上が、左上が、左下がなので、と同じようなやり方で篩が使えます。 0.1だと一瞬ですが、この割合が小さくなると急速に時間がかかるようになり、0.06でも4秒くらいでした。 import sys #################### process ##…

https://atcoder.jp/contests/abc367/tasks/abc367_d累積和を計算して、Mの剰余が同じ位置を集めます。そしてその位置の集まりで差がN以下の個数をカウントします。そのとき、その集まりが大きくなる可能性がありますが、尺取り法的に計算すれば速くなります…

https://projecteuler.net/problem=57分子と分母は と漸化式で表されます。 厳密には多倍長整数使いますが、実数でも問題ないです。分子が10を超えたら両方10で割ればよいです。 import sys #################### BigInteger #################### @value st…

https://projecteuler.net/problem=56掛け算していくしかないですね。 import sys #################### List #################### fn sum_list(a: List[Int]) -> Int: var s = 0 for e in a: s += e[] return s #################### process ############…

https://projecteuler.net/problem=55そのままですね。 import sys #################### library #################### fn digits(owned n: Int) -> List[Int]: var ds = List[Int]() while n > 0: var d = n % 10 ds.append(d) n //= 10 return ds fn reve…

https://atcoder.jp/contests/abc366/tasks/abc366_eこれも累積和を使います。 x方向とy方向は分解できるので、それぞれで計算して、あとで統合します。 はxとなる座標の個数 とすると、 xでのx方向の距離の和は、 なら、 なら、 なら、 となります。 x方向…

https://atcoder.jp/contests/abc366/tasks/abc366_d を計算しておけば包除原理で求められますが、このPを求めるときも包除原理を使います。 // Cuboid Sum Query #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -</t:>…

https://projecteuler.net/problem=54各役をC++のように基底クラスを継承したいのですが、どうやったらいいのでしょうね。同じくTraitを使うRustは頑張れば同じVecに入れられるのですが、MojoだとListに入れられるのでしょうか。 import sys ###############…

https://projecteuler.net/problem=53nに対して1000000を超える最小のrとそのときのコンビネーションの値を記憶しておけば、n+1に対するrをO(1)で計算できます。 import sys #################### process #################### fn greater_limit(n: Int, pr…

https://projecteuler.net/problem=52各数字が何個あるかを4ビットで表します。 import sys #################### process #################### fn count_digits(owned n: Int) -> Int: var c = 0 while n > 0: var d = n % 10 c += 1 << (d * 4) n //= 10 …

https://projecteuler.net/problem=51素数が8つ以上だと、マスクしている数字は3の倍数個でないといけません。なぜなら、そうでなければ数字ごとに3の剰余が変わってしまうから、最大10個できる整数のうち3個は3の倍数になってしまうからです。 素数9つはす…

https://atcoder.jp/contests/abc365/tasks/abc365_e三重和になっていて、累積和を使っても二重和になっていて間に合いませんが、XORなのでビットごとに計算すれば間に合います。 入力例1の1 3 2を二進数で表すと、 01 11 10なので、ビットごとにみると、 1 …

https://atcoder.jp/contests/abc365/tasks/abc365_d単なるDPですね。 // AtCoder Janken 3 #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mu</t:>…

https://projecteuler.net/problem=50和のインデックスと[first, last)で表し、さらにその素数の和をStateとします。そのとき、@valueというdecoratorを付ければ、フィールドだけ書けばCollectionElementを実装したことになります。 HeapQueueはComparableCo…

https://projecteuler.net/problem=4910進で表した数字をソートした数をキーに素数を集めます。ただし降順に並べます。例えば、1320なら3210です。昇順だと123になってしまい違う桁の数も同じキーになってしまいます。 問題なのは4つの数が等差数列になるか…