hotpepsiの練習帳

SRM 578

02:46

Div1 Easy (250) GooseInZooDivOne

問題

• 檻の中にガチョウとアヒルがいる
• ガチョウは1匹以上、合計で偶数匹いる
• あるガチョウからマンハッタン距離dist以内にいる鳥はガチョウである
• ガチョウとアヒルの取りうる組み合わせを求める

方針

• あるグループがガチョウでない場合は全てアヒル
• その場合、他のガチョウとはdistより離れている
• ということは、いずれにしろdist以内でグループ化すればよい
• union-findでグループ化した(けど普通にDFSでいい)
• グループ単位でガチョウなのかアヒルなのかの2択
• それに1羽以上と偶奇の制約が加わる
• 最大50×50＝2500グループ
• 1グループずつ偶奇を数え上げてみる
• 作れる偶数の総数と奇数の総数でDP
• 直前の偶数の場合の数をeven、直前の奇数の場合の数をoddとする
• 次のグループが偶数なら、そのグループを足しても偶奇が変わらない
• そのグループを使う場合と使わない場合で、場合の数はそれぞれeven×2とodd×2になる
• 次のグループが奇数なら、偶奇が変わる
• 奇数に足すときは偶数が作れるので、evenに加えてodd個の偶数が作れる
• 偶数に足すときは奇数が作れるので、oddに加えてeven個の奇数が作れる
• 最後に、存在しない(ゼロ羽)場合を引く
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_578/GooseInZooDivOne.cpp

結果

o-- 100.88pt 299th/576 rating 1271 -> 1320 (+49)

方針自体はだいたい合っていた。偶数のグループの数は2の累乗であり、奇数のグループは偶数個だけ取り出すのだが、それも2の累乗で求めることができるので、もっと簡単に書けたらしい。

goose＝ぐーす＝偶数、な気がする。