ABC185 C - Duodecim Ferra
タイプ
- comb()（組み合わせ）
解説
組み合わせの問題。
例えば、oooooooooooooo（oは整数）という並びがあったら、oとの間にかぶらないように11本の仕切りをおいて分割すれば求められる。したがって、(L-1) C 11の計算をcomb()で行えば良い。
回答例
# comb()
from math import comb
L = int(input())
num = L - 12
ans = comb(num + 11, 11)
print(ans)
ABC186 C - Unlucky 7
タイプ
- oct()
- in str()
解説
問題文の通り、「1以上N以下の整数のうち、10進法で表しても8進法で表しても7を含まないような数はいくつありますか？」。
文字列の中にある文字が含まれているという書き方は、探したい文字列をa、検証する文字列をbとすると、a in str(b)とかける。8進数はoct()でわかるので、これについて7を含んでいるものを数え上げ、全体Nから引くと、値が求められる。
回答例
# oct(), in str()
N = int(input())
cnt = 0
for i in range(1, N+1):
if '7' in str(i) or '7' in str(oct(i)):
cnt += 1
print(N - cnt)
ABC187 C - 1-SAT
タイプ
- set()
解説
問題文に忠実に従えば解ける問題。
要約すると、**文字列Sのなかに、頭に!がついた文字と!がついていない文字がどちらも存在したとき、ついていない方を出力する。**という問題。
Sは重複なしでいいので、set()で文字を保存。これを一文字ずつループに入れていき、頭に!がついた文字があれば、ついていないものをprint()してexit()。何もなければ、'satisfiable'を出力。
回答例
# set()
N = int(input())
S = set(input() for _ in range(N))
for s in S:
if '!' + s in S:
print(s)
exit()
print('satisfiable')
ABC188 C - ABC Tournament
タイプ
- while
- （両端キュー）
解説
難しそうに書いてあるが、要は「トーナメントの準優勝の選手番号を出力してね」という問題。
今回は制約が緩いので、書いてあるとおりにやれば、ACできる問題。
トーナメントなので、2つずつ値を見ていく。for i in range(len(result) // 2):で、リストの半分の数だけループを回す。$2_i$番目と$2_i+1$番目を比べて、値が高い方をリストansに追加。これをもう一度resultに入れ直して、再度ループを回す。決勝戦であるlen(result) == 2のときにbreak。準優勝者の値をdataに参照し、index番号をとってくる。
また、両端キューでの実装も可能。
回答例
whileで実装
# while
N = int(input())
data = list(map(int, input().split()))
result = data
while True:
if len(result) == 2:
break
ans = []
for i in range(len(result) // 2):
test = max(result[2*i], result[2*i+1])
ans.append(test)
result = ans
print(data.index(min(result))+1)
両端キューで実装
# 両端キュー
from collections import deque
N = int(input())
A = [-1] + [*map(int, input().split())]
stay = deque(range(1, 2 ** N + 1))
for _ in range(N-1):
win = deque()
while stay:
left = stay.popleft()
right = stay.popleft()
if A[left] > A[right]:
win.append(left)
else:
win.append(right)
stay = win
left = stay.popleft()
right = stay.popleft()
if A[left] > A[right]:
print(right)
else:
print(left)
ABC189 C - Mandarin Orange
タイプ
- 全探索
- （PyPyで実行）
解説
問題文を要約すると、**連続した皿から取れるみかんの合計の最大値はいくつですか、**ということ。
コードを上から順番に見ていこう。
まず、左端lを固定して、forで1ずつずらせるようにする。今回、条件が$l \leq r \leq N$となっているので、次のforはlからNまでとする。
これらlからrの区間の最小値（みかんが取れる最小の数）を求め、max()で値が大きいものを保存していくというコードとなっている。
なお、このコードはPythonで実行してもTLEしてしまい通らない。したがって、実行速度の早いPyPyで提出する必要がある。（これがPythonのデメリット）
回答例
# 全探索（PyPyで実行）
N = int(input())
A = [*map(int, input().split())]
ans = 0
# 左端をlで固定
# +1ずつ右にシフト
for l in range(N):
init = 10 ** 6 # init > 10^5で初期化
# l <= r <= Nを満たすようにループ
for r in range(l, N):
d = r - l + 1 # l-rの区間
init = min(init, A[r]) # l-rの最小値
score = init * d # 最小のみかんの数、l-r区間の皿から取る
ans = max(ans, score) # 比較して多い方を取る
print(ans)
編集後記
185-189はそんなに難しくなかったという感覚。
「公式解説を見ても解説になっていない！」と思って始めました。
C100問解きのような、なにかの参考になれば幸いです。
＜参考文献＞
続きはこちら