Paiza オンラインハッカソンの感想
(注)正確な解法ではなく感想です．
更新途切れそうなのでエントリ更新．
少し前から，paizaのオンラインハッカソンをやってました．
女子大生とペアプロするだけの簡単なお仕事です！｜paizaオンラインハッカソンVol.2
やはりプロコンに足りないのは萌え要素だとかそんなことを考えながら．
このシリーズは2回目みたいで，その時も別の問題が出ていたのですが，1回目の時はモチベーションも高くなく，問題もとっつきにくかったのでスルーしてしまいました．
今回は研究室のプロコン大会の題材になったこともあり，わりと張り切って解けたかなと思います．
問題と感想
詳しくは問題を見てもらえればいいかと思いますが，ところどころにウィジェットを入れるためのマス目がある長方形のスマホ画面が与えられて，長方形のウィジェットをはめ込むパターンの数を出力せよ，というものです．
最初は解けるまでの時間を競っていたということもあり，各マス目について，そこを左上としたときにウィジェットが入るかどうかを逐次確認するというクソコードを書きました．
O(H2 W2)くらいだと思います．
これは3つ目のテストコードぐらいまでしか通らなくて笑いものにされましたw
これではあまりにもひどいということで，書いたのがこちら．
これは，事前に，各マス目に対して，それをウィジェットの左上の座標とした時に，どれだけの大きさのウィジェットなら入るのかを計算し，ウィジェットが入力されるごとにそれを参照するようにしています．
事前計算により，6つ目のテストケースまでは通るようになったのですが，後1つがどうしても通らない…
そのまましばらく放置していると，公式や各所から解法らしきものが上がってきたので，そちらを参考に書いて，最終的に100点はもらいました．
動的計画法を用いることで，各マス目について，ウィジェットの右下の座標から見て，各高さのウィジェットを入れられる最大幅を求めます．
例えば，
1000
1101
1001
0001
1111
1111
1111
というスマホ画面が与えられた場合，例えば座標(3,4)が右下に来るような，*1
- 高さ1の長方形が入る最大幅は3
- 高さ2の長方形が入る最大幅は2
- 高さ3の長方形が入る最大幅は1
- 高さ4の長方形が入る最大幅は1
のようになります．
これは，
(座標(i, j)が右下に来るような高さhの長方形が入る最大幅) =
min( (座標(i, j)が右下に来るような高さ1の長方形が入る最大幅), (座標(i-1, j)が右下に来るような高さh-1の長方形が入る最大幅) )
のように一般化できます．*2
プロコン歴が浅いので，動的計画法などのプロコン独特の考え方にはまだ慣れてません…
これからももっといろんなコードを書いていきたいと思います！
