ABC005 おいしいたこ焼きの焼き方

D おいしいたこ焼きの焼き方

Submission #2481293 - AtCoder Beginner Contest 005

所見

必要な要素は二次元累積和とテーブル生成による再計算の省略。二次元累積和は見た瞬間思いつけたが、テーブル生成は思いつかず結局1時間50分かけてしまった。とはいえ両方自力で思いつけたのには成長を感じる

問題概要

N*Nの盤面があり、1つ1つのマスにはおいしさが定義される。N²人の店員が面積P[i]の領域でたこ焼きを焼けるとき、それぞれの店員が出せるおいしさの最大値を求めよ。制約はN<=50である。

取った方針

愚直に計算すると、一人当たりO(N⁶)(長方形がN⁴個、そのおいしさの和を求めるのにN²)かかり、それがN²人いるのでO(N⁸)となり間に合わない。
二次元累積和を用いると、事前計算がO(N²)で、おいしさの和をO(1)で求めることができるようになる。それによりO(N⁶)で求められるようになるが、N<=50のためまだ間に合わない。
面積がnのときのおいしさの最大値は店員によって変化しないことを利用して、O(N⁴)の事前計算で面積がn以下の時のおいしさの最大値のテーブルを作っておくと、店員ごとにすべての長方形のおいしさを計算する必要がなくなり、事前計算O(N⁴)、店員N²に対する回答O(N²)になり間に合う。

正しい方針

同上

得られた知見

・二次元累積和の実装(paizaのこれがわかりやすい)
・同じ計算が何度も行われる && 事前計算で全体のテーブルを作っても間に合う 場合、テーブルを作ることが有効
・累積和 っぽい最大値の持ち方

解くのに必要な要素

・二次元累積和
・事前計算によるテーブル生成
・累積和っぽい最大値の持ち方(面積n以下におけるおいしさの最大値をtable[n]に入れておく)

周辺調査によって得られた知見

特になし