Xenous の精進記録

AtCoder関連他、学習したことの記録です。

ABC204 参加記録

  • 3完1ペナ 24分でした

A - Rock-paper-scissors

じゃんけんの値を調べて、同じならあいこを出し、異なるなら残り一つを出します。

x, y = map(int, input().split())
if x == y:
    print(x)
else:
    print(3-x-y)

B - Nuts

木の実を一つずつ確認して、問題文の通りに処理します。

N = int(input())
A = list(map(int, input().split()))
ans = 0
for a in A:
    if a > 10: ans += a - 10
print(ans)

C - Tour

各頂点から出発して、BFS を行って到達できる頂点を調べます。計算量は、BFS が  O(N+M) で、各頂点を巡るので  O(N(N+M)) となります。

C 問題 提出コード

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1; B -= 1
    graph[A].append(B)

ans = set([])
for i in range(N):
    fr = i
    que = deque([fr])
    goneset = set([fr])
    count = [-1] * N; count[fr] = 0
    while True:
        fr = que.popleft()
        for to in graph[fr]:
            if to in goneset:
                continue
            count[to] = count[fr] + 1
            que.append(to)
            goneset.add(to)
        if len(que) == 0:
            break
    for j, c in enumerate(count):
        if c != -1: ans.add((i, j))
print(len(ans))

D - Cooking

この DP が苦手すぎて、同じ問題を 3 度解けていません。。。(これ苦手なやつだ、となりそのまま終わってしまいました。)

最初に思いついた方針は嘘解法でした。

  •  A を大きい順(降順)に並べる。
  • それぞれのレンジの使用合計時間の短い方に入れる。同じ場合はレンジ1に入れる。

これは、以下のようなパターンで WA となります。

6
9 10 13 20 17 4

嘘解法では、「20、10、9」「17、13、4」が選択され、合計は 39 です。 一方、実際は「9、10、17」「20、13、4」で 37 が最短になります。

しかし嘘解法が正しいと思い込んでいる間は反例をなかなか作り出すことができず、この問題を後回しにしてしまいました。 反省として、全探索ができる範囲でテストケースをランダムに作成してテストすることにしました。

さて、嘘解法の反例が見つかったところで、正しい回答の方針です。まず片方のオーブンにかかる時間がわかれば、もう一方は自動的に定まります。 したがって、問題文を次のように言い換えるとわかりやすくなります。

  •  N 品の中からいくつかを選び、1つ目のオーブンで調理します。あり得る調理時間を全て洗い出してください。

洗い出した調理時間からもう一方も加味して、最短になるものを選べば良いです。

ここで、調理時間の候補が膨大だと成り立たないわけですが、問題文の制約で  N \leq 100 T_i \leq 10^{3} がわかっており、最大でも  10^{5} までの時間ということがわかります。したがって今回は可能な範囲です。

調理時間の候補を洗い出すには、以下のような遷移を考えます。

  •  10^{5} までの配列  \mathrm{DP} を用意する。中身の値について、候補の調理時間は 1 とし、それ以外を 0 とする。初期値として  \mathrm{DP}_0 = 1 を入れる。(何一つ選ばなかったときの調理時間は 0)
  •  N 品を順に見ていく。
    •  1 品目を選んだ場合、 \mathrm{DP}_{T_1} = 1 とできる。選ばない場合は  \mathrm{DP}_{0} = 1 のまま。
    •  2 品目は、配列上の候補の調理時間(2品目の場合  \mathrm{DP}_0 \mathrm{DP_{T_1}} )のそれぞれに対して、2品目を選んだ場合、選ばなかった場合を考える。
    • ... これを  N 品目まで繰り返す。

f:id:Xenous:20210613165829p:plain
DP 遷移のイメージ

 i 品目を選んでいるときは、 i-1 品目を選び終わった状態の DP を参照する必要があります。逆にいうとそれ以前の情報はもう使わないので、実装上は更新前と更新後の2種類を使い回していけば良いです。

最後に、各候補の値について、もう一方のレンジにかかる時間を出しておき、全て調理するまでの時間を計算した結果の最小値を答えとします。

計算量は  O(N^{2}T) です。大体  10^{7} くらいで、間に合います。

以下が参考コードです。

D 問題 提出コード

def main():
    N = int(input())
    T = list(map(int, input().split()))

    # 初期化
    DPbf = [0] * (1000*N+1)
    DPaf = [0] * (1000*N+1)

    # 初期値
    DPbf[0] = 1
    sumT = sum(T)

    # 遷移
    for i in range(N):
        for j, k in enumerate(DPbf):
            if k == 1: 
                DPaf[j] = 1
                DPaf[j+T[i]] = 1
        DPbf = DPaf.copy()
        DPaf = [0] * (1000*N+1)

    # 答え
    ans = float('inf')
    for k, flag in enumerate(DPbf):
        if flag == 1:
            ans = min(max(k, sumT-k), ans)
    print(ans)


if __name__ == "__main__":
    main()


さて、このD問題は bitset の考え方で実装することもできます。 先程の DP の遷移ですが、調理時間の候補になるかどうかを 0 と 1 で対応させたとき、DP は 二進数として見ることができます。 また、更新の動きをよく見ると、右シフト と OR 演算で更新できます。

f:id:Xenous:20210613222703p:plain
bitset の考え方イメージ

python3 では、整数 int多倍長整数なので、整数の値の大きさを特に気にすることなく実装できます。そのまま整数値と bit の状態を対応させます。

最大は 1<<(10**5) で、とてつもなく大きな数字ですが気にせず実装します。DP の解法よりはコードがシンプルになります。

D 問題 bitset の考え方に基づくコード

def main():
    N = int(input())
    T = list(map(int, input().split()))
    # 二進数表記で考える
    DP = 1 << (1000*N)
    sumT = sum(T)

    for i in range(N):
        # 右にシフトして OR をとる
        t = DP >> T[i]
        DP |= t

    # 答え
    ans = float('inf')
    cnt = 1 << (1000*N+1)
    for k in range(1000*N+1):
        cnt >>= 1
        if cnt & DP != 0:
            ans = min(max(k, sumT-k), ans)
    print(ans)


if __name__ == "__main__":
    main()

実行速度は以下のようになりました。(平均とかは取ってません。)

  • python 3.8.2 DP配列: 702ms
  • python 3.8.2 bitset: 488ms
  • pypy3 bitset: 458ms
  • pypy3 DP配列: 189ms

pypy だとリストへのアクセスが python に比べて超高速になるので、こちらの方が速くなっているようです。一方 bitset では大きな差にはなりませんでした。

E - Rush Hour 2

三分探索で実装しましたが、見事に穴にハマりました。

後々記載します。