A - パ研合宿2103

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 100 点

問題文

筑駒パ研が成長し，全国有数の大企業と肩を並べる規模となった 2103 年，「パ研合宿2103」が開催されることとなりました．

「パ研合宿2103」は，12 月 A 日の朝に始まり，12 月 B 日の夕方に終わります．

この合宿は何日間でしょうか．

制約

  • 1 \leq A \leq B \leq 31．
  • 入力はすべて整数

部分点

この問題には部分点は存在せず，すべてのテストケースに正解すると 100 点が与えられます．

入力

入力は以下の形式で標準入力から与えられます． 

A B

出力

「パ研合宿2103」が何日間の合宿か，整数で出力してください．

入力例 1

24 27

出力例 1

4

入力例1において，「パ研合宿2103」は，12 月 24 日に始まり，12 月 27 日に終わります．
そのとき，合宿は 12/24, 12/25, 12/26, 12/27 の 4 日間かけて行われます．

入力例 2

15 15

出力例 2

1

「パ研合宿2103」は 1 日しか行われない場合があることに，注意してください．

入力例 3

9 22

出力例 3

14
B - 多数決

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 100 点

問題文

ある日，パ研のイメージカラーを「黒」にするか「白」にするか決めるために，投票が行われることになりました．

N 人の投票者は，どちらをイメージカラーをすべきか投票しました．より具体的には，i 番目の投票者はイメージカラー S_i に投票しました．ただし，S_i が black の場合「黒」に投票したことを表し，white の場合「白」に投票したことを表します．

イメージカラーは多数決によって，投票した人数が多い方に決まります．

パ研のイメージカラーが何色になるかを求めるプログラムを書いてください．

制約

すべての入力データは，以下の制約を満たす．

  • N は 1 以上 99 以下の奇数
  • S_i は black と white のどちらか一方

部分点

この問題はいくつかの小課題に分けられ，その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます．
提出したソースコードの得点は，正解した小課題の点数の合計となります．

  1. (50 点) N = 1 である．
  2. (50 点) 追加の制約はない．

入力

入力は以下の形式で標準入力から与えられます． 

N
S_1
S_2
S_3
 :
S_N

出力

パ研のイメージカラーが黒になるなら black，白になるなら white と，1 行で出力してください．

入力例 1

1
black

出力例 1

black

この場合、1 人しか投票者がいません．ただ 1 人の投票者は「黒」に投票したので，パ研のイメージカラーは黒になります．

入力例 2

7
black
white
white
white
white
white
black

出力例 2

white

「黒」に投票した人が 2 人、「白」に投票した人が 5 人なので、「白」に投票した人数の方が多いです．
そうして，パ研のイメージカラーは白になります．

入力例 3

9
black
black
black
black
black
black
black
black
black

出力例 3

black

9 人全員が「黒」に投票しましたので，パ研のイメージカラーは「黒」になります．
全会一致で決まる場合もあります．

C - カラオケ

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 100 点

問題文

1, 2, ..., N と番号づけられている N 人の生徒から成るグループが，「全国統一カラオケコンテスト」に出場することとなりました．

このコンテストで歌える曲は，曲 1，曲 2，...，曲 M の M 曲あります．また，番号 i の生徒が曲 j を歌うと，必ず A_{i, j} 点を取ります．

さて，コンテストのルールは，以下のようになります．

  • M 曲の中から 2 つの曲を選ぶ．（それぞれ T_1 と T_2 とする．）
  • それぞれの生徒が，曲 T_1 と曲 T_2 の両方を歌う．
  • 各生徒の得点は，その生徒が歌った 2 つの曲の点数のうち高い方となる．
  • グループの得点は，生徒 1, 2, ..., N の得点の合計となる．

そのとき，グループの得点として考えられる最大の値を求めてください．

制約

  • 1 \leq N \leq 100
  • 2 \leq M \leq 100
  • 0 \leq A_{i, j} \leq 100 \ 000 \ 000
  • 入力はすべて整数

部分点

この問題はいくつかの小課題に分けられ，その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます．
提出したソースコードの得点は，正解した小課題の点数の合計となります．

  1. (10 点) N = 1，M = 2．
  2. (25 点) M = 2．
  3. (35 点) N = 1．
  4. (30 点) 追加の制約はない．

入力

入力は以下の形式で標準入力から与えられます． 

