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

問題

D: おいしいたこ焼きの焼き方 - AtCoder Beginner Contest 005 | AtCoder

ソースコード

解説

AtCoder Beginner Contest 005 解説 from AtCoder Inc.

www.slideshare.net

AtCoderより

こちらを参考に。

実装の流れ

1. ある点から始点(1, 1)までの範囲の美味しさの合計を算出
2. それぞれのサイズ(面積)で作られる長方形において、最大の「美味しさ」を算出
3. 書くプレイヤーが焼けるサイズに対応する「美味しさ」を出力

ポイント１

スライドでは右下から動的計画法だが、配列のインデックスに対応させソースでは左上から行っている。 これにより計算量はO(n²)。

ポイント２

int maxTasteWithSize(int size)について

引数に指定したサイズで作られる長方形の中で、美味しさが最大になる時の最大値を返すメソッド。

こうすることで、sizeで作られる長方形の幅と高さが決定する。 size = 4の時、 width = 3の場合４で割り切れないので横幅になることはできない。width = 4の場合、heightは１と決定され1 × 4の長方形ができることが分る。

(x, y)と(x + width, y + height)の２点でできる長方形の美味しさの合計を求める。

(1, 1)と(x + width, y + height)で作られる長方形から、いらない部分の長方形を引く。引きすぎてしまった長方形を足す。

ポイント３

今回は指定したサイズの面積の全てを使わないパターンが最大になることもある。

よって、

によって最大値を更新し続ける必要がある。 これによってできたtastesは、そのインデクスの数(サイズ)で作られた長方形の最大美味しさに対応しているので、プレイヤーが作成できるたこ焼きの数に応じて出力させる。