アルゴリズム忘備録

競技プログラミングとかデータ分析とか

TopCoder SRM 720 Div1 Med

n, k (n>=k) が与えられる。n x n行列で、任意の行及び列を取り出した時、その中で異なる要素がk個になるような行列を構成したい。このような行列の中で、全要素について異なる要素が最大のものを一個構成せよ。

 

なんかEasyでも良さそうな問題。(今回はEasyがやたら難しかったので問題を取り違えた説もある)。まず全要素を0で並べた行列を作成し、1行目は {1, 2, 3,...,k, 0, 0, 0, ...} 、

2行目は{0, (k+1), (k+2), (k+3),...,(k+k), 0, 0, 0, ...} という感じで、{1, 2, 3..k, 0, 0, ..} という数列を非ゼロ要素をk-インクリメントしながらローテーションしたものを並べると目的の行列が構成できる。

 

Hackケースとして、ローテーションではなく末尾を落とした場合がたくさんあった模様。