N M
A_{1, 1} A_{1, 2} A_{1, 3} ... A_{1, M}
A_{2, 1} A_{2, 2} A_{2, 3} ... A_{2, M}
A_{3, 1} A_{3, 2} A_{3, 3} ... A_{3, M}
:
A_{N, 1} A_{N, 2} A_{N, 3} ... A_{N, M}

出力

グループの得点として考えられる最大の値を，整数で出力してください．

注意

この問題におけるカラオケは，通常のカラオケとは違い，100 \ 000 \ 000 点までの点数が出ることがあります．
また，点数は必ず整数となり，314159.265 点のような整数でない点数が出ることはありません．

入力例 1

1 2
80 84

出力例 1

84

生徒 1 の曲 1 の点数は 80 点，曲 2 の点数は 84 点です．よって，生徒 1 の得点は 84 点となります．
また，グループには 1 人しか生徒がいないため，グループの得点は 84 点となります．

なお，この入力例は，小課題 1 の制約を満たします．

入力例 2

3 4
37 29 70 41
85 69 76 50
53 10 95 100

出力例 2

250

例えば，このグループが曲 1 と 3 を歌った場合：

  • 生徒 1 : 曲 1 の点数は 37 点，曲 3 の点数は 70 点．よって，この生徒の得点は 70 点．
  • 生徒 2 : 曲 1 の点数は 85 点，曲 3 の点数は 76 点．よって，この生徒の得点は 85 点．
  • 生徒 3 : 曲 1 の点数は 53 点，曲 3 の点数は 95 点．よって，この生徒の得点は 95 点．

よって，このグループの得点は 70+85+95=250 点となります．グループの得点を 251 点以上にする方法はありません．

入力例 3

8 2
31000000 41000000
59000000 26000000
53000000 58000000
97000000 93000000
23000000 84000000
62000000 64000000
33000000 83000000
27000000 95000000

出力例 3

581000000

この入力例は，小課題 2 の制約を満たします．

D - パ研軍旗

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 100 点

問題文

筑駒パ研は，近い将来，パ研戦争に臨むことになりました．そのために，軍旗を作ることになりました．

旗のデザインは縦に 5 個，横に N 個に分かれた 5 \times N のマス目で表されます．上から i 行目，左から j 列目のマスを，(i, j) で表すことにします．

現在，旗のそれぞれのマスは赤・青・白・黒のいずれかで塗られています．より具体的には，マス (i, j) は色 S_{i, j} で塗られています．ただし，S_{i, j} は R, B, W, # のいずれかで，それぞれ赤・青・白・黒で塗られていることを表しています．

E869120 君は，パ研軍旗を、次の条件を満たすように青・白・赤で塗り替えたいです．

  • N 個の列すべてにおいて，その列の 5 マスが「全部青」「全部白」「全部赤」のいずれかである
  • どの隣り合った 2 つの列も，色が異なる

ただし，黒いマスがあったら条件を満たさないことに注意してください．

以下が，条件を満たす旗と条件を満たさない旗の例です．

  • 例 1 は条件を満たします．
  • 例 2 は，例えば左から 2 番目の列で青と白のマスがあり，5 つ全部同じになっている必要があるという条件を満たしません．
  • 例 3 は，例えば左から 3 番目の列と左から 4 番目の列の色が同じなので，条件を満たしません．
  • 例 4 は，例えば左から 5 番目の色が黒になっているので，条件を満たしません．

E869120 君は，旗の作成時間を短くするため，できるだけ塗り替えるマスの個数を少なくしたいです．
最小でいくつのマスを塗り替える必要があるか求めるプログラムを書いてください．

制約

すべての入力データは，以下の制約を満たす．

  • N は 1 \leq N \leq 999 をみたす整数
  • S_{i, j} は R, B, W, # のいずれか

部分点

この問題はいくつかの小課題に分けられ，その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます．
提出したソースコードの得点は，正解した小課題の点数の合計となります．

  1. (11 点) N = 1 である．
  2. (13 点) N = 3 である．
  3. (29 点) N \leq 10 である．
  4. (22 点) 5 つの行すべてにおいて，その行の N 個のマスがすべて同じ色である．
  5. (25 点) 追加の制約はない．

ただし，小課題 4 について，「N 個の列すべてにおいて，その列の 5 個のマスがすべて同じ色である」のような読み間違えをしないように注意してください．

