数学

AGC039 C - Division by Two with Something

問題 atcoder.jp 解法 各操作を観察すると、どちらも「最も下のビットをpopして反転して最も上にpushする」と言い換えられる。これをN回繰り返すと元の数のビットを反転させたものが得られるので、2N回繰り返すと必ず元の数が得られる。よって繰り返して元の…

AGC038 C - LCMs

問題 atcoder.jp 解法 mobile.twitter.com自分の学習のために式を書き直してみたが全く同じになってしまった……ここで とすると なので コード use mod_int::ModInt; const MOD: usize = 998244353; fn main() { let s = std::io::stdin(); let mut sc = Scan…

Project Euler 679 Freefarea

問題 projecteuler.net長さ n で A, E, F, R からなる文字列のうち、4つのキーワード FREE, FARE, AREA, REEF を各1回ずつ含むものはいくつあるか。n=30について求めよ。 解法 全ての文字列を陽に持つ必要はなく、(各キーワードを持っているかどうか, 接尾辞…

AtCoder Beginner Contest 136 F - Enclosed Points

問題 atcoder.jp 解法 各点について、自分の (左上、右上、左下、右下) にある点の数を数える。これは 座標圧縮 => Fenwick Tree で O(N logN) でできる。各点について、その点を含まない長方形の数は以下の合計である。 右下の空でない点集合の数 * 右上の…

エクサウィザーズ 2019 D - Modulo Operations

問題 atcoder.jp 解法 解説にあるとおり、ある数が使われた後、その数より大きい数を使ったとしても剰余には影響しないので、大きい数から順番に見ていって数列に詰めていくことを考える。i番目(0 コード const MOD: usize = 1e9 as usize + 7; fn main() { …

エクサウィザーズ 2019 E - Black or White

問題 atcoder.jp 解法 毎回 (i個目を取る時に白が無くなっている確率) + (i個目を取る時に白も黒も無くなっていない確率)/2 を出力する。 (i 個目を取る時に白が無くなっている確率) = (i-1個目を取る時に白が無くなっている確率) + (i-1個目で最後の白を取…

ARC094 D - Worst Case

問題 beta.atcoder.jp 解法 が全て より小さくなるような x、すなわち、 となるような x の最大値を求めたい。 で x は a より大きいとすると、 を満たす x を求めれば良い。 コード /// Thank you tanakh!!! /// https://qiita.com/tanakh/items/0ba42c7ca3…

CODE FESTIVAL 2018 qual B E - Game of +-

問題 beta.atcoder.jp 解法 を足したり引いたりしてを作る。 を足したり引いたりして 1 を作る。 にすることを目指すのではなく にすることを目指す。 であることは である。 なので、各 p について独立に考えればよいということになる。 コード /// Thank y…