207.1

次のSRMまで時間があいたので過去問を解いてみる。余り良くないセットだったなぁ...。

250

Nチームのリーグ戦で、チーム間での勝つ確率が与えられるので、最終的に何勝するかを多い順に答えよという問題。

ソートをちゃんと実装しましょうというありがちな問題。

500

N都市に商品を売りに行く。移動コストと時間が与えられ、ある都市での利益が与えられる。ただし、商売敵が存在して、相手よりも先に到達しなければ、利益は商売敵の数だけ半減する。いかない都市があっても良いとき、売上の最大値を答えよという問題。

最初の都市に来たら処理を終了する形で、N!のパスを検索するだけ。普通に実装しても特に問題はなかった。実装速度勝負の問題。

1000

巨大なチェス盤の中にいくつか黒いマスが指定され、すべての黒いマスを通る時、原点にいるナイトが移動しなくてはならない最小の回数を答えよという問題。

これまたN!のパスを検索するだけ。ただし、移動にかかる歩数の計算をうまくやらないといけない。近傍数マスについてはテーブルに入れておいて、後は近傍までにどういうパスを利用するかを一通り試してみれば良さそう。

x2,y1という移動とx1,y2という移動の二つに制限するような変換ができるので、前者をある程度の回数使うときに後者が何回で近傍に入るか調べて、入る範囲で最小のものを計算すればいいんじゃないかなぁ。適当にグリーディにやってみたらうまくいかなかったけれど、うまくいっているっぽい人もいるので、調整をどうやるかの問題だと思う。すっきりした解答がない感じ。(すっきりしたルーチンの中に正解があるとは思う。ないと問題として成立しないような気もするので。)