入力

入力は以下の形式で標準入力から与えられます．
ただし、旗のそれぞれの行の色の情報 S_{i, 1}, S_{i, 2}, S_{i, 3}, \dots, S_{i, N} は，これがつながった N 文字の文字列として入力されることに注意してください． 

N
S_{1, 1} S_{1, 2} S_{1, 3} \cdots S_{1, N}
S_{2, 1} S_{2, 2} S_{2, 3} \cdots S_{2, N}
S_{3, 1} S_{3, 2} S_{3, 3} \cdots S_{3, N}
S_{4, 1} S_{4, 2} S_{4, 3} \cdots S_{4, N}
S_{5, 1} S_{5, 2} S_{5, 3} \cdots S_{5, N}

出力

パ研軍旗を作るときに塗り替える必要のあるマスの個数の最小値を，1 行で出力してください．

入力例 1

1
B
R
#
W
B

出力例 1

3

以下の 3 通りのパ研軍旗を作ることができます．

  • すべてのマスを赤にする．そのとき，マス (1, 1), (3, 1), (4, 1), (5, 1) の 4 マスを塗り替える必要がある．
  • すべてのマスを青にする．そのとき，マス (2, 1), (3, 1), (4, 1) の 3 マスを塗り替える必要がある．
  • すべてのマスを白にする．そのとき，マス (1, 1), (2, 1), (3, 1), (5, 1) の 4 マスを塗り替える必要がある．

その中では，「すべてのマスを青」にするのが最適です．そのとき，塗り替えるマスの個数は 3 個になります．

ちなみに，これは N = 1 なので，小課題 1 の制約をみたします．

入力例 2

3
WWR
#RW
BW#
##B
RBR

出力例 2

10

1 列目を青、2 列目を白、3 列目を赤にすると，塗り替えるマスの個数を 10 個にできて，これが最適です．

(ここでは，「★」は塗り替えられたマスを表します)

ちなみに，これは N = 3 なので，小課題 2 の制約をみたします．

入力例 3

8
RRRRRRRR
########
BBBBBBBB
RRRRRRRR
WWWWWWWW

出力例 3

28

次の図のように塗り替えるのが最適です．塗り替えるマスの数は 28 個となります．(ここでは，「★」は塗り替えられたマスを表します)

入力例 4

7
BR#WB#R
RWW#WRB
##WBR#W
WB#B#RW
BRW##BB

出力例 4

21

次の図のように塗り替えるのが最適です．塗り替えるマスの数は 21 個となります．(ここでは，「★」は塗り替えられたマスを表します)

E - 大きなクリスマスプレゼント

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 100 点

問題文

PAKEN City は，南北に H メートル，東西に W メートルの長方形の形をしています．これは南北に 1 メートルずつ，東西に 1 メートルずつに区切られた H \times W 個のマスに分けられており，北から i 番目，西から j 番目のマスを (i, j) で表します．

PAKEN City のいくつかのマスには建物が建っていて通れません，それ以外のマスは通行可能なマスです．より具体的には，S_{i, j} が # のとき建物が建っていて通れないことを表し，. のとき通行可能であることを表します．

サンタクロースの E869120 君は，パ研王国にプレゼントを Q 回配ることにしました．

i 回目のプレゼント配りは次のようになっています．

  • 最初，マス (X_i, Y_i) を左上のマスとして，一辺 L_i メートルの正方形の形をしたプレゼントが置かれている．
  • その後，プレゼントを移動することができる．より具体的には，「建物と重ならないように，プレゼントを回転させずに，東西南北のいずれかの方向にちょうど 1 メートル動かす」操作を何回か (0 回でも良い) 行う．

ただし，PAKEN City の外にプレゼントが一部でも出るような移動はしてはなりません．

それぞれのプレゼント配りで，最終的なプレゼントの位置として考えられるものは何種類あるかを求めてください．

制約

  • 1 \leq H \leq 1 \ 500
  • 1 \leq W \leq 1 \ 500
  • 1 \leq Q \leq 150 \ 000
  • H, W, Q はすべて整数である
  • Q 個すべてのプレゼントの最初の位置は PAKEN City の内部にあり，その L_i^2 個のマスに建物は一つもない

部分点

