https://atcoder.jp/contests/abc303/tasks/abc303_e最初にグラフを作るのではなく、エッジから直接次数が2より大きいノードを選んで、そのエッジを取り除いてグラフを作ります。 // A Gift From the Stars #![allow(non_snake_case)] use std::collections:…

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:>…