Atcoder ABC302のA,B,C,D,問題をpythonで解説していきます！
拙い文章で分かりづらい部分がありましたら、@EitaSugiご連絡いただけると幸いです！！
A – Same
A – Sameの考察
・考えた内容の概要
この問題は、与えられた整数のリストが全て同じ値であるかどうかを判断するシンプルな問題です。全ての要素が等しい場合は”Yes”を、そうでない場合は”No”を出力します。
・考えたことの内容
リストの全ての要素が等しいかどうかを確認する一つの方法は、リストの最初の要素と他の全ての要素を順番に比較することです。一つでも異なる要素があれば“No”を出力し、プログラムを終了します。全ての要素が等しい場合は“Yes”を出力します。
・実装した内容
コードでは、まず整数Nを入力として受け取り、次にN個の整数を含むリストAを入力として受け取ります。その後、Aの最初の要素と他の要素を順番に比較します。もし異なる要素があれば“No”を出力し、プログラムを終了します。全ての要素が等しい場合は“Yes”を出力します
コード
# 入力される整数Nを受け取る
N = int(input())
# N個の整数をリストとして受け取る
A = list(map(int, input().split()))
# リストAの最初の要素と他の要素を順番に比較
for i in range(1, N):
# もしA[0]とA[i]が等しくないなら"No"を出力し、プログラムを終了
if A[0] != A[i]:
print("No")
exit()
# 全ての要素が等しいなら"Yes"を出力
print("Yes")
B – 3-smooth Numbers
B – 3-smooth Numbersの考察
・考えた内容の概要
この問題では、与えられた正の整数 NがN =2x3y の形になるかどうかを判断します。ここで、x と y は整数です。もし N がこの形になるなら “Yes” を、そうでなければ “No” を出力します。
・考えたことの内容
N が 2x3yの形になるかどうかを判断するためには、まず N をできるだけ 2 で割り、次に 3 で割ります。
もし最終的に N が 1 になるなら、“Yes” を出力します。それ以外の場合は “No” を出力します。
・実装した内容
コードでは、まず N を入力として受け取ります。次に、N が 2 で割り切れる限り 2 で割り続け、3 で割り切れる限り 3 で割り続けます。
最終的に N が 1 であれば “Yes” を、そうでなければ(2と3以外の素因数を持つなら) “No” を出力します。
コード
# 入力される整数Nを受け取る
N = int(input())
# Nが2で割り切れる限り2で割り続ける
while True:
if N % 2 == 0:
N = N // 2
else:
break
# Nが3で割り切れる限り3で割り続ける
while True:
if N % 3 == 0:
N = N // 3
else:
break
# 最終的にNが1であれば"Yes"を、そうでなければ"No"を出力
if N == 1:
print("Yes")
else:
print("No")
C – Error Correction
C – Error Correctionの考察
・考えた内容の概要
この問題は、与えられた文字列 T が、別の文字列 T′ から一定のルールに基づいて変換されて得られるかどうかを判断するものです。具体的には、以下の4つの条件のいずれかが成り立つかを確認します。
- T′ は T と完全に一致している
- T′ は T に1文字を挿入したもの
- T′ は T から1文字を削除したもの
- T′ は T から1文字を別の文字に変更したもの
・考えたことの内容
この問題を解くためには、各条件を一つずつ確認し、いずれかの条件が成り立つかをチェックします。特に、文字列の長さを利用して、どの条件をチェックするかを判断します。
例えば、T と T′ の長さが等しい場合、条件1または条件4のみをチェックします。
・実装した内容
コードでは、
- まず T′ の長さに基づいて、チェックすべき条件を絞り込みます。
- 次に、各条件を確認し、条件が成り立つ場合にはそのインデックスを記録します。
- 最後に、条件を満たす文字列の数と、それらのインデックスを出力します。
条件1: T’ は T と完全に一致している
この条件は最も単純で、単純に2つの文字列が等しいかどうかを確認します。
Pythonでは`if T_dash == T:`と記述することで、2つの文字列が等しいかどうかを確認できます。
条件4: T’ は T から1文字を別の文字に変更したもの
この条件も比較的シンプルで、2つの文字列の各位置を比較し、異なる文字が1つだけ存在するかどうかを確認します。
`zip`関数を用いて2つの文字列を同時にループさせ、異なる文字の数をカウントします。異なる文字が1つだけの場合、この条件を満たします。
条件2: T’ は T に1文字を挿入したもの
- ケース1: T′ の最後の文字が追加された文字である場合。
この場合、if T_dash[:-1] == T:でチェックします。T_dash[:-1]は、最後の1文字を除いた文字列を表します。 - ケース2: T′ の途中に文字が追加されている場合。
この場合、追加された文字の位置を特定し、その文字を除いた残りの部分が Tと一致するかを確認します。コード内のfor j in range(len(T)):ループがこのチェックを行っています。ループ変数jは、チェックする文字の位置を表します。
if T_dash[j] != T[j]:で、 T ′ とTで文字が異なる位置を見つけ、if T_dash[j+1:] == T[j:]:で、その位置以降の文字が一致しているかを確認します。
条件3: T’ は T から1文字を削除したもの
この条件も条件2と似ていますが、今回はTの各位置で1文字を削除し、残りの部分がT’と一致するかどうかを確認します。
コード
# 入力される整数Nと文字列Tを受け取る
N, T = input().split()
N = int(N)
ans = []
# N回ループを回して、各T'をチェックする
for i in range(N):
T_dash = input() # T'を入力として受け取る
# 条件1と4: T'とTの長さが等しい場合
if len(T_dash) == len(T):
# 条件1: T'とTが完全に一致している場合
if T_dash == T:
ans.append(i + 1)
# 条件4: T'とTが1文字だけ異なる場合
else:
diff_count = sum([s != t for s, t in zip(T_dash, T)])
if diff_count == 1:
ans.append(i + 1)
# 条件2: T'がTに1文字を挿入したものである場合
elif len(T_dash) - len(T) == 1:
# ケース1: T'の最後に文字が挿入された場合
if T_dash[:-1] == T:
ans.append(i + 1)
continue
# ケース2: T'の途中に文字が挿入された場合
for j in range(len(T)):
if T_dash[j] != T[j]:
if T_dash[j + 1:] == T[j:]:
ans.append(i + 1)
break
# 条件3: T'がTから1文字を削除したものである場合
elif len(T) - len(T_dash) == 1:
# ケース1: Tの最後の文字が削除された場合
if T[:-1] == T_dash:
ans.append(i + 1)
continue
# ケース2: Tの途中の文字が削除された場合
for j in range(len(T_dash)):
if T[j] != T_dash[j]:
if T[j + 1:] == T_dash[j:]:
ans.append(i + 1)
break
# 条件を満たすT'の数と、それらのインデックスを出力
print(len(ans))
ans.sort()
print(*ans, sep=" ")D – Square Permutation
D – Square Permutationの考察
・考えた内容の概要
この問題は、与えられた数字の文字列 S を並べ替えてできる文字列を十進法の整数として解釈したもののうち、平方数であるものがいくつあるかを求めるものです。
具体的には、S の各文字を並べ替えてできる全ての整数について、それが平方数であるかどうかを確認します。
・考えたことの内容
- 1≤N≤13 より、S の並べ替えは 13! であり、これは >108 となり、計算量が多くなりすぎるため、Pythonで実行すると時間制限を超えてしまいます（TLE）。
そこで、考え方を変え、平方数の最大値に注目します。
今回は、ありうる最大の平方数は、S を並べ替えてできる最大値の平方数となります。
S を並べ替えてできる最大値はすべての数字が「9」の時の 9999999999999 で、この数の平方数 x は 107 以下になります
（9999999999999<10144 より sqrt(1014)=107のため)
そのため今回1からあり得る平方数の最大値まで全探索することが可能です。
・実装した内容
- まず S を並べ替えてできる最大の整数を求めます。
- その後その平方根までの全ての整数について、その平方が S の並べ替えで表現できるかどうかをチェックします。
具体的には、各整数の平方を文字列として生成し、その各桁の数字の出現回数が S の各桁の数字の出現回数と一致するかどうかを確認します。
コード
from collections import Counter
# 入力を受け取る
N = int(input())
s = input()
# 各数字の出現回数をカウント
s_count = Counter(s)
# Sを並べ替えてできる最大の整数の平方根を計算
max_val = int("".join(sorted(s, reverse=True)))
sqrt_limit = int(max_val ** 0.5)
ans = 0 # 答えとなるカウントを初期化
# 1からsqrt_limitまでの各整数について、その平方がSの並べ替えで表現できるかをチェック
for i in range(sqrt_limit + 1):
square_str = str(i * i) # iの平方を文字列として生成
squared_count = Counter(square_str) # 各数字の出現回数をカウント
# Sの各桁の数字の出現回数と一致するかをチェック
for num in ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]:
if num == "0":
# 0の場合、squared_count[num]がs_count[num]以下であればOK
if squared_count[num] > s_count[num]:
break
else:
# 0以外の場合、squared_count[num]がs_count[num]と一致する必要がある
if squared_count[num] != s_count[num]:
break
else:
# 全ての数字について出現回数が一致した場合、答えのカウントを増やす
ans += 1
# 答えを出力
print(ans)ここで、square_str は i×i の文字列形式であり、squared_count はその各数字の出現回数をカウントしたものです。
次に、for num in ["0","1","2","3","4","5","6","7","8","9"]: ループで、各数字について以下のチェックを行います。
num == "0"の場合、squared_count[num]がs_count[num]よりも大きいならば、breakでループを抜けます。これは、sの中にある0の数よりも、平方数の中に0が多い場合、その平方数は条件を満たさないためです。
(なぜ0の個数に関してはsquared_count[num]がs_count[num]よりも小さくても良いのかは、数値の先頭にある0は無視されるため。例えば、001は1として扱われます。したがって、sの中にある0の数が多くても、平方数の中に0が少なくても、その平方数はsから作成可能であると考えられます)num != "0"の場合、squared_count[num]がs_count[num]と等しくない場合、breakでループを抜けます。これは、sの中の非ゼロ数字の出現回数と、平方数の中の非ゼロ数字の出現回数が一致しない場合、その平方数は条件を満たさないためです。
else: ans += 1 は、for ループが break なしで正常に終了した場合（すなわち、全ての数字について条件を満たした場合）に実行されます。この場合、答えとなるカウント ans を1増やします。
コメント