日本情報オリンピック 第3回 女性部門

2023年1月24日
情報オリンピック日本委員会

問題文

机の上に，縦 H 行，横 W 列の長方形状にコインが並べられている． 最初，上から i 行目 (1 ≦ i ≦ H)，左から j 列目 (1 ≦ j ≦ W) のコインは， S_i,j= # のとき表面，S_i,j= . のとき裏面が見えている状態である．

葵と凛は，これらのコインを用いてゲームを行うことにした．ゲームは以下のような流れで行われる．

1. 葵がどれか 1 つの行を選び，その行のコインをすべてひっくり返す．
2. 凛がどれか 1 つの列を選び，その列のコインをすべてひっくり返す．
3. 葵が，表面が見えるコインをすべて獲得する．また凛が，裏面が見えるコインをすべて獲得する．

葵と凛はそれぞれ，できるだけ多くのコインを獲得したい．

ゲーム開始時のコインの状態が与えられたとき， 両者が最善を尽くした場合にそれぞれが獲得できるコインの枚数を求めるプログラムを作成せよ．

制約

• H ≧ 1．
• W ≧ 1．
• H × W ≦ 500 000．
• S_{i, j} は #，. のいずれかである (1 ≦ i ≦ H，1 ≦ j ≦ W)．
• H, W は整数である．

小課題

1. (2 点) H = 1，W = 1．
2. (8 点) H = 1，W ≦ 40．
3. (9 点) H ≦ 40，W = 1．
4. (14 点) H = 2，W = 2．
5. (23 点) H ≦ 40，W ≦ 40．
6. (18 点) H ≦ 250，W ≦ 250．
7. (26 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．
H W
S_1,1 S_1,2 … S_1,W
S_2,1 S_2,2 … S_2,W
︙
S_H,1 S_H,2 … S_H,W

出力

葵と凛の得点をこの順に空白区切りで出力せよ．

入出力例

入力例 1
1 1
#

出力例 1
1 0

この入力例では，必ず以下のようにゲームが進行する．

1. まず，葵が 1 行目のすべてのコインをひっくり返す．
2. 次に，凛が 1 列目のすべてのコインをひっくり返す．

このとき，唯一のコインの見える面は「表→裏→表」と変化するため，葵が 1 枚のコインを獲得できるが，凛はコインを獲得できない．したがって，1，0 をこの順に空白区切りで出力する．

なお，この入力例は小課題 1, 2, 3, 5, 6, 7 の制約を満たす．

入力例 2

5 5
#####
####.
###..
##...
#....

出力例 2
13 12

両者が最善を尽くした場合の，ゲームの進行の一例を下図に示す．

この入力例は小課題 5, 6, 7 の制約を満たす．

入力例 3
1 40
..........##########..........##########

出力例 3
19 21

この入力例は小課題 2, 5, 6, 7 の制約を満たす．

入力例 4
7 1
#
#
#
#
#
#
#

出力例 4
1 6

この入力例は小課題 3, 5, 6, 7 の制約を満たす．

入力例 5

5 5
.###.
...##
..##.
.##..
##...

出力例 5
11 14

この入力例は小課題 5, 6, 7 の制約を満たす．

入力例 6

10 40
........................................
..######.....####.....#####.....####....
.....#......#....#......#......#........
.....#......#....#......#......#........
.....#......#....#......#......#........
.....#......#....#......#......#..####..
..#..#......#....#......#......#....#...
..#..#......#....#......#......#....#...
...##........####.....#####.....####....
........................................

出力例 6
104 296

この入力例は小課題 5, 6, 7 の制約を満たす．