Atcoder Beginners contest 321 "CutOff"解説 In Python
今回はついこないだ解いたCutOffという問題をPythonで解説していきます。
過去問として解いていくときの参考になれば幸いです。
問題
問題文にはいろんなことが書いてありますが、僕なりに要約するとこんな感じです。
分かりにくかったら下のリンクから問題文を読んでください。
- Nラウンド行われる試験がある
- 各ラウンドには0-100のスコアが存在する
- 総合的なスコアは最低値と最大値を除いたものになる
- iラウンド目のスコアはAi
- **最終結果（総合的なスコア）をX点以上にするためには何点取る必要があるか？
- もし１００点をとってもX点以上にならない場合-1を出力しろ。**
入力方法
N X
A1 A2 A3 .....
アルゴリズム
今回のアルゴリズムはこんな感じ。
まずこの問題では得点は下の画像の様に、最大値でも最小値でもない数字の合計点が得点となっています。
なのでもし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)