https://atcoder.jp/contests/abc303/tasks/abc303_dCaps LockがOffとOnの2状態でDPします。 // Shift vs. CapsLock #![allow(non_snake_case)] use std::cmp::min; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = Str</t:>…
https://atcoder.jp/contests/math-and-algorithm/tasks/abc167_d全く予期していなかったのですが、この問題の解法は問題59と完全に同じです。この問題も、ある状態から一意に次の状態に進むことができますが、後ろに一意に戻れるかわかりません。 このため…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_baある状態について、次の状態が全て必勝ならその状態は必敗、次の状態に一つでも必敗があれば必勝です。 1は必敗、2は次の状態の1が必敗なので必勝、3は次の状態の2が必勝なので…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_az4の剰余を取るだけですね。 // Stones Game 1 #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new();</t:>…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_ayべき乗の計算をするだけですが、それでは芸がないので、周期を求めます。こうすると計算量が減る可能性があります。2のべきで10の剰余を取りますが、2と10が互いに素でないので…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_ax届くかと偶奇の判定だけですね。 // Move on Squares 1 #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = Strin</t:>…
https://atcoder.jp/contests/abc302/tasks/abc302_eQueryをenumにして、matchで分けるときれいに書けますね。 HashMapでborrowするとややこしいことになりますね。 // Isolation #![allow(non_snake_case)] use std::collections::{HashMap, HashSet}; ////…
https://atcoder.jp/contests/abc302/tasks/abc302_dAと同じか小さい一番大きなBを尺取り法で探します。逆もやります。 // Impartial Gift #![allow(non_snake_case)] use std::cmp::max; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T</t:>…
https://atcoder.jp/contests/abc301/tasks/abc301_eSとGとお菓子マスの距離のグラフにします。そして、グラフをたどっていって、今の位置と今までたどった位置を状態とみなし、その状態の最短距離を求めます。ただ、間に合わないので、各ステップで状態数を…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_awこれは状態遷移の問題ですね。タイルを左上から並べていきます。すなわち、最もタイルが左にある高さにタイルを敷き詰めます。こう決めることによって、タイルを並べる順番が一…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_av とおけば、なので、行列表示にすると、3×3の行列になるだけで、あとは同じです。 // Recurrence Formula 2 #![allow(non_snake_case)] //////////////////// constants ///////…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_au行列が変わるだけですね。 // Recurrence Formula 1 #![allow(non_snake_case)] //////////////////// constants //////////////////// const D: i64 = 1000000007; ///////////…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_atとすると、と書けます。これを行列表示にすると、とおくと、だから、となります。あるいは、と書けます。 // Fibonacci Hard (mod 1000000000) #![allow(non_snake_case)] /////…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_as を使ってもよいですが、行列などで割り算ができないこともあります。そういう時は繰り返し2乗法のように和を取る方法が使えます。などと再帰的に求めればよいです。 // Sum of …
https://atcoder.jp/contests/math-and-algorithm/tasks/abc145_d(1, 2)方向にx歩、(2, 1)方向にy歩進んで(X, Y)に到達するとすると、 となるので、xとyが0以上の整数になればよいです。しかし、一方が整数になればもう一方も整数になるので、X + Yが3の倍数…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_ar単なる組合せですね。 // Combination Hard #![allow(non_snake_case)] //////////////////// constants //////////////////// const D: i64 = 1000000007; ///////////////////…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_aq繰り返し2乗法というやつですね。 // Power #![allow(non_snake_case)] //////////////////// constants //////////////////// const D: u64 = 1000000007; ///////////////////…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_apまでなので、の解法で十分ですね。 手元ではPythonのような、 (a, b) = (b, (a + b) % D) というコードが通りましたが、AtCoderでは通りませんね。 // Fibonacci Easy (mod 1000…
https://atcoder.jp/contests/abc300/tasks/abc300_e例えば6なら、確率をで表すとすると、 なので、 となります。一般には、 と書けます。メモを関数の外に持つのはクレートを使わないと難しそう。 // Dice Product 3 #![allow(non_snake_case)] use std::co…
https://atcoder.jp/contests/abc300/tasks/abc300_dしらみつぶしで十分ですね。 エラトステネスの篩を実装してみました。 // AABCC #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String:</t:>…
https://atcoder.jp/contests/math-and-algorithm/tasks/arc084_b最初に、2と5の素因数があれば5と2を掛ければ10のべき乗になるので排除できます。例えば、12なら25を掛けて300なので、3を考えればよいです。 29を考えてみましょう。100000000000001が29で割…
https://atcoder.jp/contests/abc299/tasks/abc299_e最初に全部黒にして、dより内側は全て白くします。そこで、dのところが全て白でないかを調べます。簡単そうですが、トラップがあります。 // Nearest Black Vertex #![allow(non_snake_case)] use std::co…
https://atcoder.jp/contests/abc299/tasks/abc299_d最初が0で最後が1と決まっているのがポイントですね。あとは二分探索で。 // Find by Query #![allow(non_snake_case)] use std::cmp::min; //////////////////// library //////////////////// fn read<T: std::str::FromStr>()</t:>…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_aoグラフをたどるだけですね。 // Bipartite Graph #![allow(non_snake_case)] use std::collections::HashSet; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -></t:>…
https://atcoder.jp/contests/math-and-algorithm/tasks/abc007_3PointをGenericを使って書くととたんに難しくなりますね。 幅優先探索のQueueは、VecDequeを使います。 // 幅優先探索 #![allow(non_snake_case)] use std::ops::{Add, Sub}; use std::collec…
https://atcoder.jp/contests/abc298/tasks/abc298_e単なるDPですが、Dを法とした逆数を求めなければなりません。拡張ユークリッド互除法ですね。一度書けば終わりですが。 // Unfair Sugoroku #![allow(non_snake_case)] use std::cmp::min; //////////////…
https://atcoder.jp/contests/abc298/tasks/abc298_d剰余を用意して、1なら10倍して足して、2なら数字×10のべき乗を引けばいいのですが、Rustには負数の剰余を取ると負になるというトラップがありますね。 // Writing a Numeral #![allow(non_snake_case)] /…
https://atcoder.jp/contests/math-and-algorithm/tasks/typical90_bzそのままですね。 RustのIteratorにはcountがあるのがいいですね。 // Easy Graph Problem #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> </t:>…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_an各辺の距離を1として、ダイクストラ法を使えばよいです。 PriorityQueueは、BinaryHeapで実装できます。 // Shortest Path 1 #![allow(non_snake_case)] use std::collections::…
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_am連結成分に分けるコードとだいたい同じです。 グラフの隣接ノードを追加するのに、get_mutを使うと便利ですね。 // Depth First Search #![allow(non_snake_case)] use std::col…
