321.1

もうちょっと慎重にやりませんか？

250

矩形が与えられるので、指定された面積になるように、軸平行な切断を行うとき、何回切断する必要があるか答えよ、という問題。

高々2回切ればいいのはさておき...。指定された面積を二つの整数の積に分割して、元の矩形の中に入るかどうかを判定する。入らない方は切断することにして、切断回数最小なものを答えれば良い。

500

整数配列が与えられるので、i番目の要素がi+1番目の要素よりも1だけ小さくならないように並べたもので辞書順で先頭のものを答えよ、という問題。

一番小さいのを先頭に置いてみたとき、後ろに可能な並べ方があるかを判定していく。

基本的には後ろの要素で、一番小さいのを選択し、それが直前のと競合するなら二番目に小さいのを選択する。(二番目に小さいのを選択した場合は更に小さいのが後ろにいるので、逆順にソートした上で、一番大きいのが競合しなければ可能、競合しても一番小さいのを先頭の持ってくれば競合回避できるので可能。)一番小さいのを除いて逆順にソートしてみて、競合が起きる場合、一番小さいのとそれより1だけ大きい要素からなる配列なので、大きい順に並び替えればおしまい。

1000

有向グラフが与えられるので、ノードをマージしてループだけからなるグラフに変形したい。最小で何回マージすれば良いか答えよ、という問題。

同じグループから辺が出ている、同じグループへ辺が出ている場合にはマージしなくてはならない。後は、グループがどういう形状になるかを考える。ループがなければ、すべてのグループの結合状態をループになるようにつなげば良い。ループがある場合は、出現するループ長の最大公約数のループ長になる。後はひたすら実装あるのみ。