naoya_t@hatenablog

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

SoundHound Inc. Programming Contest 2018 (春)

やってたから(もう始まってたけど)出てみた
2完。(レーティング変動なし)

A - SoundHound

2単語それぞれの頭文字がS,Hであるか見るだけ
AC
https://soundhound2018.contest.atcoder.jp/submissions/2021759

C - 広告

Union-Findして
島ごとに市松模様2パターンの良い方を取る(想定嘘解法)
WA
https://soundhound2018.contest.atcoder.jp/submissions/2022782

4 7
...****
...*...
.......
*.**...

こういうので死ねるし

〜〜

Maximum Independent Set(最大独立集合)を取らないと駄目、らしい。

まずこれを二部グラフにする。それぞれの升目を市松模様のどちらに属するかで二部のどちらかに置いて
上下左右繋がるところに線を引く。
最大マッチングを求めて、頂点数からそれを引いたもの、でいいのかな。

D - 建物

読んだ
DPで解けるんだろうなあと思った

E - カッコ列

読んだけど
パス