ABC167 復習

ABC AtCoder

はい、今回もCまで解けました。（Bで2WAが辛い）
というわけで復習です。

atcoder.jp

A - Registration

A問題は、2つの文字列比較をする問題でした。
1つ目の文字列と、2つ目の文字列の末尾を除いた部分が一致しているかを判定します。
pythonだと以下のように書けます。

s = input()
t = input()

if s == t[:-1]:
    print('Yes')
else:
    print('No')

B - Easy Linear Programming

冒頭でも書きましたが、まさかの2WAとなってしまいました。
1点がA枚なので、最大でもA点（A>=K の時か A + B >= K）。 A+B枚がK未満なら、残った枚数だけ引きます。

a, b, c, k = map(int, input().split())

ans = 0
if a >= k:
    ans = k
elif a + b >= k:
    ans = a
else:
    ans = a - (k - (a + b))

print(ans)

C - Skill Up

bit全探索ですね。
Nが12以下なので、すべての本に対して買うかどうかを調査することで、答えが求まります。
具体的には、2Nのパターンをすべて列挙して、合計金額と理解度の両方を計算します。
ちなみに、bit全探索であることはわかったのですが、シフト演算がうまくできなかったため2進表記を文字列であらわしています。（このあたりは要勉強）

n, m, x = map(int, input().split())

costs = []
a = []
ans = 10 ** 9

for i in range(n):
    c, *j = map(int, input().split())
    costs.append(c)
    a.append(j)

for y in range(2 ** n):
    # 合計金額
    total = 0
    # 理解度（はじめはすべて0）
    b = [0] * m
    #パターンについて、2進数表記の文字列にする
    bi = '{:b}'.format(y).zfill(n)
    for i in range(n):
        #2進表記で1の部分の本を買う
        if bi[i] == '1':
            total += costs[i]
            r = a[i]
            for j in range(m):
                b[j] += r[j]
    if all([k >= x for k in b]):
        ans = min(ans, total)

if ans == 10 ** 9:
    ans = -1
print(ans)

D - Teleporter

考え方としては、ループ（サイクル）が起こる個所を発見することが第一目標ですね。
周期さえ見つかってしまえば、K回の移動も剰余を見つけてしまうことでK回の移動をしなくとも済みます。
と、ここまではコンテスト中にも想定できたのですが、うまくコードに落とし込むことができませんでした。

また今度やる。