AtCoderBeginnerContest167復習＆まとめ（前半）

AtCoder ABC167

2020-05-10(日)に行われたAtCoderBeginnerContest167の問題をA問題から順に考察も踏まえてまとめたものとなります．
前半ではABCDまでの問題を扱います．
問題は引用して記載していますが，詳しくはコンテストページの方で確認してください．
コンテストページはこちら
公式解説PDF

A問題　Registration

問題文
高橋君はとあるWebサービスに会員登録しようとしています。
まずIDを$S$として登録しようとしました。しかし、このIDは既に他のユーザーによって使用されていました。
そこで、高橋君は$S$の末尾に$1$文字追加した文字列をIDとして登録することを考えました。
高橋君は新しくIDを$T$として登録しようとしています。これが前述の条件を満たすか判定してください。

このあたりは，pythonであれば特に悩むことなく解けるかなと思います．
t[:-1]は，t[:len(t)-1]みたいに書いてもいいかなと思います．
どちらも文字列の一番後ろの一文字を除いた文字列を作ることができます．

• 例："takaito" → "takait"

abc167a.py

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

B問題　Easy Linear Programming

問題文
$1$が書かれたカードが$A$枚、$0$が書かれたカードが$B$枚、$−1$が書かれたカードが$C$枚あります。
これらのカードから、ちょうど$K$枚を選んで取るとき、取ったカードに書かれた数の和として、 ありうる値の最大値はいくつですか。

とりうる値を大きくするには，可能な限り，$1$がかかれたカードを選び，$-1$を極力選ばないようにする必要があることを考慮して，場合分けをしました．

• 選択しなくてはいけないカードの枚数が$A$枚以下であれば，全て$1$が書いてあるカードを選べばいいので，最大値は$K$になる．
• 選択しなくてはいけないカードの枚数が$A+B$枚以下であれば，$1$が書いてあるカードを全て選び，残りは$0$が書いてあるカードを選べばいいので，最大値は$A$になる．
• それ以上の枚数のカードを選択しなくてはいけない場合は，$-1$のカードを$K - (A + B)$枚を選ぶ必要があるため，$A - (K - (A + B))$が最大値になる．

あとはif文で条件分岐実装するだけです．

abc167b.py

a, b, c, k = map(int, input().split())
if a >= k:
    print(k)
elif a + b >= k:
    print(a)
else:
    print(a - (k - (a + b)))

B問題解けたのが開始6分程度だったので，このあたりまでは自分の理想とする時間で解けているかなと思っています．

C問題　Skill Up

問題文
競技プログラミングを始めた高橋くんは、学びたいアルゴリズムが$M$個あります。 最初、各アルゴリズムの理解度は$0$です。
高橋くんが書店に行くと、$N$冊の参考書が売っていました。$i$番目の参考書$(1 \leq i \leq N)$は$C_i$円で売られていて、購入して読むことで、各$j(1 \leq j \leq M)$について$j$番目のアルゴリズムの理解度が$A_{i,j}$上がります。また、それ以外の方法で理解度を上げることはできません。
高橋くんの目標は$M$個すべてのアルゴリズムの理解度を$X$以上にすることです。高橋くんが目標を達成することが可能か判定し、可能な場合は目標を達成するのに必要な金額の最小値を計算してください。

$1 \leq N,M \leq 12$と制約が小さい．
$N$冊の参考書の買い方は，「購入する」 or 「購入しない」の2択であり，全部で$2^N$通りなので，全探索で解けます．
自分は全探索するとき，再帰関数使うことが多いなと思いました．
他の"AC"出してる提出結果を見ると，意外にも再帰関数使ってないコードが多かったです．
再帰関数使って，どの本を買うのかを示すベクトル（例えば，$[1, 0, 1, 1]$）を作成し，計算はnumpyを使って，行列計算してみました．
提出したコードは各行の受け取りを，一度リストで受け取って，金額と理解度のリストに分けてましたが，Twitterで「こうやって受け取ることができるよ。c, *a = map(int, input().split())」と書いてあったのを参考に値の受け取りの部分だけ修正したものとなります．

abc167c.py

import numpy as np
def func(ans, b_list, a_list, c_list, k, x):
    if k == 0:
        b_list = np.asarray(b_list)
        x_list = np.dot(b_list, a_list)
        if np.all(x_list >= x):
            return np.inner(c_list, b_list)
        else:
            return ans
    ans = min(ans, func(ans, b_list + [1], a_list, c_list, k - 1, x))
    ans = min(ans, func(ans, b_list + [0], a_list, c_list, k - 1, x))
    return ans
n, m, x = map(int, input().split())
c_list = [] 
a_list = []
for i in range(0, n):
    c, *a = map(int, input().split())
    c_list.append(c)
    a_list.append(a)
