204.1

類題解いたのに...。
問題セットとしては悪くないと思う。

300

3の累乗の重さのおもりを使って、指定された重さを天秤で測定するには、どうおもりを配置すれば良いか答えよという問題。

3^Nまでのおもりをつかって実現できる重さは3^(N+1)/2なので、それよりも大きい重さが必要ならば3^(N+1)のおもりを使うというのを釣り合うまで両側に乗せていけば良い。もちろん大きい方のおもりから評価しないとダメ。

600

N枚のカードが渡され、そのカードを以降のK枚で任意の1枚を上書きすることができる。上書きしないことも可能。最初のN枚のカードを上書きして広義単調増加するように書き換えるのに必要なカードの最小枚数を答えよという問題。

頭から1枚ずつ使うカードを増やしていって、広義単調増加にできればそれで終了。うまいことやれば最初からソートされている状態を例外処理しなくてもいいとは思うけれど、今回は例外処理した。

まず使うカードをソートする。元のN枚のカードを先頭から順に見ていって、広義単調増加にならない最初の位置に使うカードのうち未使用のもので最小のものに置き換える。カードを使い終わった後にソートが完了しているか、カードを使い切れなかったらソートは完了しているので、その時の使用枚数を答える。

1000

N国の人から重複しないようにK国の人を取り出してグループを作るとき、最大でいくつグループが作れるか答えよという問題。

グループの数がMのとき、各国の人は高々M人までしか呼べない。全部の国から呼べる合計がM*K以上ならば、K人の組がM個作れる。後は最大のMをバイナリサーチで求めるだけ。ちなみに図示すると以下の通り。結構ありがち...。

AAAAAAAA
BBBBBBBC
CCCCCCDD
DDDDEEEE
EFFFGGHI

これが5人組みを8つ作る場合で、こういうように割り当てればいいので、ちゃんとグループが作れる。