Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2008-12-18

SubrectanglesOfTable (SRM429 DIV2 Medium)

| 02:22 | SubrectanglesOfTable (SRM429 DIV2 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SubrectanglesOfTable (SRM429 DIV2 Medium) - TopCoder煮ブログ

リハビリ。何も考えずに書いたら6重ループぐらいになって時間内に終わらずに出戻り。諦めて解いた人の方針をぐぐって調べて、座標ごとに個数を求めればいいことが分かり、素直に書いたら4重ループで素直に解けた。

DIV2 の Mid=DIV1 の Easy が解けなかったのはやヴぁい…。リハビリがんばらねば。

早い人の答えをみたら、(x, y) の回数が ( x + 1 ) * ( y + 1 ) * ( W - x ) * ( H - y ); で求まってるんだけど、何でこの式でいけるのかがさっぱり分からん。教えて、誰か!

分かった。

x=0 のとき、x 方向に取り得るパターンは横幅が1のとき1、横幅が2のとき1…横幅が2mのとき1。つまり1+1+…1=W。x=1のときは横幅が1のとき1、横幅が2のとき2、横幅が3のとき2…。つまり、1+2+2+2+…+2+1=2W-2。同様に、x=3のとき1+2+3+3+…+3+2+1=3W-6。一般化して、xのとき1+2+…+x+x+…+x+(x-1)+…+1=(x + 1)(W - x)だと。x>W/2のときが不安になるけど、式を見ると対象性もあるので問題なさげ。で、xの取り得るパターンとyの取り得るパターンを掛け合わせれば答えになる。なるほどぅ。