2024-01-01から1年間の記事一覧

MojoでProject Euler 29(1)

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

MojoでProject Euler 28

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…

AtCoder Beginner Contest 349 E

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:>…

AtCoder Beginner Contest 349 D

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:>…

AtCoder Beginner Contest 348 D

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:>…

MojoでProject Euler 27

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

AtCoder Beginner Contest 347 F

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

AtCoder Beginner Contest 347 E

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

AtCoder Beginner Contest 347 D

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:>…

AtCoder Beginner Contest 346 F

https://atcoder.jp/contests/abc346/tasks/abc346_f直接kを求めるのは難しいですが、kを与えて部分列かを調べるのは比較的易しいので、二分探索を行います。 // SSttrriinngg in StringString #![allow(non_snake_case)] use std::collections::HashMap; //…

AtCoder Beginner Contest 346 E

https://atcoder.jp/contests/abc346/tasks/abc346_e逆から考えればよいです。例1なら、下から見て、1 3 2だから、3行目が2になって、2が4個は確定です。次に、1 3 3ですが、3行目はもう終わったので無視です。2 4 0は、4列目を0にしますが、3行目がすでに確…

AtCoder Beginner Contest 346 D

https://atcoder.jp/contests/abc346/tasks/abc346_d文字列を左から見ていって、位置と直前の文字と隣が同じだったことが何回あるかを状態としてDPします。 // Gomamayo Sequence #![allow(non_snake_case)] use std::cmp::min; //////////////////// librar…

MojoでProject Euler 26

https://projecteuler.net/problem=26各に対し、となる最小の自然数を求めます。オイラーの定理からなので、の約数となります。 実際のところは、素数の大きい方から順に調べて、周期がその数より1小さいものがあれば、その素数が求める答えです。 from math…

MojoでProject Euler 25

https://projecteuler.net/problem=25真面目にフィボナッチ数列を求めてもいいのですが、以下のように概算できます。 漸化式から、 となります。10進でN桁として、 となる最小のを求めればよいです。 右辺第2項は小さいので無視すると、 となります。 ところ…

MojoでProject Euler 24

https://projecteuler.net/problem=24例題で、 ["0", "1", "2"] という配列を用意します。 5番目の順列を決めるのに、 4/2!=2なので、 "2"が頭になります。これを配列から除去して、["0", "1"]となります。 余りが0だったので、0/1!=0で、"0"を取り出します…

AtCoder Beginner Contest 345 D

https://atcoder.jp/contests/abc345/tasks/abc345_dしらみつぶしで十分間に合います。次に長方形を置く場所を決めるとき、必ず左上から左に空いているマスを探します。 // Tiling #![allow(non_snake_case)] //////////////////// library ////////////////…

MojoでProject Euler 23

https://projecteuler.net/problem=23素直に23111までの過剰数を求めて総当たりします。 import sys #################### library #################### def div_pow(n: Int, d: Int) -> Tuple[Int, Int]: var m = n var e = 0 while m % d == 0: e += 1 m …

MojoでProject Euler 22

https://projecteuler.net/problem=22ファイルを読むのもまだめんどうなようです。1行ずつ読むメソッドも無いようです。今回の問題は最初から1行ですが。 DynamicVector[Int]はソートする関数が用意されているようですが、DynamicVector[String]は無いようで…

MojoでProject Euler 21

https://projecteuler.net/problem=21約数の和はエラトステネスのふるいのようにまとめて求められますが、元々の値をオーバーしたら個別に素因数分解して求めます。 import sys #################### library #################### def div_pow(n: Int, d: I…

AtCoder Beginner Contest 344 E

https://atcoder.jp/contests/abc344/tasks/abc344_e双方向リストを作って、それぞれのノードの値とノード自体を辞書にすればいいのですが、ノードをいくつも共有しなければならないので、たぶん参照カウントを使うしかないです。そうすると非常に複雑になっ…

AtCoder Beginner Contest 344 D

https://atcoder.jp/contests/abc344/tasks/abc344_d単なるDPですね。どこまで一致したかが状態で、そのなかで最小の金額を記憶しておきます。 // String Bags #![allow(non_snake_case)] use std::cmp::min; //////////////////// library ////////////////…

MojoでProject Euler 20

https://projecteuler.net/problem=20DynamicVectorに__iter__()が実装されたようです。ただし、所有権は放棄しないので、Reference型を返します。これをデリファレンスするには、 for e in v: print(e[]) のようにします。 from math import max import sys…

MojoでProject Euler 19

https://projecteuler.net/problem=19よく考えると、月の日数は2月を除けば簡単に求められますね。 fn is_leap_year(y: Int) -> Bool: return y % 4 == 0 and (y % 100 != 0 or y % 400 == 0) fn mdays(y: Int, m: Int) -> Int: if m == 2: return 29 if is_…

MojoでProject Euler 18

https://projecteuler.net/problem=18全てのパスで和を計算して、最大値を得ます。パスは2進数で表せます。左に行くのは0で右は1です。 最新のバージョンでletでwarningが出るようになりました。そのうち使えなくなるそうです。めんどうなのでそのままにして…

AtCoder Beginner Contest 343 F

https://atcoder.jp/contests/abc343/tasks/abc343_f木を作って、各ノードに大きい方から2番目までの値と個数を保持しておけばよいです。 Boxを外すときas_ref()を使いますが、変更するならas_mut()を使うんですね。 // Second Largest Query #![allow(non_s…

AtCoder Beginner Contest 343 D

https://atcoder.jp/contests/abc343/tasks/abc343_d選手ごとの得点のテーブルと、どの得点に何人いるかのマップを持っておきます。 // Diversity of Scores #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T {</t:>…

AtCoder Beginner Contest 342 F

https://atcoder.jp/contests/abc342/tasks/abc342_fまず最終的にyがいくつになるかの確率を求めて、自分の勝つ確率を求めます。そこでやめたときの勝つ確率と、サイコロを振ったときの勝つ確率を求めます。 // Black Jack #![allow(non_snake_case)] use st…

AtCoder Beginner Contest 342 E

https://atcoder.jp/contests/abc342/tasks/abc342_e逆から考えれば単なるダイクストラです。 // Square Pair #![allow(non_snake_case)] use std::cmp::min; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::n</t:>…

AtCoder Beginner Contest 342 D

https://atcoder.jp/contests/abc342/tasks/abc342_d基本的には、素因数分解して、指数が奇数の素数だけ残して、同じものを数えればよいです。 // Square Pair #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T</t:>…

MojoでProject Euler 17

https://projecteuler.net/problem=17Mojoには、 let v = ["one", "two", ...] みたいなのがあるにはあるんですが、これはListLiteralといって、要素にアクセスするにはタプルと同じように、 print(v.get[1, StringLiteral]()) コンパイル時にインデックスを…