問題概要 C - Switches 解法(解説AC) bit全探索を行う。 この問題系は虚無でbit全探索も判定も書けるようにしたい。 提出コード readl= lambda: list(map(int, sys.stdin.readline().split())) readt= lambda: tuple(map(int, sys.stdin.readline().split())…

問題概要 グループに所属する数を数えよ Problem - C - Codeforces 解法 サイズ付きUnionFindを用いる。 が、(10^5) * 5はPythonだと相当きつい。 PyPy3を用いたが、Input関数を止めてsys.stdin.readlineで高速化しない無理だった。。。 参考 www.kumilog.ne…

問題概要 Problem - B - Codeforces数列aが渡される。 1≤i,j≤nとしたとき、 k*|i−j|≤min(ai,aj)を満たすkを答えよ 解法 k = ai / max(i, n- i)を全て試せばよい。例えば、Nを9としたとき |i-j|の最大値は数列aiから 0 1 2 3 4 5 6 7 8 (要素)と並べたとき 8 …

問題概要 A - Darker and Darker H*W列内に".", "#"が存在する。 存在する#を起点に十字で.を#に置き換える。 上記を繰り返したときに、何回目で全てのマスが埋まるか答えよ。 解法 "."→"#"に置き換えたところをqueueに入れ、幅優先探索で置き換えていけば良…

問題概要 C - オセロ N個の文字列(初期値0i0i+1...0i+N)に対して、範囲を指定すると対象の要素が1⇔0と反転する。 範囲指定をQ回行った時、Nの文字列を答えよ。 解法 範囲指定の積み重ねの結果で表裏が決まるため、Imos法で解ける。 提出コード n, q = map(in…

問題概要 D - Number of Amidakuji あみだくじ。 0本目からスタートし、W本の長さH + 1までにを任意の線を引いた時 K本目にたどり着くパターンは何パターンあるか答えよ。 解法(解説AC) 現在の位置状態での線の引き方を全列挙し、DP(メモ化再帰)を用いて答え…

問題概要 C - /\/\/\/ 数列Aに対して、偶数列を任意の値a, 奇数列を任意の値bの2種類のみに置き換える時 最小で何か所置き換えれば条件を満たせるか答えよ。 ※ただし、値a, 値bは異なる値とする 解法 偶数列、奇数列から、それぞれ1番目に多い値(a1,b1)と2番…

問題概要 E - 放課後 解法 0 →Di → Di+1...Di+B→Nの間でどれだけAの区間が得られるか数えればよい。 数えた結果、Dに到達していれば0、Dに到達していなければ 必要なAの区間の個数が解となる。 提出コード typedef long long ll; typedef unsigned long long…