Mag Beginner Contest 003 開催記
2021/12/14 22:00-23:00 コンテストを開きました。とっておきのグラフ問×4を放流しました。
問題 (配点)
結果
最終順位上位3名
1. 700 (33:00) SayakaAmemiya さん
2. 700 (49:47) hotman78 さん
3. 700 (62:44) Suu0313 さん
First Accepted
A: (01:49) tute7627 さん
B: (07:11) tute7627 さん
C: (11:01) googol_S0 さん
D: (19:10) ir_1st_vil さん
参加してくださった方々、お疲れ様でした。ありがとうございました！
感想
難易度を見積もるのが難しかったんですが、多分一番簡単だと思ったので先頭に置きました。
巡回セールスマン問題はNP問題ですが、木の場合は簡単に解けるというのが面白いポイントだと思います。おそらく、なもりグラフでも$ O^*(N)くらいで解けるはずです。
特に理由はないですが、長さの総和を$ 10^9以下に収めるために辺の長さを小さくしました。別解が見つかったり、小さいというところでひっかかるのを少し期待していました。
重み付きUnionFindを使う問題を作ってみたいなーと思って作りました。しかし、テストをしていると普通にDFSでも解けてしまうことに気づいたので100点にしました。
唯一のハマりポイントは頂点$ Xからも$ Yからもつながっていない連結成分にある矛盾だと思います。
もしXORではなく和とかだったら有向グラフで考える必要があったのですが、XORは$ x=x^{-1}となるので辺の向きを考える必要がないというのは少し面白いと思います。
なもりグラフを使いたいなーと思ったので、ループを検出する問題にしました。
最初はどこに行くのか求めさせようと思っていましたが、まったく同じ問題があったのでちょっとひねりました。 最短路クエリを高速に求めれたら、すごくないか？と思います。なもりグラフならできると知ったので、問題にしました。
制約を大きくしすぎたので、定数倍が大きいと通らないし、MLEが多発してしまいました。大変申し訳ないです。
結構な方が想定解や準想定解で解いておられたのですが、ACとなった方は4名のみでした…。