Python で解く AtCoder ABC130

2019年6月16日に行われたAtCoder Beginner Contest 130のPython3 での実装例です

A - Rounding

使用テクニック： if文 (if-else)

B - Bounding

使用テクニック： メモ化

跳ねた回数と現在のボールの座標をそれぞれ cnt と D にメモしておきます。 D が X 以下であれば、まだ跳ねることができるため cnt を $1$ 増やします。

C - Rectangle Cutting

使用テクニック： 長方形の重心

方針

長方形の性質として、その重心を通る直線は長方形の二等分線となります。また、二等分線は分割された2つの面積を等しくし、この時に小さい方の面積が最大化されます。

長方形上の任意の点において、常にその点と重心を結ぶ直線を引くことで、1本の二等分線を引くことができます。また、与えられた点が重心であれば複数の二等分線を引くことが可能となります。

　実装

Python では真偽値 (True, False) を整数に変換するとそれぞれ $(1, 0)$ になります。これを利用して分割方法が複数あるかの出力を得ています。(7行目)

D - Enough Array

使用テクニック： 累積和、尺取り法

方針

配列 $A$ の $i$ 番目から $j$ 番目 $(i \leqq j)$ の連続部分列の和は、 $j$ 番目までの累積和から $i-1$ 番目までの累積を引くことで求めることができます。

まず、配列の左端の位置を left として保持し、左端を開始点とした連続部分列の和が $K$ を超える点を right として保持します。配列 $A$ の要素は非負であるため、right よりも右の点を終点とした連続部分列の和は必ず $K$ を超えます。よって、left を始点とした連続部分列の和が $K$ を超える連続部分列の数は $N - right + 1$ となります。

あとは、left を右に1つ動かし、同じことを繰り返します。この時、新しいright の位置は、現在の right よりも必ず右側になります。

以上を再帰的に繰り返すことで計算量 $O(2N)$ となります。

実装

E - Common Subsequence

使用テクニック： 動的計画法(DP), 包除原理

方針

動的計画法により答えを求めます。 $dp _ {i, j}$ を整数列 $S$ の $i$ 番目までと整数列 $T$ の $j$ 番目までに対して、 $S$ の部分列と $T$ の部分列が等しくなる組み合わせの数とします。また、整数列 $S$ の $i$ 番目までの数列を $S _ i$ 、 $i$ 番目の要素を $s _ i$ とします。整数列 $T$ も同様です。

$S _ i$ と $T _ j$ までの整数列で $s _ i \ne t _ j$ であれば、 $S _ i, T _ j$ までの条件を満たす部分列は、 $S _ {i-1}, T _ j$ までの条件を満たす部分列と、 $S _ i, T _ {j-1}$ までの条件を満たす部分列の和集合となります。 $dp _ {i,j}$ はこの和集合の要素数です。
よって、包除原理を用いて dp遷移は次のようになります。

$dp _ {i, j} = dp _ {i-1, j} + dp _ {i, j-1} - dp _ {i-1, j-1}$ $(s _ i \ne t _ j)$

以上に加え、 $s _ i = t _ j$ であったときは、 $S _ {i-1}, T _ {j-1}$ までの条件を満たす部分列の最後に $s _ i (= t _ j)$ を足した部分配列も条件を満たします。また、 $s _ i, t _ j$ のみからなる部分配列も条件を満たします。
よって、この時のdp遷移は次のようになります。

$dp _ {i, j} = dp _ {i-1, j} + dp _ {i, j-1} - dp _ {i-1, j-1} + dp _ {i-1, j-1} + 1$ $(s _ i = t _ j)$

以上の dp遷移を繰り返し、 $dp _ {N, M}$ が求める答えとなります。
この実装の計算量は $O(NM)$ となり、入力条件から計算量の最大値が $4 \times 10 ^ 6$ となります。この計算を Python3 で行うのは厳しいですが、PyPy を使用すれば時間内に計算を終わらせることができます。