367.1

250

50桁くらいの整数が与えられるので、Nという数字を含むように加える最小の正整数を答えよという問題。

BigIntegerで0から9まで足してみればおしまい。

500

送信したいデータをオフセットと長さで与えられるときに、最小送信量はどれくらいになるか求めよという問題。ただしパケットに区切る必要があり、パケットには連続区間のデータしか入れられない。関係ないデータを送っても構わない。

各区間について、いくつ送り残した状態で次の区間につなぐか、もしくはつながないかについて、最小コストを計算していくDPをやればいい。

1000

有向グラフが与えられて、ルートに直接ぶら下がることのできるノードがある。ルートから一番分岐の多いノードの分岐数が最小になるような木にするとき、親の配列を答えよという問題。複数候補がある場合には配列として小さいものから答える。

ランクの大きいノードから削れる枝を削っていけばいいのかなぁと思ったけれど、実際にどうなるかは不明。最大値じゃなくなるまで削れないならば削る必要ないので、複数最大値のノードがあると怪しい...。