square869120Contest #4 C - Calendar 2
昔解いた問題の忘備録。
a[i]が与えられる。幅7マスでn行あるカレンダーについて、すべてのa[i]について、mで割った余りがa[i]であるようなマスを黒く塗る時の連結成分の個数を求める問題。
まず最初に7nがmの倍数であるようにa[i]を調整しよう。(a mod x を a mod yにするのはそれほど難しくない)。その状況で実際に実験してみる。すると連結成分の数がある種の1次関数になっていることがわかる。その為、切片と傾きを求めて終わり。
まず連結成分の数が1次関数になるということは感覚ではわかるが証明はぱっと思いつかない。でも競プロではある程度自明なことはそのまま信じよう。次に塗りつぶし系は実験が大事。こういう問題ではまずロジックを考えるのではなく愚直に実行して可視化してみるべき。
