問題 解法 解答 問題 codingcompetitions.withgoogle.com N が与えられる．N は少なくとも 1 つの桁に 4 を含む自然数．これを自然数 A, B を用いて A + B = N とあらわしたい．ここで，A, B は 4 を含んではならない．どれか 1 つ考えうる A, B を出力する…

問題 解法 解答 問題 atcoder.jp 解法 a_l, a_(l + 1), ... , a_r の平均が K 以上であるには (a_l - K) + (a_(l + 1) - K) + ... + (a_r - K) が 0 以上であればよいので，a_i から K を引いた値で考える．また，a の累積和 a_imos を考えると，a_l ~ a_r …

問題 解法 解答 問題 atcoder.jp 解法 各クエリで与えられる部分文字列を A だけの最も短い文字列にすることを考える．まず，部分文字列中の B を全て AA に変換し，残った A だけの文字列のうち AAA と 3 つ A が並んでいる箇所は空文字列に出来るので出来…

問題 解法 解答 問題 atcoder.jp 解法 次の DP を考える： dp(i, j) := 白いボールを 1 ~ i 番までソートし，黒いボールを 1 ~ j 番までソートしたときの，残っている 2 * N - (i + j) 個のボールをそれぞれの色でソートするのにかかる操作回数の最小値 この…

問題 解法 解答 問題 atcoder.jp 解法 i の偶奇で場合分けする． i が奇数の場合，サイコロの目として出てはいけない組み合わせ（禁止された組み合わせ）は (1, i - 1), (2, i - 2), ... となる．この組み合わせの個数を p とおき，これら 2 * p 個の数のう…

問題 解法 解答 問題 atcoder.jp 解法 まず，s[0] は必ず 1 で s[|s| - 1] は必ず 0 でなければならない．なぜなら，葉に繋がる辺を切れば必ず大きさ 1 の部分木が出来て，どこかの辺で切ったら木全体が２つに分けられるため大きさ |s| の部分木は出来ないか…