2022/03/25 Eに追記
コンテスト中AC:A〜E
C - Shapes
難しかったです。
以下の2点を解決する必要があります。
- 90°回転の実装
- 平行移動の方法
90°回転は回転行列で解決しました。なお、全てのマスはxy座標上の点と見なしています。
\begin{align}\begin{pmatrix}x' \\ y'\end{pmatrix}=\begin{pmatrix}\cos90° & -\sin90° \\ sin90° & \cos90° \end{pmatrix}\begin{pmatrix}x \\ y\end{pmatrix}=\begin{pmatrix}-y \\ x\end{pmatrix}\end{align}
平行移動は、全ての点を「最も左下の点」からの相対位置として計算することで解決しました(全ての座標から左下の座標を引く)。これは、最も左下の点が原点行くように平行移動させているとも言えます。
以上を考慮し、図形の相対位置がSとTで等しいかを調べ、一致すればYes、しなければ90°回転します。
3回回転しても一致しなければNoです。
D - Rectangles
軸に平行な線分2つについて、線分の端点同士を繋ぐように
軸に平行な線を引いて長方形が作れるか調べることを考えます。
すると、
座標が同一である
座標のペアが、
座標の異なる別の
座標のペアと同一であれば
軸に平行な線分を引くことが可能です。
例えば、入力例1の
の長方形では、
そこで、
軸に平行な線分の端点のペア(すなわち
座標が同一な
座標のペア)を全列挙します。
このペアを保存する配列を
とすると、
となるような、
の組みの総数を調べる問題となります（但し、
）
-----------------------------------------------------
イメージ
x = 0 | y = {1,4,5} -> (1, 4), (1, 5), (4, 5)の組み(線分)ができる
x = 2 | y = {1,5} -> (1, 5)の組みができる
P = {(1, 4), (1, 5), (4, 5), (1, 5)}
(1,5)は同一なので、長方形を一つ作れる。
-----------------------------------------------------
同一な要素の組みの総数を得るのは頻出のテクニックで、
番目の要素について、
に
個の同一な要素が存在すれば、
は
個の組みを作ることが可能です。
同一な要素の個数をハッシュマップに順次記録しながら要素を前から順番に探索していくと、全ての組みの個数が線形時間で得られます。
実装上、
座標が同一な
座標を二次元配列に保存したいので、
座標は座標圧縮しておきます。
なお、同一の点が存在しないという制約上、
座標が同一な
座標のペアが2つ選ばれ、長方形とならず、単なる線分となってしまうことはありません。
の大きさは最大でも
なので、ペアを作るところが
ボトルネックとなり、
くらいです。
E - Destruction
グラフの連結性の問題は、全域木を疑います。
全域木はグラフを連結にする最小の構成です。全域木に属さない辺を取り除いても連結性は保たれます。また、全域木を作ると、それ以外の取り除いて良い辺の集合の要素数は、最大となります。
ここで、最小全域木を求めてみると、
は大きい方から順に残るので、全域木以外の辺を取り除いた時の報酬を最大化できます。
そこで、Kruscal法に基づいて、以下のように処理を追加します。
について、
と
が連結なら、
は取り除けるので、
にを足す
答えはです、と言いたいところですが、これでWA出しました。
全域木以外の辺は、取り除いても良いですが、取り除かなくても良いです。
そのため、
の時は、全域木を構成する辺でなくても取り除かない(報酬に追加しない)ように修正します。
- について、とが連結で、かつ、
なら、を取り除き、にを足す
答えはです。
提出コード：https://atcoder.jp/contests/abc218/submissions/25777236
-------------------------------------
2022/03/25 追記
上記解法及び公式解説を見直したら、上記解法が正しくないことに気がつきました。
というのも、最小全域木を構築すると、それ以外の辺のの和は最大化されそうですが、の辺はそもそも切断する必要がありません。
すると、例えば全域木以外の辺のが例えば、
(1) -5 6
(2) -3 5
とすると、和は(2)の方が大きくなります。しかし、負の場合は接続してもよいので、無視できます。すると(1)の方が切断した時に得られるスコアが大きくなります。
というわけで、以前書いた解法は間違っていると思われます。
改善策として、youtubeの公式解説の通り、負のコストを持つ辺は必ず接続するという風にするか、負の辺はコスト0の辺と見なしてもよいと思います。