2008年06月06日

オフィスに向かう直前に少し参加．250点だけといて，500点は問題読んだだけであきらめて，950点はアルゴリズムわかったけど書いてる時間なかったのでパス．950点は帰ってきてから試したらテスト通ったのでアルゴリズムは正しかったらしい．

250点問題：ルールに従った0-9の数字でできた上三角を復元する問題．それぞれの数字は，その上の行にある二つの数（直上とその右の数）を足した結果の１の位．で，各行の数字がひとつだけわかっている状況から全体を復元しろと．下から順に決まるので問題ない．

500点問題：数列の区間和の差を最小化してみろという問題．ナイーブにやると時間オーバー．効率的な構造が良くわからなかったのでパス．

1000点問題：各企業は独自のデータフォーマットを持ち，変換可能な他企業のフォーマットが決まっている．さらに，処理できるデータの量と，運営コストがある．で，与えられた企業からもうひとつの与えられた企業へのデータフォーマットをなるべく沢山したい．安いコストで．さてどの企業を動かしますか？　とりあえず，各企業を二つのノード（入／出）で表してそのノード達をつなぐエッジに処理可能量を容量として指定する．そして，その出ノードを変換可能な他企業の入ノードにつないだネットワークを作る（このエッジの容量は処理能力の和とか）．あとは運営するかどうかの全パタンに対して最大流をといて，流量最大かつ費用最小のパタンをはく．最初の企業と最後の企業も処理能力までしか入出力できないことに気をつければ他にはまりそうなところは無い．