School Team Contest 2 (Winter Computer School 2010/11)

スポンサーリンク

A. Indian Summer

unique するだけです.

B. Cola

2 種分について全探索しました.dp 等もありでしょう.

C. Holidays

区間に足すだけです.

D. Hyperdrive

完全グラフの最小サイクルを聞かれているということになります.三角不等式から単に三角形を全探索すれば十分です.

E. Anfisa the Monkey

長さを平均化して判定.

F. BerPaint

あらゆる交点,辺,面を列挙しておきます.点・辺・面からなるグラフを作ります.あとは作ったグラフ上で,同じ色のものをたどって色を書き換えるというシミュレーションをします.

交点,辺,面の列挙に苦戦しました.面というのが厄介で,多角形の内側にある多角形をくり抜いた連結領域などをどう扱うのかという問題が発生します(幾何でも平面グラフ理論でもこういうのは通常「面」と呼ばないはず,面でない連結領域をどう列挙するかが難しいということ).

必ず連結になるようにすることで対処しました.線分ではなく直線を追加することにしてしまって交点を列挙します.そのあとで,白い点・辺と黒い点・辺があるというように処理しました.

クエリ点がどの面に含まれるかの判別も,最初にクエリ点を含む直線を追加してしまうことで対応しました.

G. Shooting Gallery

$z$ の小さい長方形から順に見ていって,それが含むクエリ点を列挙します.

H. Phone Number

dp で数えます.自分自身が規則で作れるときには 1 を引く必要があります.

I. Toys

再帰的に作ります.$N-1$ の解があるときに $N$ の解にすることを考えます.

$N-1$ の場合の解のどこかに $N-1$ を挿入する,あるいは $N-1$ だけからなる箱を追加するというパターンを全部生成することで $N$ の場合の解になります.ひとつの $N-1$ の解に対してそれに対応する $N$ の場合の解をまとめて作るようにして,境界の接続だけ調整すればよいです.

J. Triminoes

辞書順で最初のマスから順に見ていくと,局所的な情報だけで置き方が定まります.

CodeForces
スポンサーリンク
シェアする
maspyをフォローする
maspyのHP
タイトルとURLをコピーしました