質問: 0 # 各数値の2通りの選択通り数を足していく for i in range(N): sumWay += choose2(uni[i]) """ 全ての要素数 - 削除する要素の通り数 + 削除する要素を引いた際の通り数 を求める """ for i in range(N): print(sumWay - choose2(uni[An[i]]) + choose2(uni[An[i]]-1)) ```
回答: ### テストケースの中身 AtCoderでは、テストケースの中身が(一部のコンテストを除き)公開されています。 トップページの便利リンク集から飛べます。 今回のテストケースはこれです。 ### WAになる原因 `uni`配列では、要素`i+1`に数字`i`が書かれたボールの個数が入っています。 そのため、`uni[0] = 0`です。(なぜなら、`1 <= A[i] <= N`なので) そして、`uni[N]`には数字`N`が書かれたボールの個数が入っています。 しかし、18行目のfor文は0~n-1までしか回っていません。 そこを訂正するとACしました。 少し他にも書き換えた部分があるので、質問の内容とは関係ないですが、説明します。 ### 前計算 何度も`choose2` を計算するのは、(制約が大きくなった場合は)計算量が大きくなってしまいTLEする可能性が高くなってしまいます。 今回は、0C2 ~ nC2を求めたいので、事前に`con`配列にそれぞれ代入しておきました。