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

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

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