読者です 読者をやめる 読者になる 読者になる

天下一2015 qualA

13位でした。
Bから開く,あっ(察し)
Cを見る どうせ二部マッチング→ちょうどうまくいく二つ以外(奇数サイクルの)swapする意味が無い(そいつらを全部変えればOK)ので二部マッチングするだけ.HとWを間違えて1WAのあとAC.
Aを見る.普通に1WAした後展開図をググって通す.
Bをやる.出す.WA.
あきらめてDを見る.やる.何回かミスったあとAC.
Eの30点をやる.はじめK角形以上かと思いputs("0")をしたらWA.その後ちゃんと読んでAC.
Bをやる.WA.もうダメ.コンテストが終わる.

D:
まず二重辺連結成分分解する.すると橋たちの木になる.この木の頂点数をKとするK=1だと不可能,K=2だと0.
適当に葉をつなげてけば橋がいい感じに減らせそうな気持ちになる.
まずコーナーケースとして,K=3かつV=3だと出来ない.(K>=4なら一個のぞいて完全グラフにすればいい,V>=4だと結べる点があるので可能)
さっきも言ったように適当に葉をつなげてくんだけど,どの橋を残すかを考えた時に,"その橋を取り除いた両方の木で,二重辺連結にする"をするひつようがある.これは(葉の個数+1)/2になる.これは大体(分ける前の木の葉の個数)/2くらいになるがちょっと変わりうる(二つに分けることによって葉が増えたり,/2の切り下げが起こるによって).しかし全ての橋を試す必要はない.
まず橋は片方が葉になるようなものしか考えなくて良い.なぜかというと,そういうところを使うと葉が1or0減るので(それ以外だと減ることはない).
次に,もしある橋の両方の点の次数が「1 と 3以上」なら,そこを残そうとすると最大効率で残せることがわかる(わけても葉が増えないかつ片方が0なので偶奇によって+1無駄になったりしない).そうでない場合はまあ+1無駄になる(というか,無駄になりうる*1.

E.わかんない

Dのコード
http://tenka1-2015-quala.contest.atcoder.jp/submissions/459943

*1:葉の個数+1/2)になる