AtCoder Beginner Contest 159 の各問題の考察を書いていきます。結果はE完 (4WA) でした。

前回: 競プロ参戦記 #74 Divisible Substring | ABC 158 - Qiita
問題一覧: https://atcoder.jp/contests/abc159/tasks

A - The Number of Even Pairs

問題概要: 偶数が書かれた N 個のボールと、奇数が書かれた M 個のボールがある。2つの異なるボールを選ぶとき、書かれている整数の和が偶数となる場合の数を求めよ。

A: 考察

N 個のものから2つの異なるものを選ぶ場合の数は N(N-1)/2 です。

整数の和が偶数になるのは (偶数)+(偶数) または (奇数)+(奇数) のときです。

したがって、偶数のボールを2つ選ぶ場合の数と、奇数のボールを2つ選ぶ場合の数を足せばよいです。

    N * (N - 1) / 2 + M * (M - 1) / 2

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc159/submissions/11089553

↑の回答では N, M を符号なし整数型 (usize) にしたせいで、オーバーフローを避けるために N=0, M=0 のケースを場合分けしています。符号ありの整数型 (i64) なら場合分けの必要がないので、その方がよかったです。

B - String Palindrome

問題概要: 長さが奇数である文字列 S が与えられる。S が「強い回文」であるか判定せよ。

強い回文の定義: 文字列 S が回文であり、S の前半と後半がそれぞれ回文であるとき、S は強い回文である。

B: 考察

S が回文なら S の後半は前半の逆順なので、S の前半が回文なら S の後半も必ず回文です。そのため、「S が回文」かつ「S の前半が回文」だけ確認すればいいです。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc159/submissions/11087531

C - Maximum Volume

問題概要: 正の整数 L が与えられる。縦、横、高さの和が L に等しい直方体の体積の最大値を求めよ。(縦、横、高さは整数とは限らない。)

C: 考察

3次元だと分かりにくいので、2次元に落として「縦、横の和が L に等しい正方形の面積の最大値」を考えてみます。縦幅を x、横幅を y とすると、x + y = L だから y = L-x であり、面積は f(x) = x(L-x) = xL - x^2 = -(x - L/2)^2 + L^2/4 と表せます。x=L/2 で最大です。

3次元でも同様に、x = y = z = L/3 で最大になります。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc159/submissions/11084992

D - Banned K

問題概要: N 個のボールがあり、i 番目のボールには整数 A(i) が書かれている。各 k = 1, ..., N につき以下のクエリに答えよ。

クエリ(k): k 番目のボールを除く N-1 個のボールから、同じ整数が書かれている2つの異なるボールを選ぶ場合の数を求めよ。

制約: N≤10^5, A(i)≤N

D: 考察

クエリごとに A に関してループを回すような実装をすると、O(N^2) 時間かかって TLE します。

いったん k のことは忘れて、同じ整数が書かれている2つの異なるボールを選ぶ場合の数を求めることを考えます。ボールに書かれている整数ごとにボールを分類し、整数 x が書かれているボールの個数 f(x) を求めます。すべての x について f(x)・(f(x)-1)/2 の総和 S が答えです。

S は k 番目のボールを選ぶ場合を含んでいて、クエリ(k)の解より少し大きいので、その補正が必要です。x = A(k) とすると、整数 x が書かれたボールは f(x) 個ではなく f(x)-1 個なので、総和 S の x に関する項を次のように書き換えます。

f(x)・(f(x)-1)/2 → (f(x)-1)・(f(x)-2)/2

したがって、クエリ(k)の解は以下の式で求まります。

    S - f(x)・(f(x)-1)/2
      + (f(x)-1)・(f(x)-2)/2
    = S - f(x) + 1

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc159/submissions/11112518

E - Dividing Chocolate

問題概要: H×W マスのグリッドがある。各マスは白または黒であり、y 行目 x 列目のマスの色 S(y, x) である。グリッドの辺と平行な、マスの境界を通る直線を1つ選び、グリッドを複数のブロックに分割する、という操作を好きなだけ行う。すべての操作の後、各ブロックに含まれる白のマスがそれぞれ K 個以下になるようにしたい。最小の操作回数を求めよ。

制約: H≤10, W≤1000

E: 考察

