こんにちは、こんぶちゃ(茶コーダー)です!
初心者視点から競プロAtCoderのABC321のA問題〜C問題の自身の解答と解答説明をしていきます。
まだまだ学習の身ですので、最適コードではない部分も多々あるかと思いますが、その部分は同じ学習者として温かい気持ちで応援&ご助言頂けば嬉しいです。
では早速行ってみましょう!
今回の参加コンテスト(ABC321)
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
問題(要約)
- 試験は1ラウンドからNラウンドまでのNラウンドからなります。
- 各ラウンドには0以上100以下の整数のスコアが与えられます。
- 最終結果は、N-2ラウンドのスコアの合計で、最高スコアと最低スコアは除外されます。
- 現在、N-1ラウンドが終了し、各ラウンドのスコアが与えられています。
- 最終結果がX以上になるために、Nラウンド目に取るべきスコアの最小値を求める必要があります。
- ただし、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)
以下詳細
- 入力されたスコアのソート:
- 入力されたスコアを昇順にソートします。これにより、最低スコアと最高スコアがわかりやすくなります。
- 最終結果の初期値 (
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
問題(要約)
特定の条件を満たす正整数である “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
をインクリメント(1を加算)します。 - もし
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を引いています。
- ループを抜けた後、K番目の321-like Numberが
感想
今週は、C問題まで解けました!悩みに悩んで残り10分で回答に辿り着けたので、非常に満足しています。
A問題は、数字を適切なタイミングで 文字列 -> 数字と扱うことで、解くことができました。
B問題は、Nラウンド目の扱いが3条件のパターンに分かれることを見出し、回答を提出しました。しかし、Nラウンド目の値を考慮する場合の下限設定不足のため、不正解になってしまいました。焦りましたが、深呼吸して間違い探しをして、回答まで辿り着けました。以前よりも焦らずに探すことができたので、成長を少し感じています。
C問題は、難解でした。問題の通りに実装してしまうと、TLE(タイムオーバー)してしまいました。とはいえ、他の解き方も思いつかず、万事急須。そこで、問題通りに実装しつつ、スキップできる検索条件を探し、検索時間を削減しました。これを提出したら、、、正解まで辿り着けました。やったーヾ(≧▽≦)ノ
このいい気分で来週もコンテストに参加したいと思います。
それでは、良い競プロライフを~!(*^▽^)/
コメント