pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces 8VC Venture Cup 2016 - Elimination Round C. Block Towers

codeforces.com

解法

「高さ h 以下で構成可能か」を二分探索する。最適な割り当て方は次のようになる。

  1. h 以下の 2 の倍数かつ 3 の倍数でない数をすべて two blocks の生徒に割り当てる
  2. h 以下の 3 の倍数かつ 2 の倍数でない数をすべて three blocks の生徒に割り当てる
  3. まだ割り当てられていない two blocks と three blocks の生徒に 2 の倍数かつ 3 の倍数である数を割り当てる

Codeforces 8VC Venture Cup 2016 - Elimination Roun ...

貪欲でも解けるらしい。