ABC005を解いた
今回はAtCoder Beginner Contest 005を解きました． 公式解説はこちら．
怒涛のたこ焼き推し．
A おいしいたこ焼きの作り方
自力完答
割り算をして小数点以下を切り捨てればできる．簡単．
B おいしいたこ焼きの食べ方
自力完答
単純に最小値を求めれば良い．
C おいしいたこ焼きの売り方
自力完答
ちょっとこの問題で詰まった．結局，たこ焼きリストとお客リストを，それぞれ別のインデックスで管理することによって処理した．
ループを抜ける条件を勘違いしていたためにちょっと詰まってしまった．問題文はちゃんと読むべき．
D おいしいたこ焼きの焼き方
自力では解けず．解説見て100点
自力では解けなかった．どうやって長方形を列挙すれば良いのかがわからなかったが，公式解説を見て理解できた．
アルゴリズムの流れを簡単にまとめるとこうなる．
- 各場所から右下までの領域を動的計画法で求める．
- たこ焼き器上で取りうる全ての長方形の領域を求める．
- 長方形の面積(たこ焼きの個数)とたこ焼きの美味しさを記録する．
- 美味しさの最大値を塗りつぶす(公式解説参照)．
右下までの領域を求めてから，全長方形を列挙することによって，計算時間を大幅に短縮できる． このように，大きい問題をいくつかの小さい問題に分けて解くことを分割統治法と呼ぶらしい． このことさえわかってしまえば，実装はさほど難しくなかった．
途中で出てくるrange(n)[::-1]は，こう書くとの順番でfor文を回せるのでとても便利．
ゴリ押しで全列挙するのではなく，問題を分けて考えることが重要だと思った．
