Codeforces #313 Div.2

今回は自分的に簡単だと思った。3完できてよかったけど、Dが考え方はあってたが実装できず悔しい。このまま行けば目標のDiv.1にいけそうなのでこの調子でがんばりたい。(1566->1672)

A. 考えてみれば1があるかどうかが問題になってることがわかる。

B. 長方形の内部に入れられるかの問題。8種？のパターンがあるので、これを全部精確にif文にするのどっかでミスしそうだったのでswap(x,y)をして2^3パターンを全部試した。

C. 想定解は、でかい三角形から小さい三角形3つをひくものらしい。僕は上辺の1列目の三角形の個数を数えて、横の辺の長さによって、一つ下の列の三角形の個数がどうかわるかを調べた。0(n)なのでちょっと遅いけど、通るので問題はなし。

D. 読んでみると再帰で愚直に実装が思いつくけどO(n^2)っぽい？（ここに関しては最悪パターンを思いつくのが難しいので愚直解でも落とせなかったりする。平均n^1.5とかぐらいになって、早い言語だと通ってしまうっぽい）

　推移律を用いて等価変形を行っていけば良いのがわかって、特殊？ソートをすればいい。そこまでは思いついていたが実装ができなかった。場数が足りない。

E. 既知感のある問題。R,Cが小さければdpでおしまいだけど、R,Cが大きいのでTLE.解法として思い浮かぶのは包除定理だけど2^nで無理っぽい？で思考停止してしまった。

実際の解法はというと、黒のマスを左上からのマンハッタン距離でソート。その後DP[i]=(i-1までの黒マスを通らないでiの黒マスにたどり着き方)とすれば、O(n)で解ける。

たどり着き方はmod1e9+7なのでオイラーの小定理をつかえばいいかな。