234.1

クイックソートの存在意義って何だろうと考えみたくなったり。多分、メモリをそんなに食わないのがメリットなんだと思う。マージソートだとコピー領域があると幸せになれるわけだし。

250

N/Dの形式で与えられる分数を、1/Kの和の形に直せという問題。ただしKは小さい順に利用する。

実装によっては既約分数じゃないことに注意する必要があるけれど、後は単純に引き算するだけ。約分しなくてもintの範囲から出ないような気もする。

650

チェス盤の上にK個のルークをお互い取れないように置くとき、何もないマスのうち左ないし上にルークがいないマスはいくつあるか、というのをすべて列挙せよ、という問題。

単純に全探索＋自明な枝狩りで終わるみたい。

850

N要素の整数配列のうち、ソートされていないペアは何組あるか答えよ、という問題。

実際にソートしながらソートされていないものを数え上げる。マージソートの仮定で、後ろ側の配列の方に小さい要素があれば、前側の配列の残っている要素分だけソートされていないことになるので。ソートアルゴリズムはO(N^2)にならなければなんでも良さそう。