Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2009-12-29topcoderについて

SRM455 Div1 250 DonutsOnTheGridEasy

| 21:04 | SRM455 Div1 250 DonutsOnTheGridEasy - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM455 Div1 250 DonutsOnTheGridEasy - SRM diary(Sigmar) SRM455 Div1 250 DonutsOnTheGridEasy - SRM diary(Sigmar) のブックマークコメント

'0'と'.'で構成されたGridにおいて、ある長方形の枠が全て'0'で構成されており、高さと幅が両方とも3マス以上の長方形をドーナツであると言う。
あるGridが与えられ、ドーナツの内側にドーナツが含まれ、更にその内側にドーナツが含まれ・・という連鎖的なパターンを探すとき、最大何個の連鎖的なドーナツが存在するか。
ここでドーナツが内側のドーナツと同じマスを共有している場合、外側のドーナツは内側のドーナツを「含む」とされない。
Gridのサイズは最大50*50。

Gridが高々50*50マスなので、dfsとメモ化で解くことができます。
ある長方形は、左上の座標と右下の座標を指定することで特定できます。ある長方形が(その長方形も含め)内側にいくつの連鎖的ドーナツを含むか、メモ化で記憶します(最大50^4=6,250,000程度)。
最大の長方形から始めて、長方形がドーナツだった場合は全ての辺を1つずつ内側にした長方形の結果+1を解とします。長方形がドーナツでなかった場合は、各辺を1つ内側にした長方形(4種類)の結果のうち、最も大きいものを解とします。以下dfsします。

SRM455 Div1 550 ConvexHexagons

| 22:05 | SRM455 Div1 550 ConvexHexagons - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM455 Div1 550 ConvexHexagons - SRM diary(Sigmar) SRM455 Div1 550 ConvexHexagons - SRM diary(Sigmar) のブックマークコメント

三角形の各辺をN等分し、各辺の分割点同士を直線で結ぶと、N*N個の小さな三角形に分割することができる。この図形の中で、六角形を何個見つけることができるか。mod 1000000007で解を求めよ。
Nは最大500,000。

とても難しいです・・・
方針として、六角形の各辺を総当たりで組み合わせ、各辺が六角形の条件を満たすときに解を+1する方法を考えましたが、普通にやれば500,000^6となり、何かdpしようとしてもうまくいかないのでやめました。
方針を変えて、N-1の結果からNの結果を出すことを考えましたが、これなら何とかなりそうです。
C++のtop submissionも同じ方針のようでしたので参考にしました。

まず六角形を2種類に分けて考えます。1つは、六角形の辺のうち元の(N*N分割する前の)三角形の辺に接する辺が2つ以下の六角形、もう1つは、六角形の3辺が元の三角形の辺に接する六角形です。Nをkとして、前者の六角形数をg(k)、後者の六角形数をh(k)とすると、解はf(k)=g(k)+h(k)です。
別の言い方をすると、g(k)に含まれる六角形は全てf(k-1)に含まれるものと同じ形状の六角形であり、h(k)に含まれる六角形は全てf(k-1)に含まれない六角形となります。

f:id:jackpersel:20091229211847p:image:right

g(k)について考えます。サイズkの元の三角形は、サイズk-1の三角形が3つ含まれます(図の赤、青、緑の三角形)。そのため、g(k)はf(k-1)*3から計算できそうです。ただし、赤と青の重複する部分でサイズk-2の三角形に含まれる六角形を二度計上していますので、その分減算しなければなりません。同様に青と緑、緑と赤でk-2の三角形の重複があるので、f(k-1)*3-f(k-2)*3とする必要があります。さらに、赤、青、緑の3つの三角形が重複する部分でk-3の三角形に含まれる六角形をf(k-1)*3で3回計上し、-f(k-2)*3で3回減算してしまったので、もう1度計上しなければなりません。
以上から
$g(k)=f(k-1)*3-f(k-2)*3+f(k-3)$

次に、h(k)について考えます。h(k)に含まれる六角形は、元の三角形から隅の三角形を3個取り除いて作ることができます。したがって、隅の三角形(小三角形とする)の大きさの組み合わせを全て計上することで六角形の数を計算できます。各小三角形の大きさを(a,b,c)とすると、制約条件はa,b,c>=1、a+b,b+c,c+a<=k-1です。といってもこれだけでは計算が難しいので、h(k-1)からh(k)を計算する方法を考えます。h(k-1)は、制約条件がa,b,c>=1、a+b,b+c,c+a<=k-2となる小三角形の組み合わせを全て含むので、h(k)の計算のためには、a,b,c>=1、a+b,b+c,c+a<=k-1、a+b=k-1∨b+c=k-1∨c+a=k-1の小三角形の組み合わせのみを計上し、h(k-1)と加算すれば良いことになります。a>=b>=cの制約を追加して、(a,b,c)の順列を掛け合わせるようにすると、以下のように具体的な小三角形の組み合わせを列挙できます。
(k-2,1,1)*3、(k-3,2,2)*3、(k-3,2,1)*6、(k-4,3,3)*3、(k-4,3,2)*6、(k-4,3,1)*6、・・・
一般化すると(k-i,j,l)(i>=2,k-i>=(k-1)/2.0,j<=i-1,l<=j)のときの小三角形の組み合わせ数は3+(i-2)*6(ただしk-i=(k-1)/2.0のとき、a=bとなるので1+(i-2)*3)
あとはΣで足し合わせれば良いですが、iの値の範囲と、k-i=(k-1)/2.0(a=b)となる条件がまだ明確ではありません。数式で算出することもできますが、具体的にk=3からk=10くらいまでケーススタディ的に小三角形の組み合わせ数を列挙してみるほうが簡単に分かると思います。ケーススタディは省略しますが、結果的にはkの値に関わらず3+(i-2)*6をi=2からk/2まで加算し、kが奇数のときのみ更に1+(k/2-1)*3を加算すれば良いことになります。
以上から
$h(k)=h(k-1)+\sum\limits_{i=2}^{k/2}(3+(i-2)*6)+(k%2)*(1+(k/2-1)*3)$
$=h(k-1)+(k/2-1)*(k/2-1)*3+(k%2)*(1+(k/2-1)*3)$


最終的に以下を計算すれば解f(N)が算出できます(最大500,000*2=1,000,000回程度の計算量)
f(1)=f(2)=h(1)=h(2)=0
$h(k)=h(k-1)+(k/2-1)*(k/2-1)*3+(k%2)*(1+(k/2-1)*3)\pmod{1000000007}$
f(k)=g(k)+h(k)
=f(k-1)*3-f(k-2)*3+f(k-3)+h(k)\pmod{1000000007}
なお、f(k)の計算においてはmodの中で減算を行うので、単にf(k)%1000000007のような計算を行うと負の解が出てしまいます。そのため、n (mod p)の計算において、nが負の値の場合、p-((-n)%p)のような計算を行って正の値に直してやる必要があります。

何だかややこしすぎて、とても時間内には解けませんでした。もっと簡単な方法がありそうです。
(特にh(k)の計算方法がややこしすぎるのが良くないです。)
他の人の解を見ていると、O(1)っぽいやり方をしている人もいました。
(もちろん、上記のh(k)とf(k)の漸化式を解けばO(1)ですが・・・漸化式から解くのは私には難しそうです)

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20091229