SRM637 Div1Medium can be solved even if the width of the board is very very large.
There is O(|black cells|) solution.
Let's consider only 8 cells near the edge. There are three(four) cases:
1) There are black cells in both side.
In this case, already result is fixed because the players can not change a parity of the number of turns while the game ends.
2) There are black cells in only one side.
In this case, the first player can win because he can decide a parity by coloring the other side cell black.
3) There is no black cell in both side.
In this case, the player who color a side cell black at the first loses. Hence the winner in the board without 8 side cells wins. You can determine the winner recursively.
0) The width of the board is less than 4.
In this case, it is easy to determine the winner.