367.1

サブミットできなかった...。

250

ある整数が与えられるので、それ以上の整数である数字を含むものを答えよ、という問題。

一の位が一周するまで全部試すだけ。整数が大きいのでBigIntegerでも使えば良い。

500

開始位置と長さが与えられるので、その区間のデータを転送したい。転送する際には連続領域のみの転送しかできず、また一回の転送で送ることのできる最大量とオーバヘッドとなるコストが分かっている。このとき最小の転送コストを答えよ、という問題。

区間はオーバラップしないので、順番にソートする。ある区間から特定の区間までを分割しないで転送する場合(途中の無駄なデータ転送は許容されている)のコストは、開始区間の先頭から、終了区間の末尾までのサイズを貪欲に一回の転送に詰め込んだ結果と端数のコストの合計で求められる。後はこれをDPしてやるだけ。

1000

DAG上のネットワークが与えられる。ルート以外のノードについて、子の数の最大値ができるだけ少なくなるように木にしたい。このときの親子関係を表現する辞書順で最初の表現を答えよ、という問題。

基本的には親子関係の有無でグラフを作り、最大流を流す。親は子に持てる数だけの流量を終端に流せる。ルートノードは無限の流量を終端に流せる。これを親が子に持てる数について全部試せば、子の数が分かる。

次に辞書順で最初の表現を得るために、辞書順で一番重みの大きいノードから順に、親子関係を小さい順に割り当ててみる。これにより固定される流量をグラフから除去して、再び最大流を流してみる。うまくいけば次のノード、失敗すれば別の親子関係、というように割り当てていくだけ。