410.1

久し振りに0点取った。久し振りってほど久し振りじゃないかも知れないけれど。それにしても、これのデフォルトの日付って、何時になったらその日になるんだろう？

250

N個のノードの連結関係が与えられて、K個の代表元が与えられる。代表元間での結合がないように、できる限り追加できる結合の個数を答えよ、という問題。

取り敢えずグループ化して、一番大きいグループに残りの点を加えていく。各グループの中で全点間で結合できるだけすれば良い。

500

大きさNのメモリのうち連続するKだけ乗るキャッシュがある。アドレスのアクセス順が与えられるので、キャッシュミス時にないものすべてを拾うとして、メモリアクセス回数の最小回数を答えよ、という問題。

アクセスシーケンスを適当な長さに切ってDPする。各アクセスシーケンスの中では何があっても今までのキャッシュを使いまわすように努力する。アクセスシーケンスから昇順の部分と降順の部分を切り出して、各シーケンスで必要なメモリ量を求める。シーケンス間で共有する部分は除去しつつ、二つ前のシーケンスで、キャッシュ位置に何か制約が入るなら、それを引き継ぐ、などグチャグチャやったらSRM2回分くらいの時間で通るようなルーチンが出来上がった。

正解は、アクセスするアドレスを上限か下限にとるようにキャッシュをセットする感じのDPだそうで。

1000

格子点に辺が乗らない多角形の内部にある格子点の数を答えよ、という問題。

数値がでかいのでどうやって高速に処理しますか？という問題だと思う。手が回らないや。