読者です 読者をやめる 読者になる 読者になる

AtCoder CodeFormula2014 予選A C - 決勝進出者

問題
http://code-formula-2014-quala.contest.atcoder.jp/tasks/code_formula_2014_qualA_c

N回の予選があり、開かれる順序の早い順に、それぞれの順位がK位まで与えられる。ここからK人を選抜したい。

選抜の方法は以下である。
1. 予選の順位が高いほうが優先される。
2. 予選の順位が同じなら、より順番の早い予選に参加した人が優先される。
3. K人が選抜されるまで続ける

上から1つずつ予選を開催するごとに、その時点で初めて選抜が確定した人を番号順にソートして全て出力せよ。
1 <= N <= 50, 1 <= K <= 1000
1 <= a[i][j] <= 999999

解答
上から確定できるだけ左に見ていき、確定できなくなったら下に移動する。
同順位なら予選の開催が早い人を優先するので、入力の表の上で今見ている人の上側にある人のうち、1回目の予選から今開催した予選まで順番に調べる。
後に開かれる予選でも、より順位が高い人が選抜に優先されるので、選抜を検討している人物の表の上での場所の左下にできる長方形領域に含まれる人物に、出来る限り未確定な人物が含まれると考える。それでもなお、選抜されることが確定する場合は、現在開いた最後の予選に対して選抜された番号を含める。