https://projecteuler.net/problem=931～9から4つの順列を発生させて、それぞれに対して3つ演算の順番の種類で計算します。なかなかめんどうです。 from math import sqrt import sys #################### library #################### fn gcd(n: Int, m: …
https://projecteuler.net/problem=92までとすると、次はまでになります。だから、そこまでの1か89のどちらにたどり着くかの表を作っておきます。そうしておいて重複組み合わせの一つ一つがどちらにたどり着くかを調べます。例えば、1111222と1212121は同じ…
https://projecteuler.net/problem=91直角がどの点か決めて、Qが直角ならQPがOQに直交するようにPを定めます。 速くなりそうな気もしますが、難しいですね。 from math import sqrt import sys #################### library #################### fn gcd(n:…
https://atcoder.jp/contests/abc388/tasks/abc388_d石の数を変化させる順番を変えると組みやすくなります。 入力例1は、 5 0 9 3から、最初の宇宙人は最終的に3つ石を2～4番目の宇宙人に配るので、 2 1 10 4となります。2番目の宇宙人は2つ石を配りたいとこ…
https://projecteuler.net/problem=90Stringは__getitem__で1文字を取れるんですね。 from math import sqrt import sys #################### List #################### fn insert_list[T: CollectionElement](inout v: List[T], e: T, i: Int): v.append(…
https://projecteuler.net/problem=89Stringは__getitem__で1文字を取れるんですね。 from math import sqrt import sys #################### process #################### fn read_romans(path: String) -> List[String]: var romans = List[String]() tr…
https://projecteuler.net/problem=88たくさんの素数から合成された数のほうがkが大きくなるのは明らかですが、小さい数から順に分解してkを求めるしかなさそうですね。 Mojoで謎のエラーが出て苦戦しました。次のように素因数分解構造体を次のようにすると…
https://atcoder.jp/contests/abc387/tasks/abc387_e9で割れるには各桁の和が9で割り切れればよいです。8で割れるには下3桁が8で割り切れればよいです。ある程度桁数があれば、80…000、140…012などで全て範囲をカバーできます。 // Digit Sum Divisible 2 #!…
https://atcoder.jp/contests/abc387/tasks/abc387_d幅優先探索すればいいのですが、同じマスでも上下から入った場合と左右から入った場合で分けるとよいです。 // Snaky Walk #![allow(non_snake_case)] use std::collections::VecDeque; /////////////////…
https://projecteuler.net/problem=87同じ値で違う組み合わせがあるので、ナイーブに組むしかなさそうです。 import sys #################### library #################### fn int_sqrt(n: Int) -> Int: var x = 1 x = (x + n // x) // 2 while True: var …
https://projecteuler.net/problem=86例だと、またぐ辺が5と3だから8で、6と直角になって斜辺が10となります。直方体の最も長い辺が直角三角形の一つの辺で残りの辺の和で直角を成します。 なので、直角三角形を最も長い辺になる長さが小さいほうから列挙す…
https://projecteuler.net/problem=85左上の点を共有する長方形の面積の合計と同じです。 長方形の高さをh、幅をwとすると面積の合計はhが小さいほうから最適なwを求めていけばいいです。 import sys #################### library #################### fn …
https://projecteuler.net/problem=84ちゃんと計算しようとすると大変です。カードをシャッフルして上から取って一番下に入れるというのが難しいです。シャッフルしてからでも状態の数が10240あります。シャッフルしてから収束させて、すべてのシャッフルに…
https://atcoder.jp/contests/abc386/tasks/abc386_eKがN/2以下のときはふつうに分割統治法を使えばよいですが、Kが大きいときは分割したときの個数が大きくなることがあります。例えば、N=100でK=99だと、100を2つで割って50個の有り無しになるので、2[sup]…
https://atcoder.jp/contests/abc385/tasks/abc385_f原点から全てのビルを見られなければ、左から順に左隣のビルの陰にならないように高さを上げていきます。 これ、最初からf64にするとハマりますね。 // Santa Claus 2 #![allow(non_snake_case)] ////////…
https://atcoder.jp/contests/abc385/tasks/abc385_d同じ場所を何度も通ってそこにたくさんの点があると時間がかかるので、重複を除いてあらかじめ通る場所を計算しておきます。そのために、各固定座標に対し範囲をBTreeSetにし、そこに範囲を追加して、範囲…
https://projecteuler.net/problem=83ダイクストラ法ですが、実装するのはけっこう大変ですね。TupleがComparableCollectionElementとKeyElementを実装してくれれば簡単なんですけどね。 import sys #################### List #################### trait P…
https://projecteuler.net/problem=82上下に動けるので一気にDPを使えず、マスごとに上から来るのと下から来るのと左から直接来るのとで最も小さいものを選びます。 import sys #################### List #################### fn initialize_list[T: Colle…
https://projecteuler.net/problem=81ループがない有向グラフなので、DPを使えばよいです。 import sys #################### Matrix #################### fn read_matrix(path: String) -> List[List[Int]]: try: var matrix = List[List[Int]]() with ope…
https://atcoder.jp/contests/abc384/tasks/abc384_fふつうに計算すれば以上かかりますが、Aを偶数と奇数に分けてみましょう。そうすると、偶数から一つ奇数から一つ取って足せば割らなくてもいいので、和を簡単に計算できます。これがd=2のときです。d=4の…
https://atcoder.jp/contests/abc384/tasks/abc384_e周りのマスをQueueに入れて、値が小さい順に取り出します。 // Takahashi is Slime 2 #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = St</t:>…
https://atcoder.jp/contests/abc384/tasks/abc384_d繰り返し部分を除いて、数列Aの中か両端で和がSになる範囲を探せばいいですが、尺取り法でO(N)でできます。 // Repeated Sequence #![allow(non_snake_case)] //////////////////// library /////////////…
https://projecteuler.net/problem=802ならにして、平方根を取って小数点以下を切り捨てます。 import sys #################### List #################### fn initialize_list[T: CollectionElement](N: Int, init: T) -> List[T]: var a = List[T](capaci…
https://projecteuler.net/problem=79319なら、3 → 1 → 9などとして、単純有向グラフを作ります。そして、トポロジカルソートとします。 import sys #################### List #################### trait Printable(CollectionElement, Stringable): pass …
https://atcoder.jp/contests/abc383/tasks/abc383_f単純なDPです。商品をCで並び替えて、合計金額と今の色をすでに使ったかを状態にします。値は満足度の最大値です。今の色の商品が終わったら、全てまだ色を使っていないことにします。 // Diversity #
https://projecteuler.net/problem=78分割数そのものですが、剰余計算をします。 上限が分からないので、上限を倍々にします。 import sys #################### Pair #################### @value struct Pair(KeyElement, Stringable): var x: Int var y: …
https://atcoder.jp/contests/abc383/tasks/abc383_d次のように素因数分解すると、 約数の個数は、 となります。なので、との形しかありえません。。 // 9 Divisors #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>()</t:>…
https://projecteuler.net/problem=77五角数定理みたいなものはないので、素直に を計算します。 import sys #################### List #################### fn initialize_list[T: CollectionElement](N: Int, init: T) -> List[T]: var a = List[T](capa…
https://projecteuler.net/problem=76これは分割数から1引いたものです。 n個をm以下で分割した数を、とすると、 となります。これでを求めると、計算量はですが、これでも十分間に合います。 しかし、母関数を使うともっと速くなります。 なので、これをま…
https://atcoder.jp/contests/abc382/tasks/abc382_e一つのパックにレアカードがi枚入っている確率は、 で得られます。n枚以上手に入れるまでのパック数の期待値をとしたとき、まずです。一つパックを開けたことを考えます。入力例2でを考えると、1枚か2枚だ…
