TCO Qualification Round 3

前回が途中でサーバダウンのため中止になったので1日後の今日再び行われた．

250

点を与えられた条件で動かしていったときの最終状態を求めよというありがちな問題．218.97pt

500

与えられた重みつきグラフから非連結にならないように枝を除去した時のとれる重みのが合計の最大値を返せという問題．枝の重みのの合計から最小全域木の枝の重みの合計を引くだけ．404.69pt

1000

N行M列(N,M奇数)の盤面に0,1の数字が書いてある．操作として一つの列か行を選んでその列または行の0,1をすべて反転させるという操作が許されているときに，各行各列の1の合計が全て偶数となるような状態に最短で何回かかるか答えよという問題．
初期盤面で1の合計が偶数であるという条件をみたす行の数をR，列の数をCとしたときに1の合計が偶数の行をひっくり返したとき状態は行の0の数が奇数であることに注意すると

(R,C) -> (R - 1 , M - C)

と変化することがわかる，同様に考えると一つの状態からいける遷移は他に

(R,C) -> (R + 1 , M - C)
(R,C) -> (N - R , M - 1)
(R,C) -> (N - R , M + 1)

の3つだけであり，状態(R , C)から状態(N , M)まで幅優先探索すれば解ける．

上の方針を思いつければよかったのだけどコンテスト中には思いつかずOpened．

順位は152位だったのでQualification Roundは通っていると思います．