初心者必見！40代サラリーマンが競プロでPythonチャレンジ【ABC321_A-C問題】

こんにちは、こんぶちゃ(茶コーダー)です！

初心者視点から競プロAtCoderのABC321のA問題〜C問題の自身の解答と解答説明をしていきます。

こんな人にオススメしたい

競技プログラミング初心者で、問題の解き方がわからない方
AtCoderの公式解説は読んだが、内容が理解できなかった方
Pythonでの解法を知りたい方

まだまだ学習の身ですので、最適コードではない部分も多々あるかと思いますが、その部分は同じ学習者として温かい気持ちで応援＆ご助言頂けば嬉しいです。

では早速行ってみましょう！

今回の参加コンテスト(ABC321)
感想

今回の参加コンテスト(ABC321)

AtCoder Beginner Contest 321

A問題：321-like Checker

A – 321-like Checker

問題(要約)

与えられた整数 N が “321-like Number” であるかどうかを判定する問題です。”321-like Number” とは、以下の条件を満たす正整数のことです：

N の各桁を上から見ると狭義単調減少になっている。
- つまり、N の桁が左から右へ進むにつれて、その値が減少していくこと。

例えば、321、96410、1 は “321-like Number” ですが、123、2109、86411 は “321-like Number” ではありません。

解答

# 入力を受け取ります。Nは文字列として扱われます。
N = input()

# Nの各桁を左から右へ比較し、条件をチェックします。
for i in range(1, len(N)):
    # i番目の桁と(i-1)番目の桁を整数に変換して比較します。
    if int(N[i-1]) <= int(N[i]):
        # 条件を満たさない場合、"No"を出力して終了します。
        exit(print("No"))

# ループを抜けた場合、全ての桁で条件が満たされているので、"Yes"を出力します。
print("Yes")

N = input():
- ユーザーからの入力を受け取り、文字列として変数Nに格納します。
- ＊文字列として扱うのがポイントです＊
for i in range(1, len(N))::
- このループはNの各桁を左から右へ比較するためのものです。
- range(1, len(N))は1からNの桁数-1までの範囲を表します。
if int(N[i-1]) <= int(N[i])::
- ループ内で、i番目の桁と(i-1)番目の桁を整数に変換し、それらを比較しています。
- 条件式は、i番目の桁が(i-1)番目の桁以上である場合をチェックしています。
exit(print("No")):
- 条件が満たされない場合、つまりNが “321-like Number” の条件を満たさない場合、”No”を出力してプログラムを終了させます。
- exit()はプログラムの実行を終了するための関数です。
print("Yes"):
- ループを抜けた場合、すべての桁で条件が満たされていることを意味します。
- したがって、”Yes”を出力してプログラムを終了させます。

B問題：Cutoff

B – Cutoff

問題(要約)

試験は1ラウンドからNラウンドまでのNラウンドからなります。
各ラウンドには0以上100以下の整数のスコアが与えられます。
最終結果は、N-2ラウンドのスコアの合計で、最高スコアと最低スコアは除外されます。
現在、N-1ラウンドが終了し、各ラウンドのスコアが与えられています。
最終結果がX以上になるために、Nラウンド目に取るべきスコアの最小値を求める必要があります。
ただし、Nラウンド目にどのようなスコアを取っても最終結果がX以上にならない場合、代わりに-1を出力する必要があります。

解答

Nラウンド目の値が３パターン考えられるため、３パターンの条件分けをして回答を導いています。

higher_case: Nラウンド目が最大値以上の場合
lower_case: Nラウンド目が最小値以下の場合
mid_case: 上記のどちらでもない場合 (Nラウンド目の値が合計値に採用する場合)

# 入力からnとxを受け取ります。nは試験のラウンド数、xは目標の最終結果です。
n, x = map(int, input().split())

# 各ラウンドのスコアを受け取り、昇順にソートしてAに格納します。
A = sorted(list(map(int, input().split())))

# 初期値としてansを100に設定します。
ans = 100

# 最高スコアを除いた合計を計算し、higher_caseに格納します。
higher_case = sum(A[1:])

# もし目標の最終結果xがhigher_caseより大きい場合、不可能なので-1を出力してプログラムを終了します。
if x - higher_case > 0:
    exit(print(-1))
else:
    # そうでない場合、ansを最高スコアに設定します。
    ans = A[-1]

# 最低スコアを除いた合計を計算し、mid_caseに格納します。
mid_case = sum(A[1:-1])

# もしxがmid_caseと最低スコアの間にある場合、ansを更新します。
if A[0] <= x - mid_case <= A[-1]:
    ans = x - mid_case

# 最低スコアを除いた合計を計算し、lower_caseに格納します。
lower_case = sum(A[:-1])

# もしxがlower_case以下の場合、ansを0に設定します。
if x - lower_case <= 0:
    ans = 0

# 最終的なansの値を出力します。
print(ans)

以下詳細

