TCO 2010 Round 2

ひどい負け方をした...。問題自体は簡単なセットです。

250

対象な隣接行列が与えられるので、0の地点から開始して、一筆書きできるかどうか判定せよ、という問題。

要は連結かどうか判定する問題です。BFSなりDFSなりお好きな方をどうぞ...。BFSするときはqueueのi番目のときにiではなくて要素をちゃんと見ましょう...。

500

奇数だけからなる整数の和に分割することを考える。N以上の整数でそれが可能な最小の値を答えよ、という問題。

分割可能かどうかを判定するルーチンを必死に書いて、順番に試すだけ。判定は、下から見ていって、0だったらキャリーが必須で、他の偶数なら、次が奇数ならキャリー、そうじゃなければそのまま。奇数が出てくれば、一方の整数にはもう桁がないので、残り全部奇数かどうか判定。

で、実は奇数だけからなる数を全部列挙して、全部について、和がN以上になる最小の数を求めてやって、和の最小値を答えるというのが正しい方法みたい。バイナリサーチなり、片方が単調増加ならもう片方が単調減少なり、お好きな方をどうぞ。

1000

x軸かy軸に沿って長方形を切る。指定された点だけからなる長方形を切り出すことを考える。(これは分割されていてもくっついていても良い。)切る最小数を答えよ、という問題。

各軸に沿って切るときに、まとめて切れるかどうかを判定する問題。二本の軸の間に交点があったら、その交点を通れる枝は1本なので、という感じにグラフを作って、最大流を流してやると、まとめて切れる辺の数が求まる。後は全体からそれを引くだけ。グラフがかなり大きいのでTLE対策が必要？