Hello 2022

　Dまで四完。なお、ツイートでは4WAと書いてますが、5WAだったようです。

コンテストへのリンク

コンテスト後のツイート

Hello 2022 Dまで四完。Dの解法がギャグなのに気付かずWAを4つ出し、Eの実装が間に合わず終了。
A 対角線に一個おきに並べる。
B 最小値・最大値を管理。全体をカバーするものがあるときに注意。
C ループするまで同じところを聞く
D 角の八点を見る

— titia (@titia_til) January 3, 2022

E. New School

　実装が間に合わなかったが、やり方はあっていた。

　人を削らないなら、グループ年齢の平均値が大きい順に、教師の年齢が大きいものを割り当てるのが最適。

　人を削ったら、そのソートした年齢順のリストの、あるindex xからindex yへうつる。その際、年齢平均のindexが[x, y]にあったグループのものは、一つプラス側かマイナス側にずれ、他は変わらない。

　なので、初期状態、一つプラス側にずれた場合、一つマイナス側にずれた場合、それぞれについて教師を割り振ることができるかを前計算しておく。そして、各人を削るごとに、そのグループがx→yへうつるかを二分探索により計算し、そのグループの判定および、他の判定を上記のようにすれば良い。

　私は、初期状態、プラス側、マイナス側についてセグ木を立てて実装したが、累積和でできる模様。

　また、ソートに小数を使う必要はなく、ceilさえ分かっていれば良い（教師の年齢は整数なので）というのは目から鱗だった。