naoya_t@hatenablog

いわゆるチラシノウラであります

Google Code Jam 2018 - Round 2

B-smallだけ通して終了…
通過ライン(Tシャツラインとも言う〉の1000位に遠く及ばず。

お疲れさまでした。

A - Falling Balls (5pt, 12pt)

なんか難しく考えてた。
一旦飛ばしてB,Cの後にA-smallだけでも通そうと思って最短経路問題(玉の状態を坂パターンで遷移)に落としてたんだけど答え合わないと思ったらパターン数じゃなくてNでループしてた。

〜〜

解説読んだら目から鱗で、なるほどすぎて、書き直したらさくっとAC取れた

B - Graceful Chainsaw Jugglers (7pt, 17pt)

B-smallはDPで通したんだけどlargeどうすれば。

解説読んだけど頭に入ってこなくてそのまま寝落ち...(あとでまた読む)

C - Costume Change (8pt, 19pt)

Cはなんかそういうやつ(二部グラフで最大独立集合でみたいな)の匂いがしたんだけどそこまで落とせなかった。貪欲な嘘解法で1WA

色別に最大マッチングして合計を出せばよかったのか。
Analysisを読んで完全に理解したと思って投げたらlargeがTLE。ローカルで最悪ケースで22秒かかるし。Ford-Fulkerson使ってるからか…

Spaghetti Sourceさんから二部グラフの最大マッチングのコードを持ってきてちょっといじったやつに差し替えたら1.3秒で終わるようになってlargeも通った。

D - Gridception (10pt, 22pt)

開いてない