Xenous の精進記録

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

ABC209 参加記録

  • 4完1ペナ 22分でした

A - Counting

 A \leq B のとき、答えは  B-A+1 個です。問題文の制約を見ると  A > B の場合も普通にあるのでそのときだけ気をつけます。(ここで 1ペナもらいました。勿体無い。。)

A, B = map(int, input().split())
if A <= B: print(B-A+1)
else: print(0)

B - Can you buy them all?

 N \leq 100 なので、純粋に一個一個代金を足し合わせて、最後に所持金  X と比較すれば間に合います。

N, X = map(int, input().split())
A = list(map(int, input().split()))
res = 0
for i in range(N): res += (i%2 == 0) * A[i] + (i%2 == 1) * (A[i] - 1)
if res <= X: print('Yes')
else: print('No') 

C - Not Equal

そのままやろうとすると調べ上げるのに時間がかかってしまいます。

まず、この問題の条件を調べ上げるにあたって、 C の順番は特に関係ないことがわかります。 次に、一度使った数字が使えないことから、 C_i が大きいときよりも、小さいときの方が使える候補が少なく、強い制約であることがわかります。

数え上げでは、強い制約から考えていくとうまくいく場合があります。今回の問題は C を小さい順に並べてから使って良い数字をカウントしていくと、場合分けなどせずに数え上げることができます。

MOD = pow(10,9)+7

N = int(input())
C = list(map(int, input().split()))
C.sort()

cnt = 0
ans = 1
for c in C:
    ans *= c - cnt
    if c - cnt == 0:
        print(0)
        return
    ans %= MOD
    cnt += 1
print(ans)

D - Collision

道路の長さが同じということから、街どうしを結ぶ最短経路の道路の本数が偶数なら街で出会い、奇数なら道路で出会います。 与えられるグラフは木になっているので、適当な頂点から BFS などで距離を求めて、高橋くん、青木くんの出発点の値の偶奇が一致しているかどうかで判定することができます。

提出コード

from collections import deque
import sys

input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    graph = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        a -= 1; b -= 1
        graph[a].append(b)
        graph[b].append(a)
    
    # BFS
    fr = 0
    que = deque([fr])
    goneset = set([fr])
    count = [0] * N
    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 _ in range(Q):
        c, d = map(int, input().split())
        c -= 1; d -= 1
        if count[c]%2 == count[d]%2: print('Town')
        else: print('Road')


if __name__ == "__main__":
    main()

E - Shiritori

本番では、先頭3文字と末尾3文字を有向グラフで表し、巡回部分を DRAW で固定した後、そうでないところに対して DFS を行い末尾から、「この頂点から始まった場合の勝ち負け」を判定をしていくことをしました。しかし WATLE どちらもとれず、、後々考えると巡回部分の DRAW や勝ち負けを記入する際のルールが一部間違っており、考察不足でした。。

まず、この問題では、しりとりで使う単語の先頭3文字と後ろ3文字で有向グラフを使うと見通しが良くなります。例えば、有向グラフにおいて、行き先がなければ次の単語が言えず「負け」です。逆に、「負け」に矢印が出ている頂点は「勝ち」です。単語の中から「負け」になる末尾3文字の単語を言えば勝ちになります。(下図の例で、ghi の始まりの単語がないので負け。def 始まりで、defghi を言えば、相手を負けにできるので勝ち。)

f:id:Xenous:20210718152323p:plain
グラフ化の例

有向グラフをプログラム上で扱うときは、3文字の英字と頂点番号を対応させておくと良いです。今回は出てきた3文字順に0から順番に数字を振っていくようにしました。

3文字の英字と頂点番号を対応づけさせるコード例

strings = dict() # 3文字の単語と頂点番号を対応させる辞書
for _ in range(N):
    s = input()[:-1]
    bfs = s[:3]; afs = s[len(s)-3:]
    if bfs not in strings:
        strings[bfs] = cnt
        cnt += 1
    if afs not in strings:
        strings[afs] = cnt
        cnt += 1

さて、ゲームの問題では、後ろから勝ち負けを判定していくのがセオリーです。先程の例のように、「負け」の頂点へ有向辺が出ていれば「勝ち」というようなルールを整理します。頂点の次数を「その頂点から出ている有向辺の数」とし、勝ち負けが確定した頂点への有向辺を削除する(次数を減らす)操作をしていくと、以下のように考えることができます。

  • 次数が 0 である頂点は「負け」
  • 「負け」に移動できる頂点は「勝ち」
  • 「負け」に移動できない頂点で、次数が 0 となった頂点は「負け」。

最後の条件について考えます。次数が 0 でないときは、「負け」には移動できないが、「勝ち」以外の頂点へ移動できることになります。これが引き分け状態となります。次数が 0 のときは、行き先が全て確定していて、それが「勝ち」であるパターンしか残りません。したがって「負け」で確定します。

以上より、各頂点の状態の更新が止まったら、「勝ち」「負け」、そして勝ちでも負けでもない「引き分け」と割り振れば良いです。

実装では、次数が 0 の方から探索するので逆向きのグラフにしています。

提出コード

from collections import deque
import sys

sys.setrecursionlimit(10**7)
input = sys.stdin.readline

