Day 1 Task 3: 住み心地 (Quality of Living)

アルバータ州の市は格子状に区切られ，区画にわかれる傾向がある． 各区画は，南北座標(北から南へ順に 0 から R-1 までの番号を付ける)と，東西座標(西から東へ順に 0 から C-1 までの番号を付ける)によって区別される．

各区画は住み心地によって 1 以上 R*C 以下のそれぞれ異なる数で順位付けされている．これをランク (quality rank) と言う．ランクの最上位は 1 であり，最下位は R*C である．

都市計画局は南北方向の高さが H，東西方向の幅が W となるような長方形の範囲のうち，最もランクの中央値が高くなるようなものを知りたい． ただし，H と W はそれぞれ R と C を超えない奇数である． ランクが奇数個あるとき，ランクの中央値とは，m より上位のランクを持つ区画の数と m より下位のランクを持つ区画の数が等しくなるような m である．

プロシージャー rectangle(R,C,H,W,Q) を実装せよ． R と C は市の大きさを表し， H と W は長方形の大きさを表す． Q は南北座標が a，東西座標が b の区画のランクが Q[a][b] となる配列を表す．

あなたの実装は，ランクの中央値が最も良くなる（数字の上では最も小さくなる）高さ H，幅 W の長方形の範囲を見つけ，その範囲のランクの中央値を rectangle の返り値として返す必要がある．

各テスト実行は rectangle を一度だけ呼び出す．

例 1

R=5, C=5, H=3, W=3, 
Q=  5 11 12 16 25
   17 18  2  7 10
    4 23 20  3  1
   24 21 19 14  9
    6 22  8 13 15
この例では，ランクの中央値が最も良くなる（数字の上では最も小さくなる）範囲（Q の中央右の太字で示されている範囲）のランクの中央値は 9 である．つまり， 
rectangle(R,C,H,W,Q)=9
である．

例 2

R=2, C=6, H=1, W=5, 
Q=  6  1  2 11  7  5
    9  3  4 10 12  8
この例での正解は 5 である．

小課題 1 [20 点]

R と C は 30 を超えない．

小課題 2 [20 点]

R と C は 100 を超えない．

小課題 3 [20 点]

R と C は 300 を超えない．

小課題 4 [20 点]

R と C は 1 000 を超えない．

小課題 5 [20 点]

R と C は 3 000 を超えない．

実装の詳細