2023-08-01から1ヶ月間の記事一覧
https://atcoder.jp/contests/math-and-algorithm/tasks/typical90_j累積を取るパターンですが、1組と2組の2つを取るところが特殊ですね。 // Score Sum Queries #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -></t:>…
https://atcoder.jp/contests/math-and-algorithm/tasks/abc140_cBの小さいところから、それを挟むAがまだ定まっていなければBと同じ値にします。 // Maximal Value #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>()</t:>…
https://atcoder.jp/contests/abc317/tasks/abc317_e題意通りに"!"を付けて、Queueを使って最短距離を得ます。 // Avoid Eye Contact #![allow(non_snake_case)] use std::ops::Add; use std::collections::VecDeque; //////////////////// library ////////…
https://atcoder.jp/contests/abc317/tasks/abc317_d単なるDPですね。上の選挙区から処理して、獲得した議席の数を状態とします。ナップザック問題に似ていますね。 // President #![allow(non_snake_case)] use std::cmp::min; //////////////////// librar…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_brこれもしらみつぶしで十分です。 // Beautiful Rectangle #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = Str</t:>…
https://atcoder.jp/contests/abc315/tasks/abc315_fただのDPですね。ただし、状態は位置番号とCです。Cはなので、DPの計算量はです。 // Prerequisites #![allow(non_snake_case)] use std::cmp::min; use std::ops::{Add, Sub}; //////////////////// libr…
https://atcoder.jp/contests/abc315/tasks/abc315_eトポロジカルソートですね。1から辿れるノードを集めて、そのノードだけで逆向きのグラフを作って、トポロジカルソートです。 // Prerequisites #![allow(non_snake_case)] use std::collections::{HashSe…
https://atcoder.jp/contests/abc315/tasks/abc315_d題意どおりに組めばいいだけですが、Rustだとめんどうですね。 // Magical Cookies #![allow(non_snake_case)] use std::collections::HashMap; //////////////////// library //////////////////// fn re…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_brしらみつぶしでも十分速いのですが、O(1)でも計算可能です。 の条件だと、正三角形の領域になります。ここでN以下という条件をつけると、NがX-2より小さければ、正三角形の頂点…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_brしらみつぶしで十分速いです。 // How Many Ways? #![allow(non_snake_case)] use std::cmp::min; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mu</t:>…
https://atcoder.jp/contests/math-and-algorithm/tasks/typical90_y1011まであるので、しらみつぶしできないと思えるかもしれませんが、そうでもありません。数字を入れ替えただけなら同じ積になるからです。例えば、113、131、311は同じです。重複組み合わ…
https://atcoder.jp/contests/abc314/tasks/abc314_e必要な残りのポイント数を状態、支払金額を値にしてDPすればよいです。 ただ、Sが0のときは注意が必要ですね。 ですが、例2でルーレット2を選んだとき(m > 0)、 なので、 となります。 // Roulettes #![al…
https://atcoder.jp/contests/abc314/tasks/abc314_d1が続く間は、変えた位置を記録しておきます。2か3が出てくるとそれをリセットします。最後に、全体を大文字か小文字にしますが、記録していた位置だけは大文字、小文字を変えずにそのままにします。 Rust…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_byを判定すればよいですが、でなければが大きいならを掛けていけばそのうちを超えます。 // Log Inequality 2 #![allow(non_snake_case)] //////////////////// library /////////…
https://atcoder.jp/contests/math-and-algorithm/tasks/arc107_a ですね。 // Simple Math #![allow(non_snake_case)] //////////////////// constants //////////////////// const D: u64 = 998244353; //////////////////// library ////////////////////…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bq ですね。 // Simple Math Easy #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::std</t:>…
https://atcoder.jp/contests/abc313/tasks/abc313_e1より大きい数字が2つ続くと明らかに終わらないので、1のブロックと1より大きい数字が交互に現れるという前提にします。また、最初に1より大きい数字が現れたとき、最初の数字は固定されるので、最初の数…
https://atcoder.jp/contests/abc313/tasks/abc313_dのとき、 とすれば、上下の差を取ると、1と2、2と3、1と4、4と5が逆になっているか否かが分かります。ジャッジシステムの問題を初めて解いたのですが、どう書けばいいか分かりにくいし、デバッグもふつう…