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問解きのような、なにかの参考になれば幸いです。

＜参考文献＞

続きはこちら