106. 昨日と今日解いた問題（2022.04.19）

問題一覧

E - K-colinear Line (Diff: 1292)
E - Chain Contestant (Diff: 1413)

自分の解法など

E - K-colinear Line

前回ABCのE問題。普通にアプローチを知らなくて解けなかった系なので、じっくり考えながら進めました。

問題のアプローチについて

まず、幾何の問題は（演算の簡潔さ・使える道具の数から）ベクトルに落とし込むことが多いようです。というわけで、2 点 $A, B$ を通る直線は、実数 $k$ を用いて $\overrightarrow{OA} + k\overrightarrow{AB}$ と表現します。これを整理すると、 $A \neq B$ という前提で、 $(x_B - x_A)(y - y_A) = (x - x_A)(y_B - y_A)$ という方程式が出てきます。これを満たす $(x, y)$ は直線上に乗っています。また、入力は全て整数なので、整数で判定を完結できます。これで誤差を考える必要はなくなりました。

今回は $N \le 300$ なので、「2 点の組」を全て走査して直線を作った上で、全ての点を走査してその直線上に乗っているかの計算を行っても間に合います。つまり、 $O(N^3)$ で解くことにします。

直線の表現について

3 つ以上の点が同一直線上に乗っている場合、先ほどの解き方では重複した直線が出てきます。問われていることを考えると、重複したものは弾く必要があります。ここで直線を表現する方法が問題になります。

先ほどの方程式をもう一度整理すると、 $x_A \neq x_B$ のとき、傾き $\displaystyle \frac{y_B - y_A}{x_B - x_A}$ 、切片 $\displaystyle \frac{-x_A y_B + x_B y_A}{x_B - x_A}$ であることが分かります。よって、これらを直線の情報として扱えばよさそうです。

しかし、誤差の問題から浮動小数点数はなるべく扱いたくないです。そこで、既約分数にして分子・分母を整数で保持することで、整数 4 つで直線を表現することを考えます。 $a = y_B - y_A, b = -x_A y_B + x_B y_A, c = x_B - x_A$ として、2 点 $A, B$ を通る直線は、

$x_A \neq x_B$ のとき、 $\displaystyle \left( \frac{a}{\gcd(a, c)}, \frac{b}{\gcd(b, c)}, \frac{c}{\gcd(a, c)}, \frac{c}{\gcd(b, c)} \right)$
$x_A = x_B$ のとき、 $\displaystyle ( x_A, x_A, 0, 0 )$

と表現できます。これを Tuple として表現します。C# では Tuple は HashSet や Dictionary のキーに使えるようなので、HashSet で持っておけば重複チェックできます。

この問題の教訓としては、

幾何はベクトルで考えたい
なるべく浮動小数点数を使わないようにする
直線の表現方法、有理数は既約分数にすればいい感じに扱える
Tuple って HashSet や Dictionary のキーにできたんだ…

という感じです。めちゃくちゃ収穫が多かったです。

E - Chain Contestant

発想10分ほど、実装1時間ほど…。

問題文がややこしいので、問われていることをしっかり理解するところから。入力例 1 を見ると 13 通り。長さ 4 の入力に対して全ての選び方は 15 通り（ $2^4 - 1$ ）なので、BGB と BGBH のみがダメだということがわかります。つまり、BGH や GBH はよいです。

とりあえず DP っぽいです。1 文字ずつ見ていくとして、今までに採用していない文字であれば取ることができます。ということは、「ある文字が今までに採用されているか」が状態の 1 つで、これはビットで表現すればよさそうです。扱うのは 10 文字なので、 $2^{10} = 1024$ の状態数です。また、「今までに採用した文字」であっても「直前に採用した文字」であれば取れます。これも状態に加えます。いわゆる bitDP の問題です。

DPテーブルの定義は、

$dp[i文字目まで見た, 今まで採用した文字(bit表現), 直前に採用した文字] := 通り数$

です。 $(N + 1) \times 2^{10} \times 11$ の状態数なので大丈夫そうです。なお、直前に採用した文字が無い場合はインデックス 10 を利用することにします。よって、初期状態は $dp[0, 0, 10] = 1$ 、それ以外 $0$ です。

この問題で難しいのは遷移で、ちゃんと頭を整理して考える必要があります（ここに50分くらいかかりました）。 $i$ 文字目を見ているとして、

「採用しない」選択はいつでもOK
- $dp[i, j, k] = dp[i-1, j, k]$
文字目が今まで採用した文字に含まれないなら、「採用する」選択はOK
- $dp[i, j \; or \; 2^{S_i}, S_i] = dp[i-1, j, k]$
文字目が今まで採用した文字に含まれないなら、最後に採用した文字が等しい場合のみ「採用する」選択はOK
- $dp[i, j, S_i] = dp[i-1, j, S_i]$