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]()) コンパイル時にインデックスを…

AtCoder Beginner Contest 341 D

https://atcoder.jp/contests/abc341/tasks/abc341_d包除原理+二分探索です。(first, last]とするとよいです。 // Only one of two #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String:</t:>…

MojoでProject Euler 16

https://projecteuler.net/problem=16Problem 13のBigIntegerに掛け算を付け加えただけです。 from math import max import sys #################### BigInteger #################### struct BigInteger(CollectionElement): var v: DynamicVector[Int] fn…

AtCoder Beginner Contest 340 F

https://atcoder.jp/contests/abc340/tasks/abc340_fを解くだけですが、けっこういやらしいですね。 // F - S = 1 #![allow(non_snake_case)] use std::cmp::min; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = Strin</t:>…

AtCoder Beginner Contest 340 E

https://atcoder.jp/contests/abc340/tasks/abc340_e入力例1で、初回で2 2 0 5 6になって、2回目は6を取り出して、0に2を1~4に1を足します。このように範囲に同じ値を足すので、そういう木を作ればよいです。 // Mancala 2 #![allow(non_snake_case)] /////…

AtCoder Beginner Contest 340 D

https://atcoder.jp/contests/abc340/tasks/abc340_d単なるダイクストラ法です。 隣が2つと決まっているので、グラフをVecにしやすいです。 // Super Takahashi Bros. #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr></t:>…

AtCoder Beginner Contest 339 E

https://atcoder.jp/contests/abc339/tasks/abc339_e簡単なDPです。まで最大の列の長さをとすると、 となります。ただ、このままだと計算量がで間に合わないので、範囲の最大値を取れる木を用意します。 // Smooth Subsequence #![allow(non_snake_case)] us…

AtCoder Beginner Contest 339 D

https://atcoder.jp/contests/abc339/tasks/abc339_d二人のプレーヤーの位置を状態としたDPですね。最初、HashMapを使っていたのですが、実行時間ががギリギリで、4次元の配列に直したら速くなりました。 // Synchronized Players #![allow(non_snake_case)]…

AtCoder Beginner Contest 338 E

https://atcoder.jp/contests/abc338/tasks/abc338_eA // Chord #![allow(non_snake_case)] use std::cmp::{min, max}; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mu</t:>…

AtCoder Beginner Contest 338 D

https://atcoder.jp/contests/abc338/tasks/abc338_d一歩ずつ進みます。例1だとまず1から3ですが、封鎖した橋が1か2なら長さ1、3なら長さ2です。次に3から2ですが、封鎖した橋が1か3なら長さ1、2なら長さ2です。このように同じ長さが続くので、セグメント木…

MojoでProject Euler 15

https://projecteuler.net/problem=15Combinationの計算をすればよいですが、あえてDPで計算しています。Matrix構造体を1次元ベクトルで表現しています。 import sys #################### Matrix #################### struct Matrix: var H: Int var W: In…

AtCoder Beginner Contest 337 E

https://atcoder.jp/contests/abc337/tasks/abc337_e2進数で考えて、1回ごとに各桁を決めます。すなわち、i桁目が1になるものだけを友人iに // Bad Juice #![allow(non_snake_case)] use std::cmp::min; //////////////////// library //////////////////// …

AtCoder Beginner Contest 337 D

https://atcoder.jp/contests/abc337/tasks/abc337_d1行ごとにDPで最小値を求めます。 // Cheating Gomoku Narabe #![allow(non_snake_case)] use std::cmp::min; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = Strin</t:>…

競プロ典型 020

https://atcoder.jp/contests/typical90/tasks/typical90_tか調べればよいですが、cのべき乗を次々と計算していけばよいです。 // Log Inequality #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut l</t:>…

MojoでProject Euler 14

https://projecteuler.net/problem=14メモ化をすれば簡単ですが、グローバルにDynamicVectorを持てますね。 import sys #################### process #################### var memo = DynamicVector[Int]() fn Collatz_length(n: Int) -> Int: if n < memo…

競プロ典型 019

https://atcoder.jp/contests/typical90/tasks/typical90_sDPで区間を状態にして、単に2つを足すか、両端の差とその間の区間、と考えれば簡単にDPの式が得られます。なぜこの2つかと言うと、両端が残るまで取りつくさないと、どこかで2つに分割するのと同じ…