質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.92%

AtCoder159の「D-BannedK」の問題で何が間違っているかわからない

解決済

回答 2

投稿

  • 評価
  • クリップ 0
  • VIEW 95

Msk07

score 19

AtCoderのD-BannedKの問題で下記コードを提出したのですが、「WA」の結果となります。
サンプルケースではあっているのですが、一部のテストケースで「WA」となるようです。
何が間違っているのかについて教えてください。
提出結果はこちらです。

""" スニペット """
def get_int():
    return int(input())

def get_ints():
    return list(map(int, input().split()))
""" スニペット """
import math
# 2つ選ぶ通り数を算出 nC2
def choose2(n):
    return math.floor(n*(n-1)/2)

# インプット
N = get_int()
An = get_ints()
""" 全ての要素から2つのボールを選ぶ通り数を求める """
uni = [0] * (N+1)
# ユニーク数の配列を求める
for i in range(N):
    uni[An[i]] += 1
sumWay = 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)) 
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

+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配列にそれぞれ代入しておきました。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/09/16 23:47

    bamboo_music_acさん

    ご回答ありがとうございます!
    >AtCoderでは、テストケースの中身が(一部のコンテストを除き)公開されています。
    テストケースの中身が公開されているなんて知りませんでした。
    大変貴重な情報をいただきありがとうございます!
    WAになった原因については理解できました。
    N個目の要素にアクセスできていなかったのですね。
    回答例や、応用問題への方法まで教えていただき大変勉強になりました。
    ここまで丁寧でわかりやすいご回答をいただき感動いたしました。
    ありがとうございました!!!

    キャンセル

  • 2020/09/17 13:35

    競プロは、結構有志の便利なサイトとかコンテンツがいっぱいありますよ〜!

    キャンセル

+1

sumWay = 0
# 各数値の2通りの選択通り数を足していく
for i in range(N):
    sumWay += choose2(uni[i])


choose2(uni[N])を足し忘れてます

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/09/16 23:49

    yudedako67さん

    ご回答ありがとうございます。
    uni[N]の要素が足せていないことを理解できました。
    ありがとうございました!

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.92%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る