Official

A - Three Cells per Row and Column Editorial by maroonrk_admin


\(N\)\(3\) の倍数の時は簡単です. 以下のように,\(3\) 個横並びになった黒いマスを各行に設置すればよいです.

###......
...###...
......###
###......
...###...
......###
###......
...###...
......###

\(N\)\(3\) の倍数でないときに同じように置こうとすると,黒いマスが右と左で分裂してしまう行があります.

###.......
...###....
......###.
##.......#
..###.....
.....###..
#.......##
.###......
....###...
.......###

上は \(N=10\) の例です. \(4\) 行目と \(7\) 行目で分裂しているため,連結成分の個数が \(N+2\) になってしまいます. そこで,\(1\) 行目と \(3\) 行目,および \(8\) 行目と \(10\) 行目を swap することで \(2\) 個の連結成分を連結し,成分の個数を \(N\) にすることができます.

...###....
......###.
###.......
##.......#
..###.....
.....###..
#.......##
.......###
.###......
....###...

一般の \(N\) に対しても同様に,\(1\) 行目と \(\lfloor N/3 \rfloor\) 行目,および \(N-\lfloor N/3 \rfloor +1\) 行目と \(N\) 行目を入れ替えることで,構成が可能です.

posted:
last update: