SRM580

SRM580のwriterをしていました。
点数はsolveまでの時間にも依存するので必ずしも600が激ムズという訳では一応ないです。

Div2 Easy

概要:区間が与えられるので重なってるペアの個数を数えよ。
解法:区間が50個しかないので全ペアについて試す。

Div2 Medium, Div1 Easy

概要:うなぎが区間として与えられるので、2点を選んでそれらのうちどちらか又は両方を含む
区間を最大化せよ。
解法:tから2つ選ぶのを全て試す。

Div2 Hard

概要:コストまたは通れないマスが書かれたgridがあるので、うまく横方向の壁を置いて左上のマスから下の段までの上移動を使わないpathのコストを最大化せよ。
解法:dp[i][j] = i段目に初めて到達したマスが左からj個目である時のコスト

Div1 Medium

謝罪:TCでO(N^2)という制約はこういう入力にするしかなかったのです・・・
概要:うさぎに対応する区間が与えられ、区間が重なってるうさぎどうしはtwitterみたいなのでフォローし合う。うさぎ全員の投稿を全員が見られるようにするために必要なRTの回数の最小値を求めよ。
解法:両端それぞれについて、あるうさぎの投稿が端のうさぎに伝わるために必要なRT回数のテーブルを計算しておき 、それらを足し合わせる。ただし、初めてRTするうさぎだけは両方向へ拡散できることもあるのでそれも全部試す。ちなみに知らなくてもほとんど変わらないと思いますがグラフの構造はこれです interval graph

Div1 Hard

概要:コストが書かれたgridがある。うさぎは初ターンに上段の好きなマスに駒をおき、それ以外のターンは上方向以外の隣接したマスに駒を動かす。うなぎはうさぎのターン終了後に横方向の壁を好きなだけ置ける。最下段にたどり着けなくなるようには壁を置けない。うさぎはコストを小さくしたくて、うなぎはその逆。両者が最善を尽くした時のコストは?
解法:うなぎは駒のあるマスの真下に壁を置くという行為以外は無意味(うさぎに余分な情報を与えて喜ばせるだけ)です。
dp[i][j] = i段目に初めて到達したマスが左からj個目である時のコスト
を求めたいのですが、それは答えで二分探索し「コストがそれ以下になりそうな時だけうなぎは壁を置き、うさぎがうまく駒を動かすことによってその段に壁が全部置かれればうさぎの勝ち」というゲームをやればいい。これは区間と駒がどちらの端にいるかを持つDPで求まる。
が、二分探索は必要ないらしい。壁を置く場所は各段ごとに区間にすれば良いということに気づけば、dp[駒の座標][その段に置かれている壁の区間]というDPでできてしまいます。
元ネタはQuoridorというゲームです。面白いですよ。りんごさん強かった。