Code Formula 2014 C - 決勝進出者

f:id:tkr987:20210415034231p:plain

f:id:tkr987:20210415034238p:plain

https://atcoder.jp/contests/code-formula-2014-quala/submissions/21743681

  •  j \times n + i で二次元データに順位を付ける

f:id:tkr987:20210415043053p:plain

昔は日本語読解が困難な問題も多く、問題文の意味を理解するのが難しいが…一番簡単なテストケースとして重複が一切ない場合は左図のように a[i][j] の順位を  j \times n+i として k=9 まで出力すれば良い。二次元データに順位を付けて横に見る意識。

難しいのは右図のように a[i][j] に重複がある場合で、現在 i=3 を見ているとする。今までに確定した(ユニークな)ID、を重複(ただし重複せずに確定した数字も含む)しているIDとする。このとき、本来なら k=9 まで見れば良かった範囲が k = k - (の個数) + (の個数) = 11 へと変化する。

もう少し詳しく理由を述べると、例えばユニークな確定IDが5個あるなら残り4個までしか採用しないので k - (の個数) になる。重複IDがあるなら採用できなかったので、そのぶん範囲が増加されて k + (の個数) になる。ただし、重複が極端に少ないと範囲が元より減る可能性があり、それは明らかに正しい答えにならないのでの個数は正確には重複IDの個数だけでなく確定IDの個数も含めるよう定義しなければならない。

したがって、右図で具体的に考えると i=3 の出力は「11 17」になる。このように i=3 まで見て初めて i=0 のIDが確定されて出力されることもあるので注意する。

 

感想: 日本語読解まで本質に含まれる問題あまり好きではない…