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)] /////…

https://atcoder.jp/contests/abc363/tasks/abc363_d桁数を指定すれば、その中で何番目の回文数は何かわかります。 オーバーフローの問題はi128を使えばよいです。 // Palindromic Number #![allow(non_snake_case)] //////////////////// library /////////…

https://projecteuler.net/problem=46自然数nに対し、が素数なのか調べます。素数のSetを作っておけばいいのですが、答えがNなら、計算量はくらいなので、計算量をくらいに抑えたければ600000くらいまで素数を作っておけばよいです。 import sys ###########…

https://projecteuler.net/problem=45とします。まずは簡単で、 両辺を8倍して1を足すと、 だから、 です。 は、 両辺を24倍して3を足すと、 とおくと、 となって、これはPell方程式を拡張したものです。 この解は、 と書けます。 import sys fn f() -> Int:…

https://projecteuler.net/problem=44とすると、 両辺を24倍して2を足すと、 とすると、 だから、ふるいで素因数分解をしておいて、xの小さいほうから(x-1)(x+1)を素因数分解を求めます。そうすると約数が簡単に求められるので、そのときに、yとzが6で割って…

https://projecteuler.net/problem=43素数が大きいほうから絞るとよいと思います。 import sys #################### library #################### fn digits(owned n: Int, m: Int) -> List[Int]: var ds = List[Int]() for _ in range(m): var d = n % 10…

https://atcoder.jp/contests/abc362/tasks/abc362_eDPです。状態は(次の値, 公差, 長さ)、値は頻度にすればよいですが、次の値ですぐに検索できるようにHashMapのキーを次の値にしておきます。 // Count Arithmetic Subsequences #![allow(non_snake_case)]…

https://atcoder.jp/contests/abc362/tasks/abc362_dほぼダイクストラ法ですね。 // Shortest Path 3 #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read</t:>…

https://projecteuler.net/problem=42String.splitあるんですね。前からありましたかね。 import sys #################### library #################### #################### process #################### fn get_words(data: String) raises -> List[St…

https://projecteuler.net/problem=41nが9でも8でも1～nのpandigitalは9で割り切れるから、n=7を考えればよいので、107までエラトステネスの篩をして、上からpandigitalで素数のものを探せばよいです。 ただ、一般の進法を考えると、Millar-Rabinを使えばよ…

https://projecteuler.net/problem=40nが何桁のところにあるか分かればかんたんですね。 import sys #################### library #################### fn digits(owned n: Int) -> List[Int]: var ds = List[Int]() while n > 0: var d = n % 10 n //= 10…

https://projecteuler.net/problem=39直角三角形の各辺は なので、となります。なので、約数が多い方が同じpで違う(k, m, n)の組が多そうです。ただ、そんなに簡単ではありません。 まず、m+nは奇数です。mは奇数でも偶数でも可能ですが、を満たさなければな…

https://atcoder.jp/contests/abc361/tasks/abc361_fこれは昔からよく見る問題です。 として、2乗で表せる整数は、3乗で表せる整数はなどとなります。しかし、例えばなどと重複するのでそのまま数えてはいけないです。そこで底をべき乗で表されないものに限…

https://atcoder.jp/contests/abc361/tasks/abc361_e端点から端点に移動するとき、横道は2回エッジを通りますがそうでない経路は1回しか通らないので、木の直径を求めればよいです。 // Tree and Hamilton Path 2 #![allow(non_snake_case)] ///////////////…

https://atcoder.jp/contests/abc361/tasks/abc361_d各マスはWかBか空なので2ビットで表されます。あとはしらみつぶしで。 // Go Stone Puzzle #![allow(non_snake_case)] use std::collections::{VecDeque, HashSet}; //////////////////// library ///////…

https://atcoder.jp/contests/abc360/tasks/abc360_e例えばN=3で考えると、1から2に移動する確率は2/9で、1から1に移動する確率は1-2/9*2=5/9です。一般には、ある位置から他に移動する確率は、で、同じところにとどまる確率はとなります。なので、1回での状…