[ABC308 Python]CodeQUEEN 2023 予選 (AtCoder Beginner Contest 308)
A問題
# 入力S
S = list(map(int, input().split()))
# Sが広義単調増加であるか確認
if sorted(S) != S:
print("No")
else:
# Sの全ての整数sについて
for s in S:
# 100以上675以下、25の倍数の条件を確認
if s < 100 or 675 < s or s%25 != 0:
print("No")
exit()
print("Yes")問題文のとおり、整数の配列Sについて、
3つの条件を確認していきます。
数列Sが広義単調増加であるかどうか→Sを昇順にsortしたものとSが等しければ、条件を満たします。
100以上675以下→条件を満たさない整数がなければ条件を満たします。
25の倍数→条件を満たさない整数がなければ条件を満たします。
B問題
# インポート
from collections import defaultdict
# 入力N,M
N, M = map(int, input().split())
# 入力C
C = list(input().split())
# 入力D
D = list(input().split())
# 入力P
P = list(map(int, input().split()))
# d[色] = 価格を表すdefaultdict
d = defaultdict(int)
# 全ての色について
for i in range(M):
# 色と価格を対応させる
d[D[i]] = P[i+1]
# 価格の合計を表す変数
ans = 0
# 髙橋君が食べた全ての料理について
for i in range(N):
# 料金表に載っていれば、その料金をansにプラス
if C[i] in d:
ans += d[C[i]]
else:
# 料金表に載っていなければ、P0が料金になる
ans += P[0]
print(ans)
最初にdefaultdictで料金表を作っておくと簡単に解けるかと思います。
料金表に載っていればその値段、載っていなければP0を価格の合計に足していくことで答えが求められます。
C問題
# インポート
from decimal import Decimal
from collections import defaultdict
# 入力N
N = int(input())
# d[成功率] = [その成功率の人の番号の集合]を表すdefaultdict
d = defaultdict(list)
# N人について
for i in range(N):
# 入力A,B
A, B = map(int, input().split())
# 成功率ごとに番号をまとめる
d[Decimal(A)/(Decimal(A)+Decimal(B))].append(i+1)
# 成功率に対して、降順にsort
sort = sorted(d.items(), key=lambda x:x[0], reverse=True)
# sortしたdefaultdictから、成功率ごとに番号を取得し
for success_rate, num_list in sort:
# 番号を昇順に並べ替え
num_list.sort()
for num in num_list:
# 一人ずつ空白区切りで出力する
print(num, end=" ")コンピュータでは10進数の小数を正確に表示することができないので、単純にA/A+Bをしてしまうと間違った答えになってしまいます。
Pythonでは以下のようなモジュールを使うと、小数まで正確に保存することができるので、今回は以下を使いました。
成功率ごとに番号をまとめ、
成功率は降順に、
成功率が等しい場合は番号を昇順に並べ替えることができます。
ただ、このプログラムはPython3ではACになりますが、
PyPy3ではTLEとなってしまいます。
原因はPyPyだとDecimalが遅くなってしまうからです。
以下の記事を参考にしました。
D問題
# インポート
from collections import deque
# 入力H,W
H, W = map(int, input().split())
# 入力S
S = [list(input()) for _ in range(H)]
# 訪れる予定の座標を表すdeque
d = deque()
# 最初は(0, 0)にいます
d.append((0, 0))
# 既に訪れた場所は2回以上いかないように保存しておく
visited = [[False for _ in range(W)] for _ in range(H)]
# 訪れる予定の場所がなくなるまで
while len(d) > 0:
# 次に訪れる場所を取得
now = d.pop()
# その場所のx座標
x = now[0]
# その場所のy座標
y = now[1]
# その場所にまだ訪れていなかったら
if not visited[x][y]:
# その場所を訪れたことにする
visited[x][y] = True
# 最終地点(H,W)に到着したらYesと出力
if x == H-1 and y == W-1:
print("Yes")
exit()
# 現在の場所に書かれた文字がsで
elif S[x][y] == "s":
# x方向に+1してもグリッドを超えなくて、
if x+1 <= H-1:
# 次の場所に書かれた文字がnだったら
if S[x+1][y] == "n":
# 次の訪れる場所としてdに追加する
d.append((x+1, y))
# y方向に+1してもグリッドを超えなくて、
if y+1 <= W-1:
# 次の場所に書かれた文字がnだったら
if S[x][y+1] == "n":
# 次の訪れる場所としてdに追加する
d.append((x, y+1))
# x方向に-1してもグリッドを超えなくて、
# 次の場所に書かれた文字がnだったら
if x-1 >= 0 and S[x-1][y] == "n":
# 次の訪れる場所としてdに追加する
d.append((x-1, y))
# y方向に-1してもグリッドを超えなくて、
# 次の場所に書かれた文字がnだったら
if y-1 >= 0 and S[x][y-1] == "n":
# 次の訪れる場所としてdに追加する
d.append((x, y-1))
# 以下n,u,k,eについても同様に行う
elif S[x][y] == "n":
if x+1 <= H-1 :
if S[x+1][y] == "u":
d.append((x+1, y))
if y+1 <= W-1 :
if S[x][y+1] == "u":
d.append((x, y+1))
if x-1 >= 0 and S[x-1][y] == "u":
d.append((x-1, y))
if y-1 >= 0 and S[x][y-1] == "u":
d.append((x, y-1))
elif S[x][y] == "u":
if x+1 <= H-1 :
if S[x+1][y] == "k":
d.append((x+1, y))
if y+1 <= W-1 :
if S[x][y+1] == "k":
d.append((x, y+1))
if x-1 >= 0 and S[x-1][y] == "k":
d.append((x-1, y))
if y-1 >= 0 and S[x][y-1] == "k":
d.append((x, y-1))
elif S[x][y] == "k":
if x+1 <= H-1 :
if S[x+1][y] == "e":
d.append((x+1, y))
if y+1 <= W-1 :
if S[x][y+1] == "e":
d.append((x, y+1))
if x-1 >= 0 and S[x-1][y] == "e":
d.append((x-1, y))
if y-1 >= 0 and S[x][y-1] == "e":
d.append((x, y-1))
elif S[x][y] == "e":
if x+1 <= H-1:
if S[x+1][y] == "s":
d.append((x+1, y))
if y+1 <= W-1 :
if S[x][y+1] == "s":
d.append((x, y+1))
if x-1 >= 0 and S[x-1][y] == "s":
d.append((x-1, y))
if y-1 >= 0 and S[x][y-1] == "s":
d.append((x, y-1))
# 訪れる予定の場所がなくなり、最終地点にたどり着いてなければ、
# Noと出力する
print("No") DFSやBFSを使用して、解いていきます。
辺で隣接するマスのみ移動可能なので、
上下左右のみしか移動することができません。
また、グリッドの端にいた場合は、
移動ができない方向があります。
すぬけ君が移動しようと思っているマスが、
グリッドをはみ出していないか、
s→n→u→k→e→s…..の条件を守っているかを、
移動ごとに確認しながら最終地点までたどり着くことができるか確認しましょう。
この記事が気に入ったらサポートをしてみませんか？