Codeforces 90

Bでトラブルがあったらしくレートなし。なんか激しくやる気出ない...。

A

N個の石がある。二人のプレイヤーはそれぞれAとBという値を心に決めていて、残っている石の数との最大公約数だけ石を取り除く。交互にプレイするとき、最後の石を取るプレイヤーを答えよ、という問題。

愚直に実装するだけ。

B

N個の問題があり、K個の問題セットに分割されている。N/K問ずつに分割されていて、いくつかのセットについての情報は得られている。各問題について得点の期待値が与えられるので、問題セットの期待値の最大値と最小値を答えよ、という問題。

どのセットにも出現していない問題はどういうセット割になっているか分からないので、N/K問のセットが任意にくると考える。これはソートしてやって、期待値の小さい方からと大きい方から適当に選べばよい。既知のセットについては計算するだけ。

C

授業科目ごとに、難易度と宿題の分量の許容範囲が決まっている。難易度が下がらないようにスケジューリングするが、宿題の分量もK倍または+Kという形で増やしていきたい。このとき、トータルの宿題量を最大化するスケジューリングのいずれかを答えよ、という問題。

DPしましょうという問題。宿題の許容範囲自体は狭いので、実際に与えられた宿題の量はその都度再計算する。前に受けた授業と、そのときにこなした宿題の分量(実際には許容範囲のどこか)を覚えておきつつテーブルを更新してやれば、宿題の総量が最大になるところを復元できる。

D

文字列が二つ与えられる。一つ目の文字列の真ん中の数文字を先頭に持ってきて、後ろ側を反転して、前側を反転して結合したものが二つ目の文字列に合致するような、真ん中の数文字の位置のうち、できるだけ後ろでできるだけ短いものを答えよ、という問題。

二つ目の文字列を後ろから読んだものがどこまで一つ目の文字列と合致するかはO(N)で比較できる。また、二つ目の文字列の先頭からの何文字かが一つ目の文字列のどこに出現し得るか、みたいなのは文字列探索アルゴリズムでかなり高速にできる。最後のパートの検証コストがいまいち見積もれない...。

E

3次元空間上にN個の点がある。これをある平面に垂線を降ろす形でマップし、同一円を描いたときに共通する点が存在する最小の半径を、K個の平面について求めよ、という問題。ただし、面の裏側から垂線を下ろす場合は、円の半径が小さくなる補正が入るので、そこに注意すること。

強実装幾何問題。バイナリサーチでできると思うけれど、既出問題だろうと思うこと以外には何も分からない。