547.1

int溢れするコード書くとかセンスなさ過ぎる。

250

N階建ての建物とM階建ての建物のそれぞれからランダムに階を選んでロープを張るとき、ロープの長さの期待値を答えよ、という問題。

N*M通り試すとTLEするので、ロープの傾きについて考えつつやる。傾きが分かれば、二つの建物の階として適切な値の範囲が求まるので、その分だけ可能なロープの張り方がある。後は最後に全パターン数で割ってやるだけ。

500

整数を順番に矩形状に並べたものから、一部の矩形領域を選んで書かれている数字の合計をSにしたい。このときに可能な領域サイズの最小値を答えよ、という問題。

選択する矩形領域の大きさが決まっているとすると、その左上の値を取り敢えず0として合計値が分かる。これをスライドさせることを考えるとき、全部の要素が同様の値だけ増加するので、左上の値が何であれば良いかが分かる。後はこの矩形が適切に元の矩形の内部に入っているかを吟味してやる。

矩形領域の大きさとSの関係から枝が刈れるので、全探索可能。

1000

正N角形の対角線を交差しないようにして三角形に分割する。このとき、一番大きい三角形が複数できないようにする方法は何通りあるか答えよ、という問題。

一番大きくしたい三角形を作るために三頂点を全パターン(一点固定ののちにN倍(等間隔ならN/3倍)すれば良いのでN^2通り)ためして、残りの領域について、それ以上大きさのものが作れないような組み合わせは何通りあるかを探索して...、という妄想中。