https://atcoder.jp/contests/abc371/tasks/abc371_e和を二重に取っている問題は和を取る順番を入れ替えるのが定番ですが、この二重和は対等なので、そこじゃないです。ある値を含む範囲がいくつあるかを数えます。ある値がp番目のみなら、かつだから、その…

https://atcoder.jp/contests/abc371/tasks/abc371_dソートして累積和を取って二分探索ですね。 // 1D Country #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::std</t:>…

https://projecteuler.net/problem=63素直に書くとオーバーフローしてしまうので、logを使ってごまかします。 整数と浮動小数点数の変換は、Float64とintを使います。 from math import log10 #################### process #################### fn f() -> …

https://projecteuler.net/problem=62数字をソートして同じ数になるものを集めます。ただし、昇順だと0があると桁数がわからなくなるので、降順にソートして整数に直します。 import sys #################### library #################### fn digits(owned…

https://atcoder.jp/contests/abc370/tasks/abc370_dどの壁を爆破するかを素早く決めて、どの壁が壊れているかの情報をアップデートするために、二分木を使いたいです。縦と横でそれぞれ二分木を使います。 RustならBTreeSetで、[first, last)の範囲が壁か否…

https://projecteuler.net/problem=61三角数から辿っていけばよいです。 import sys #################### List #################### fn initialize_list[T: CollectionElement](N: Int, init: T) -> List[T]: var a = List[T](capacity=N) for n in range(…

https://projecteuler.net/problem=60各エッジについて、両端と共通のノードを探して、ということを繰り返して完全グラフを作ります。 しかし、Graphを alias Node = Int struct Graph: var g: Dict[Node, Set[Node]] としようとしても、SetがCollectionElem…

https://atcoder.jp/contests/abc369/tasks/abc369_eワーシャルフロイド法で各ノード間の最短距離を求めておいて、クエリーの端を並び替えてその中でDPで橋の両端を入れ替えて最短距離を求めます。 // Bonus EXP #![allow(non_snake_case)] use std::collect…

https://atcoder.jp/contests/abc369/tasks/abc369_d単なるDPです。 // Bonus EXP #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mut line).o</t:>…

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つの数が等差数列になるか…

https://atcoder.jp/contests/abc364/tasks/abc364_e計算量が多そうですが、xが小さいほうから見ていって、yが小さくならないものは捨てられるので、意外とたくさん捨てられるようです。 // Maximum Glutton #![allow(non_snake_case)] ////////////////////…

https://projecteuler.net/problem=48そのままですね。 import sys #################### library #################### fn add(a: Int, b: Int, d: Int) -> Int: var c = a + b if c < 0: # overflow c -= d elif c >= d: c -= d return c fn mul2(a: Int, …

https://projecteuler.net/problem=474つの異なる素数からなる連続する4つの自然数を見つけるなら、4つの異なる素数からなる自然数を昇順に生成すればよさそうですが、4つ並んでいるとなるとそれなりにそういう自然数の密度が高くなって、あまり速くなりませ…

https://atcoder.jp/contests/abc363/tasks/abc363_f分割を全部出してそこから題意に合うものを出力すればいいと思ったのですが、それでは間に合わず、それなりに絞って行かないといけないです。 // Palindromic Expression #![allow(non_snake_case)] /////…