この問題はいくつかの小課題に分けられ，その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます．
提出したソースコードの得点は，正解した小課題の点数の合計となります．

  1. (13 点) H = 1，W \leq 200，Q = 1 で，プレゼントの一辺の長さ L_i は全て 1 である．
  2. (13 点) H \leq 200，W \leq 200，Q = 1 で，プレゼントの一辺の長さ L_i は全て 1 である．
  3. (19 点) プレゼントの一辺の長さ L_i は全て 1 である．
  4. (11 点) H \leq 200，W \leq 200，Q = 1 である．
  5. (11 点) H \leq 200，W \leq 200，Q \leq 1 \ 000 である．
  6. (11 点) H \leq 200，W \leq 200 である．
  7. (22 点) 追加の制約はない．

入力

入力は以下の形式で標準入力から与えられます． 

H W
S_{1, 1} S_{1, 2} S_{1, 3} \cdots S_{1, W}
S_{2, 1} S_{2, 2} S_{2, 3} \cdots S_{2, W}
S_{3, 1} S_{3, 2} S_{3, 3} \cdots S_{3, W}
 :  :   :
S_{H, 1} S_{H, 2} S_{H, 3} \cdots S_{H, W}
Q
X_1 Y_1 L_1
X_2 Y_2 L_2
X_3 Y_3 L_3
 :  :
X_Q Y_Q L_Q

出力

最初のプレゼント配りから順に，最終的なプレゼントの位置としてありうるものの種類数を，1 行ずつ出力してください．

入力例 1

1 10
.#..##...#
1
1 7 1

出力例 1

3

この入力例は小課題 1 の制約を満たします．

プレゼントは、最初の位置を含めて，以下のような 3 つの位置に動かすことができます．

入力例 2

6 5
#..#.
..#..
#.#..
..#..
.#..#
.#...
1
3 4 1

出力例 2

12

この入力例は小課題 2 の制約を満たします．

プレゼントは 12 つの位置に動かすことができます．

入力例 3

8 8
....#...
..#.....
......#.
#.......
...#....
.#......
.....#..
.......#
6
4 5 1
1 6 2
2 5 2
7 1 2
4 6 3
6 3 3

出力例 3

56
2
14
6
2
1
F - クリスマス飾り2

Time Limit: 2.5 sec / Memory Limit: 1024 MB

配点: 100 点

問題文

AtCoder 王国で最も高いタワーである，「AtCoder Tower」には，クリスマスを迎えるため，一直線上に N 個のオーナメントが飾られています．

オーナメントには N 種類の色があり，それぞれ色 1，色 2，色 3，..., 色 N と番号づけられています．最初，「AtCoder Tower」の，左から i 番目のオーナメントは，色 A_i です．

さて，国王である高橋君は，いくつかのオーナメントを選び，取り除くことによって，飾り付けを「見栄えが良い」状態にしたいと考えています．「見栄えが良い」状態というのは，以下の条件をすべて満たすことを指します．

  • 残されたオーナメントの色の種類数が，2 色以下である．
  • 隣り合うオーナメントの色が同じであるような場所は存在しない．

例えば，[A] [B] のような取り除き方をすると，「見栄えが良い」状態となります．

一方で，[C] [D] のような取り除き方をすると，「見栄えが良い」状態にはなりません．

ところで，「AtCoder Tower」では，クリスマスを迎えるための飾りつけが Q+1 日間に渡って行われます．i 日目の夜には，左から X_i 番目のオーナメントの色が，色 Y_i に変更されます．

そこで，i = 1, 2, ... Q+1 それぞれについて，以下の答えを求めてください．

  • もし高橋君が，i 日目の昼の段階で，飾りつけを「見栄えが良い」状態にする場合，最小で何個のオーナメントを取り除く必要があるでしょうか．

制約

  • 1 \leq N \leq 3 \ 000
  • 0 \leq Q \leq 7 \ 000
  • 1 \leq X_i \leq N
  • 1 \leq Y_i \leq N
  • 1 \leq A_i \leq N
  • 入力はすべて整数

部分点

この問題はいくつかの小課題に分けられ，その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます．
提出したソースコードの得点は，正解した小課題の点数の合計となります．

  1. (2 点) N = 1，Q = 0．
  2. (11 点) N \leq 15，Q = 0．
  3. (12 点) A_i \leq 2，Y_i \leq 2．
  4. (13 点) N \leq 250，Q = 0．
  5. (18 点) Q = 0．
  6. (44 点) 追加の制約はない．

