VK Cup Round 1

93位。

A

兵士がN人いて、兵士のための服がM枚ある。それぞれ大きさが決まっていて、大きさがAの兵士は大きさが [A-X, A+Y] の範囲の服を着ることができる。兵士-服の最適な割り当て（最も多くの兵士が服を得ることができる）を求めよ。

greedy やるだけで通る。

B

N個の品物（スツールか鉛筆）があり、それらをK個のカートに分けて買う。空のカートがあってはならない。今セールをやっていて「スツールが入っているカートでは、そのカートの中で最も安い値段のものが半額」になる。最も安くN個全部の品物を買う方法（カートへの入れ方）を求めよ。

スツールが十分少ない場合は、スツールをそれぞれ別なカートに入れ、空のカートに鉛筆を入れる。
スツールがK以上ある場合は、最も高いK-1個のスツールだけを含むカートを作り、他の品物はすべて1つのカートに入れる。

C

a -> aba -> abacaba -> …　のように文字列を作っていく。30番目の文字列の[l1, r1]の部分と[l2, r2]の部分の最長共通部分文字列の長さを求めよ。

わかりにくいので文字列を1213121412131215…のように表すと、i文字目(1-origin)の数は(iを何回2で割れるか)+1になっている。
文字列の「軸」を定め、軸を基準に最長共通部分文字列を求めることを考える。軸は、部分文字列中に現れる最大の数である。ある2つの文字列において、それらの軸が位置含めて等しく、さらに軸より左、右にある文字数が(2^(K-1)-1)以下(Kは軸の数)であるときには、2つの文字列は等しい。
ある文字が文字列のどこに現れるかはすぐに特定できる。すると、軸を定めたときに部分文字列の軸から左、右方向への長さが限られることから、考えるべき部分文字列の数は2つでよいことがわかる。

D

木の2頂点の組で、間の辺の数が K になるものの組の数を求めよ。

PKUに同じような問題があったのでそれを流用して少しいじるだけで解ける

E

K*Kのマス目があり各マス1桁の数字が書いてある。縦、横に数字を続けて読むと素数になっている。leading-zero があってもいい。一番上の列は決まっている。また、左上-右下の対角線を軸に線対称である。そのような数字の書き方は何通り存在するか。

りんごさんによると、対角成分以外は高々10^6通りで、そこが決まれば対角成分はO(1)で埋められるためよいらしい