2009 Round2

去年よりも圧倒的に難しくて、これはダメだ、って感じだったけれど、システムテスト後で421位らしい。ほとんど気合い実装で通したとしか言いようがない...。

A

0と1からなる行列が与えられて、行のスワップだけで、下三角行列に変換する最小回数を答えよ、という問題。

smallは8行だったので、メモしつつBFSした。結局上から順に、Greedyに入る一番近い子をスワップで拾ってくるだけだった。

B

自分の立っている場所の右下か左下を掘ることができる状況で、一番下の層まで降りたい。無事に降りられる段数が決まっていて、降りるときは常に垂直に落下する。このとき、無事に最下層に到着するために、掘る最小回数を答えよ、という問題。

今の位置と、同じ層と下の層の形状を状態にしてDPするだけ。遷移がやたらと多くて大変。largeは手に負えなかった...。

C

グラフがN個与えられる。重ならないグラフは一枚に書くことができるとするとき、少なくとも何枚に分けて書く必要があるか答えよ、という問題。

重なるかどうかでグラフ作って、クリーク(？)は一枚に書ける...、みたいな問題なのは分かるけれど、グラフはさっぱり分からないので、仕方がないからQM法のようなものを作ってsmallだけ。ArrayListが遅くてダメだったりしたので、整数配列にするとか微妙な高速化で通した。

D

N個の円を含むように2個円を書く。このとき円の半径の最小値を答えよ、という問題。

smallはNが3以下なので場合わけ。1個ならその円の半径、2個なら大きい方の半径、3個なら、2個と1個に分けて、大きい方。2個の円を含む円は、中心距離と二つの円の半径の和が直径になる。