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

競プロ典型 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つの約数に分解しますが、そうすると分…

競プロ典型 014

https://atcoder.jp/contests/typical90/tasks/typical90_n小学生と通う小学校を同じ並びにすればよいです。 // We Used to Sing a Song Together #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut l</t:>…

AtCoder Beginner Contest 334 F

https://atcoder.jp/contests/abc334/tasks/abc334_fDPですが、状態が今いる位置と持っているプレゼント数なので、状態数がO(NK)なので間に合いません。しかし、スタートに戻る以外は次に移るので同じ値を足すだけです。また、スタートに戻るのは各状態から…

AtCoder Beginner Contest 334 D

https://atcoder.jp/contests/abc334/tasks/abc334_dRをソートして累積和を求めておいて二分探索ですね。 // Reindeer and Sleigh #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::n</t:>…

MojoでProject Euler 8

https://projecteuler.net/problem=8毎回13個の数字を掛け算すればよいですが、もう少し頑張れば計算量を減らせます。0が13個の間に何個あるのかと最後の0のあと積を記憶しておけばよいです。 # e008.mojo import sys struct ProductGenerator: var L: Int v…

競プロ典型 013

https://atcoder.jp/contests/typical90/tasks/typical90_m1とNと両方からダイクストラをやればよいです。 // Passing #![allow(non_snake_case)] use std::collections::BinaryHeap; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { l</t:>…

AtCoder Beginner Contest 333 G

https://atcoder.jp/contests/abc333/tasks/abc333_g分母がN以下で実数rに最も近い分数を最良近似と言います。これは連分数と結びついています。 例えば、0.45を連分数で表すと、 となります。これは次のように求められます。 の逆数を取るとで、この整数部…

AtCoder Beginner Contest 333 F

https://atcoder.jp/contests/abc333/tasks/abc333_fN個の中でiが最後まで残る確率をと書くと、1回動かすと、なので、最初の式のに最後の式を代入して、という処理を次々していけば、となるので、が求まって、他の確率も求まります。 // Takahashi Quest #![…

AtCoder Beginner Contest 333 E

https://atcoder.jp/contests/abc333/tasks/abc333_eタイプが違うと独立に考えられます。タイプトごとに、逆向きに、符号も逆にして考えます。トータルで負になるときだけ、パスします。 // Takahashi Quest #![allow(non_snake_case)] use std::cmp::max; /…

AtCoder Beginner Contest 333 D

https://atcoder.jp/contests/abc333/tasks/abc333_d1を含むエッジを除いてUnion-Findを構築します。そうしたとき、一番点の数の大きな木以外を足すと求める値になります。 // Erase Leaves #![allow(non_snake_case)] use std::cmp::max; /////////////////…

AtCoder Beginner Contest 332 D

https://atcoder.jp/contests/abc332/tasks/abc332_d行と列の順列は独立なので、それぞれの順列と隣同士の互換がどれだけ要るかを計算しておけば、あとはしらみつぶしです。 // Swapping Puzzle #![allow(non_snake_case)] use std::collections::{HashMap, …

AtCoder Beginner Contest 331 E

https://atcoder.jp/contests/abc331/tasks/abc331_ePriorityQueueを使って、合計が多い組み合わせから列挙していきます。 // Set Meal #![allow(non_snake_case)] use std::collections::{BinaryHeap, HashSet}; //////////////////// library ////////////…

AtCoder Beginner Contest 331 D

https://atcoder.jp/contests/abc331/tasks/abc331_d二次元累積和を使うと高速にエリア内の黒の個数を求めることができます。 // Tile Pattern #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line</t:>…

MojoでProject Euler 7

https://projecteuler.net/problem=7配列にはいろいろな種類があるようです。ここでは2種類を使います。 Pointerはallocateして最後にfreeするというCで領域確保するのと同じものです。恐ろしいですね。 DynamicVectorはpush_backして要素を追加できるので、…

AtCoder Beginner Contest 330 F

https://atcoder.jp/contests/abc330/tasks/abc330_f辺の間隔(=長さ)を一定とすると、辺をずらすとどこかで移動量の最小値がありますが、片方の辺を端からずらしていくと移動量が下に凸になるので、両方の辺を合わせても下に凸になります。なので、領域を…

