[ABC314 A~D Python]AtCoder Beginner Contest 314
A問題
# 入力N
N = int(input())
# 円周率の小数第N位まで
print("3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679"[:N+2])小数第N位まで出力するということは、
小数の前に「3.」があるので、
文字列で考えると、N+2まで出力すればいいことになります。
B問題
# 入力N
N = int(input())
# 賭けた目の個数の最小値(Xに賭けた人の中で)
bet_number_min = 38
# Cのリスト
C_list = []
# Aのリスト
A_list = []
for i in range(N):
# 入力C,A
C = int(input())
A = list(map(int, input().split()))
C_list.append(C)
A_list.append(A)
# 入力X
X = int(input())
# 参加者全員について
for i in range(N):
C = C_list[i]
A = A_list[i]
# Xに賭けた、かつ、賭けた目の個数がこれまでで最小
if X in A and C < bet_number_min:
# 最小値を更新
bet_number_min = C
# 最小値が更新されたので、新しく番号を保存するリストを作成する
ans = []
# 人の番号を追加
ans.append(i+1)
# Xに賭けた、かつ、賭けた目の個数の最小値と同じ
elif X in A and C == bet_number_min:
# 人の番号を追加
ans.append(i+1)
# 最小値が変化なかった=Xにかけた人がいなかった
if bet_number_min == 38:
print(0)
else:
# 人の人数と人の番号を出力
print(len(ans))
print(*ans)
賭けたもの個数の最小値を更新していきます。
対象になるのはXに賭けた人のみになります。
C問題
# インポート
from collections import defaultdict
# 入力N,M,S,C
N, M = map(int, input().split())
S = input()
C = list(map(int, input().split()))
# 色ごとに何の文字かを保存するdefaultdict
color_index = defaultdict(list)
# 色ごとに何文字目かを保存するdefaultdict
color_str = defaultdict(list)
# Sの全ての文字について
for i in range(N):
# 文字を色ごとに保存
color_str[C[i]-1].append(i)
# インデックスを色ごとに保存
color_index[C[i]-1].append(S[i])
# 色ごとに巡回シフト
for i in color_index:
color_index[i] = color_index[i][1:]+[color_index[i][0]]
# 操作後の文字の場所を表すdefaultdict
ans_dict = defaultdict(str)
# 色ごとに、文字と場所を関連させる
for i in color_str:
for j in range(len(color_str[i])):
ans_dict[color_str[i][j]] = ans_dict[i][j]
# defaultdictをソート
ans_dict = sorted(ans_dict.items(), key=lambda x: x[0])
# 答えとして出力する変数を用意
ans = ""
# 答えに文字を加えていく
for i in ans_dict:
ans += i[1]
print(ans)文字とインデックスを分けて操作していきます。
リスト等で文字を移動させると、
計算量がかかるので、
辞書型で、インデックスと文字とを対応させながら操作します。
D問題
# インポート
from collections import defaultdict
# 入力N,S
N = int(input())
S = input()
# 英大文字
big = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
# 英小文字
syou = "abcdefghijklmnopqrstuvwxyz"
# 各文字の場所と文字名を保存するdefaultdict
S_dict = defaultdict(int)
# 英大文字と小文字を相互変換するためのdefaultdict
conv = defaultdict(str)
# convの準備
# 英大文字と小文字を対応させる
for i in range(len(big)):
conv[big[i]] = syou[i]
conv[syou[i]] = big[i]
# Sの各文字が、大文字かどうか判定するリスト
# 特にti=1の時に使う
big_judge = [False]*N
# 現時点で大文字か小文字か判断
for i in range(N):
# S_dictに文字と場所を保存
S_dict[i] = S[i]
# 大文字か小文字かも同時に保存しておく
if S[i].islower():
big_judge = [False]*N
# 入力Q
Q = int(input())
# ti=2またはti=3によって、
# 全体が大文字または小文字に変化されたかどうかを保存する変数
# judge=""→ti=2またはti=3が入力されず、全体での変化はなし
# judge=True→全て小文字に変更する
# judge=False→全て大文字に変更する
judge = ""
# ti=1の時に変更を一時保存するためのdefaultdict
now_conv = defaultdict(str)
# Q回の操作
for i in range(Q):
# 入力t,x,c
t, x, c = input().split()
# t=1の時
if t == "1":
# 変更を一時保存
now_conv[int(x)-1] = c
# t=2の時
elif t == "2":
# judgeをTrueに
judge = True
# これまでの変更を反映
for j in now_conv:
S_dict[j] = now_conv[j]
# big_judgeも変更
if now_conv[j].islower():
big_judge[j] = True
else:
big_judge[j] = False
# 全て変更したので、初期値に戻す
now_conv = defaultdict(str)
# t=3の時
else:
# judgeをFalseに
judge = False
# これまでの変更を反映
for j in now_conv:
# big_judgeも反映
if now_conv[j].islower():
big_judge[j] = True
else:
big_judge[j] = False
S_dict[j] = now_conv[j]
# 全て変更したので、初期値に戻す
now_conv = defaultdict(str)
# judgeが""でなければ、
# つまり全体での大文字小文字変更が必要であれば
if judge != "":
# Sの全ての文字について
for i in S_dict:
# 現在の大小と全体の変更に相違があれば、
# それぞれ変更する
if big_judge[i] != judge:
S_dict[i] = conv[S_dict[i]]
# まだ、t=1で変更していない物を変更させる
for i in now_conv:
S_dict[i] = now_conv[i]
# 最終的には文字列Sを出力する
for i in S_dict:
print(S_dict[i],end="") Q個の操作をするときに、
入力された順番にやるとTLEになります。
この手の問題は、
操作をある程度まとめて一気にやることで、
解答することができます。
今回まとめる必要があるのは、
t=2の時と、t=3の時です。
Sの全ての文字を大文字⇔小文字に変換しなきゃいけないので、
最後に1回するだけで十分です。
ただ、t=1が入力された後に、t=2,3が入力されない場合は、
そのままcに変換されるので、注意が必要です。
流れとしては
①t=1の時、変更する
②t=2,3によって、大文字⇔小文字の変換をする
③残りのt=1の変更をする
この記事が気に入ったらサポートをしてみませんか？