ただし，小課題6に関しては，以下のように採点されます．

  • Q \leq 600 を満たすテストケースすべてに正解すると，24 点が与えられる．
  • Q \leq 1 \ 500 を満たすテストケースすべてに正解すると，さらに5 点が与えられる．
  • Q \leq 2 \ 500 を満たすテストケースすべてに正解すると，さらに5 点が与えられる．
  • Q \leq 4 \ 500 を満たすテストケースすべてに正解すると，さらに5 点が与えられる．
  • すべてのテストケースに正解すると，さらに5 点が与えられる．

小課題3のヒント

この小課題は，どの日においても，オーナメントの色が色 1 と色 2 しかありません．つまり，「見栄えの良い」状態において，残されたオーナメントを左から見たとき，色 1, 2, 1, ... と交互に並んでいるか，色 2, 1, 2, ... と交互に並んでいるかのどちらかしかありません．小課題 3 に取り掛かる人は，このヒントを踏まえて考えてみるのも良いでしょう．

入力

入力は以下の形式で標準入力から与えられます． 

N
A_1 A_2 A_3 ... A_N
Q
X_1 Y_1
X_2 Y_2
X_3 Y_3
:
X_Q Y_Q

出力

Q+1 行に渡って出力してください．
i 行目には，i 日目の昼の時点で飾りつけを「見栄えの良い」状態にするために，最小で何個のオーナメントを取り除く必要があるか，出力してください．

入力例 1

1
1
0

出力例 1

0

この入力例において，オーナメントを取り除かなくても，飾りつけは「見栄えの良い状態」です．
よって，0 と出力するのが正解となります．

入力例 2

10
1 3 4 2 3 1 4 2 1 4
0

出力例 2

4

以下の図のように，4 つのオーナメントを取り除くと，「見栄えの良い」状態となります．

なお，この入力例は，小課題2の制約を満たします．

入力例 3

12
8 9 9 4 4 11 11 8 4 9 9 4
10
3 9
1 4
2 9
10 11
7 4
1 8
3 8
6 9
6 8
2 9

出力例 3

8
8
7
7
7
7
7
7
6
6
6

Q=10 ですので，11 行に渡って出力しなければなりません．

G - プレゼント配り2

Time Limit: 5 sec / Memory Limit: 1024 MB

配点: 100 点

問題文

E869120 君は「AtCoder サンタ事務局」の社員であり，サンタにプレゼントを効率的に配らせるための仕事を，毎年行っています．

さて，今年もクリスマスがやってきました．彼の今年の仕事は，「AtCoder 通り」において，サンタと家の位置の情報を仕入れ，サンタのプレゼント配りを効率化することです．

AtCoder 通りは，西から東に走る，長さ 1 \ 000 \ 000 \ 000 の道路です．最初，E869120 君に入ってきた，家の位置とサンタの位置の情報は，以下のようになります．

  • その通りに家は N 軒ある．家には 1, 2, ..., N と番号づけられており，番号 i の家は，道路の西端から A_i メートルの位置にある．
  • その通りにサンタは M 人いる．サンタには 1, 2, ..., M と番号づけられており，番号 i のサンタは，道路の西端から B_i メートルの位置にいる．

しかし，AtCoder 通りでは，家の引っ越しやサンタの移動などがたびたび起こります．そのため，クリスマスまでに Q 回の情報変更が行われます．i 回目の情報変更について，

  • T_i = 1 のとき：番号 C_i の家の位置が，道路の西端から D_i メートルの位置に変更される．
  • T_i = 2 のとき：番号 C_i のサンタの位置が，道路の西端から D_i メートルの位置に変更される．

そのとき，i = 0, 1, 2, ..., Q について，i 回目の変更直後の情報において，以下の問題に答えてください．

  • すべての家にプレゼントが配られるために，M 人のサンタを合計して，何メートル移動する必要があるか，求めよ．
  • ただし，すべてのサンタは常にプレゼントを十分な個数持っているものとする．
  • また，サンタは家のある位置に移動することによって，プレゼントを配ることができる．遠い位置からプレゼントを投げて配るなどということはできない．サンタ達はプレゼントを配り終わった後，元の場所に戻る必要はない．

ただし，「0 回目の変更直後の情報」というのは，最初に E869120 君に入ってきた情報のことを指します．