def main():
    N = int(input())
    slist = []; strings = dict(); cnt = 0
    # 次数 d_out: 出ていく辺の本数で定義
    for _ in range(N):
        s = input()[:-1]
        bfs = s[:3]; afs = s[len(s)-3:]
        if bfs not in strings:
            strings[bfs] = cnt
            cnt += 1
        if afs not in strings:
            strings[afs] = cnt
            cnt += 1
        slist.append(s)
    
    graph_reverse = [[] for _ in range(cnt)]
    d_out = [0] * cnt
    for s in slist:
        bfs = s[:3]; afs = s[len(s)-3:]
        graph_reverse[strings[afs]].append(strings[bfs])
        d_out[strings[bfs]] += 1
    
    ans = ['*'] * cnt
    que = deque([])
    for i, x in enumerate(d_out):
        if x == 0:
            que.append(i)
            ans[i] = 'L'

    n = 0
    while que:
        # 次数が 0 のところからスタート
        # 操作
        #   行き先の状態が確定していたらスキップ
        #   次数を減らす
        #   Lose から伸びている辺は Win を書く
        #   Lose から伸びておらず、次数が 0 なら Lose を書く
        fr = que.popleft()
        for to in graph_reverse[fr]:
            if ans[to] != '*': continue
            d_out[to] -= 1
            if ans[fr] == 'L':
                ans[to] = 'W'
                que.append(to)
            elif d_out[to] == 0:
                ans[to] = 'L'
                que.append(to)

    # Win Lose 判定
    for s in slist:
        bfs = s[:3]; afs = s[len(s)-3:]
        res = ans[strings[afs]]
        if res == 'L': print('Takahashi')
        elif res == 'W': print('Aoki')
        else: print('Draw')


if __name__ == "__main__":
    main()

ABC208 参加記録

  • 3完0ペナ 25分でした

A - Rolling Dice

最も小さい数 1 で合計した場合と、最も大きい数 6 で合計した場合を考えれば良さそうです。その間の数は 1 から 6 を自由に使えるのでいくらでも作れます。

よって、 1\times A \leq B \leq 6\times A が成り立てば Yes、そうでないなら No です。

A, B = map(int, input().split())
if 1*A <= B <= 6*A: print('Yes')
else: print('No')

B - Factorial Yen Coin

この問題の貨幣の単位である  x ! 円は、 x! + (x+1)! > (x+2)! が成り立つことはないので、大きい方から単純に払っておけば良いです。これが成り立つ場合は DP で遷移を考える必要があります( (x+2)! 円よりも  x! + (x+1)! 円で払った方が結果的に枚数が少なくなる場合が出てくる)。

ゆえに、大きい方から商を答えに加算し、余りを次の  P 使って計算してけば、最小枚数を計算できます。 最大枚数が 100 枚しかないので、その処理も追加しておけば問題ないと思います。

P = int(input())
S = [1]
for n in range(2, 11):
    S.append(S[-1] * n)

S.reverse()
ans = 0
while P > 0:
    for s in S:
        tmp = P//s
        if tmp > 100: 
            ans += 100
            P -= 100*s
        else:
            ans += tmp
            P = P%s
print(ans)

C - Fair Candy Distribution

まずは  K \geq N であれば、全員に同じ個数のお菓子を配れるので配ってしまいます。 余りは、番号の小さい順に足していきます。python でやる際はソートする列の位置を次のように指定できます。例えば2列目をキーにしてソートする場合は list.sort(key=lambda x: x[1]) とかけます。

 A のインデックスと番号を持つリストに直して、番号でソートした後にお菓子を配り、出力時にはインデックスでソートして元の並び順に戻します。

N, K = map(int, input().split())
A = [(i, a) for i, a in enumerate(map(int, input().split()))]
A.sort(key=lambda x: x[1])
tmp = K//N
K %= N
ans = []
for i, _ in A:
    if K > 0:
        ans.append((i, tmp+1))
        K -= 1
    else:
        ans.append((i, tmp))
ans.sort(key=lambda x: x[0])
for _, x in ans:
    print(x)

D - Shortest Path Queries 2

本番ではダイクストラで実装しました。ダイクストラだと計算量が  O(N^{2}(N+M)\log{N}) となりますが、今回の制約だと  O(N^{3}) 6.4 \times 10^{7} くらいになり、この時点で厳しいです。特に  (N+M) の部分を失念しており、最悪は  M の制約が  M \leq N(N-1)/2 であることから、 O(N^{4}\log{N}) となります。

ちなみにダイクストラでの方針は、まずはスタートの頂点を固定(ここで  O(N))して、次に  k の値を動かすようにしました。 k が増えていくごとに移動可能な頂点からの道を追加し、移動可能になった頂点をキューに入れてそこからダイクストラする、という風にしました。しかし辺が多いパターンでは計算量からして間に合わず、やはり TLE になります。

実際は、ワーシャルフロイド法を使って  O(N^{3}) でできます。

私の中でワーシャルフロイド法は、書く手順だけ覚えて中身を理解できていないもの代表になっていました。 まずはコードですが、要素がコストである隣接行列 g を使って以下のように書けます。

for k in range(N):
    for i in range(N):
        for j in range(N):
            g[i][j] = min(g[i][k] + g[k][j], g[i][j])

さて、この問題の状況で考えてみます。まずは、 k = 0 の場合です。スタートの頂点とゴールの頂点のみで到達できるかどうかを見ます。その際は g[i][j] を見れば良いです。

次に、 k = 1 の場合を考えます。頂点  1 を通る場合と通らない場合では、以下のように書けます。

  •  k = 1 で固定して、g[i][k] + g[k][j]g[i][j] を比較する。比較した値を隣接行列に反映する。

次に、 k = 2 の場合を考えます。同じく頂点  1 2 を通る場合と通らない場合を考えますが、上記で  1 を通った場合と通らない場合を調べた結果が反映されているので、頂点  2 についても同様に

  •  k = 2 で固定して、g[i][k] + g[k][j]g[i][j] を比較する。比較した値を隣接行列に反映する。

となります。これを続けていくと、結果ワーシャルフロイドの実装方法と同じになります。

初期化する際、辿り着かない値を大きな値にするのですが、float('inf') を使った場合なんと TLE になりました。 int 型と float 型を混ぜると幾分か低速になるようです。

