https://atcoder.jp/contests/abc373/tasks/abc373_d有向グラフですが、逆方向に符号が反対の重みを持ったエッジを張って、適当に辿ればよいです。 // Hidden Weights #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr></t:>…

https://projecteuler.net/problem=69 とすると、 となって、これが一番大きいので、要はN以上になるまで素数を小さい順に掛けていくだけです。 import sys fn is_prime(n: Int) -> Bool: var p = 2 while True: if p * p > n: return True elif n % p == 0:…

https://projecteuler.net/problem=68しらみつぶしすればいいですが、ちょっとややこしいですね。 import sys #################### List #################### fn initialize_list[T: CollectionElement](N: Int, init: T) -> List[T]: var a = List[T](cap…

https://projecteuler.net/problem=67単なるDPですね。 import sys #################### library #################### fn read_csv(path: String, delim: String) -> List[List[Int]]: try: var table = List[List[Int]]() with open(path, "r") as f: var…

https://atcoder.jp/contests/abc372/tasks/abc372_djより左で最も右のHjより高いビルの位置を探せばよいです。そういう木を作ります。 // Buildings #![allow(non_snake_case)] use std::cmp::max; //////////////////// library //////////////////// fn r…

https://projecteuler.net/problem=66Pell方程式は連分数と密接に関連しています。Pell方程式の解はの連分数を途中で打ち切った分数の分子と分母になっています。なので、漸化式で分子と分母を求めて、それがPell方程式の解になっていればそれが最小解です。…

https://projecteuler.net/problem=65連分数の係数fに対して、連分数を途中で打ち切って通常の分数にしたとき、例えば、としたとき、その手前で打ち切ったときは、さらにその手前で打ち切ったときはとなりますが、それぞれの分子分母をとすると、 と計算でき…

https://projecteuler.net/problem=64平方根の連分数の周期は、たぶん具体的に計算するしかないです。 まず、とすると少し見通しがよくなります。 の逆数を取ると、となります。なので、の場合に限り、周期1になります。 この整数部分がfだとすると、整数を…

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:>…