ARC105感想戦

🤔

NoSubだったので、感想戦も何もないんですが。。。

CDEのどれかが解ければ出ようという感じで問題を見る。Cがまずどうすればいいのかまったく分からん。

Nが8以下で小さいので、順番を決めてからそれぞれ求めるんだろうな、と予想したけど、順番を決めたところでどうやるのかさっぱり。できる限り前の方に押しやるのか？と思ったけど、そんなの計算できるだろうか。。。ということでパス。

Dは、Nimがまだあんまりわかっていないのでパス。

Grundy数（Nim数, Nimber）の理論 | クリエイティヴなブログ

前にこの記事を読んでわかった気になってたけど、わかってなかった。ということでパス。

Eは、点数的に解けるわけないだろうと思いつつ、とりあえず考えてみる。図をかいてみると、「連結ダメ、自己ループダメ、多重辺ダメ」ってことは、ギリギリの状態では島が2つできていて、各島ではこれ以上辺がはれない状態になってるってことだな、というのはわかる。

なので、頂点1と頂点Nにつながっている点の数をそれぞれ求めて、なんかごにょごにょすればOK？

連結成分のサイズを $x$ とおくと、辺のmaxは $\dfrac{x(x-1)}{2}$ 本なので、1を含む島とNを含む島の本数を考えて、すでにひいている辺の本数 $M$ を引けば、偶奇によってどちらが勝つかはわかる。

でも、辺をつなげていったときに偶奇がどう変わるのかがわからず。連結成分が奇数の島につなげたり偶数の島につなげたりしたら状況が変わってしまうなぁ、うーん、みたいなところでぐるぐる回っていた。

というか、島につなげていくゲームと見れば、これもNimじゃないか。これもパス。

ということで、NoSub撤退で睡眠。

解説を見ると、Eは、上のような感じでは、最後が詰め切れずに結局できなかったなぁ、という印象。先が長い。