Panasonic Programming Contest 2023(AtCoder Beginner Contest 301)
EとF、GとExの得点が微妙に異なるようになった。
3次元座標における直線処理と、有理数の正確な一致判定。
3次元座標に慣れていないと時間がかかるだけであって、やることはさほど複雑ではない。
(コンテスト本番では、100分しかない上に、他にも実装が重たい問題があったので、解答者がめちゃ少なかったけど)
Pythonなら、有理数を分数として正確に扱うには、fractionsモジュールが使える。
通常のintやfloatと比較するとそこそこ重たくはなる。
まず、Xi が全て同じ場合は隠れるのが不可能なので N。それ以外を考える。
直線列挙が O(N2)、交点列挙が更にその2乗の O(N4) となる。
同じ直線や交点を同じと管理するために連想配列を用いた場合、言語や実装によって logN が付く。
最大値の代入で約 3.5×107 となり、 有理数で計算を行う場合は定数倍も軽いとは言いがたいが、 実行時間制限を長めに取ってくれているので間に合う。
3次元座標上の直線は、3次元ベクトルとパラメータ t を使って →a+t→b で表すことができる。
→a が直線上の任意の1点、→b が方向ベクトルを示すので、2点を (X1,Y1,Z1),(X2,Y2,Z2) として、
となる。ただ、これだと同じ直線でも異なる表現が可能になってしまうので、一意に揃える。
今回の場合、
ことで、一意にできる。(y,z,dy,dz) の4変数で直線を表現できることになる。
全2点間でその2点を通る直線をカウントしていくと、
k 個の点を通る直線は、k(k−1)2 回カウントされることになる。
カウントを2倍して平方根を取ることで、その直線で隠れる人数が特定できる。
(0,y1,z1)+s(1,dy1,dz1)=(0,y2,z2)+t(1,dy2,dz2) となる点の有無と、ある場合はその座標を求めたい。
x 座標の一致を考えると、パラメータは一致しなければならない。 s=t
y 座標を使って t を解くと t=y1−y2dy2−dy1 となる。
これが 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整数では不可能となる。