dohatsutsu’s diary

日記を書いています。

【No.034】「 AOJ 2376 Disconnected Game」

AOJ 2376 Disconnected Game

問題文

http://judge.u-aizu.ac.jp/onlinejudge/IMAGE/winter-camp-2011-day3.pdf#page=15

 

AOJ-ICPC 難易度600にあった問題です。

 

今回は解説記事ではなくて、自分の考察の過程のメモという感じになります。

 ( 問題のネタバレを含みます )

 

 

 

グラフの連結成分の個数が2個になった場合、「あと何個のエッジを追加できるのか」を数え上げることで簡単に勝敗を判定できます。

 

※ノードの数をVとおき、すでに設置されているエッジの数をEとおき、2つの連結成分に含まれているノードの数をそれぞれa,bとおくと、

[ V×(V-1)÷2 - (a×b) - E ]の偶奇で判定できます

(V=a+b)

 

V×(V-1)÷2-E通りあるエッジの設置候補のうち、a×b通りが設置できなくなるので

a×bの値の偶奇がこのゲームの勝敗を分ける鍵となります。

 

(入力で与えられた初期のグラフについて)V×(V-1)÷2-E が偶数ならば、

太郎はa×bの値が奇数になるように行動するべきで、

花子はa×bの値が偶数になるように行動するべきです。

 

反対に、

V×(V-1)÷2-E が奇数ならば、

太郎はa×bの値が偶数になるように行動するべきで、

花子はa×bの値が奇数になるように行動するべきです。

 

a×bの値を偶数にするためには、aかbのどちらか一方さえ偶数にすればよいので、奇数個のノードを含む連結成分の数が減るようにエッジを設置していけばよいです。

(要するに奇数個のノードを含む連結成分どうしを結ぶようにエッジを設置していけばよい。)

 

 

a×bの値を奇数にするためには、aとbの両方を奇数にする必要があるので、偶数個のノードを含む連結成分の個数が減るようにエッジを設置していけばよいです。

(要するに偶数個のノードを含む連結成分と何か別の連結成分どうしを結ぶようにエッジを設置していけばよい。)

 

 

 #define 奇数のやつ 奇数個のノードを含む連結成分

 #define 偶数のやつ 偶数個のノードを含む連結成分

 

奇数のやつの個数は、ゲームが進むにつれて、減少することはあっても、増加することはないです。また、減少する場合は、必ず2つずつ減少します。

太郎と花子のうち、片方のプレイヤーは必ず、奇数のやつどうしを結ぶように行動し続けるので、最後に残る2つの連結成分の両方が奇数のやつになることはほとんど無いです。

 

あるとすれば「最初から奇数のやつが2つのみになっているとき」と、「最初から奇数のやつ2つと偶数のやつ1つのみで、太郎がa×bの値を奇数にしたいとき」ぐらいです。

 

 

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2152583#1

 

 

gist.github.com

 

 

 そういえば、太郎が先手とは問題文に明記されていない気がしました。