ABC-only 回です。E完でした。
AtCoder Beginner Contest 130
- この連載記事では、着手した問題の考察を自分なりに書いていきます。
- 問題の詳細は問題一覧を参照してください。
A - Rounding
問題概要: 非負整数 X, A (≤9) が与えられる。X が A 未満のとき 0 を出力し、A 以上のとき 10 を出力せよ。
A: 考察
実装に使う言語の分岐や比較の構文を確認しましょう。
if X < A { 0 } else { 10 }
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc130/submissions/5957469
B - Bounding
問題概要: 数直線上でボールが N+1 回弾んだ。i 回目に弾んだ位置を x = D(i) とするとき、以下の式が成り立つことが分かった。0≤x≤X の領域で弾んだ回数を求めよ。
式:
- D(1) = 0
- D(i) = D(i-1) + L(i-1) (ただし i≥2)
B: 考察
実際にループを回して D(i) の値をすべて求めて、X 以下か否かを判定すればよいです。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc130/submissions/5958136
C - Rectangle Cutting
問題概要: 平面上に長方形 (0, 0)..(W, H) がある。点 P(x, y) が与えられる。点 P を通る直線で長方形を2つの部分に分割するとき、面積の大きく ない 方の面積の最大値を求めよ。また、最大値を実現する直線がちょうど1つであるかを判定せよ。
制約: 点 P は長方形の内部または周上
C: 考察
中心を通る直線で二分割された長方形の面積は二等分されます。2つの部分が合同だからです。そのため、P と中心を通る直線を引けば、「大きくない方」の面積を最大化できます。逆に、他の直線では二等分になりません。そのような直線が複数存在するのは P と中心 (W/2, H/2) が一致するときに限ります。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc130/submissions/5955272
D - Enough Array
問題概要: 長さ N の正の整数列 A と、整数 K が与えられる。A の連続する部分列で、総和が K 以上であるものの個数を数えよ。
制約: N≤10^5
D: 考察
連続する部分列は O(N^2) 通りあるので、すべて列挙して総和が K 以上か判定する方法では間に合いません。
A が正の整数列であることに注目します。ある連続する部分列の総和が K 以上なら、その部分列を含む他のすべての部分列の総和も K 以上であることが分かります。
例えば A=(3, 1, 4, 1, 5), K=5 とします。A の連続する部分列 (1, 4) は総和が 5 以上なのでカウントできます。この部分列を含む (1, 4, 1), (1, 4, 1, 5) も総和が 5 以上です。
このことを踏まえて部分列を先頭の位置 l ごとに分類して数えることを考えます。部分列の先頭の位置 l に対して、範囲 l..r の総和が K を超える最小の r を R(l) と表すことにすると、求める総和は Σ N-R(l)+1 で表せます。
このままでは O(N^2) になってしまいますが、しゃくとり法というよくある手法を使えば R(l) が高速に求まるので、全体で O(N) 時間になって間に合います。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc130/submissions/5963219
なお提出したコードでは「以上」の代わりに「未満」の部分列を列挙して総数から引くという回り道をしていますが、大筋は同じです。
E - Common Subsequence
問題概要: 整数列 S, T が与えられる。S と T からそれぞれいくつかの要素を取り出して、部分列のペアを作ることを考える。2つの部分列が一致するような要素の選び方を数えよ。
制約: |S|, |T| ≤ 2×10^3
E: 考察
数列だと分かりにくいので、文字列ということにします。
例えば S=ab, T=aa なら、部分列が一致するような選び方は3通りあります。
- S, T からどの要素も取り出さない (部分列は "")
- S の1文字目の a を取り出し、T の 1 文字目の a を取り出す ("a")
- S の1文字目の a を取り出し、T の 2 字目の a を取り出す ("a")
- S から b を取り出すケースでは部分列が一致しない (T から b を取り出せない) ので、他の選び方はない
もう少し実践的な具体例をみます。S=abca, T=bca として、短い部分列のペアから数えていきます。
- 長さ 0 の部分列 ("") は1個
- 長さ1の部分列は、ペアとして "a" が2個、"b" が1個、"c" が1個 (合計 4)
- 長さ2の S の部分列は ab, ac, aa, bc, ba, ca の6通りで、T の部分列は bc, ba, ca の3通り。一致するのは bc, ba, ca の3つ
- 長さ3の部分列は "bca" の1個
さて、「最長共通部分列」という有名な DP 問題があります。この問題の解法 (詳細略) が今回の問題に応用できそうなので、試してみましょう。
一致する部分列の最後の1文字を取り除いたものも一致する部分列である、ということに注目します。
例えば S=abca, T=bca には一致する部分列 ba, ca, bca が含まれますが、最後の a を除去した b, c, bc も一致する部分列の選び方です。
- b → ba
- c → ca
- bc → bca
つまり、S, T から取り出す最後の文字が a であるような選び方の個数は、 S, T の a より前の部分から一致する部分列を選ぶ方法の個数 と等しいです。
いかにも DP できそうなので、DP 表の設計を考えます。上の強調部分が簡単に計算できるような表がよいです。 (注釈: S(..n) は S の前から n 文字の範囲という意味)
- dp(si)(ti) = n : S(..si) と T(..ti) から文字を取り出して部分列のペアを作るときに一致する場合の数が n 通り
こうすると、例えば末尾の文字 a が S, T のそれぞれ si, ti 番目に出現するとき、a を末尾にする選び方は dp(si)(ti) になります。
初期状態は「空文字列が1個」です。
- dp(i)(0) = 1
- ti=0 のケースでは T から文字を取り出せないので、空の部分列だけ選べる
dp(0)(0) = 1 は明らかですが、dp(1)(0) = 1 も成り立つことに注意。S, T の範囲をどのように絞り込んでも空文字列の選び方があるので、dp(si)(ti) の値が 1 を下回ることはありません。
次に遷移として、文字 c = T(ti) が部分列の末尾になる選び方を考えます。
c = S(si) = T(ti) となる si があるとします。前述の通り、S(..si), T(..ti) の範囲からの一致する部分列の選び方が dp(si)(ti) 通りあるので、範囲に同じ文字 c を加えた状態である、遷移先 dp(si+1)(ti+1) の値はそれだけ増えます。
さらに、すべての dp(si+i)(ti+1) (i≥1) についても、同じだけ場合の数が増えます。いまカウントした、末尾が c になる新しい部分列の選び方はすべて dp(si+i)(ti+1) でもカウントできるからです。
すべての文字 c=T(ti) の出現について上記の遷移をすればよいです。
全体の計算量は以下のように O(N^3) (ただし N=|S|+|T|) であり、このままでは間に合いません。
- ti (< |T|) についてループ
- その中で S から文字 c=T(ti) を探すループ
- その中で dp(si+i)(ti+1) への更新をするループ
3つ目のループを imos 法によって省略すると、O(N^2) にできます。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc130/submissions/5977778