ABC301のA,B,C,D問題をpythonで解説していきます。
A – Overall Winner
考察
考えた内容の概要
この問題は文字列の各文字を順に読んでいき、文字が ‘T’ なら高橋くんの勝ち、’A’ なら青木くんの勝ちとカウントし、最終的にどちらが多く勝ったかを判定する問題です。ただし、勝った試合数が同じ場合は最後に勝った方が負けとなります。
実装した内容
Pythonの文字列操作とif-else文を使って実装を行いました。文字列の各文字を順に読み込み、’T’なら高橋くんの勝ち、’A’なら青木くんの勝ちとカウントします。そして、2人の勝利数を比較し、多い方を出力します。
ただし、勝利数が同じ場合は最後に負けた方を出力します。
コード
N = int(input())
letter = input()
t_cnt = 0
a_cnt = 0
last = ""
for i in range(N):
if letter[i] == "T":
t_cnt += 1
else:
a_cnt += 1
last = letter[i]
if t_cnt == a_cnt:
if last == "T":
print("A")
else:
print("T")
else:
if t_cnt > a_cnt:
print("T")
else:
print("A")B – Fill the Gaps
考察
考えた内容の概要
この問題は、特定の条件に基づいて数列に数を挿入し、それを繰り返すことで最終的に得られる数列を求める問題です。
具体的には、隣接する2項の差の絶対値が1でない場合にその間に適切な数を挿入します。この操作を隣接する2項の差の絶対値が全て1になるまで繰り返します。
考えたことの内容
数列の先頭から見て行き、隣接する2項の差の絶対値が1でない場合にその間に数を挿入することを考えました。挿入する数は、隣接する2項の値に応じて決まります。具体的には、小さい方の数から大きい方の数の手前までの連続した整数を挿入します。これを数列の末項まで繰り返します。
実装した内容
Pythonのリストとforループを使ってこの問題を実装します。
まず、空のリストansを作成します。
次に、数列の先頭から順に隣接する2項を見て行き、その差の絶対値が1でない場合にその間に数を挿入します。挿入する数は新たなリストadd_listに格納し、それをansに結合します。
これを数列の末項まで繰り返した後、数列の最後の要素をansに追加します。最終的にansを出力します。
コード
N = int(input())
A = list(map(int, input().split()))
ans = []
for i in range(N-1):
ans.append(A[i])
if abs(A[i]-A[i+1]) == 1:
continue
elif A[i] < A[i+1]:
add_list = []
for j in range(A[i]+1, A[i+1]):
add_list.append(j)
ans.extend(add_list)
elif A[i] > A[i+1]:
add_list = []
for j in range(A[i]-1, A[i+1], -1):
add_list.append(j)
ans.extend(add_list)
ans.append(A[-1])
print(*ans, sep=" ")
C – AtCoder Cards
考察
考えた内容の概要
この問題では、与えられた2つの文字列が、ある操作を行った結果、一致するかどうかを判定することが求められています。この操作とは、文字列内の各文字を自由に並び替えることと、”@”の文字を任意の”a”, “t”, “c”, “o”, “d”, “e”, “r”に置き換えることです。
考えたことの内容
まず、各文字列に登場する各文字の個数をカウントします。そして、各文字について、2つの文字列でその文字の出現回数が一致しているか確認します。一致していれば次の文字へ、一致していなければその差分だけ”@”の文字を該当の文字に置き換えていきます。この時、”@”の文字が足りない場合や置き換えられない文字列の場合はゲームに勝てないので”No”を出力します。全ての文字で出現回数を一致させることができれば”Yes”を出力します。
実装した内容
具体的には、PythonのcollectionsモジュールのCounterを用いて各文字列内の文字の出現回数を辞書として保存し、それらの辞書を比較して問題を解きます。その過程で、”@”の文字を必要な文字に置き換える操作も行います。
コード
from collections import Counter
s = input()
t = input()
alha = [chr(ord("a")+i) for i in range(26)]#アルファベット列挙
#文字列sとtに含まれる各文字の出現回数をカウント
cnt_S = Counter(s)
cnt_T = Counter(t)
for i in range(26):#すべてのアルファベットについて探索
letter = alha[i]
if cnt_S[letter] == cnt_T[letter]:#sとtで出現するi番目のアルファベットの数が等しいなら
continue
elif cnt_S[letter] > cnt_T[letter]:
if letter == "a" or letter == "t" or letter == "c" or letter == "o"or letter == "d" or letter == "e" or letter == "r":
#atcoder のどれかで
if cnt_T["@"] >= cnt_S[letter] - cnt_T[letter]:#@の数が0以上なら
cnt_T["@"] -= cnt_S[letter] - cnt_T[letter]#不足分を補完して、その分@のカウントをへらす
continue
else:
print("No")
exit()
else:
print("No")
exit()
elif cnt_S[letter] < cnt_T[letter]:
if letter == "a" or letter == "t" or letter == "c" or letter == "o"or letter == "d" or letter == "e" or letter == "r":
if cnt_S["@"] >= cnt_T[letter] - cnt_S[letter]:
cnt_S["@"] -= cnt_T[letter] - cnt_S[letter]
continue
else:
print("No")
exit()
else:
print("No")
exit()
else:
print("No")
exit()
print("Yes")D – Bitmask
時間内に解けなかったよー涙
考察
考えた内容の概要
本問題はビット演算と全探索による問題です。文字列Sの中の?を0または1に置き換えて2進整数として解釈し、それらの数の中から与えられた整数N以下で最大のものを見つける必要があります。
考えた内容の概要
まず最初に、?を全て0に置き換えた場合の数（min_num）を作成します。これはSから生成可能な数のうち最小のものです。もしmin_numがNを超えていたら、Sから生成可能な数は全てNを超えるため、-1を出力してプログラムを終了します。
次に、?の位置をリストcnt_indに保存します。
その後、文字列Sの左から順に見ていき、?の位置であればそこを1に置き換え、それによって作られる数がNを超えない場合は1に置き換え、超える場合は0に置き換えます。
上記操作を全ての?について行うことで、N以下で最大の数を作成することができます。
実装した内容
Pythonのビルトイン関数bin()を使用して、Nを2進数表記の文字列に変換します。そして、?を全て0に置き換えたmin_numを作成し、min_numがNを超えていないかチェックします。min_numがNを超えていれば、-1を出力してプログラムを終了します。
その後、?の位置をリストcnt_indに保存し、文字列Sの左から順に見ていきます。?の位置であれば、そこを1に置き換えた数がNを超えないかチェックします。超えない場合はその位置を1に置き換え、超える場合は0に置き換えます。この操作を全ての?の位置について行うことで、N以下で最大の数を求めることができます。
コード
s = input()
N = int(input())
a = bin(N)#2進数に変換
two_N = a[2:]#b0はいらないので、取り除く
cnt_ind = []
for i in range(len(s)):#?の場所を記憶しておく
if s[i] == "?":
cnt_ind.append(i)
#？→0にしてもNよりも大きかったら、-1
min_num = s.replace("?", "0")
if int(min_num,2) > N:
print(-1)
exit()
cnt = ""#答えとなる値を2進数で記憶
for i in range(len(s)):
#シフト演算がよくわからなかったので、文字列として記憶して、結合→int変換しています・・・
if i in cnt_ind and int((cnt + "1")+min_num[i+1:],2) <= N:
#もしi番目が?→0に変換した場所でかつ、?→1に変換した場合でもN以下なら
cnt += "1"
else:#それ以外
cnt += min_num[i]
print(int(cnt,2))シフト演算むじー
コメント