TopCoder SRM525

300

グリッド上に石が何個か乗っかっている。今、方向を選んで、その方向にすべての石を1マス動かすという操作ができる。落っこちた石は棄てる。残りの石をちょうどK個にするために必要な操作の回数の最小値を求めよ。

残りの石は長方形状の場所に収まることが自明。長方形を全部列挙して、中の石の個数を数えて、Kに一致したら操作回数を求める。
上下、左右ごとに考えるが、例えば左と右を両方使う場合は、回数が少ない方を先に実施して後で反対側の操作をたくさん実施する必要がある。

525

うさぎが高々16匹いる。うわさが2つあり、各うさぎは「どっちも知ってる」か「どっちも知らない」かのどちらかである。毎回、うさぎは知っている噂のうち1つを選んで、広めるということを実施する。但し、各うさぎごとに噂を広められる他のうさぎが決まっている。それらのうさぎに対しては広められるが、それ以外のうさぎについては直接は広められない。うさぎは「2種類のうわさを同時に聞く」ことや「うわさを広めつつうわさを聞く」こともあり得る。全員が両方のうわさを知るために必要な最小ステップ数を求めよ。

うさぎは、1つのうわさしか知らないなら自明にそれを広める。2つのうわさを知っているなら、「Aを広めた次にBを広める」か「Bを広めた次にAを広める」かのどちらかである。各うさぎについて、2つのうわさを知っていてかつどちらも広めてないときの広める順序を決めてやると、簡単にステップ数はシミュレートできる。その上で最小手数を求める。

950

N*Nのグリッド上によくわからないパターンがある。もともとのパターンに対して、0<=i,j

結果

、と思ったんだけど、300も525も落ちた。絶望

rating := -INT_MAX