脳log[20200922] ACL Contest 1／A 問題 Reachable Towns

最終更新: 2020-10-14T18:33+0900

♪ [AtCoder] ACL Contest 1／A 問題 Reachable Towns

ACL は ARC と AGC の中間あたりの位置づけだそうな。この A 問題は 300 点問題。１問目のこれしか解けそうにない。

 最初の提出 #16962327 (TLE)

移動可能な範囲が第Ⅰ象限と第Ⅲ象限に限られるが、移動先の点からさらに移動先を選ぶことができる。双方向に移動可能だし、X と Y の比率を変えながらジグザグに Y=-X 方向に移動することもできる。ともあれこの感じ(「友達の友達は友達」)は UnionFind だと思った。

問題は Union する点の選び方で、見境なく Union したら TLE になった。

見境なくとは言っても、相互に移動可能なら片方向だけを取り扱えば足りるわけで、X 座標の昇順に処理することで X 座標の大きい方から小さい方だけを見るようにしている。X 座標のソートに関してもこの問題で NlogN の時間をかけるのはもったいなくて、線形時間でソート列が手に入る。

 ３番目の提出 #16962544 (AC / 565 Byte / 559 ms)

Union した中で一番条件のいいものだけ代表として残すようにしたら AC。

 Python で一番速い提出 #16928237 (maspy さん / 363 ms)

よくわからないが UnionFind ではない。キーは12行目の if x + min_y == N+1: だと思う。UnionFind で形作られるグループが持つ幾何学的性質が何かあるのだろうか。

右上がりの対角線上に並ぶ場合と右下がりの対角線上に並ぶ場合を対極として、その中間の状態がうまく考えられない。

X 座標と Y 座標がともに 1..N の順列だということから導かれる論理的必然性を何か見落としてると思う。

検索してたら答えらしきものが見えちゃったんだよな、maspy さんのページは避けてたんだけど他の所で。

頂点をソートして x 座標が小さい順に見ます。

頂点 i と頂点 i+1 について、「y1, …, yi が (N,…, N−i+1) の順列」であるときのみ非連結であり、そうでないとき必ず連結になることがわかります（あとで証明かなんかできたらいいな、、）

「わかります」(わかりません)

 提出 #17013139 (AC / 1055 Byte / 326 ms)

maspy さんの提出に沿って*理解したことをひとつひとつコメントにしながら書いた。完全にそのままではなく、「# ymin の最初期化が必要？」とコメントしたように、ループ中の代入をひとつ省略した。(あ、タイポ。最初期化→再初期化)

しかし、ガイドなしの独力でこの道筋が見つけられるとは思わん。

 「UnionFind で形作られるグループが持つ幾何学的性質」

けんちょん(敬称略)のページにわかりやすい図があった。へー、そうだったのか(まだ見えていなかった)。

「ACL Contest 1 A - Reachable Towns (300 点) - けんちょんの競プロ精進記録」

でも図を見てみたらある意味わかって当然の図ではあった(それがわからなかった)。つまり、x + y = N+1 という X と Y の関係式を見て幾何学的性質について考えたのだし、であれば、その性質は y = -x + N+1 という直線に関わるものでしかありえない。答えを目の前にしながら「わからんなあ」と悩むふりをしていたのだった。下手の考え……。