310.1
PKUのやり方について検討する気分になったので、SRMの方に手を出す感じ。
250
1x1x1の立方体をK個詰むことを考える。1,4,9,16,...個ずつ積みたいが、数がちょうどにならない場合については、一回り大きいように積んで、上の方は空にする。各段については、左上から順番に並べる。このときK個の立方体を積むと表面積はいくつになるか答えよ、という問題。
実装あるのみ...。
500
N個のランダムデータを先頭からN-K+1個、K個ずつのシーケンスを考える。このN-K+1個のシーケンスの中央のデータについて、合計を求めよ、という問題。
K個ずつのシーケンスを上と下に分けて、K個のシーケンスに入るデータと出るデータを見比べる。うまくバランスしながら上下を更新しつつ、中央値を合計していけばいい。
上下をそれぞれPriorityQueueにして、上下それぞれについていらないデータを覚えておいて、移動させるときとか中央値を取りだすときとかにそれらをスキップするように実装してみた。もっと綺麗に書けるはずだけれども...。