Panasonic Programming Contest 2023（AtCoder Beginner Contest 301）G問題メモ

Panasonic Programming Contest 2023（AtCoder Beginner Contest 301）

EとF、GとExの得点が微妙に異なるようになった。

G - Worst Picture

• 3次元座標上に $N$ 人、$i$ 番目の人は $(X_i,Y_i,Z_i)$ にいる
  • 全ての人は、$x$ 座標で正の位置にいる（$X_i \gt 0$）
• $x \lt 0$ の好きな位置 $p$ から写真を撮る
• $p,(X_i,Y_i,Z_i),(X_j,Y_j,Z_j)$ がこの順に一直線に並ぶとき、かつその時に限り、人 $j$ は人 $i$ に隠れて見えなくなる
• 最も写真に写る人数が少ない（隠れる人が多い）場合の、写る人数の最小値を求めよ
• $1 \le N \le 50$
• $1 \le X_i \le 1000$
• $|Y_i|,|Z_i| \le 1000$
• 実行時間制限 4sec.

3次元座標における直線処理と、有理数の正確な一致判定。

3次元座標に慣れていないと時間がかかるだけであって、やることはさほど複雑ではない。
（コンテスト本番では、100分しかない上に、他にも実装が重たい問題があったので、解答者がめちゃ少なかったけど）

Pythonなら、有理数を分数として正確に扱うには、fractionsモジュールが使える。
通常のintやfloatと比較するとそこそこ重たくはなる。

• fractions --- 有理数 — Python ドキュメント

まず、$X_i$ が全て同じ場合は隠れるのが不可能なので $N$。それ以外を考える。

• 全2点間を通る直線を列挙する
  • $p$ はこれらの直線上のどこかになる
  • 3人以上が同じ直線上にいるかもしれないので、直線は同じものは同じと判定できるようにし、直線毎に隠れる人数を数える
• 列挙した直線から、全2直線間の交点を調べる
  • $x \lt 0$ で交わる場合、そこを $p$ にすればその2直線で隠れる人数を同時に隠せる
  • この場合も、3直線以上が交わる点があるかもしれないので、交点が同じものは同じと判定できるようにし、交点毎に隠れる人数を数える
• 「1直線で隠せる人数の最大」または「2直線以上の交点から隠せる人数の最大」が、全体的な隠せる人数の最大
  • $N$ から引いたものが答え

直線列挙が $O(N^2)$、交点列挙が更にその2乗の $O(N^4)$ となる。
同じ直線や交点を同じと管理するために連想配列を用いた場合、言語や実装によって $\log{N}$ が付く。

最大値の代入で約 $3.5 \times 10^7$ となり、 有理数で計算を行う場合は定数倍も軽いとは言いがたいが、 実行時間制限を長めに取ってくれているので間に合う。

3次元座標上の直線は、3次元ベクトルとパラメータ $t$ を使って $\vec{a}+t\vec{b}$ で表すことができる。
$\vec{a}$ が直線上の任意の1点、$\vec{b}$ が方向ベクトルを示すので、2点を $(X_1,Y_1,Z_1),(X_2,Y_2,Z_2)$ として、

• $\vec{a} = (X_1,Y_1,Z_1)$
• $\vec{b} = (X_2-X_1,Y_2-Y_1,Z_2-Z_1)$

となる。ただ、これだと同じ直線でも異なる表現が可能になってしまうので、一意に揃える。

今回の場合、

• $\vec{a} = (x,y,z)$ の $x$ を $0$ に揃える（直線が $x=0$ の $yz$ 平面を通過する時の $y,z$ 座標）
  • この問題では $x=0$ の面を通過する直線のみを考えればよいことから、必ずこのような表現ができる
• $\vec{b} = (dx,dy,dz)$ の各数値は、$dx=1$ に揃える
  • これも、$dx \neq 0$ の直線だけを考慮しているので可能。一般の場合は場合分けが必要

ことで、一意にできる。$(y,z,dy,dz)$ の4変数で直線を表現できることになる。

全2点間でその2点を通る直線をカウントしていくと、 $k$ 個の点を通る直線は、$\frac{k(k-1)}{2}$ 回カウントされることになる。
カウントを2倍して平方根を取ることで、その直線で隠れる人数が特定できる。

$(0,y_1,z_1)+s(1,dy_1,dz_1)=(0,y_2,z_2)+t(1,dy_2,dz_2)$ となる点の有無と、ある場合はその座標を求めたい。

$x$ 座標の一致を考えると、パラメータは一致しなければならない。 $s=t$

$y$ 座標を使って $t$ を解くと $t=\frac{y_1-y_2}{dy_2-dy_1}$ となる。
これが $z$ 座標の $z_1+t \times dz_1=z_2+t \times dz_2$ でも成立すれば交点が存在する。