制約

  • 1 \leq N \leq 100 \ 000
  • 1 \leq M \leq 100 \ 000
  • 0 \leq Q \leq 100 \ 000
  • 0 \leq A_i \leq 1 \ 000 \ 000 \ 000, A_i は偶数
  • 0 \leq B_i \leq 1 \ 000 \ 000 \ 000, B_i は奇数
  • 1 \leq T_i \leq 2
  • T_i = 1 のとき，1 \leq C_i \leq N，0 \leq D_i \leq 1 \ 000 \ 000 \ 000 を満たし，D_i は偶数である．
  • T_i = 2 のとき，1 \leq C_i \leq M，0 \leq D_i \leq 1 \ 000 \ 000 \ 000 を満たし，D_i は奇数である．
  • 2 つの家が同じ位置に来るような情報の変更はない．
  • 2 つのサンタが同じ位置に来るような情報の変更はない．

部分点

この問題はいくつかの小課題に分けられ，その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます．
提出したソースコードの得点は，正解した小課題の点数の合計となります．

  1. (2 点) M = 1，Q = 0．
  2. (6 点) M = 2，Q = 0．
  3. (14 点) N \leq 250，M \leq 250，Q = 0．
  4. (9 点) N \leq 3 \ 000，M \leq 3 \ 000，Q = 0．
  5. (9 点) Q = 0．
  6. (35 点) N \leq 40 \ 000, M \leq 40 \ 000, Q \leq 40 \ 000, T_i = 1．
  7. (19 点) N \leq 40 \ 000, M \leq 40 \ 000, Q \leq 40 \ 000．
  8. (6 点) 追加の制約はない．

入力

入力は以下の形式で標準入力から与えられます． 

N
A_1 A_2 A_3 ... A_N
M
B_1 B_2 B_3 ... B_M
Q
T_1 C_1 D_1
T_2 C_2 D_2
T_3 C_3 D_3
: : :
T_Q C_Q D_Q

出力

Q+1 行に渡って出力してください．
i 行目には，i-1 番目の変更の直後の情報において，サンタの合計移動距離の最小値を出力してください．

入力例 1

5
12 18 36 50 68
1
25
0

出力例 1

69

以下のようにサンタが移動する場合，合計移動距離 69 となり，これが最小です．

  • サンタ 1 が家 1 に移動し，プレゼントを配る．その時点での移動距離は 13 である．
  • サンタ 1 が家 2 に移動し，プレゼントを配る．その時点での移動距離は 19 である．
  • サンタ 1 が家 3 に移動し，プレゼントを配る．その時点での移動距離は 37 である．
  • サンタ 1 が家 4 に移動し，プレゼントを配る．その時点での移動距離は 51 である．
  • サンタ 1 が家 5 に移動し，プレゼントを配る．その時点での移動距離は 69 である．

入力例 2

5
138 218 224 110 146
2
127 157
0

出力例 2

120

この入力例は小課題2の制約を満たします．
なお，小課題2は，入力例 1 のような M = 1 の場合を含まないことにご注意ください．

入力例 3

10
2412 1276 1948 2000 2542 2558 2070 2712 2820 1542
6
3001 1545 1213 2473 2559 2019
0

出力例 3

595

この入力例は小課題 3, 4, 5 の制約を満たします．

入力例 4

10
2412 1276 1948 2000 2542 2558 2070 2712 2820 1542
6
3001 1545 1213 2473 2559 2019
7
1 2 1348
1 8 3200
2 3 2951
1 4 2102
2 5 1137
1 10 420
2 1 2207

出力例 4

595
667
866
778
830
959
1676
1840
H - パ研王国を守れ！

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 100 点

問題文

ついにパ研戦争が始まりました！

パ研戦争の戦場は，N \times N のマス目で表されます．この戦場の，上から i 番目，左から j 番目のマスを (i, j) で表すことにします．

ここに，パ研王国の兵士が M 人，敵国の兵士が M 人立っています．より具体的には，S_{i, j} が X のときマス (i, j) にはパ研王国の兵士が立っており，Q のとき敵国の兵士が立っています．. のときは何もないマスです．

敵国の兵士は，銃を上下左右斜めの 8 方向に撃つことができます．(具体的には，下図のようになっています)

