247.1

300

椅子取りゲームで負けるプレイヤーを答えよ、という問題。

一番近い椅子が一番遠いプレイヤーが必ず負ける、という注釈が書いてあるので、それに従って実装するのみ。検証できていないけれど...。一番近い椅子に順次割り当てを行っていって、最後に残ったプレイヤーというのと同値になるように、1/n間隔のものと1/(n-1)間隔のものをマッチさせる状況ではできている、ということなんだろう。

500

与えられた英単語でのしりとりのチェイン長が最長のもののうち、文字列がアルファベット順で最初のものを答えよ、という問題。

文字は必ずAからZの方に進んでいくので、同じ文字でループするものを除けば後ろの方は簡単に固定できる。実際には同じ文字でループするものを少し例外処理した上でソートし、後ろから順に決定していけば良い。ソートアルゴリズムの問題かも。

1000

N人でK個の宝石からなるネックレスをN回の切断のみで分割するとき、分割した領域の最大値と最小値の差の最小値を答えよ、という問題。

最大値となる部分を固定した上で、分割の結果発生し得る値から最小値になり得るものを全探索。残りの部分を最小値以上最大値以下になるような分割でいくつに区切れるかを計算し、それがN-1になるかどうかを判定すれば良さそう。アルゴリズム自体は間違っていないはずなので、バグを埋め込んだんだと思いたいけれど...。