【ABC321】競プロのA-C問題を40代サラリーマンがPython解説!初心者にもわかりやすく

abc321 AtCoder

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

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

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

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

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

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

AtCoder Beginner Contest 321

A問題:321-like Checker

A – 321-like Checker

問題(要約)

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

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

B問題:Cutoff

B – Cutoff

問題(要約)

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

解答

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

  • 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)

以下詳細

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

C問題:321-like Searcher

C – 321-like Searcher

問題(要約)

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

  1. 各桁を上から見ると狭義単調減少になっている。
  2. 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)

以下詳細

  1. is_321like 関数の定義:
    • この関数は、与えられた整数が321-like Numberであるかどうかを判定します。
    • 整数を文字列に変換し、隣接する桁を比較して条件をチェックします。
    • 条件を満たさない場合、Falseとその位置(i)を返します。条件を満たす場合、Trueと0を返します。
  2. K番目の321-like Numberを求めるための初期化:
    • k はあたえられたK番目になります。
    • num は現在の候補の321-like Numberを保持します。
    • cnt は321-like Numberのカウンターで、K番目の321-like Numberを見つけるために使用されます。
  3. メインのループ:
    • cnt がKに達するまでループが実行されます。
    • is_321like 関数を使って、num が321-like Numberであるかどうかを判定します。
    • もし num が321-like Numberであれば、cnt を増やし、次の候補の数を探索するために num をインクリメント(1を加算)します。
    • もし num が321-like Numberでなければ、条件を満たすように num を修正します。具体的には、i番目の桁を1増やし、それ以降の桁をすべて0にリセットします。
      (コード直前の例を参考にして下さい)
  4. 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ラウンド目の扱いが3条件のパターンに分かれることを見出し、回答を提出しました。しかし、Nラウンド目の値を考慮する場合の下限設定不足のため、不正解になってしまいました。焦りましたが、深呼吸して間違い探しをして、回答まで辿り着けました。以前よりも焦らずに探すことができたので、成長を少し感じています。

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

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

それでは、良い競プロライフを~!(*^▽^)/

コメント

タイトルとURLをコピーしました