提出コード

import sys

input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    graph = [[10**12]*N for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        A -= 1; B -= 1
        graph[A][B] = C
    
    for i in range(N):
        graph[i][i] = 0
    
    ans = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                tmp = min(graph[i][j], graph[i][k] + graph[k][j])
                if tmp < 10**12: ans += tmp
                graph[i][j] = tmp
    print(ans)


if __name__ == "__main__":
    main()

E - Digit Products

これは桁DP だな、、と思いましたが EDPC の桁DP がまだ理解できていなかったので諦めました。EDPC 履修後にやります。

F - Cumulative Sum

やれたらやります。

ABC207 参加記録

  • 3完0ペナ 22分でした
  • また3完だ... と思ったら DEFが最高に難しい回だったので仕方がない感じでした。

A - Repression

探索させても良いですし、ソートして大きいもの2つを取る、でも良いと思います。下記の実装は後者です。

X = list(map(int, input().split()))
X.sort()
ans = X[-1] + X[-2]
print(ans)

B - Hydrate

式に落とすと以下になります。

  •  A + kB \leq kC \times D を満たす最小の0以上の整数  k を見つける。

式変形すると  A \leq k(C\times D -B) になります。  A は制約上  10^{5} までしかとらないため、 k の最大も  A 程度になります。

したがって この式を直接  k でループさせて調べることができて、越えればその  k の値ですし、超えないなら -1 です。

A, B, C, D = map(int, input().split())
for i in range(10**7):
    if A + i*B <= D*i*C:
        print(i)
        return
print(-1)

C - Many Segments

区間を左から順に舐めとっていこうとすると混乱します。今回の問題は単純に全ての区間から2つを選ぶ全探索が  O(N^{2}) で回るので、こちらの方針で実装します。

区間の重なりについては以下のように判定します。

区間  i区間  j を取ります。それぞれを比較したとき、左端  l の値が小さい方を  i と改めておきます。 そうしたとき、区間  i の右端  r_i区間  j の左端  l_j で以下のような場合があります。

f:id:Xenous:20210626230401p:plain
区間の場合分けイメージ

区間の持ち方でパターン (i)、(ii)、(iii) に分かれ、右端と左端の関係を図のように確認し、満たすのであれば重なりがあるとしてカウントします。 以上で各区間の重なりを見ることができました。

N = int(input())
sector = []
for _ in range(N):
    t, l, r = map(int, input().split())
    sector.append((t, l, r))

ans = 0
for i in range(N):
    for j in range(i+1, N):
        ti, li, ri = sector[i]
        tj, lj, rj = sector[j]
        if li > lj:
            ti, tj = tj ,ti
            li, lj = lj, li
            ri, rj = rj, ri
        
        if ti == 2 or ti == 4:
            if lj < ri: ans += 1
        elif (ti == 1 or ti == 3) and (tj == 1 or tj == 2):
            if lj <= ri: ans += 1
        else:
            if lj < ri: ans += 1
print(ans)

D - Congruence Points

本番では重心で考える方法を思いつきはしましたが、小数の扱いになるとミスしやすいのでその方法は諦め、原点に戻す点( S T を一致させるための基準点)を全探索する方針にしました。しかし、公式解説にもありますが、重心は各点を  N 倍しておけば整数のまま扱えます。

また、整数点を回転させて整数点になるのは 90 度回転だけでは?ということを本番中否定できなかったのも反省です。これは 例えば以下のようなパターンで否定できます。三平方の定理で斜めの線分の長さが整数になるパターンです。

f:id:Xenous:20210628202134p:plain
90度回転以外の場合

ということで、角度は確定でなく探索する必要があります。しかし実数なので全探索はできません。

全体の方針としては、以下の流れで回転を調べます。

  1.  S T の重心をそれぞれ求める(各入力の点を  N 倍しておき、重心を整数で扱えるようにする)
  2.  S T の重心をそれぞれ原点へ移動させる。
  3.  S から 1 点、 T から 1 点選び、それらを重ねるように、  S の点に対する原点を中心とした回転角を求める。
  4. 求めた回転角で実際に  S を回転させて、 T と一致するか確かめる。
  5. どこかで一致したら Yes 。全部調べて一致しなかったら No とする

以下、この方針に沿って実装したコードを見ていきます。

1  S T の重心をそれぞれ求める(各入力の点を  N 倍しておき、重心を整数で扱えるようにする)

書いてあるとおり、入力時点で  N 倍します。その座標を使って重心を求めれば必ず整数になります。(なので小数点切り捨てでの割り算をしています)

N = int(input())
S = []; T = []
Sgx, Sgy = 0, 0
for _ in range(N):
    a, b = map(int, input().split())
    S.append((a*N, b*N))
    Sgx += a*N; Sgy += b*N
Sg = (Sgx//N, Sgy//N)

Tgx, Tgy = 0, 0
for _ in range(N):
    c, d = map(int, input().split())
    T.append((c*N, d*N))
    Tgx += c*N; Tgy += d*N
Tg = (Tgx//N, Tgy//N)

2  S T の重心をそれぞれ原点へ移動させる。

平行移動させるだけなので、それぞれの重心の座標を  S  T の集合から引いていくだけで良いです。

# 重心で重ねる
nS = []; Sgx, Sgy = Sg
for x, y in S:
    nS.append((x-Sgx, y-Sgy))

nT = set([]); Tgx, Tgy = Tg
for x, y in T:
    nT.add((x-Tgx, y-Tgy))

3  S から 1 点、 T から 1 点選び、それらを重ねるように、  S の点に対する原点を中心とした回転角を求める。

原点に移動させた  S の点と  T の点でループさせて、回転角を求めます。 回転角は  S の点の角度と、 T の点の角度をそれぞれ出して差を求めています。

# 一致させる点を探索する
for a, b in nS:
    for c, d in nT:
        # 回転角を求める
        stheta = theta(a, b, positive=True)
        ttheta = theta(c, d, positive=True)
        psi = ttheta - stheta
# x 軸からの回転角を求める関数
def theta(x:float, y:float, positive = False) -> float:
    if x == 0 and y == 0: return 0
    value = sqrt(x**2 / (x**2 + y**2)) * (1*(x >= 0) - 1*(x < 0))
    sign = 1 * (y >= 0) - 1 * (y < 0)
    res = acos(value) * sign
    if positive:
        res += 2*pi*(sign < 0)
    return res

求めた回転角で実際に  S を回転させて、 T と一致するか確かめる。

上の for 文の中で書きます。 回転行列の式を使って各点を原点を中心とした回転をさせます。このとき誤差が生じますが、整数点との差分がとても小さいなら、格子点上にあるとみなします。

# 点を丸める
err = 0.0000001

nnS = []
for x, y in nS:
    x, y = route(x, y, psi)
    rx, ry = round(x), round(y)
    if abs(x-rx) <= err and abs(y-ry) <= err:
        nnS.append((rx, ry))

# 整数点であることを確かめる
if len(nnS) != len(nT): continue

# 一致するか確かめる
if check(nnS, nT):
    print('Yes')
    return
# T に一致するか確かめるための関数
def check(s:list, t:set) -> bool:
    for x,y in s:
        if (x, y) not in t:
            return False
    return True

# 原点中心の回転を行う関数
def route(x:int, y:int, theta:float) -> tuple:
    return (x*cos(theta) - y*sin(theta), x*sin(theta) + y*cos(theta))

どこかで一致したら Yes 。全部調べて一致しなかったら No とする

回し切って、Yes にならなかったら No です。

以上です。計算量は  O(N^{3}) です。偏角ソートなどを使えば  O(N^{2}\log{N}) くらいになります。

提出コード

import sys
from math import cos, sin, sqrt, acos, pi

input = sys.stdin.readline
err = 0.0000001

def check(s:list, t:set) -> bool:
    for x,y in s:
        if (x, y) not in t:
            return False
    return True


def route(x:int, y:int, theta:float) -> tuple:
    return (x*cos(theta) - y*sin(theta), x*sin(theta) + y*cos(theta))


def theta(x:float, y:float, positive = False) -> float:
    """
    点(x, y) と x 軸との角度 theta を求める.

        Peremeters:
        -----------
        x, y: float
            点(x, y) の座標.
        positive: bool
            返却値を 0 <= theta < 2*pi の範囲にする
        
        Returns:
        --------
        theta: float
            点(x, y)とx軸との角度 theta
            positive が False であれば -pi/2 < theta <= pi/2 の範囲で返す
            positive が True であれば 0 <= theta < 2*pi の範囲で返す
            点(0, 0) の場合は 0 を返す
    """
    if x == 0 and y == 0: return 0
    value = sqrt(x**2 / (x**2 + y**2)) * (1*(x >= 0) - 1*(x < 0))
    sign = 1 * (y >= 0) - 1 * (y < 0)
    res = acos(value) * sign
    if positive:
        res += 2*pi*(sign < 0)
    return res


def main():
    N = int(input())
    S = []; T = []
    Sgx, Sgy = 0, 0
    for _ in range(N):
        a, b = map(int, input().split())
        S.append((a*N, b*N))
        Sgx += a*N; Sgy += b*N
    Sg = (Sgx//N, Sgy//N)

    Tgx, Tgy = 0, 0
    for _ in range(N):
        c, d = map(int, input().split())
        T.append((c*N, d*N))
        Tgx += c*N; Tgy += d*N
    Tg = (Tgx//N, Tgy//N)

    # 重心で重ねる
    nS = []; Sgx, Sgy = Sg
    for x, y in S:
        nS.append((x-Sgx, y-Sgy))

    nT = set([]); Tgx, Tgy = Tg
    for x, y in T:
        nT.add((x-Tgx, y-Tgy))

    # 一致させる点を探索する
    for a, b in nS:
        for c, d in nT:
            # 回転角を求める
            stheta = theta(a, b, positive=True)
            ttheta = theta(c, d, positive=True)
            psi = ttheta - stheta

            # 点を丸める
            nnS = []
            for x, y in nS:
                x, y = route(x, y, psi)
                rx, ry = round(x), round(y)
                if abs(x-rx) <= err and abs(y-ry) <= err:
                    nnS.append((rx, ry))
            
            # 整数点であることを確かめる
            if len(nnS) != len(nT): continue

            # 一致するか確かめる
            if check(nnS, nT):
                print('Yes')
                return
    print('No')    

if __name__ == "__main__":
    main()

E - Mod i

後ほど書きます。

F - Tree Patrolling

後ほど書きます。

バーチャル参加 ABC126

  • 全完1ペナ 65分でした

A - Changing a Character

小文字に置き換えるのは python であれば s を文字列型として s.lower() でできます。 該当箇所のみ lower を使って、それ以外はそのまま表示させるようにします。

N, K = map(int, input().split())
S = input()
print(S[:K-1] + S[K-1].lower() + S[K:])

B - YYMM or MMYY

MM として表示できるのは  1 \leq \mathrm{MM} \leq 12 になります。この範囲内であれば、MM と言えます。そうでない場合は YY です。 MMMM となる場合は AMBIGUOUS となります。片方 MM のパターンはそのままで、それ以外は全て NA です。

S = input()
bf = S[:2]; af = S[2:]
if 1 <= int(bf) <= 12: bf_flag = True
else: bf_flag = False

if 1 <= int(af) <= 12: af_flag = True
else: af_flag = False

if bf_flag and af_flag: print('AMBIGUOUS')
elif bf_flag and not af_flag: print('MMYY')
elif not bf_flag and af_flag: print('YYMM')
else: print('NA')

C - Dice and Coin

1回目の出た目の数によって、何回あと表出し続けないといけないかが変わるのでそれごとに計算します。

1回目は  1 から  N まで等確率で目が出るので、確率は  \frac{1}N 。1回目に出た値を  a とおくと、そのあとの確率は、表を連続して出す確率なので、  \left(\frac12\right)^{j} k a \times 2^{j} \geq K を満たす最小の整数)と表せます。

これを  1 から  N までのパターン全て計算して足し合わせれば良いです。

N, K = map(int, input().split())
p0 = 1/N; ans = 0.0
for score in range(1, N+1):
    cnt = 0
    while score < K:
        score *= 2
        cnt += 1
    ans += p0 / (2 ** cnt)
print(ans)

D - Even Relation

同じ色に塗られた任意の  2 頂点について、その距離が偶数である。

色が先で、その後距離を見ると、頂点どうしの距離が偶数である、という確認の順番です。

思いつきで、根を黒で借り決めして、距離が偶数であるときは親と同じ色、距離が奇数であるときは親と異なる色、とすると、塗り分けが可能で、問題文の状態を満たすことができます。

提出コード

from collections import deque

N = int(input())
graph = [[] for _ in range(N)]
for _ in range(N-1):
    u, v, w = map(int, input().split())
    u -= 1; v -= 1
    graph[u].append((v, w))
    graph[v].append((u, w))

fr = 0
que = deque([fr])
goneset = set([fr])
ans = [-1] * N; ans[fr] = 0
while True:
    fr = que.popleft()
    for to, w in graph[fr]:
        if to in goneset:
            continue
        if w%2 == 0: ans[to] = ans[fr]
        else: ans[to] = (ans[fr]+1)%2
        que.append(to)
        goneset.add(to)
    if len(que) == 0:
        break
print(*ans, sep='\n')

E - 1 or 2

 A_{X_i} + A_{Y_i} + Z_i が偶数」の情報だけだと  A_{X_i} A_{Y_i} の偶奇を確定できません。このうち片方が分かれば両方を特定できます。この場合はコスト1を使う必要があります。

また、上で明らかになった  A_{k} の情報が、他の  A_{X_j} + A_{Y_j} + Z_j で使えれば、コストを払う必要がありません。

したがって、コスト 1 払ったときに連鎖的にわかる範囲が管理できていればよく、UnionFind を使って実装できます。

提出コード

class UnionFind():
    """
    unionfind を扱うクラス (0-index)

        Parameters:
        -----------
        n: int
            管理するデータの要素数
    """
    def __init__(self, n:int):
        """
        Parameters:
        -----------
        n: int
            要素数
        parents: list
            各要素が属する親の要素番号
        grouping: set
            親番号の集合
        rank: list
            親の rank を保持するためのリスト
        size: list
            親の size を保持するためのリスト
        """
        self.n = n
        self.parents = [-1]*n
        self.grouping = set(range(n))
        self.rank = [0]*n
        self.size = [1]*n


    def find(self, x:int) -> int:
        """
        要素 x の親の要素を見つけるメソッド

        Parameters:
        -----------
        x: int
            要素番号
        
        Returns:
        --------
        int
            x の親の要素番号
        """
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    

    def union(self, x:int, y:int) -> None:
        """
        要素 x, y の属するグループを結合するメソッド
        
        Parameters:
        -----------
        x, y: int
            結合対象の要素番号
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            # rank(x)の方が小さい場合は, xをくっつけて, y を親にする
            self.size[y] += self.size[x]
            self.parents[x] = y
            self.grouping.difference_update(set([x]))
        else:
            # そうでないときは, y をくっつけて, x を親にする
            self.size[x] += self.size[y]
            self.parents[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.grouping.difference_update(set([y]))


    def msize(self, x:int) -> int:
        """
        要素 x の属するグループの大きさを返すメソッド

        Parameters:
        -----------
        x: int
            要素番号
        
        Returns:
        --------
        int
            x の属するグループの大きさ(要素数)
        """
        return self.size[self.find(x)]


def main():
    N, M = map(int, input().split())
    uf = UnionFind(N)
    for _ in range(M):
        X, Y, _ = map(int, input().split())
        X -= 1; Y -= 1
        uf.union(X, Y)
    ans = len(uf.grouping)
    print(ans)


if __name__ == "__main__":
    main()

F - XOR Matching

XOR の bit 演算は、以下のようになります。

XOR 1 0
1 0 1
0 1 0

演算は、以下のように数字の各 bit どうしを比較して上記演算の結果を返します。

# ^ は XOR
5^13 #8
10進数 2進数
5: 0101
13: 1101
8: 1000

また、結合法則、交換則が成り立ちます。( \oplus

  •  (a \oplus b) \oplus c = a \oplus (b \oplus c)
  •  a \oplus b = b \oplus a

そして、0 は以下を満たします。

  •  a \oplus 0 = a
  •  a \oplus a = 0

さて、問題文の状況から、 0 以上  2^{M} 未満の整数が2つずつ使える中で数列を作り、同じ値で囲まれる間の数列の XOR を行うと  K になるようにします。

まず、XOR は bit 演算なので、演算した後に bit の最大の桁数が増えることはありません。したがって、 K \geq 2^{M} の場合は XOR して  K を作ることができません。

そうでない場合は、数列のなかに  K を入れることができます。 a \oplus a = 0 が成り立つので、以下のように  K を同じ数字で囲むと、問題文の条件を満たせます。

0 2 3 4 K 4 3 2 0

 Kうしの場合どうするかですが、次の性質を使うと簡単です。

  •  1 から  2^{M}-1 以下の整数を全てXORすると、0 になる

よって、ここから一つ  K という数字を外すと、XOR は  K になります。

ゆえに、数列を作る際は、 Kうしの間は  K 以外の  1 から  2^{M}-1 以下の整数を並べれば良いです。

例えば  M = 3 K = 5 の場合は、以下のようにすれば良いです。

0 1 2 3 4 6 7 5 7 6 4 3 2 1 0 5

これで大体答えですが、特殊なケースについて考えておきます。

 K = 0 の場合は、隣どうし数字を並べたりすることで満たせます。

また、 M=1 K=1 の場合は、このときは 0 と 1 しか使える数字がなく、どう並び替えても条件を満たす数列を作れません。この時は -1 を出します。

以上で、 O(2^{M}) で条件を満たす数列が作れました。

提出コード

from collections import deque

M, K = map(int, input().split())
if 2**M-1 < K:
    print(-1)
    return

if K == 0:
    ans = deque([])
    for i in range(2**M):
        ans.appendleft(i)
        ans.append(i)
    print(*ans)
    return

if M == 1:
    print(-1)
    return

ans = deque([K])
for p in range(0, 2**M):
    if p != K:
        ans.appendleft(p)
        ans.append(p)
ans.append(K)
    
print(*ans)

ABC206 参加記録

  • 3完0ペナ 8分でした
  • Dに関してはサンプルの値に引っ張られすぎて、正しい考察ができていなかったのが反省です。
  • E問題は AND 条件を分割して考えることを意識しようと思います。

A - Maxi-Buying

 N 円に 1.08 倍して小数点以下を切り捨てます。その値と 206 を比較して、問題文にあるような出力をします。

from math import floor

N = int(input())
res = floor(N * 1.08)
if res > 206: print(":(")
elif res == 206: print('so-so')
else: print('Yay!')

B - Savings

 10^{5} から  10^{6} の間の加算を行うだけでも、 10^{10} は超えます。( 10^{5} 9\times 10^{5} 加算することになるので)

したがって順に足していき、初めて  N を超えたら終了させれば良いです。

N = int(input())
res = 0
for i in range(1, 10**8+1):
    res += i
    if res >= N:
        print(i)
        break

C - Swappable

 A_i \neq A_j となる (i,j) の組の数は、全体(全ての  (i, j) の組の数)から  A_i = A_j となる (i, j) の組の数を引いて求めることができます。

 A_i = A_j となる (i, j) の組の数は、 A の要素の出現回数をカウントして、「同じ数を2つ選ぶ」場合を考えれば求めることができます。

N = int(input())
A = list(map(int, input().split()))
counterA = Counter(A)
ans = (N*(N-1))//2
res = 0
for _, cnt in counterA.items():
    if cnt >= 2: res += (cnt*(cnt-1))//2
ans -= res
print(ans)

D - KAIBUNsyo

解説AC です。

まず、サンプルで考えてみると、以下のように、回文になっていないところを確認することができます。

f:id:Xenous:20210620152647p:plain
回文になっていないところをペアにした図

ここで、5 と 3 と 2 は数珠繋ぎになっています。5 と 3 と 2 のうち、どれかひとつの数字に全て変換しないと回文にすることができません。この場合の答えは、回文にならない数字の集合の大きさから1引いたものになります。

さて、以下の場合はどうでしょうか。

f:id:Xenous:20210620153249p:plain
回文になっていないところをペアにした図 その2

この図では、2と6、1と3と5 をまとめて同じ数字にする必要はなく、それぞれのグループで、ひとつの数字に変換させれば良いです。

グループの管理は unionfind を使えばできます。制約より  A_i \leq 2\times 10^{5} なので、 A の値でグループ管理します。 あとは各グループの大きさから1引いたものが最小回数になります。

本番ではこのパターンが抜けていました。。気づけなかったのが残念すぎます。

D問題 提出コード

# UnionFind は細部を省略して記載
class UnionFind():
        """
        Parameters:
        -----------
        n: int
            要素数
        parents: list
            各要素が属する親の要素番号
        grouping: set
            親番号の集合
        rank: list
            親の rank を保持するためのリスト
        size: list
            親の size を保持するためのリスト
        """

    def find(self, x:int) -> int:
        """
        要素 x の親の要素を見つけるメソッド
        """

    def union(self, x:int, y:int) -> None:
        """
        要素 x, y の属するグループを結合するメソッド
        """

    def msize(self, x:int) -> int:
        """
        要素 x の属するグループの大きさを返すメソッド
        """


def main():
    N = int(input())
    A = list(map(int, input().split()))
    uf = UnionFind(max(A)+1)
    ans = 0
    for i in range(N//2):
        if A[i] != A[N-i-1]:
            uf.union(A[i], A[N-i-1])
    for g in uf.grouping:
        ans += uf.msize(g)-1
    print(ans)


if __name__ == "__main__":
    main()

ちなみに、もし  A の値が  10^{9} まで取り得るときでも、 A の値を圧縮する(要素の大きさの順位を  A の要素にする)ことで、unionfind で扱える大きさに縮小させて、以下同様に解くことができます。

E - Divide Both

解説AC です。本番では D がイマイチ解けなさそうだったので逆転を狙って E に取り組んでいました。

まず「最大公約数」とか言われると扱いにくいので、基本的な言い換えをします。

  •  \gcd(x, y) = g が成り立つ( x y の最大公約数が  g)」なら、「 x y g の倍数」

これは逆は成り立たないことに注意します。

さて、問題文の条件について見てみます。

  •  L \leq x, y \leq R
  •  g x y の最大公約数とすると、以下が成り立つ
    •  g \neq 1 ... ① かつ  \frac xg \neq 1 ... ② かつ  \frac yg \neq 1 ... ③

① は最大公約数が 1 でないことを意味します。 x, y はともに何かしらの 1 でない自然数の倍数になっているということになります。

②③は、最大公約数  g x または  y が同じ値にならない、と言えます。例えば  x = 6, y = 12 のとき、  \gcd(x,y) = 6 になりますが、これは②を満たしていません。

次にどのように組み立てていくかですが、まずは  g によって場合分けします。すなわち、最大公約数が 2 のときの  (x, y) の組の数、最大公約数が 3 のときの  (x, y) の組の数、... と見ていきます。そこで  (x, y) の組の数を洗い出して、②③を満たさないものを除いていきます。

最初の言い換えを使って、  \gcd(x, y) = 2 だから、 x, y は 2 の倍数。 (x, y) の組の数は( L, R の範囲内の)2の倍数の組み合わせだ、とやりたいところですが、例えば  x = 8, y = 12 はどちらも 2 の倍数でありながら  \gcd(x,y) = 4 になります。このようなパターンは不適です。

数えたいのは、 \gcd(x, y) がちょうど  2 になる  (x, y) の組の数です。先程の求め方では、 \gcd(x, y) = 4, 6, 8, ... = 2k のパターンが含まれています。したがって、大きい方から順に計算していき、除いていくのが良さそうです。

以上より、まずは最大公約数  g の大きい方から  (x, y) の組の数を洗い出していきます。 L, R の範囲だけ考えればよく、最大公約数は  R が最大ですから、 R から  2 (①より  1 の場合は考えなくて良い)まで見ていきます。

 \gcd(x, y) = R となるのは、( x y R の倍数と言えるので) (R,R) だけになります。 \frac R2 まではこのように 1 通りになります。

 \gcd(x, y) = k については、 k の倍数で構成された数字の組が候補になります。 R までの  k の倍数の数字の個数を  Z_k とおくと、候補の組は  Z_k^{2} 個あります。ちょうど  \gcd(x, y) = k となるには、今まで計算した  \gcd(x, y) = mk m は2以上の整数)の場合の数を除きます。

例えば、下記の例で、例えば  \gcd(x, y) = 3 を考えます。候補の数字は、3の倍数なので、3と6です。 これらの数字を使ったペアの作り方は (3, 3), (3, 6), (6, 3), (6, 6) の4通りあります。各  g について計算すれば  Z_g^{2} の行が埋まります。

そして、ちょうど  \gcd(x, y) = 3 となる組の数を調べるため、最後の行の後ろから埋めていきます。8から5までは2倍すると  R を超えるので 1 通りのままです。 \gcd(x, y) = 4 は、 \gcd(x,y) = 8 の場合に 1 通りダブりが生じるので、それを除いて、3 通りです。 \gcd(x, y) = 3 も同じ要領で計算して 3 通りとわかります。

 \gcd(x, y) = 2 となる組みも同様に、 \gcd(x, y) = 4, 6, 8 となる場合にダブりが生じているのでそれを除いて 4 通りになります。

f:id:Xenous:20210620230542p:plain
計算のイメージ

次に、②③の条件を満たさないものを除きます。

②③の条件は、 g = x または  g = y となる場合で、これは  g L, R に含まれているときに除外する必要があります。 除くのは  (g, g) と、 (g, kg) k = 2, 3, \cdots)とその逆の場合です。

以上で全ての条件を満たした  (x, y) の組を数え上げることができました。

実装では、 \gcd(x, y) = g を調べる部分をエラトステネスの篩の要領でテーブルを作ることができます。計算量は  O(R\log{R}) です。

E問題 提出コード

def main():
    L, R = map(int, input().split())
    table = [0] * (R+1)
    for k in range(2, R+1):
        cnt = 0; i = 1
        while k*i <= R:
            if L <= k*i <= R: cnt += 1
            i += 1
        table[k] = cnt
    gcnt = [c**2 for c in table]
    
    for g in range(R, 1, -1):
        i = 2
        while g*i <= R:
            gcnt[g] -= gcnt[g*i]
            i += 1
    
    ans = 0
    for g, t in enumerate(gcnt):
        if g < L: ans += t
        elif L <= g <= R:
            if t <= 1: continue
            ans += t - (table[g]-1)*2 - 1
    print(ans)


if __name__ == "__main__":
    main()

ARC122 参加記録

  • 1完(C問題)2ペナ 130分でした

A - Many Formulae

 A_i について、マイナスの個数がそれぞれわかれば良さそうです。 DPplus、DPminus を以下のように定めます。

  • DPplus[i] :  i 番目までで、 i 番目がプラスで終わるようなプラスマイナスの並び方の総数
  • DPminus[i] :  i 番目までで、 i 番目がマイナスで終わるようなプラスマイナスの並び方の総数

遷移は以下のようになります。

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

この遷移で更新させると、最後の  N 番目のマイナスで終わる並び方の総数はわかりますが、それ以前がぱっと見わかりません。 実は、表を埋めていくと、以下のような法則が見つけられます。

f:id:Xenous:20210615213318p:plain
 A_i でマイナスの場合の数を算出する

  • DPminus[i]  \times DPminus[N-i] の数が、 A_i がマイナスになる場合の数と同じ

以上より、 O(N) で計算することができました。

提出コード

MOD = pow(10,9)+7
def MODINV(n:int, MOD=MOD):
    return pow(n, MOD-2, MOD)


def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    # 初期化
    DPplus = [0] * N
    DPminus = [0] * N

    # 初期値
    DPplus[0] = 1

    # 遷移
    for i in range(1, N):
        DPplus[i] = (DPplus[i-1] + DPminus[i-1])%MOD
        DPminus[i] = DPplus[i-1]%MOD
    
    # 場合の数
    al = (DPminus[N-1] + DPplus[N-1])%MOD
    m = [0]
    for i in range(1, N):
        m.append((DPminus[i] * DPminus[N-i])%MOD)
    
    # 答え
    ans = 0
    for i, a in enumerate(A):
        ans += a * (al - m[i]) - a * m[i]
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

B - Insurance

自分が失う金額を以下のようにおきます。


y_{i} = x + A_{i} - \min(A_{i}, 2x)

求める期待値は次のように表せます。

 \displaystyle
\frac1{N}\sum_{i} y_{i} = \frac{Nx + \sum_{i} A_{i} - \sum_{i} \min(A_{i}, 2x)}{N}

右辺の分母の値の最小化を考えます。各  y_i が凸関数であれば、その和も凸関数であるので、三分探索で見つけることができます。

 y_i = x + A_{i} - \min(A_{i}, 2x) について、グラフを描いてみます。 \min の部分で場合分けが必要です。

  •  A_{i} > 2x、すなわち  \frac{A_{i}}{2} > x のとき

 y_i = x + A_{i} - \min(A_{i}, 2x) = x + A_{i} - 2x = -x + A_{i}

  •  A_{i} \leq 2x、すなわち  \frac{A_{i}}{2} \leq x のとき

 y_i = x + A_{i} - \min(A_{i}, 2x) = x + A_{i} - A_{i} = x

f:id:Xenous:20210615211703p:plain
 y_i = x + A_{i} - \min(A_{i}, 2x) の図

 y_i が凸関数ということがわかります。したがって和も凸関数で、求める式の最小化を三分探索します。

実装では、あらかじめ  A をソートしておき、累積和を求めておくと、 \min の計算を  O(1) でできます。全体では  O(N\log{N}) でできます。

提出コード

from itertools import accumulate
from bisect import bisect_left

def f(x:int):
    global A, accumulateA, N, sumA
    idx = bisect_left(A, 2*x)
    res = N*x + sumA - accumulateA[idx] - 2*x*(N-idx)
    return res


def main():
    global A, accumulateA, N, sumA
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    sumA = sum(A)
    accumulateA = [0] + list(accumulate(A))

    # 三分探索
    L = 0; R = 10**14+1
    err = 0.0000001
    while abs(R-L) > err:
        c1 = (L*2 + R) / 3
        c2 = (L + R*2) / 3
        if f(x = c1) > f(x = c2): L = c1
        else: R = c2
    ans = min(f(L), f(c1), f(c2))/N
    print(ans)


if __name__ == "__main__":
    main()

C - Calculator

唯一解けました。実装含め70分くらいかかってます。

最初に 1 を加えてから、操作3, 操作4, 操作3, 操作4, ... と操作するのが最も数字を大きくできる方法のように見えます。実際に計算するとこれがフィボナッチ数列になっていることもわかります。

ちなみに  10^{18} には、上記のように操作するとして、合計90回くらいで到達できます。

次に操作1, 操作2 の意味について考えます。 操作1や操作2を行うと、そこから加算されていく数字がフィボナッチ数列的に増えていきます。

f:id:Xenous:20210613003019p:plain
遷移例と操作2による差分の増加具合

方針としては、 N を超えない最大のフィボナッチ数を求めて、その値との差分をさらにフィボナッチ数を構成することで縮めていくことを考えます。

以下は  N = 50 のときの数列の例です。

f:id:Xenous:20210613003359p:plain
 N = 50 のときの (x,y)の遷移

初手では  34 が最も( 50を超えずに)  50 に近い数字になります。その差分の  16 を埋めることを考えます。

 16 に最も近い数字の  13 は、一行目の (x, y) の遷移 7番目 (0-index) に初めて出てきています。つまり、差分が  16 となっているところから 7回前で、操作1 を行うことで、差分を  13 埋めることができます。その操作を行なった遷移列が 2 行目の  (x, y) の遷移になります。

このように求めたい数字との差を、フィボナッチ数列の値で縮めていくために、何回前に 操作1, 操作2 をしておけばいいのかを探索することで、求める操作列を作ることができます。

提出コード

from bisect import *


def fibonacci_l(n, seta=1, setb=0):
    l = [(seta-1, setb)]
    a, b = seta, setb; l.append((a, b))
    for k in range(n):
        a, b = l[-1]
        if k%2 == 0: l.append((a, a+b))
        else: l.append((a+b, b))
    return l


def main():
    N = int(input())
    if N == 1:
        print(1)
        print(1)
        return
    base = fibonacci_l(100)
    baselside, _ = map(list, zip(*base))
    
    ans = base.copy()
    idx = bisect_left(baselside, N)-2
    diff = N - base[idx][0]
    #print(ans[:idx+1])

    while diff > 1:
        #print(diff)
        nextidx = bisect_left(baselside, diff)-2
        i, j = ans[idx+1 - nextidx]
        #print(i, j)
        ans = ans[:idx+1 - nextidx] + fibonacci_l(100, i+1, j)
        lside, _ = map(list, zip(*ans))
        idx = bisect_left(lside, N)-2
        #print(ans[:idx+1])
        diff = N - ans[idx][0]

    #print(idx)
    ans = ans[:idx+1]
    #print(ans)

    res = []
    for k in range(len(ans)-1):
        bfx, bfy = ans[k]
        afx, afy = ans[k+1]
        if bfx == afx:
            if afy == bfy+1: res.append(2)
            else: res.append(4)
        else:
            if afx == bfx+1: res.append(1)
            else: res.append(3)
    
    res.append(1)
    print(len(res))
    print(*res, sep='\n')


if __name__ == "__main__":
    main()

D - XOR Game

少しだけ考えました。あとで解きたい問題です。

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

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

後々記載します。