• ただし例外処理として、
• $dy_1=dy_2$ の場合、$y_1=y_2$ でなければならない
  • そうでなければ $xy$ 平面に投影したときに切片の異なる平行な2直線となり、交点を持たない
  • $y_1=y_2$ の場合、$y$ 座標は $t$ の値に依らず常に一致するので特定できない
  • →$z$ 座標を使って $t=\frac{z_1-z_2}{dz_2-dz_1}$
    • これも、$dz_1=dz_2$ の場合、交点を持たない（$z_1=z_2$ なら、2直線は完全に一致してしまうのであり得ない）

交点の $x$ 座標が $x \lt 0$ となる時のみ、そこを $p$ とすることが可能になる。
そのような交点ごとに、「どの直線で交わったか」をsetなどで記録しておくと、最終的にその交点でいくつの点が隠れるのか算出できる。

有理数で表現すると正確ではあるが、演算を重ねる内に分子・分母が巨大になったら、 結局、計算に時間がかかりすぎて扱えないという話になってしまう。
足し算ひとつとっても、分母が互いに素だと通分するだけでオーダーが2乗になるなど、結構あっさり大きくなるので侮れない。

コンテスト中は、「なんか意味ありげに $X_i,Y_i,Z_i$ の制約がそこそこ小さめだし、配慮してくれてるんだろう」で投げてしまうことも多いが、本来はちゃんと考える必要がある。

各変数や結果の分子分母のオーダーを考えると、2次元で考えるとして、制約を $|X_i|,|Y_i| \le D$ として

• 直線を表す変数の $dy$（$dx=1$ に揃えた後）
  • 2点を $(X_1,Y_1),(X_2,Y_2)$ として、$dy=\frac{Y_2-Y_1}{X_2-X_1}$
  • 分子: $O(D)$
  • 分母: $O(D)$
• 直線を表す変数の $y$（$x=0$ に揃えた後）
  • $y=Y_1-X_1 \times dy$
  • 分子: $O(D^2)$
  • 分母: $O(D)$
  • ※$y$ と $dy$ の分母は一致する
• 交点を求める際のパラメータ $t$
  • $t = \frac{y_1-y_2}{dy_2-dy_1}$
  • $y$ と $dy$ の分母の一致を生かして、分子分母に $(y_1の分母)(y_2の分母)$ をかける
  • 分子: $O(D^3)$
  • 分母: $O(D^2)$
• 交点座標 $cy$
  • $cy = y_1 + t \times dy_1$
  • 分子: $O(D^4)$
  • 分母: $O(D^3)$

となり、制約の4乗レベルまで値が大きくなる可能性がある。
今回は $D=10^3$ なので大丈夫だが、$10^5$ になるともう通常の64bit整数では不可能となる。

Python3

from collections import defaultdict
from fractions import Fraction
from math import gcd

n = int(input())
points = [tuple(map(int, input().split())) for _ in range(n)]

lines = defaultdict(int)
for i in range(n):
    x1, y1, z1 = points[i]
    fx1 = Fraction(x1)
    for j in range(i + 1, n):
        x2, y2, z2 = points[j]
        dx = x2 - x1
        dy = y2 - y1
        dz = z2 - z1
        if dx == 0:
            continue
        t = fx1 / dx
        y0 = y1 - t * dy
        z0 = z1 - t * dz
        if dx < 0:
            dx *= -1
            dy *= -1
            dz *= -1
        g = gcd(gcd(dx, dy), dz)
        dx //= g
        dy //= g
        dz //= g
        lines[y0, z0, dx, dy, dz] += 1

# 全てが 同一yz平面上で、どの2点も重ねられない
if len(lines) == 0:
    print(n)
    exit()

lines2 = []
duplicate_count = []
fdxs = []
for params, cnt in lines.items():
    lines2.append(params)
    duplicate_count.append(int((cnt * 2) ** 0.5))
    fdxs.append(Fraction(params[2]))

m = len(lines2)
cross = defaultdict(set)

for i in range(m):
    y1, z1, dx1, dy1, dz1 = lines2[i]
    fdx1 = fdxs[i]
    for j in range(i + 1, m):
        y2, z2, dx2, dy2, dz2 = lines2[j]
        fdx2 = fdxs[j]
        k = fdx1 / fdx2
        if dy1 - k * dy2 == 0:
            if y1 != y2:
                continue
            if dz1 - k * dz2 == 0:
                continue
            t = (z2 - z1) / (dz1 - k * dz2)
        else:
            t = (y2 - y1) / (dy1 - k * dy2)

        if t >= 0:
            continue

        if z1 + t * dz1 != z2 + t * k * dz2:
            continue

        cx = t * dx1
        cy = y1 + t * dy1
        cz = z1 + t * dz1
        cross[cx, cy, cz].update({i, j})

max_duplicate = max(duplicate_count)
for line_set in cross.values():
    tmp = 0
    for i in line_set:
        tmp += duplicate_count[i]
    max_duplicate = max(max_duplicate, tmp)

print(n - max_duplicate)