水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

square869120Contest #4:C - Calendar 2

問題

beta.atcoder.jp

解法

lcm(7, m) のマスは 0 のマスと塗られているかどうかは同じになるので,lcm(7, m) - 1 のマスまでマス目を塗るシミュレーションをすれば十分.縦 lcm(7, m) / 7 マス,横 7 マスの表を S と置く.S の下に新しく S をつけ足していくことを考える.この時,白いマスの連結個数は S の個数を k と置くと

a + d (k - 1)

で表される(故に等差で増えていく).a は S 単独の白いマスの連結個数であり, d は S を上下に2つ繋げたものの白いマスの連結個数から S 単独の白いマスの連結個数を引けば求まる.それぞれ DFS をすれば求まる.k は n / ( (lcm(7, m) / 7) ).O(m).

解答

beta.atcoder.jp

解法がすぐに考え付いて,一発 AC 出来たのでよかった.

f:id:babcs2035:20181102201532p:plain