2023-06-01から1ヶ月間の記事一覧
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bk距離をQueueを使って求めるのですが、120が上限を忘れないように。 // Distance Sum #![allow(non_snake_case)] use std::cmp::min; use std::collections::VecDeque; /////////…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bjxとyを分けるだけですね。 // Distance Sum #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); s</t:>…
https://atcoder.jp/contests/math-and-algorithm/tasks/abc186_dこの問題のポイントは、各要素間の距離の総和だからAを並べ替えても値が同じということですね。 // Sum of difference #![allow(non_snake_case)] //////////////////// library ////////////…
https://atcoder.jp/contests/abc307/tasks/abc307_e状態遷移ですね。最初が0だとして、0という状態と0じゃないという状態を考えればよいです。 行列の演算をGenenicに書いてみましたが、なかなか大変ですね。 // Distinct Adjacent #
https://atcoder.jp/contests/abc307/tasks/abc307_d(の位置をstackにpushして、)があればpopして、その位置まで削除します。 // Mismatched Parentheses #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { le</t:>…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_biこれも数え方の問題ですね。例の20や22が頂点でいくつカウントされるか考えます。頂点までのパスの数なので、パスカルの三角形と同じになります。 // Pyramid #
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bhこれも数え方の問題ですね。の係数は1がi-1個、-1が(N-i)個なので、合わせて重みは(2i-N-1)となります。 // Sum of difference Easy #![allow(non_snake_case)] ///////////////…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bgこれも数え方を変える問題ですね。例えばが最大値になる選び方は、が選ばれるか選ばれないので、4通りです。 前の問題から数学寄りになっていますね。 // Sum of Maximum #
https://atcoder.jp/contests/math-and-algorithm/tasks/jsc2021_cgcdはなので、dを1から順に代入していけばよいです。 // Max GCD 2 #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String</t:>…
https://atcoder.jp/contests/abc306/tasks/abc306_fふつうに数えていったらとても間に合わないので、別の数え方を考えます。 入力例1を考えると、順位を0ベースとして、1と同じ列とその下に自分より小さい数が無いのでカウント無しで、3は1と2があるので、2…
https://atcoder.jp/contests/abc306/tasks/abc306_e平衡木を実装できれば簡単なのですが、そうでなくてもK番目前後で分けて、出し入れが管理できていればよいです。そのために、2つBtreeMapを用意して、クエリーのたびにそれらをアップデートします。 // Be…
https://atcoder.jp/contests/abc306/tasks/abc306_d単なるDPです。 AtCoderでは定数を関数とかで定義するのはダメみたいです。 // Poisonous Full-Course #![allow(non_snake_case)] use std::cmp::max; //////////////////// library ////////////////////…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bf線形計画法ですが、2次元なので、領域が多角形になり、その周辺（というか頂点）をたどっていけばよいです。 ただ、微妙な数値誤差が嫌らしいので、分数を使っています。AtCoder…
https://atcoder.jp/contests/math-and-algorithm/tasks/abc075_dナイーブな実装でも余裕で間に合っていますが、次のようにすると速いです。 xでソートしてxの範囲を固定します。その範囲の中のyを取り出します。その中のK個を取り出すためにスライドして、y…
https://atcoder.jp/contests/math-and-algorithm/tasks/abc178_bxを固定すると、最大値は正ならd、負ならcになります。要するに、どちらにしても端だけを見ればよいです。 手元ではreduceが使えますが、AtCoderでは使えないんですね。 // Product Max #
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_beこれも包除原理ですね。 Vecのスライスを使うと書きやすいようです。 // Number of Multiples 2 #![allow(non_snake_case)] //////////////////// library ////////////////////…
https://atcoder.jp/contests/abc305/tasks/abc305_ePriorityQueueに(進める距離, ノード番号)を格納してグラフを進んでいくとよいです。 // Art Gallery on Graph #![allow(non_snake_case)] use std::collections::BinaryHeap; //////////////////// libra…
https://atcoder.jp/contests/abc305/tasks/abc305_d開始時刻と終了時刻がAのどこに含まれるかを二分探索で特定します。 // Sleep Log #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = Strin</t:>…
https://atcoder.jp/contests/math-and-algorithm/tasks/typical90_d包除原理ですね。i行目の和を、j行目の和をとすると、が求める和です。 // Cross Sum #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { le</t:>…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bd各カードに書かれた整数をa, b, cとして、aを固定します。aが1とNから遠いところなら場合の数は同じです。それを含めて総当たりにすればよいです。 // Three Cards #
https://atcoder.jp/contests/abc304/tasks/abc304_fこれは、包除原理ですね。 題意を満たすシフトの数をF(M)とすると、N = 12で考えると、M=6とM=4はそれぞれF(6)とF(4)がありますが、両方にF(2)個分共通のシフトが含まれることが分かるので、結局トータル…
https://atcoder.jp/contests/abc304/tasks/abc304_eUnionFindを作って、K個の条件はrootに直してペアをHashSetにして、クエリもrootに直してHashSetにあるかどうかを調べます。 RustではUnionFindをコーディングするのが大変ですね。parentも整数してやれば…
https://atcoder.jp/contests/abc304/tasks/abc304_d二分木を作って、イチゴが一つになるかもう分割できなくなるまで分割します。 Rustで二分木を作るのは大変ですね。 // A Piece of Cake #![allow(non_snake_case)] use std::cmp::{min, max}; ///////////…
https://atcoder.jp/contests/math-and-algorithm/tasks/panasonic2020_bHWが偶数と奇数で変わりますが、HかWが1のときは身動きが取れないので特殊ですね。 // Bishop #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr></t:>…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bc問題58と同じですね。 // All Zero #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::</t:>…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bb奇数だと市松模様を考えれば存在しないことは明らかで、偶数だとパスが簡単に分かりますね。 // Move on Squares 2 #![allow(non_snake_case)] //////////////////// library //…
