https://atcoder.jp/contests/abc351/tasks/abc351_e基本的には座標でソートして累積和を取っておけば計算できます。ただ、斜めの座標に変換しておかなければならないです。 // Jump Distance Sum #![allow(non_snake_case)] //////////////////// library /…

https://projecteuler.net/problem=31この問題は母関数が使えます。具体的にはNにする方法の数を求めるとすると、 ここでpは1, 2, 5, ..., 200を取ります。もっと具体的に書くと、 例えば、3にする方法は、1を3枚か1と2を1枚ずつですが、 母関数をこう書くと…

https://projecteuler.net/problem=31合計Nに対して、使える硬貨をN以下で最上位桁が1, 2, 5となるものすべてと問題拡張しています。また、すぐに結果が大きくなるので、適当な数の剰余を答えにしています。 1pだけ使ったとき各金額で何通りあるか、2pを追加…

https://projecteuler.net/problem=302から順に等式が成り立つかどうか調べていっても十分間に合うのですが、これは重複組み合わせを使うと計算量が減ります。1634を分解して4乗和を取ると1634になりますが、1346や6431も1634になります。4桁で重複が無いか…

https://atcoder.jp/contests/abc350/tasks/abc350_e2番目を選んだ時、nのときの期待値はなので、 となります。取り得るnのは、としたときのaが程度で、これが約10000です。また、aが違ってもが同じことが多いので、さらに取り得るnは少なくなって、十分に速…

https://atcoder.jp/contests/abc350/tasks/abc350_d連結成分に分解して、個々のグラフが完全グラフにするのに何本エッジが要るかを調べます。 // New Friends #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T</t:>…

https://projecteuler.net/problem=29前回は例えば2乗までのとき何個がダブるかをナイーブに数えていましたが、2乗までなら2～N/2がダブると分かるので、数えるまでもありません。6乗までだと、N/6～N/3の間は2から5の倍数はダブりますが、重複を考えると包…

https://projecteuler.net/problem=29こういう問題はダブりの方を数える方が速いです。 例えば、5をベースで考えると、などダブりがあります。まで、49個あります。これは6でも同じです。などです。 このように、100までで何乗まであるかが同じならダブりの…

https://projecteuler.net/problem=29ならとしてダブりを排除します。ただし、がべき乗数ならべき乗を外に出します。例えば、とします。 MojoでSetを使うには、KeyElementを継承します。 from collections import Set, KeyElement import sys ##############…

https://projecteuler.net/problem=28角から次の角を求められればよいです。 import sys alias Point = Tuple[Int, Int] fn proceed(pt: Point, n: Int) -> Tuple[Point, Int]: var x = pt.get[0, Int]() var y = pt.get[1, Int]() if x >= 0 and y >= 0: re…

https://atcoder.jp/contests/abc349/tasks/abc349_e状態数がしかなくて、深さも9しかないので、ふつうにメモ化すればよいです。 // Weighted Tic-Tac-Toe #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { l</t:>…

https://atcoder.jp/contests/abc349/tasks/abc349_dRを超えないようにできるだけ飛べばよいです。 // Divide Interval #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std:</t:>…

https://atcoder.jp/contests/abc348/tasks/abc348_dふつうにQueueを使ってたどればよいです。 // Medicines on Grid #![allow(non_snake_case)] use std::collections::VecDeque; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let </t:>…

https://projecteuler.net/problem=27素数の判定をどれくらい大きさまで行っていいか分からないので、ナイーブに判定してメモ化してみました。 MojoではDictを使えるようになりました。 from collections import Dict fn main() raises: var d = Dict[String…

https://atcoder.jp/contests/abc347/tasks/abc347_f3つの正方形は、6通りの配置があって、2つの座標を定めればある長方形の範囲最大の和になります。 Rustなのに時間的にかなり際どいです。木を辿らずにいきなり値を取れるところは取るようにして、やっと通…

https://atcoder.jp/contests/abc347/tasks/abc347_e時系列でSの大きさを記録します。実際には累積和をVecにします。 // Set Add Query #![allow(non_snake_case)] use std::collections::HashMap; //////////////////// library //////////////////// fn re…

https://atcoder.jp/contests/abc347/tasks/abc347_daとbとpopcount(C)で、Cの1をどちらに何個1にするか、0を何個1にするかが決まります。 // Popcount and XOR #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> </t:>…