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

唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

TopCoder SRM 637 Div2 oo- 1168->1283

17th, 704.33pts, +1/-0 challenge
Volatility: 501->512

EasyとMediumの早解き回
部屋1位だった
1000点の問題を誤読していた(´・ω・`)

writerの解説

SRM637 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

250: GreaterGameDiv2

2人のプレイヤー(Cat Snukeとwolf Sothe)にN枚ずつカードが与えられる
2人が出すカードの順番が与えられるので、Snukeの方が大きい回数を答える

やるだけ

class GreaterGameDiv2:
    def calc(self, snuke, sothe):
        return sum(map(lambda x, y: x > y, snuke, sothe))

500: PathGameDiv2

上下に2つ、横にはいくつかのセルが並んでいる
セルは白か黒に塗られていて、上下左右の移動だけで白いセルだけを通って一番左から一番右に行ける
白いセルだけを通って一番左から一番右に行けるという条件を維持したままで何個セルを黒く塗ることができるか

上下2つのセルが両方色が塗られてない縦列の数から塗られているセルの上下の入れ替わりの数を引けばよい

class PathGameDiv2:
    def calc(self, board):
        empty = sum(map(lambda x, y: x == y, *board))
        colored = [x for (x, y) in zip(*board) if x != y]
        change = sum(map(lambda x, y: x != y, colored[:-1], colored[1:]))
        return empty - change

1000: ConnectingGameDiv2

縦横にセルが並んでいる
セルはいくつかの連続した領域に分けられている
上下左右の移動だけで一番上から一番下に行けないようにするために、いくつかの領域に色を塗って通れなくする
最小で何個のセルを塗ればよいか

領域が連続してないものだと誤読して悩んでいた

writerの解説によると平面グラフの最小カットを求めればよくて、左右に横切るような領域の最短路(セルの数が最小)を求めればよいらしい
道を塞げばよいので、上下左右だけではなく斜めも含めた8近傍のいずれかで接しているような領域に辺を張る

-->