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つに分割するのと同じ…

AtCoder Beginner Contest 336 E

https://atcoder.jp/contests/abc336/tasks/abc336_eある桁和を考えて、上の桁から、数字の和と剰余を状態としたDPを考えればよいです。上限があるのでちょっと嫌らしいです。 // Digit Sum Divisible #![allow(non_snake_case)] //////////////////// libra…

AtCoder Beginner Contest 336 D

https://atcoder.jp/contests/abc336/tasks/abc336_d左から見て、その位置からどこまでがピークになり得るかを調べます。右からも同様です。 入力例1だとそれぞれ0-basedで、 2 2 2 3 4 0 0 1 2 4そして、上の左から見ていって、2以下で一番右の場所を探しま…

MojoでProject Euler 13

https://projecteuler.net/problem=13一つのdigitを一つのIntで表す構造体を作ればよいです。 特殊メソッド__str__()はどうやって使ったらいいんでしょうね。 from math import max #################### BigInteger #################### struct BigInteger…

競プロ典型 018

https://atcoder.jp/contests/typical90/tasks/typical90_r素直に座標計算するだけですね。 // Statue of Chokudai #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io:</t:>…

MojoでProject Euler 12

https://projecteuler.net/problem=12ふつうに三角数を素因数分解しても十分速いです。 しかし、素因数分解の指数だけで約数の個数は決まるので、約数の個数が条件より大きい指数だけ考えれば速いです。 素因数分解を とすると、約数の個数は、 となります。…

AtCoder Beginner Contest 335 G

https://atcoder.jp/contests/abc335/tasks/abc335_gとなる最小のpをaの周期と呼ぶことにします。 だから、周期はP-1の約数になります。なので、P-1から割っていって1になる最小の約数を求めればよいですが、もうちょっと効率のよい方法がある気がするんです…

AtCoder Beginner Contest 335 E

https://atcoder.jp/contests/abc335/tasks/abc335_e繋がっている同じ値のノードは結合してグラフにします。そうすればあとはDPになります。 // Non-Decreasing Colorful Path #![allow(non_snake_case)] use std::cmp::max; use std::collections::HashMap;…

AtCoder Beginner Contest 335 D

https://atcoder.jp/contests/abc335/tasks/abc335_d例にあるようにらせん状にたどればよいです。 // Loong and Takahashi #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); s</t:>…

競プロ典型 017

https://atcoder.jp/contests/typical90/tasks/typical90_qある線分に対し、Lが小さい線分でその線分が交わるものを数えます。その線分をとすると、となります。線分の集合(L, R)をLでソートします。そうして、BITを用意してに1を加えていきます。そして、そ…

MojoでProject Euler 11

https://projecteuler.net/problem=11どうもグローバルで定数を定義するのができないみたいで、mainの中にstr_tableを書いたらうまくいきました。 あとは、splitも使えてそんなに難しくないです。 from math import max import sys struct Matrix: var a: Dy…

競プロ典型 016

https://atcoder.jp/contests/typical90/tasks/typical90_pA, B, Cの中で一番大きいものが何個使うか固定して、残りで一番少ない個数を調べます。 // Gravy Jobs #![allow(non_snake_case)] use std::cmp::min; //////////////////// library //////////////…

MojoでProject Euler 10

https://projecteuler.net/problem=10エラトステネスの篩をするだけですね。 from math import max, sqrt import sys fn make_prime_table(N: Int) -> DynamicVector[Int]: let a = DTypePointer[DType.bool].alloc(N+1) for i in range(N+1): a.store(i, Tr…

競プロ典型 015

https://atcoder.jp/contests/typical90/tasks/typical90_oこれは、アルゴリズムと数学 101と同じ問題です。

MojoでProject Euler 9

https://projecteuler.net/problem=9直角三角形の各辺の長さは、 と表せて、周囲の長さLは、となるので、L/2を3つの整数の積にすれば簡単にl, m, nを求められます。ただ、一般的には2つの約数に分解して、片方をさらに2つの約数に分解しますが、そうすると分…