2024-12-01から1ヶ月間の記事一覧
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枚だ…
https://atcoder.jp/contests/abc381/tasks/abc381_d入力例1なら10ごとに離れた位置だと1 11 21なので2だけ余裕があります。それを3つに分けます。分割統治法を使うとよいです。 // Keep Distance #![allow(non_snake_case)] //////////////////// library /…
