ABC116-C
問題
今回提出したやつ
紙は相変わらず大したこと書いてないのでスルー。
考察?
単純に問題に書かれてあることをそのままプログラムにするだけなので考えることは少ないはず。
実装の仕方も制約が緩いので単純にfor文とwhile文混ぜて3重のループでよい。
リアルタイムでやった時は幅l,rを受け取る再帰関数を書いていて非常にめんどくさかった(大体30分弱かかっている)。が、今回も20分強かかっているので自分の苦手分野なのかもしれない。
他人の解法
上には3重ループと書いたがO(n)で回答してる人がいる。(上位10人中3人)
目標となる高さの配列hの先頭に0を加えたものh_を左から見て行って次の高さが増えるならその高さ分答えが増える。減るなら増えない。
なにこれ、まるで訳が分からんぞ。
それぞれの高さを横につながった高さ1のブロックが積み重なっていると考えると1次元のimos法の+1の部分だけ数えてるのか?
いや、単純に左手前から光線当てて光る部分(左側の表面が露出している部分)だけを数えてるのか?
両方同じことを意味してる気がしてきた。