https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bxランダムにグラフを作ります。1点から少しずつエッジを追加していきます。次に進むノードが既存のノードか新規のノードかを確率で選びますが、新規ノードの確率を少しずつ減らし…

https://atcoder.jp/contests/abc321/tasks/abc321_fこの手の場合の数は母関数です。 として、の係数が場合の数です。 このコードだと、下9桁を答えるでも成り立ちますね。 // #(subset sum = K) with Add and Erase #![allow(non_snake_case)] ////////////…

https://atcoder.jp/contests/abc321/tasks/abc321_e2進で考えるとよいです。 始点から上と下に分けて考えます。上は一つ上がって、そこから今来たノードと違うノードの下を探ります。Kが大きければさらに上も見ます。下はKが大きすぎるときに注意が必要です…

https://atcoder.jp/contests/abc321/tasks/abc321_dAは昇順、Bは降順にして、Bの累積を計算しておいて、しゃくとり法っぽく計算します。 // Set Menu #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let m</t:>…

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bw点数がつくだけなのでどうやってもいいですが、正六角形上に並べた方が正方形に並べるよりは効率がよいので、中心を適当に変えて100個並べられて最も大きな半径を求めます。 よ…

https://atcoder.jp/contests/math-and-algorithm/tasks/arc117_c手を動かした方がいい問題ってありますよね。 B → 0, W → 1, R → 2 と読み替えて、下がxとyだった時に上をf(x, y)と表すと、 f(0, 0) = 0 f(0, 1) = 2 f(0, 2) = 1 f(1, 0) = 2 f(1, 1) = 1 f…

https://atcoder.jp/contests/arc165/tasks/arc165_aNが素数か素数べきならNoだとすぐにわかります。それ以外なら、和のほうで足りない分を1で埋めればいいだけです。 // Sum equals LCM #![allow(non_snake_case)] //////////////////// library //////////…

https://atcoder.jp/contests/abc320/tasks/abc320_f0からたどっていけば、座標と残り燃料を状態にして、金額最小を記憶するDPにすればよさそうですが、復路で給油できるかどうかわからないのでどこで給油したのか記憶しなければいけません。しかし、そうす…

https://atcoder.jp/contests/abc320/tasks/abc320_eそうめんが流れてくるのと人が戻ってくるのをイベントとして、PriorityQueueに突っ込みます。ただ、そうめんが流れてくるイベントと人が戻ってくるイベントを別構造体とすると、なかなか大変です。結局、p…

https://atcoder.jp/contests/abc320/tasks/abc320_dグラフを作って1からたどります。 // Relative Position #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin</t:>…

https://atcoder.jp/contests/math-and-algorithm/tasks/typical90_o選んだボールの1、選ばれなかったボールを0と表すと、例えばN=5で1と4が選ばれたら、10010と表現できます。 出力例を見ると、下のほうは差が等差数列になっていて簡単そうですね。一方、k…

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bv という行列を考えると、1秒進めると となります。T秒後には、 となります。 行列の乗算、べき算のコードをいろんな数値で成り立つようにしてみました。AIが書いてくれるから簡…

https://atcoder.jp/contests/abc319/tasks/abc319_e多くても1～8の最小公倍数しかパターンがないはずなので、最初にそのときの移動時間を計算しておけばよいです。 // Bus Stops #![allow(non_snake_case)] //////////////////// library /////////////////…

https://atcoder.jp/contests/abc319/tasks/abc319_dWが決まれば行数は簡単に決まるので、Wを二分探索すればよいですが、Wを変えても行数が変わらないことがあるのがいやらしいですね。 // Minimum Width #![allow(non_snake_case)] //////////////////// li…

https://atcoder.jp/contests/math-and-algorithm/tasks/typical90_amグラフを作って、1をルートにして木を辿っていくと計算できます。木のルートを端点とする距離とそれ以外の距離とを分けるとうまくいきます。 イジワルな入力で再帰が深くなるようなものだ…

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bu内部の点なら、その点と各辺からなる角度の和が2πや-2πになるはずです。外部の点なら0になります。なお、角度は符号を考えます。これは外積を使うと計算できます。 // Polygon a…

https://atcoder.jp/contests/abc318/tasks/abc318_dNが16以下なのでしらみつぶしでしかもメモ化も使わなくてよいのですが、奇数のときが // Avoid Eye Contact #![allow(non_snake_case)] use std::ops::Add; use std::collections::VecDeque; ////////////…

https://atcoder.jp/contests/abc318/tasks/abc318_eAが同じ位置をまとめて、kが小さいほうから順に計算していけばよいです。 // Sandwiches #![allow(non_snake_case)] use std::collections::HashMap; //////////////////// library //////////////////// …

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bt部分的にエラトステネスの篩を行うのはよくあることですが、1が入っていると処理が難しいので、Lが1なら2から始めることにしました。 // Primes in an Interval #![allow(non_sn…

https://atcoder.jp/contests/math-and-algorithm/tasks/abc204_d2つに分けてトータル時間が半分に近くなればよいですが、どの時間が実現可能かはDPで簡単に分かるので、半分以上で半分に近い実現可能な時間を探せばよいです。 // Cooking #![allow(non_snak…