165.1

TCCC？何それ？食べられるの？

250

1つ1msかかるタスクがたくさんあるとき、それを分担作業してやると最も早く終わるのは何人でやるときか答えよという問題。ただし全員の間でコミュニケーションしなくてはならない。

コミュニケーションはN*(N-1)/2回発生するので、その分のコストを考えた上で、全体のコストを計算するだけ。タスクの数が1M止まりなので、2000人を超えることすらない。

600

平方根を連続分数で表現したとき、ループするまでに出てくる数字の列を答えよという問題。連続分数の定義はA+1/Bなるもので、Aは整数でBは連続分数。

入力は1000までなのだけれど、実際には1Mとかでも動くルーチンになっているのがほとんど。最初から順番に計算していくのが重要。doubleでやっても精度は問題にならないし、覚えておく数字も2つだけでいいらしい。(ナイーブに4つ持っておく方が色々安心かも。)

1000

仕事のコストと依存関係が与えられるので、最大2並列までで最速に終わらせるのにかかる時間を答えよという問題。一つの仕事は始めると終わるまでやめてはいけない。

仕事の数が12個しかないので、12!通りを試す。もしかすると依存関係のない状況で、全通りやろうとすると終わらないのかも。そろそろ手に負えない問題になってきた。