ABC224 参加記録 - geam1113’s diary

コンテスト中AC:A〜D

C - Triangles?

$O(N^3)$ で全探索可能です。

面積が正でない三角形は、面積が0の三角形です。

言い換えると、直線上に3点が並んでいる時、面積は0になります。

3点 $P_1,P_2,P_3$ が直線上にある時、線分 $P_1P_2,\ P_1P_3$ の傾きが同じになるので、

三角形の面積が0でない時、

$\frac{y_3 - y_1}{x_3 - x_1} \neq \frac{y_2 - y_1}{x_2 - x_1}$

が成り立つので、これで判定できます。

このままだと、x軸やy軸に平行であるときに0除算が発生する可能性があります。そのため、変形して、

$(y_3 - y_1)(x_2 - x_1) \neq (y_2 - y_1)(x_3 - x_1)$ としても、同様に判定できます。

ちなみに、 $y_3 - y_1 = 0 \land x_3 - x_1 = 0$ のときも、同一直線上と判定されます。これは、点 $P_1,\ P_3$ が同一座標上にあるときです。

この問題では制約上あり得ないですが、同一座標の点があっても判定は上式で問題ない(はず)です。

提出コード:https://atcoder.jp/contests/abc224/submissions/26766659

D - 8 Puzzle on Graph

8クイーン問題などでは、盤面の状態を頂点とみなしたDFSで探索を行いますが、この問題は同様の解法です。

コマの置き方の1つを探索する際の状態の1つとみなしてBFSします。

入力例1を具体例にとって記載します。0-indexedとし、空の頂点を-1にしています。

初期状態

{-1, 2, 0, 3, 4, 5, 6, 7, 1}

無向辺e = (0, 1), (0, 2), (0, 8)があるので、頂点0(-1がある空の頂点)に、2, 0, 1を移動させることができるので、1回の移動で実現できるコマの置き方は以下の通りです。

{2, -1, 0, 3, 4, 5, 6, 7, 1}

{0, 2, -1, 3, 4, 5, 6, 7, 1}

{1, 2, 0, 3, 4, 5, 6, 7, -1}

以下同様にして、コマの移動を繰り返し、目的の状態{0, 1, 2, 3, 4, 5, 6, 7, -1}となれば、その操作回数が答えとなります。目的の状態にならなければ-1です。

C++での実装上、コマの置き方の状態はvectorで記録し、各状態に必要な移動回数はmapで記録しました。

計算量は、コンテスト中は見積れずなんとなく少ないだろうで通してしまったのですが、グラフG=(V,E)のBFSは $O(|V|+|E|)$ で、状態数|V|は最大でも $9!=363880$ です。mapのlogVと合わせても、 $O(log|V|(|V|+|E|))$ で、これは $10^7$ くらい?かなと思います。また、実行時間制限4 secあるので、少し余裕があります。

提出コード：

https://atcoder.jp/contests/abc224/submissions/26773031