敵国の兵士がパ研王国の兵士を直接撃てる状況にしないために，銃を通さないブロックをいくつかのマスに設置することにしました．ブロックを置ける条件は以下の通りです．

  • パ研王国の兵士も敵国の兵士もいない，何もないマスであること．

できるだけ少ない数のブロックで，どの敵国の兵士もパ研王国の兵士を直接撃つことができないようにする方法を 1 つ求めてください．

ただし，置いたブロックの個数に応じてこの問題の得点が決まるので，ブロックの個数を完全に最小化する必要はないことに注意してください．

制約

すべての入力データは，以下の制約を満たします．

  • N = 100
  • M = 300
  • S_{i, j} は Q，X，. のいずれか
  • S_{i, j} が Q となるマスは，ちょうど M 個
  • S_{i, j} が X となるマスは，ちょうど M 個

テストケース生成について

パ研王国の兵士と敵国の兵士の位置は，「パ研王国の兵士と敵国の兵士が上下左右斜めに隣り合うことはない」という条件を満たす中でほぼランダムに生成されます．具体的には、こちら の生成コードを元に作られております．

得点

提出に対する得点は，以下のように決定されます．

  • 採点に使われる 20 個のテストケースのうち，1 つでも条件を満たさない出力（不正なフォーマット・敵国の兵士がパ研王国の兵士を直接撃てるような出力）があれば，0 点となります．
  • そうでない場合，i 個目のテストケースの得点を a_i 点とするとき，提出に対する得点は floor(\frac{a_{1}+a_{2}+a_{3}+...+a_{20}}{20}) 点となります．

なお，各テストケースに対する得点は，置いたブロックの個数を L とするとき，以下のように定められます．

  • 2 \ 401 \leq L のとき，5 点．
  • 1 \ 901 \leq L \leq 2 \ 400 のとき，14 点．
  • 1 \ 501 \leq L \leq 1 \ 900 のとき，17 点．
  • 1 \ 201 \leq L \leq 1 \ 500 のとき，20 点．
  • 1 \ 001 \leq L \leq 1 \ 200 のとき，23 点．
  • 481 \leq L \leq 1 \ 000 のとき，50 - (L - 480) \times 0.05 点．
  • 431 \leq L \leq 480 のとき，100 - (L - 430) \times 1 点．
  • L \leq 430 のとき，100 点．

入力

入力は以下の形式で標準入力から与えられます． 

N M
S_{1, 1} S_{1, 2} S_{1, 3} \cdots S_{1, N}
S_{2, 1} S_{2, 2} S_{2, 3} \cdots S_{2, N}
S_{3, 1} S_{3, 2} S_{3, 3} \cdots S_{3, N}
 :  :  :
S_{N, 1} S_{N, 2} S_{N, 3} \cdots S_{N, N}

出力

マス (i, j) の状態 V_{i, j} を，次のような文字とします．

  • マス (i, j) にブロックが置かれない場合，V_{i, j} = S_{i, j}
  • マス (i, j) にブロックが置かれる場合，V_{i, j} = #

このとき，次のような形式で答えを出力してください． 

V_{1, 1} V_{1, 2} V_{1, 3} \cdots V_{1, N}
V_{2, 1} V_{2, 2} V_{2, 3} \cdots V_{2, N}
V_{3, 1} V_{3, 2} V_{3, 3} \cdots V_{3, N}
 :  :  :
V_{N, 1} V_{N, 2} V_{N, 3} \cdots V_{N, N}

入出力例

例えば，以下の入力例を考えましょう．（N, M が制約の条件を満たさないため，採点に用いられるデータには含まれません．）

7 3
.Q.....
....X..
.......
.X....Q
.......
Q.....X
.......

この入力例において，ブロックを考えないとき，戦場は以下のようになります．

さて，以下の出力をすると，正解となります．この場合に置いたブロックの個数 L = 6 となります．（図A に対応します‥）

.Q.....
.#..X..
...#.#.
.X..#.Q
......#
Q..#..X
.......

また，以下の出力をすると，不正解となります．マス (1, 2) にいる敵国の兵士が，マス (4, 2) にいるパ研王国の兵士を撃つことができるからです．

.Q.....
....X..
....##.
.X..##Q
#######
Q...##X
....##.

なお，この入力例は，N = 100，M = 300 の条件を満たさないため，テストデータには含まれません．
採点に用いられるすべてのテストケースは，N = 100，M = 300 を満たします．