AtCoder Beginner Contest 330 E

https://atcoder.jp/contests/abc330/tasks/abc330_e連続する範囲を葉にする木を作ればいいですが、実装が大変です。ですが、範囲にOrderingの各Traitを実装すればBTreeSetを使えます。範囲が重なれば等しい、そうでなければ大小ということにします。 // Cou…

AtCoder Beginner Contest 330 D

https://atcoder.jp/contests/abc330/tasks/abc330_d縦横でoの数を数えておきます。 // Counting Ls #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_</t:>…

競プロ典型 012

https://atcoder.jp/contests/typical90/tasks/typical90_l典型的なUnion-Findを使う問題ですね。 色々な型に対応できるようにUnion-Findの構造体を頑張って書いてみました。 // Gravy Jobs #![allow(non_snake_case)] use std::collections::HashMap; use s…

MojoでProject Euler 6

https://projecteuler.net/problem=6べた書きするだけですね。 # e006.mojo import sys fn f(N: Int) -> Int: var s = 0 var s2 = 0 for n in range(1, N+1): s += n s2 += n*n return s*s - s2 fn main() raises: let args = sys.argv() let N = atol(args[…

競プロ典型 011

https://atcoder.jp/contests/typical90/tasks/typical90_k単なるDPですが、よくあるパターンで終わりの日でソートします。 // Gravy Jobs #![allow(non_snake_case)] use std::cmp::max; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T</t:>…

MojoでProject Euler 5

https://projecteuler.net/problem=5gcdが使えますね。 # e005.mojo from math import gcd import sys fn lcm(n: Int, m: Int) -> Int: return n // gcd(n, m) * m fn f(N: Int) -> Int: var m: Int = 1 for n in range(1, N+1): m = lcm(m, n) return m fn …

AtCoder Beginner Contest 329 E

https://atcoder.jp/contests/abc329/tasks/abc329_e置き換える順序が大事なのですが、左から順に1文字ずつ合う状態を選んでいくとき、最近M個までの順序だけを覚えておけばよく、さらに上に最新の操作の下に埋もれてしまう操作は意味を成さないので、そこは…

AtCoder Beginner Contest 329 D

https://atcoder.jp/contests/abc329/tasks/abc329_dBTreeSetを使うとよいです。 // Election Quick Report #![allow(non_snake_case)] use std::collections::BTreeSet; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line </t:>…

競プロ典型 010

https://atcoder.jp/contests/typical90/tasks/typical90_j範囲の和をクエリを処理するのに、累積を計算しておいて差を取るという典型的な問題ですね。 // Score Sum Queries #![allow(non_snake_case)] //////////////////// library //////////////////// …

MojoでProject Euler 4

https://projecteuler.net/problem=4この問題はPriorityQueueを速いので、Pythonでこんな感じに書きます。 # e004.py from __future__ import annotations from typing import Iterator import heapq import sys def digits(n: int) -> Iterator[int]: while…

競プロ典型 009

https://atcoder.jp/contests/typical90/tasks/typical90_i1点と取って、その点と残りの点を結ぶベクトルとx軸がなす角度を計算します。そのとき、角度でソートします。そうすると、しゃくとり法的に対角の点を求めることができて、そのうち角度が最大のもの…

AtCoder Beginner Contest 328 F

https://atcoder.jp/contests/abc328/tasks/abc328_fこれもUnion-Findですね。親との差をメモしておくと、元々繋がっている時に矛盾するかチェックできます。 // Good Set Query #![allow(non_snake_case)] use std::cmp::max; //////////////////// library…

AtCoder Beginner Contest 328 E

https://atcoder.jp/contests/abc328/tasks/abc328_e全域木を全て調べればいいのですが、すでに繋がっているのかどうかの判定にUnion-Findを使います。しかし、エッジを取り除くのが難しいので、エッジを追加するときに追加する前の状態を最小限に保存してお…

AtCoder Beginner Contest 328 D

https://atcoder.jp/contests/abc328/tasks/abc328_d双方向リストを作って、ABCが現れたら削除します。 // Many Good Tuple Problems #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String</t:>…