287.1

数学のセット？

300

xとyからなる連立方程式を解け、という問題。

行列式を計算して0なら答えがないか無限か。そうでなければ解く。前者の判定に注意が必要。2x2なら、逆行列を求めるのが簡単なのを思い出した。

450

ムーアの法則に従うとして、今からN年かかる問題を最初に解き終わるのはいつか、という問題。

計算機の速度向上による減衰項と、時間経過による増加項の和は下に凸なのが自明なので、三分探索するだけ。

1000

表と裏の順番がいくつか与えられる。プレイヤー1が好きなのを選んだあとにプレイヤー2が好きなのを選ぶ。コインを振って、最初に選んだ順列が出現した方を勝ちとするとき、プレイヤー1が勝つ確率の最大値を求めよ、という問題。

取り敢えず全部のパターンの組について、それぞれの勝率を求めれば、プレイヤー1はプレイヤー2が相性の悪いのを選んだとしても勝率のいいのを選べば良い。

各パターンの組についての勝率を求めるには、オートマトンを組んで、確率付きの遷移行列を作る。このとき出現する状態は文字長の2乗だけ存在するけれど、実際にはもっと疎なので詰めるのが重要。後は行列乗算で適当な回数収束するまでべき乗してやれば、勝率が求まる。収束判定が面倒だったので、即値を入れてみたら、20乗だと間に合わなくて14乗だと精度が足りなくて、15乗だと通った。こんないい加減な問題なはずがないし、他の人の回答は違ったので、もっとすっきり数学的に解けるんだと信じている。(300点がそういう痕跡を残しているように見える。)