Atcoder Beginners contest 321 "CutOff"解説

Atcoder Beginners contest 321 "CutOff"解説 In　Python

今回はついこないだ解いたCutOffという問題をPythonで解説していきます。
過去問として解いていくときの参考になれば幸いです。

問題

問題文にはいろんなことが書いてありますが、僕なりに要約するとこんな感じです。
分かりにくかったら下のリンクから問題文を読んでください。

• Nラウンド行われる試験がある
• 各ラウンドには0-100のスコアが存在する
• 総合的なスコアは最低値と最大値を除いたものになる
• iラウンド目のスコアはAi
• **最終結果（総合的なスコア）をX点以上にするためには何点取る必要があるか？
• もし１００点をとってもX点以上にならない場合-1を出力しろ。**

入力方法
N　X
A1 A2 A3 .....

https://atcoder.jp/contests/abc321/tasks/abc321_b

アルゴリズム

今回のアルゴリズムはこんな感じ。
まずこの問題では得点は下の画像の様に、最大値でも最小値でもない数字の合計点が得点となっています。

なのでもしX点を超えれるのかどうか知りたいのであれば、この得点のデータに0-100点まで各ケースを調べれば良いです。各ケースを調べて最大点である100点をとってもX点にならないのなら問題文の通り”－１”を出力すればいいですし、もしX点になるために必要な得点が0-100にあったのならその必要な得点を出力するだけでバッチリです。

これをコードに落とし込んでいきます。

Pythonでの回答例

Pythonで実際にACしたコードです。
コメントもついているので、ぜひ参考程度にお読みください。

# -*- coding: utf-8 -*-
#まず数字を受け取る
N, X = map(int, input().split())
As = [int(x) for x in input().split()]
#次にAsを低い順からソート
As = sorted(As)
#１００回繰り返す
for x in range(0,101):
    scorenow = As[0:len(As)]
    #↑ScoreをAsの入力された初期値にリセット
    scorenow.append(x)
    #今のスコアの最大値を消す
    scorenow.remove(max(scorenow))
    #今度は最低値を消す
    scorenow.remove(min(scorenow))
    #もしスコアがXより大きかったらPrintして終了
    if sum(scorenow) >= X:
        print(x)
        exit()
    else:
        continue
#でなければ-1を出力
print(-1)