2023-01-01から1年間の記事一覧
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が逆になっているか否かが分かります。ジャッジシステムの問題を初めて解いたのですが、どう書けばいいか分かりにくいし、デバッグもふつう…
https://atcoder.jp/contests/abc312/tasks/abc312_dDPですね。'('が出てきたら右に進んで、')'が出てきたら上に進みます。'?'ならどちらにも進めます。 // Count Bracket Sequences #![allow(non_snake_case)] use std::cmp::min; //////////////////// con…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bp0からはじめて、(が来たら+1、)が来たら-1として、負になったらアウトです。 // Parentheses Check #![allow(non_snake_case)] //////////////////// library /////////////////…
https://atcoder.jp/contests/abc311/tasks/abc311_d進める方向すべてに進めばいいだけですね。 // Grid Ice Floor #![allow(non_snake_case)] use std::collections::BTreeSet; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mu</t:>…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bo積のほうから求める方法もありますが、手間がかかりますね。 // Two Conditions #![allow(non_snake_case)] use std::collections::HashMap; //////////////////// library ////…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bo三重に回せばいいので余裕で間に合います。 // Two Conditions #![allow(non_snake_case)] use std::cmp::{min, max}; //////////////////// library //////////////////// fn r…
https://atcoder.jp/contests/math-and-algorithm/tasks/panasonic2020_cならNoです。 そうでないとき二乗して、 これが成り立つかを計算します。 // Sqrt Inequality #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr></t:>…
https://atcoder.jp/contests/abc310/tasks/abc310_fDPで今の和の集合を状態とします。この集合を整数で表しますとよいです。ただし、10より大きい和は無視してよいです。0は必ずあるので、この状態の整数は奇数になりますが、10を含む状態を0で表せば、1023…
https://atcoder.jp/contests/abc310/tasks/abc310_eDPですね。でを固定したとき、0になるものと1になるもののカウントしたものを状態と考えて、の状態を計算します。 // NAND repeatedly #![allow(non_snake_case)] //////////////////// library /////////…
https://atcoder.jp/contests/abc310/tasks/abc310_dしらみつぶしすればよいです。選手を1から順にチームに配置しますが、左に空いているチームを作らないように配置します。ここで、チームの選手の集合をビットを使うと書きやすいです。 // Peaceful Teams …
https://atcoder.jp/contests/abc309/tasks/abc309_d2つグラフを作って、それぞれ最長距離を求めます。 // Add One Edge #![allow(non_snake_case)] use std::collections::VecDeque; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { l</t:>…
https://atcoder.jp/contests/math-and-algorithm/tasks/typical90_nAとBの両方をソートして距離を取ります。 // We Used to Sing a Song Together #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut </t:>…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bn終了時刻でソートすればよいです。 // Interval Scheduling Problem #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut </t:>…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bm倍数、倍数の関係になっているので、上位の札から枚数を数えていくだけですね。 // Bill Changing Problem #![allow(non_snake_case)] //////////////////// library //////////…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_blダイクストラ法ですね。 // Difference Optimization 2 #![allow(non_snake_case)] use std::collections::BinaryHeap; //////////////////// library //////////////////// fn …
https://atcoder.jp/contests/abc308/tasks/abc308_eAの組合せで分けて考えると楽になります。 // MEX #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().rea</t:>…
https://atcoder.jp/contests/abc308/tasks/abc308_dグラフにして、最初と最後が繋がっているかを調べます。 // Snuke Maze #![allow(non_snake_case)] use std::ops::{Add, Sub}; use std::collections::HashMap; //////////////////// library ///////////…
https://atcoder.jp/contests/math-and-algorithm/tasks/abc139_dをで割った余りと考えると、少しわかりやすいです。ならとしたときが最大です。と考えていくと簡単です。 // ModSum #![allow(non_snake_case)] //////////////////// library //////////////…
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 #![allow(non_snake_case…
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 #![allow(non_snak…