入力されたスコアのソート:
- 入力されたスコアを昇順にソートします。これにより、最低スコアと最高スコアがわかりやすくなります。
最終結果の初期値 (ans) の設定:
- ans は初期値として100に設定されています。
最高スコアを除いた合計 (higher_case) の計算:
- higher_case は、最高スコアを除いたスコアの合計です。
- この値がXより大きい場合、目標の最終結果Xを達成することは不可能です。そのため、-1を出力してプログラムを終了します。
最高スコアの設定:
- もしhigher_caseがX以下であれば、ansを最高スコア (A[-1]) に設定します。これは、最終結果を最高スコアにできる場合のスコアです。
最低スコアを除いた合計 (mid_case) の計算:
- mid_case は、最高スコアと最低スコアを除いたスコアの合計です。
もしXがmid_caseと最低スコアの間にある場合:
- ans をXからmid_caseを引いた値に更新します。これにより、最終結果をX以上にするための最小のスコアを求めます。
最低スコアを除いた合計 (lower_case) の計算:
- lower_case は、最低スコアを除いたラウンドのスコアの合計です。
もしXがlower_case以下の場合:
- ans を0に設定します。これは、最終結果をX以上にするためにスコアを全く加える必要がない場合です。
最終的な結果 (ans) の出力:
- 最終的に計算されたansの値を出力します。これは、Nラウンド目に取るべき最小のスコアを示しています。

C問題：321-like Searcher

C – 321-like Searcher

問題(要約)

特定の条件を満たす正整数である “321-like Number” のK番目に小さい値を求める問題です。”321-like Number” とは、以下の条件を満たす整数です：

各桁を上から見ると狭義単調減少になっている。
1桁の正整数は必ず “321-like Number” である。

与えられた整数Kに対して、K番目に小さい “321-like Number” を求める必要があります。

解答

1から順番に321-like Numberかを確認しています。ただし、全検索してしまうとTLEになってしまうため、昇順に確認し、321-like Numberでない場合は、上位桁を1繰り上げ、残りの桁の数字を0にしています。検索時間を削減することができます。

例）

1, 2, …, と昇順の順番で確認していきます。
11 の時に 321-like Number に当てはまらなくなります
- 1桁目の 1 -> 2 に1繰り上げを行います
- 2桁目の 1 -> 0 にします　＊3桁目以降がある場合も0にします。
- つまり、20 になります
11 の次の確認する数字は 20 となり、確認する個数を削減し検索能力を向上させています。

# 321-like Numberかどうかを判定する関数
def is_321like(N):
    for i in range(1, len(N)):
        # 左から右へ桁を比較し、条件をチェック
        if N[i - 1] <= N[i]:
            # 条件を満たさない場合、Falseとその位置iを返す
            return False, i
    # 条件を満たす場合、Trueと0を返す
    return True, 0

# K番目の321-like Numberを求める
k = int(input())

num = 1  # 初期値
cnt = 0  # 321-like Numberのカウンター

while cnt < k:
    # numが321-like Numberかどうかを判定
    flag, i = is_321like(str(num))
    if flag:
        # 321-like Numberの場合、カウンターを増やし、次の数を探索
        cnt += 1
        num += 1
    else:
        # 321-like Numberでない場合、i番目の桁を増やして以降の桁を0にリセット
        str_num = list(str(num))
        str_num[i - 1] = str(int(str_num[i - 1]) + 1)
        for j in range(i, len(str_num)):
            str_num[j] = str(0)
        num = int("".join(str_num))

# K番目の321-like Numberを出力（-1は1を引くことにより、K番目の前の321-like Numberを取得）
print(num - 1)

以下詳細

is_321like 関数の定義:
- この関数は、与えられた整数が321-like Numberであるかどうかを判定します。
- 整数を文字列に変換し、隣接する桁を比較して条件をチェックします。
- 条件を満たさない場合、Falseとその位置（i）を返します。条件を満たす場合、Trueと0を返します。
K番目の321-like Numberを求めるための初期化:
- k はあたえられたK番目になります。
- num は現在の候補の321-like Numberを保持します。
- cnt は321-like Numberのカウンターで、K番目の321-like Numberを見つけるために使用されます。
メインのループ:
- cnt がKに達するまでループが実行されます。
- is_321like 関数を使って、num が321-like Numberであるかどうかを判定します。
- もし num が321-like Numberであれば、cnt を増やし、次の候補の数を探索するために num をインクリメント（１を加算）します。
- もし num が321-like Numberでなければ、条件を満たすように num を修正します。具体的には、i番目の桁を1増やし、それ以降の桁をすべて0にリセットします。
  （コード直前の例を参考にして下さい）
K番目の321-like Numberを出力:
- ループを抜けた後、K番目の321-like Numberが num に格納されています。
- この num から1を引いた値を出力することで、K番目の321-like Numberを得ます。321-like Numberは0以上の整数なので、K番目の前の数を求めるために1を引いています。

感想

今週は、C問題まで解けました！悩みに悩んで残り10分で回答に辿り着けたので、非常に満足しています。

A問題は、数字を適切なタイミングで文字列 -> 数字と扱うことで、解くことができました。

B問題は、Nラウンド目の扱いが３条件のパターンに分かれることを見出し、回答を提出しました。しかし、Nラウンド目の値を考慮する場合の下限設定不足のため、不正解になってしまいました。焦りましたが、深呼吸して間違い探しをして、回答まで辿り着けました。以前よりも焦らずに探すことができたので、成長を少し感じています。

C問題は、難解でした。問題の通りに実装してしまうと、TLE（タイムオーバー）してしまいました。とはいえ、他の解き方も思いつかず、万事急須。そこで、問題通りに実装しつつ、スキップできる検索条件を探し、検索時間を削減しました。これを提出したら、、、正解まで辿り着けました。やったーヾ(≧▽≦)ﾉ

このいい気分で来週もコンテストに参加したいと思います。

それでは、良い競プロライフを～！(*＾▽＾)／