ans = float("inf")
c_list = np.asarray(c_list)
a_list = np.asarray(a_list)
ans = min(ans, func(ans, [1], a_list, c_list, n - 1, x))
ans = min(ans, func(ans, [0], a_list, c_list, n - 1, x))
if ans == float("inf"):
    print(-1)
else:
    print(ans)

最近，全探索の問題解くのに苦戦してる気がする（汗）
全探索ってわかっても，実装までに時間がかかり過ぎてるから，スマートに書けるように演習していかないとな．

D問題　Teleporter

問題文
高橋王国には$N$個の町があります。町は$1$から$N$まで番号が振られています。
それぞれの町にはテレポーターが$1$台ずつ設置されています。町$i(1 \leq i \leq N)$のテレポーターの転送先は町$A_i$です。
高橋王は正の整数$K$が好きです。わがままな高橋王は、町$1$から出発してテレポーターをちょうど$K$回使うと、どの町に到着するかが知りたいです。
高橋王のために、これを求めるプログラムを作成してください。

個人的には，C問題よりも簡単に感じました．
特に，例題に救われた感が自分は強いです（ループすることにすぐに気が付いた）．

入力例２
6 727202214173249351
6 5 2 5 3 2

入力例2では，町$1$から出発して，
$1→6→2→5→3→2→5→3→...$
のように途中から，$2→5→3→2→5→3→...$と無限に町をループし始めることがわかります．
また，ループは一度訪れた町に，再び訪れることで確定するため，見つけるのも容易です．

～方針～

• 町を指示通り巡回し，訪れる町の順番をリストに追加しながら，同じ町に訪れるまで続ける．
• 同じ町に訪れたら，町$1$からループに入るまでのテレポート回数を数える．
• 回数$K$が，ループに入るよりも小さいなら，訪れる町の順番リストの$K$番目が答え．
• ループに入っているならば，「$K$」から「町$1$からループに入るまでのテレポート回数」を引いたものを，ループの長さで割った余りで，最終的にどの町に到着できるかわかる．

プログラミングのリスト（配列）は0から始まるので，そこだけ注意が必要だが，それに気を付ければ実装はそれほど難しくないと思って最初に提出したのが，以下のコードである．

abc167d.py

n, k = map(int, input().split())
x = list(map(int, input().split()))
count = 1
machi = 0
machi_list = [0]
next_machi = x[machi] - 1
while True:
    if next_machi in machi_list:
        break
    count += 1
    machi_list.append(next_machi)
    machi = next_machi
    next_machi = x[machi] - 1
z = 0
for i in range(0, count):
    if machi_list[i] == next_machi:
        z = i
        break
loop_machi_list = machi_list[z:]
if k < z:
    machi = machi_list[k] + 1
    print(machi)
else:
    k = k - z
    machi = loop_machi_list[k % len(loop_machi_list)] + 1
    print(machi)

しかし，上記のコードは実行時間が遅く，"TLE"出て絶望．
アルゴリズム間違ってるのかと思い，これよりも早くする方法あるのか？と困惑しました．
しかし，これ以上の方法思いつかなかったので，実装に問題がある気がして見直しました．

可能性として藁にもすがる思いで，疑ったのは，同じ町を再び訪れたかを確認するために，for文の中でif next_machi in machi_list:（リストの中に，同様の値があるか確認している）をやっている部分でした．
これが悪手だった．
配列大きくなったとき，全部調べるのが時間かかってそうと思い，すぐにdictを準備．
下記のようにコード書き直したら，無事"AC"通りました．

abc167d.py

n, k = map(int, input().split())
x = list(map(int, input().split()))
count = 1
machi = 0
machi_list = [0]
next_machi = x[machi] - 1
machi_dict = {}
while True:
    if next_machi in machi_dict:
        break
    count += 1
    machi_dict[next_machi] = 1
    machi_list.append(next_machi)
    machi = next_machi
    next_machi = x[machi] - 1
z = 0
for i in range(0, count):
    if machi_list[i] == next_machi:
        z = i
        break
loop_machi_list = machi_list[z:]
if k < z:
    machi = machi_list[k] + 1
    print(machi)
else:
    k = k - z
    machi = loop_machi_list[k % len(loop_machi_list)] + 1
    print(machi)

この"TLE"が，順位に響いてるので，仕事で今後python使うこと踏まえると最低限のこのあたりの実装力は，身に着けておきたいなと思いました．
競プロで身に着けたアルゴリズムとかは，自分が今後関わる仕事で，なくてもなんとかなりそうだけど，こういう細かい実装での重くなる例とかを経験できるのはとても勉強になってます(list関係とか特に)．

前半はここまでとなります．

D問題解き終わったときの瞬間的な順位は，かなり良かったのですが，その後がよくなかったので，もう少し勉強が必要ですね．
前半の最後まで読んでいただきありがとうございました．

後半はEF問題の解説となります．
後半に続く予定．