問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!
※この問題は、2021年1月に開催されたP共通テスト(バンタンテックフォードアカデミー中高プログラミング共通テスト)で出題された問題です。
ここにあなたの友人が撮影した長方形の白黒画像があり、縦 H マス、横 W マスのマス目状に分割されています。
この画像において、上から i 番目、左から j 番目のマスの色は、S_i_j = 0
なら白、S_i_j = 1
なら黒です。
あなたは、この画像から縦 N マス以上、横 M マス以上の、グリッドに沿った長方形の白黒画像のうち、
出来るだけ黒い画像を切り抜きたいと考えています。
ここで、切り抜いた画像の黒さを、(長方形に含まれる黒色のマスの数) / (長方形のすべてのマスの数)
と定義することにします。
縦 N マス以上、横 M マス以上の長方形の白黒画像を切り抜くとき、その黒さの最大値を求めてください。
H W N M
S_1
S_2
...
S_H
与えられた白黒画像から縦 N マス以上、横 M マス以上の長方形の白黒画像を切り抜くときの、問題文に定義した黒さの最大値を小数で 1 行で出力してください。
出力した値と真の値の絶対誤差が 10^{-6} 以下であれば正解となります。
すべてのテストケースにおいて、以下の条件を満たします。
・入力はすべて整数
・1 ≦ H ≦ 10
・1 ≦ W ≦ 10,000
・1 ≦ N ≦ H
・1 ≦ M ≦ W
・S_i_j = 0 または S_i_j = 1
3 3 2 2
101
010
101
0.555555555555555
4 7 2 3
1011010
0010011
1101100
0100101
0.625000000000000