第3回ドワンゴからの挑戦状予選 C - スキーリフトの相乗り

解法

まず、順番は全く関係なく、できるだけ多くの4人グループを作成していくことだけを考えればよいです。
先にグループを決めてしまえば、決めたグループの中の誰かが先頭に来た時点で、他の人達と相乗りをすればよいです。
ということで、最初に1人、2人、3人、4人組がそれぞれどれだけ存在しているかをカウントします。 $i$ 人組の数を $C_{i}$ とします。
そして、グループを作成していきます。
まず、4人組はどう見てもそれ以上人数を増やすことができないので、そのまま答えに加算します。

3人組、2人組、1人のうち、どこから4人のグループを作成していくのがいいかというと、4人グループを組みにくい部分、つまり3人組です。ということで、以下の順番で貪欲にグループを組んでいきます。
f:id:emtubasa:20190410223531p:plain

➀:
3人組を利用して4人グループにするには、1つの3人組に、1人追加することで完成します。
ということで、まずは $min(C_{1},C_{3})$ 個の4人グループが作成できました。
さて、この時点でもし3人組が余っていたら( $C_{3} \gt C_{1}$ )、余った3人組はそのまま乗るしかないので、余った数を答えに加算します。
逆に、1人側が余っていたら、➂,④でまた登場するので、改めて $C_{1}$ とします。
次に、2人組を利用して4人グループを作成します。
➁:
まずは、2人組を2組用意することで4人グループになるので、 $C_{2}/2$ が答えに加算されます。
➂:
もし奇数組だったならば、1組だけ余ってしまうので、先ほどの $C_{1}$ をくっつけます。くっつけることができなければ、2人組単体でグループが完成です。ここでは、どちらの場合でも1が答えに加算されます。
④:
これでもまだ、1人の人々がたくさん残っていれば、4人組を組めるだけ組んでいきます。結果、 $floor(C_{1}/4)$ が答えに加算されます(floorは切り上げです)

ということで、最終的には