きろく

特筆すべき記録のまとめ

JOI '09 春合宿1:3- Pyramid 貫きピラミッド

問題

https://www.ioi-jp.org/camp/2009/2009-sp-tasks/2009-sp_tr-day1_20.pdf

解法

ピラミッドの頂点を通るような斜め状の (2 * h_i - 1) マスにピラミッドの各段の数を書き込む.このとき,マスに既に数が書かれている場合は,max を取る.この後,左上から右下にかけて,各マスに「左上・上・左のマスに書かれている数の max - 1」の値と各マスの max を書き込む.これだけではピラミッドの右下部分しか高さが反映されていないので,右下から左上にかけて,各マスに「右下・下・右のマスに書かれている数の max - 1」の値と各マスの max を書き込む.これで各マスに積まれている石の数が求まるので,合計を答えにすればよい.O(N * h + HW).

解答

atcoder.jp

ピラミッドの各段の数を書き込む際に max を取るのを忘れていて 2 WA してしまった.

f:id:babcs2035:20190207213101p:plain