ABCの昔の問題を解いてみる(ABC 005 D)

#AtCoder ABC 005 D

これまで研究が忙しいとか何とか理由をつけて競プロを長いことサボりまくっていたが、この前のARCで少し熱を取り戻したのでABCの古い問題を解いてみることにした。
加えてこれまで基本Pythonを使い続けてきたが、最近C++にちょっと慣れてきたのでこの際全部C++で書いてみる事にした。慣れてる人からみると、「へっ、汚ねえコードだ(某王子)」って思うかもしれないが所詮自分用のメモだしOKや

ABC005D(問題の詳細はリンク先で見てください)
たこ焼きに関する問題です。(語弊)

関西出身でたこ焼きとともに成長してきた(?)身としてこれは是非とも解きたい。
##解法
これは２次元の累積和ですね間違いない(脊髄反射)。

とりあえずまずは入力部と累積和の部分を書いてみよう(見切り発車)。

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

int main(){
    int N;
    cin >> N;
    vector<vector<ll> > D(N+1, vector<ll>(N));
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> D[i][j] ;
        }
    }
    vector<vector<ll> > CS(N+1, vector<ll>(N+1)); /*CSはCumulative Sum(累積和)のつもり */
    
    for(int x = 0; x < N; x++){
        for(int y = 0; y < N; y++){
            CS[x+1][y+1] = CS[x][y+1] + CS[x+1][y] -CS[x][y] + D[x][y];
        }
    }
}

CS[x][y]は長方形[0,x), [0,y)内のDの総和。

今欲しいのは長方形の面積が「P以下」という縛りの元での最大値だから、面積「P」の長方形のそれを全部あげてみる。
(※さも簡単にわかったふりをしてるがここまででかなりの思考時間を費やしている)

    vector<ll> maxval(N*N); /*配列のi番目に面積iの長方形で総和が最大のものを収納*/
/*xlはxlow, xhはxhighのつもり、なんでもいいが*/
    for(int xl = 0; xl < N; xl++){
        for(int xh = xl + 1; xh <= N; xh++){
            for(int yl = 0; yl < N; yl++){
                for(int yh = yl + 1; yh <= N; yh++){
                    ll P = (xh-xl)*(yh-yl);
                    ll sum = CS[xh][yh] -CS[xl][yh] -CS[xh][yl] + CS[xl][yl];
                    maxval[P] = max(maxval[P],sum);
                }
            }
        }
    }

正直に告白すると最大値を更新するところを忘れててなんで上手くいかないんだ！？と長い時間苦しんでた。

ここまでくればあとは面積「P以下」での最大値に各maxval[i]を更新する。これは次のようにすれば良い。

    for(int i=0; i<N*N; i++){
         maxval[i+1] = max(maxval[i+1],maxval[i]);
    }

あとは各店員さんのPについてmaxvalを表示すればOK

    ll Q;
    cin >> Q;
    vector<ll> P(Q);
    for(int i=0; i<Q; i++){
        cin >> P[i];
    }
    for(int j=0; j<Q; j++){
        cout << maxval[P[j]] << endl;
    }

これで元の問題の入力例２

3
3 2 1
2 2 1
1 1 1
3
1
4
9

を入れると

3
9
14

と正しい解が得られた。

他にもパッと解がわかる例を入れてみると

5
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
5 6 7 8 9
4
1
4
3
2

で

9
32
24
17

になったので大丈夫そうだ。

#感想
この店はたこ焼き器を買い直すべきである。