TCO2013 Round2C
250
きつねたちの間でダンスパーティが開かれている。A, B が友人もしくは、ある C が存在して A, C、B, C がいずれも友人であるときに A, B はダンスをすることができる。後者の場合ダンスの後 A, B は友人になる。1 回の曲の間に、各きつねは高々 1 人とダンスをすることができる。きつね 0, 1 が友人になるのに必要な曲の個数を求めよ。
Warshall-Floyd を実施して、きつね 0, 1 の間の距離 - 1 を返した人がたくさんいますが、複数のきつねの組が同時にダンスを実施することができるのでちがいます。
距離を d として、d == 1 となるまで d -= (d+1)/3 を行った時の処理回数を返すとよい
dist - 1 をやる人が出そうだとなぜか気づいたので 2 個落としておいた
TCO でこんな（気づく人は気づいて大虐殺が発生する）challenge ゲー出すのどんびきだなあ
500
200*200 くらいの盤面があって、あるマスが頂点である。各マスに正の整数を書き込むが、頂点に向かっていく列は strictly increasing でないといけない。いくつかのマスには最初から数字が書かれていて変更できない。マスの数字の和を最小化せよ。
各マスの数字を最小化すればいい。頂点の左上、右上、左下、右下は頂点の位置によらず一意に最小なものを決定できる。頂点を動かして、頂点の上下左右のマスたちを適当に決定すると O(N*M*(N+M)) くらい。
