304.1

全然手に負えなくなってきましたよ。

300

凸包の頂点が時計回りに与えられるので、任意に隣接しない点を選び、それぞれを好きな方向に長さ1以内の範囲で移動させる。移動させるとき、辺もそれに伴って移動するので、他の辺と重なってはいけない。このとき図形の面積の増分の最大値を答えよ、という問題。

実際は隣接する二頂点を結ぶ線分と垂直な方向に1だけ動かすのが各頂点において最適であり、これは他の辺とは交わらないことが凸包であることより保証されている。なので、頂点からどうやって選ぶかをDPするだけ。循環するのが面倒なのを除けば、直前のを使ったかどうかを覚えておいてやるだけ。

450

N個のK面さいころがある。これを振ったとき、少なくとも一個がある数字を出していたと分かったとき、合計値が指定された値以上になる確率を求めよ、という問題。

単純にDPで合計値すべての確率を求める。同時にどのさいころも特定の数字を出さない場合の確率を求める。前者から後者を引いて正規化して、合計値が特定の値以上になる確率を計算すればおしまい。

1000

N個の箱が一直線上に並んでいて、そのうちいくつかに印がついている。二人の人が、交互に1個以上の隣接する箱に印をつけていく。印を付けた個数にターンに応じたスコアを書けたものがそのターンのスコアであるとするとき、先攻のプレイヤーが後攻のプレイヤーよりも良いスコアを得るには、最初にいくつ印をつければ良いか答えよ、という問題。

隣接している箱の塊をそれぞれ整数にして管理し、現在のスコアから得られる可能な最大スコアを単純にメモ付き探索しても終わる気配が全くなかった。単純にminimaxなので枝狩りが必要な感じ？この手のゲームは全然ダメ。(そもそもゲームとして興味が持てない点で終わっている。)