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

はまやんはまやんはまやん

hamayanhamayan's blog

Facebook Hacker Cup 2017 Round 2 解説

競技プログラミング

問題はこっち
http://hamayanhamayan.hatenablog.jp/entry/2017/01/23/014337


参考
https://www.facebook.com/notes/1607098535972708
https://togetter.com/li/1073027

12: Subtle Sabotage

これは場合分けをして解く。
本番では、3番目のテストケースの答えが5になるのが、まず分からなかった。
公式Editorialで見られるような感じのやつを想定して場合分けする。

22: Big Top

マジでって感じ。
解答はsetで棒を管理する解法。

棒の集合はある棒がある棒に完全に包含される状態を含まない状態を保ちながら更新していく。
ある棒を追加する場合は左右に対して完全に包含されるかを判定して、完全に包含されるならば消していく。
一見、かなり時間が掛かりそうな感じがあるが、ある棒について消されるのは1回のみであるため、消す回数はO(N)に収まり、大丈夫。
領域のマージをする時にこんな問題を見たことがある。
若干、典型問題なのだろうか。

29: Fighting all the Zombies

37: Rain Over New York