例えば H=3, W=3 のグリッドを以下のように分割したとき、数字が同じである範囲が分割後のブロックです。(現実に板チョコを割るときのように、全体を2つに割ってから、片方のブロックだけを半分に割る、といった割り方はできないので注意。)

    1 | 4   4
    --+------
    2 | 5   5
    --+------
    3 | 6   6

グリッドを分割する直線を分割線と呼ぶことにします。水平な分割線 (y = 1, ..., H-1) と垂直な分割線 (x = 1,..., W-1) のうち最も少ない個数を選んで条件 (白がK以下) を満たすのが目標です。

制約に H≤10 とあるので、水平な分割線の選び方は全探索すればよさそうです。

垂直な分割線は貪欲に選べます。例えば上の図で K=3 だとすると、左の3列に含まれる白マスの個数は 4 (> K) なので、3列目より左に分割線が必要です。2列目の左側に分割線を入れるより、3列目の左側に分割線を入れた方が、残りの部分の条件を達成しやすくなるのでお得です。

したがって、x = 1, 2, ..., W-1 について各ブロックの白マスの個数を数えていき、いずれかのブロックの白マスの個数が K を超える直前に分割線を入れる、という手続きにより最適な分割方法を計算できます。

ただし水平な分割線の入れ方によっては、白マスが縦に K 個以上並んでいることがあり、その場合は垂直な分割線をどう選んでも条件を満たせないので注意。

全体として O(2^H・H・W) 時間で間に合います。考察より実装の方が大変かもしれません。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc159/submissions/11119318

F - Knapsack for All Segments

問題概要: 長さ N の整数列 A と、正の整数 S が与えられる。整数 L, R (1≤L≤R≤N) に対して、整数列 (x(i)) (ただし L≤x(1) < ... < x(k)≤R) で ΣA(x(i)) = S となるものの個数を f(L, R) とおく。f(L, R) の総和を求めよ。

制約: N, S, A(i)≤3000

F: 考察

例えば A=(3, 1, 4), S=4 のとき、総和が S に等しい A の部分列は (3, 1) と (4) の2種類があります。

    3 1 4
    ^^^
      ^^^

A の部分列 A(x(i)) に注目すると、この部分列は f(1, 2) と f(1, 3) で2回カウントされるので、全体の総和を +2 しています。

    3 1 4
    [ ]       f(1, 2) += 1
    [   ]     f(1, 3) += 1

同様に、部分列 (4) は +3 しています。

    3 1 4
    [   ]     f(1, 3) += 1
      [ ]     f(2, 3) += 1
        |     f(3, 3) += 1

部分列 A(x(i)) の個数 (正確には x の個数) を (L, R) に関する重複度を込めて数えればよいです。

その前に、L, R のことはいったん忘れて、x の個数を数える問題を考えます。これは DP の典型的な問題です。

A の前から i 個の要素からなる数列 A(..i) に関して、総和が s (≤S) に等しい部分列の個数を dp(i, s) とします。これが求まっているとき、次の要素 A(i) を部分列に含めるケースと含めないケースの2通りを考えることで、dp(i+1, s) が求まります。

    // 疑似コード

    dp(i, s) = 0 for i, s;
    dp(0, 0) = 1;

    for i, s {
        // 部分列に i 番目の要素を含めないケース
        dp(i + 1, s) += dp(i, s);

        // 部分列に i 番目の要素を含めるケース
        dp(i + 1, s + A(i)) += dp(i, s);
    }

最終的に dp(N, S) が解となります。

さて、L, R に関する重複を含めて x を数えるには、代わりに (L, R, x) を数えればよいです。上記と似た DP で解けます。

s=0 のケースは、上記の DP では x=() しかありませんでしたが、いま L は自由なので (L=i, x=(), R=未定) の N 通りがあります。dp(i, 0) = 1 です。

遷移としては、上記と同じく「i 番目の要素を x に加える・加えない」の遷移に加えて、R=i に遷移する道も考えます。R=i に遷移した後、x に要素を加えることはできないので (x≤R だから)、R=i に遷移したら行き止まりです。そのため総和が S であるような (L, x, R=未定) から (L, x, R=i) への遷移だけ見ればよいです。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc159/submissions/11179659