2024-01-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 /…
https://atcoder.jp/contests/abc381/tasks/abc381_e/の前後で1と2を数を数えますが、2の数が1の数以上になる右端の/の位置を二分探索して、それとそれより一つ左を比べます。 // 11/22 Subsequence #![allow(non_snake_case)] use std::cmp::{min, max}; //…
https://atcoder.jp/contests/abc381/tasks/abc381_d前から見て行って、1122の間だけ整数と位置の辞書を作って、1122でなくなったら辞書を削除して、同じ整数が出たらそこから前まで辞書から消します。 // 1122 Substring #![allow(non_snake_case)] use std…
https://atcoder.jp/contests/abc380/tasks/abc380_fカードは、プレーヤー1、2が持っているのと場にあるかなので、3つの状態があります。これは2ビットで表せます。あと、どちらの手番かを1ビットで表せばよいです。次の状態への遷移はビット操作で計算でき…
https://atcoder.jp/contests/abc380/tasks/abc380_dSの次は、ST、その次はSTTS、その次はSTTSTSSTとなります。 例えば、0-baseで6番目なら、4を引いて2、2を引いて0なので、0に到達するまでに2回です。1回ごとに反転するので、2回ならSになります。 // Stra…
https://projecteuler.net/problem=75直角三角形の辺は、 と表されるので、周囲の長さLは、 となります。なので、を当てはめていけばよいです。 計算量は、たぶんくらいです。 くらいだと間に合いますね。ただし、その分メモリを食います。この方法ではいき…
https://atcoder.jp/contests/abc379/tasks/abc379_eこれは和を取る順序を変える問題ですね。より具体的には各数字がどの桁で何回使うかを調べます。例えば123だと1は123なら100、12なら10、1なら1となるので、1は111になります。 ちゃんと書くと、k桁の数字…
https://atcoder.jp/contests/abc379/tasks/abc379_d突っ込んだものから取り出すのでQueueを使えばよいです。 ただ、突っ込んだ値を変えられないので、突っ込んだ値に経過時間を足したものを高さにすればよいです。 // Home Garden #
https://atcoder.jp/contests/abc378/tasks/abc378_eふつうに計算すると計算量は、累積和を使ってもです。しかしよく考えると、一つのrについてで計算できます。 例えば、Mが5だとして、Aが[1, 2, 3, 3]だとして、rが3のとき、和は6, 5, 3だから、Mで割った…
https://atcoder.jp/contests/abc378/tasks/abc378_dしらみつぶしでも、元に戻れないので最初以外は行けるところは3通りしかないので、311 = 177,147、始点が100個以下なので十分に間に合います。今までに行ったことがあるマスはi128を使えば簡単にわかりま…
https://atcoder.jp/contests/abc377/tasks/abc377_eiからPiにと辿っていくとループがいくつかできます。そうすると、K=1なら2歩、K=2なら4歩、K=3なら8歩そのループを進みます。 べき乗の計算はi128を使うと簡単ですね。 // Permute K times 2 #
https://atcoder.jp/contests/abc377/tasks/abc377_d例3だと、[5, 19]は[8, 12]を含みますが、この場合[5, 19]は要らないないです。こういう区間を消すと楽になります。 // Many Segments 2 #![allow(non_snake_case)] use std::collections::BTreeSet; ////…
