問題概要 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…

問題概要 Problem - B - Codeforces5つの正方形からなる十字型を n * nからなる四角形内の空いている箇所に当てはめたとき 四角形の空きが全て埋まるとき、YES、埋まらないときはNOを出力せよ。 解法 上の段から、下に向かって十字型が埋まるか貪欲に見れば…

問題概要 D - Cake 123 X 種類、Y 種類、Z 種類の3つの種類に重みがついている。 3種類の組み合わせで重みの合計が高い順にK個出力せよ。 解法(解説AC) X, Y, Zをソートしておき、 Priority Queueへ最も高い重みの合計を放り込んでおく。 最も高い重みのi, j…

問題概要 Problem - B - Codeforces 1から9までのn桁からなる数値を1から9までの各桁に対応したMAPに置き換えることができる。 1から9までのn桁からなる数値から特定の範囲を抜き出して置き換えた際に最大となる数値を答えよ。 ただし、特定の範囲は1度しか…

問題概要 D - Flipping SignsN個の数列Aに対して、任意(i 数列Bを作成する。作成したsum(数列B)が最大となる値を答えよ。 解法(解説AC) 正負判定を行い、負の値が偶数個の場合全て正の値にすることが可能。 負の数が奇数個の場合、任意の値を1つだけ負の値に…

問題概要 C - GCD on Blackboard N個の数列Ai, Ai+1, Ai+2...のうち、任意の1つのみの数値を0～10^9の任意の値に 置きかえた際に数列全体の最大公約数として考えられる最大値を求めよ 解法(解説AC) けんちょんさんの記事を参考にした。 AtCoder ABC 125 C - …

新年あけましておめでとうございます。目標を立てても基本達成できないことが多いのですが 去年は色々な方と出会う機会があり、今年は少し頑張ってみようと思いました。なので、今年はブログ100記事程書けたら良いなと思っています。 (努力目標)