Loading [MathJax]/jax/output/CommonHTML/jax.js

目次

Panasonic Programming Contest 2023(AtCoder Beginner Contest 301)G問題メモ

Panasonic Programming Contest 2023(AtCoder Beginner Contest 301)

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

G - Worst Picture

G - Worst Picture

問題

解法

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

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

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

大まかな方針

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

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

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

直線列挙

3次元座標上の直線は、3次元ベクトルとパラメータ t を使って a+tb で表すことができる。
a が直線上の任意の1点、b が方向ベクトルを示すので、2点を (X1,Y1,Z1),(X2,Y2,Z2) として、

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

今回の場合、

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

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

交点列挙

(0,y1,z1)+s(1,dy1,dz1)=(0,y2,z2)+t(1,dy2,dz2) となる点の有無と、ある場合はその座標を求めたい。

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

y 座標を使って t を解くと t=y1y2dy2dy1 となる。
これが z 座標の z1+t×dz1=z2+t×dz2 でも成立すれば交点が存在する。

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

有理数の分子・分母の値の範囲

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

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

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

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

Python3