いい方法が思いつかない。

情報オリンピック2006年度国内本選@どうかく

nチームの参加しているときに
- Piをチームiの順位
- Siをチームiのスコア
- Rijをチームiとチームjの対戦結果
とすると、

0 < i <= nな任意のiについて　
Pi + Si = n
が成り立つ

これを使うと早く計算できる方法がありそうな気がするのだが・・・。

ちなみにa)の証明自体は帰納法を使う。n+1のテーブルから全勝のチームを除外してnに帰結させればよい。

全部の組み合わせを生成するO(2^n)なやりかたは駄目コードを叩きのめしたいという出題者の思う壺だろう。

よいやりかたじゃないと計算量が採点基準に引っかかるように作られた出題だ。設問３でも正方形を作る４点を選ぶやり方と２点から計算でのこりの候補を絞るやり方では計算量が違いすぎる。前者だと得点できないはず。

・・・・・

解説をよんで納得。やっぱり採点基準は考えられているという読みはあたっていた。
しかし効率のよい解法がエレガントだなぁ。