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; ////…
https://atcoder.jp/contests/abc376/tasks/abc376_emax Aを決めて、その条件でBの和が最小になるようにすると考えるとわかりやすいです。 // Max × Sum #![allow(non_snake_case)] use std::collections::BinaryHeap; //////////////////// library ///////…
https://atcoder.jp/contests/abc376/tasks/abc376_d幅優先探索します。 // Cycle #![allow(non_snake_case)] use std::collections::VecDeque; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io</t:>…
https://projecteuler.net/problem=74辿っていくとρ型になるのですが、すでにあと何歩進めるか分かっているノードに突き当たったら、そこで終了できます。 import sys #################### library #################### fn make_factorial_table(N: Int) -…
https://atcoder.jp/contests/abc375/tasks/abc375_eDPです。状態を各チームの強さ、値を変更人数とします。各チームの強さの最大は500ですが、2チーム分だけを状態とすればよいです。 // 3 Team Division #![allow(non_snake_case)] use std::cmp::min; ///…
https://atcoder.jp/contests/abc375/tasks/abc375_d文字ごとにポジションを配列にして、それをxと書くと、その配列のサイズをNとして、とすると、となって、で計算できます。 // ABA #![allow(non_snake_case)] use std::collections::HashMap; ///////////…
https://projecteuler.net/problem=73しらみつぶしをしてもよいのですが、もっと速い方法があります。 まず、約分を考えなければ、dを固定して考えて、分母の上限をNと書くと、となります。これをがんばって計算すると、そして、約分できない分数の個数をと…
https://projecteuler.net/problem=72分母を固定すれば、を計算すればよいとわかります。頑張れば速くできる気がしますが、ふつうにふるいを使います。 import sys #################### List #################### fn initialize_list[T: CollectionElement…
https://projecteuler.net/problem=710/1と3/7の間で3/7寄りだと(0+3x)/(1+7x)とすればよいです。これで分母が1000000以下になるようにxを定めればよいですが、分母が3で割り切れるならさらにxを大きくできます。 MojoもOptionalが使えますが、TupleがCollec…
https://projecteuler.net/problem=70が小さいほうから調べればよいです。一番小さくなるのは素数ですが、素数はpermutationになりえないので、素数の平方から調べます。100未満とすると、7×7です。次に小さいのは5×5か7×13です。、なので、次は5×5です。そ…
https://atcoder.jp/contests/abc374/tasks/abc374_d?lang=ja単なるしらみつぶしですね。 // Laser Marking #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin(</t:>…
https://atcoder.jp/contests/abc373/tasks/abc373_d有向グラフですが、逆方向に符号が反対の重みを持ったエッジを張って、適当に辿ればよいです。 // Hidden Weights #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr></t:>…
https://projecteuler.net/problem=69 とすると、 となって、これが一番大きいので、要はN以上になるまで素数を小さい順に掛けていくだけです。 import sys fn is_prime(n: Int) -> Bool: var p = 2 while True: if p * p > n: return True elif n % p == 0:…
https://projecteuler.net/problem=68しらみつぶしすればいいですが、ちょっとややこしいですね。 import sys #################### List #################### fn initialize_list[T: CollectionElement](N: Int, init: T) -> List[T]: var a = List[T](cap…
https://projecteuler.net/problem=67単なるDPですね。 import sys #################### library #################### fn read_csv(path: String, delim: String) -> List[List[Int]]: try: var table = List[List[Int]]() with open(path, "r") as f: var…
https://atcoder.jp/contests/abc372/tasks/abc372_djより左で最も右のHjより高いビルの位置を探せばよいです。そういう木を作ります。 // Buildings #![allow(non_snake_case)] use std::cmp::max; //////////////////// library //////////////////// fn r…
https://projecteuler.net/problem=66Pell方程式は連分数と密接に関連しています。Pell方程式の解はの連分数を途中で打ち切った分数の分子と分母になっています。なので、漸化式で分子と分母を求めて、それがPell方程式の解になっていればそれが最小解です。…
https://projecteuler.net/problem=65連分数の係数fに対して、連分数を途中で打ち切って通常の分数にしたとき、例えば、としたとき、その手前で打ち切ったときは、さらにその手前で打ち切ったときはとなりますが、それぞれの分子分母をとすると、 と計算でき…
https://projecteuler.net/problem=64平方根の連分数の周期は、たぶん具体的に計算するしかないです。 まず、とすると少し見通しがよくなります。 の逆数を取ると、となります。なので、の場合に限り、周期1になります。 この整数部分がfだとすると、整数を…
