AtCoder ABC 005 D おいしいたこ焼きの焼き方

(※Qiitaにも全く同じものを投稿しています(そのうち完全にこちらに乗り換え予定))

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

ABC005D たこ焼きに関する問題です。(語弊)

問題

高橋君のたこ焼き屋で使っているたこ焼き器は焼く場所によって美味しさの変わるクセの強いたこ焼き器です。また、店員の力量によって一度に焼けるたこ焼きの数が違います。高橋君はそれぞれの店員ができるだけ美味しくたこ焼きを焼けるようにしようと思いました。たこ焼き器は $N×N$ の正方形をしています。それぞれの場所ごとにたこ焼きの美味しさ $D_{ij}$ が決まっています。それぞれの店員は一度に焼けるたこ焼きの上限 $P _ k$ が決まっています。また、一度に焼くたこ焼きは必ずたこ焼き器の長方形の部分になっていて、その中の全てを使わなければなりません。それぞれの店員について一度に焼けるたこ焼きの美味しさの合計の最大値を求めて下さい。ただし、店員が焼き始める時はたこ焼き器が完全に空いていてどの場所でも使えるとします。

関西出身でたこ焼きとともに成長してきた(?)身としてこれは是非とも解きたい。

解法

これは２次元の累積和ですね間違いない(脊髄反射)。

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

#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
9
14

と正しい解が得られた。

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

で

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

感想

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

院生と物理学と+α

大学院生(専攻は相対論と量子情報)が学んだこととかつらつら書いていきます

ABCの昔の問題を解いてみる(ABC 005 D おいしいたこ焼きの焼き方)

AtCoder ABC 005 D おいしいたこ焼きの焼き方

解法

感想