mean_abs_error’s blog

ソフトウェアとシステムの狭間

【AtCoder】PythonでABC320を解く

はじめに

ABC320のA,B,C,D,E問題をPython3で解きます。

A問題: Leyland Number

atcoder.jp

問題の概要

A^B + B^Aを計算せよ。

問題の考察

pythonだとべき乗はpowで計算できます。

コード

def main():
    a, b = map(int, input().split())
    ans = pow(a, b) + pow(b, a)
    print(ans)


if __name__ == "__main__":
    main()

B問題: Longest Palindrome

atcoder.jp

問題の概要

文字列 Sについて、 Sの連続する部分文字列のうち、回文であるものの長さの最大値を求めよ。

問題の考察

|S| \le 100とのことなので、全探索できそうです。連続する部分文字列の先頭と長さを全探索するのに \mathcal{O} (|S|^2)、その文字列が回文かを判定するのに \mathcal{O} (|S|)だけ掛かるため、全探索と回文判定で \mathcal{O} (|S|^3)の計算量になります。

コード

def solve(S):
    ans = 1
    for i in range(len(S)):
        for j in range(i + 1, len(S) + 1):
            subS = S[i:j]
            if subS == subS[::-1]:
                ans = max(ans, len(subS))

    return ans


def main():
    S = input()
    ans = solve(S)
    print(ans)


if __name__ == "__main__":
    main()

C問題: Slot Strategy 2 (Easy)

atcoder.jp

問題の概要

N個のリールからなるスロットがあり、 i番目のリールは数字のみからなる長さ Mの文字列 S_iで表される。リールのスロットを止めるスイッチについて押す押さないを毎秒選べ、 t秒目に i番目のリール用のスイッチを押すと S_iの (t \mod M) + 1文字目で止まる。 N=3のとき、3個のリールとも同じ数字になるよう止めるには最小で何秒だけ掛かるか。

問題の考察

10種類( \omega=10)ある0～9の各数字で揃えようとしたときのそれぞれの最小時間を求め、さらにそれらの最小時間の最小を取る方向で考えます。揃えようとする数字を決めたとき、リールを止める順序は N !個だけあり、ある順序で揃えられる場合は N M秒未満で揃えられます。結果として、 \mathcal{O}(\omega N M N!)の計算量で最小時間を求められました。

コード

from itertools import permutations


def solve(M, Ss):
    def measure_time(order):
        i = 0
        for t in range(len(Ss) * M):
            if Ss[order[i]][t % M] == target:
                i += 1
                if i >= len(order):
                    return t

        return -1

    ans = float("inf")
    for target in range(10):
        for order in permutations(range(len(Ss)), len(Ss)):
            t = measure_time(order)
            if t >= 0:
                ans = min(ans, t)

    if ans == float("inf"):
        ans = -1

    return ans


def main():
    M = int(input())
    Ss = [list(map(int, list(input()))) for _ in range(3)]
    ans = solve(M, Ss)
    print(ans)


if __name__ == "__main__":
    main()

D問題: Relative Position

atcoder.jp

問題の概要

座標平面上に N人おり、『人 A_mから見て人 B_mは、 x軸正方向に X_m、 y軸正方向に Y_mだけ離れた位置にいる』という関係性が M個だけ与えられる。人1が原点にいると分かっているとき、それぞれの人がいる座標を求めよ。

問題の考察

位置関係を有向グラフで表現し、人1から幅優先探索(BFS)すればよさそうです。BFSするため、 \mathcal{O} (N + M) の計算量で求められます。

コード

from collections import deque


def solve(N, M, A, B, X, Y):
    G = [[] for _ in range(N)]
    for u, v, x, y in zip(A, B, X, Y):
        G[u].append((v, x, y))
        G[v].append((u, -x, -y))

    P = [None for _ in range(N)]
    P[0] = (0, 0)
    fifo = deque([0])
    used = set([0])
    while fifo:
        u = fifo.popleft()
        for v, x, y in G[u]:
            if v not in used:
                P[v] = (P[u][0] + x, P[u][1] + y)
                fifo.append(v)
                used.add(v)

    return P


def main():
    N, M = map(int, input().split())
    A = []
    B = []
    X = []
    Y = []
    for _ in range(M):
        a, b, x, y = map(int, input().split())
        a -= 1
        b -= 1
        A.append(a)
        B.append(b)
        X.append(x)
        Y.append(y)
    P = solve(N, M, A, B, X, Y)
    for pos in P:
        if pos is None:
            print("undecidable")
        else:
            print(*pos)


if __name__ == "__main__":
    main()

E問題: Somen Nagashi

atcoder.jp

問題の概要

そうめん流しの会に、列の先頭から順に1～Nの番号が付いた N人が来ました。『①時刻 T_mに流れる量 W_mのそうめんを列の先頭にいる人が全て食べて列から外れ、②時刻 T_m + S_mにその人が列の元の位置に戻ってくる』という出来事が M回起こるとき、それぞれの人が食べるそうめんの合計を求めよ。

問題の考察

T_mも S_mも最大で 10^9と大きいため、毎秒シミュレーションするのは計算量的にムリだと分かります。

①そうめんが流れるイベントと②人が戻ってくるイベントはそれぞれ M回しか起こらないため、イベントの発生時刻のみをシミュレーションする方向で考えます。イベントを順に取り出したり、列の先頭にいる人を取り出したりするために、①と②のイベントをヒープで、同様に列に並んだ人もヒープで管理します。イベント用ヒープに挿入するイベントについて、①のイベントを (t, 1, -1, w, s)で、②の人iが戻るイベントを (t, 0, i, -1, -1)で表すことで、適切な順でヒープからイベントを取り出せるようになります。2つのヒープを用いてシミュレーションしつつ、各人の食べたそうめんの量を計算すると、 \mathcal{O} (M \log M + M \log N + N)の解けました。

コード

from heapq import heappop, heappush


def solve(N, M, events):
    ans = [0] * N

    customers = []
    for i in range(N):
        heappush(customers, i)

    while events:
        t, event_id, i, w, s = heappop(events)
        if event_id == 0:
            heappush(customers, i)
        else:
            if customers:
                i = heappop(customers)
                ans[i] += w
                heappush(events, (t + s, 0, i, -1, -1))

    return ans


def main():
    N, M = map(int, input().split())
    events = []
    for _ in range(M):
        t, w, s = map(int, input().split())
        heappush(events, (t, 1, -1, w, s))
    ans = solve(N, M, events)
    print(*ans)


if __name__ == "__main__":
    main()

【AtCoder】PythonでABC319を解く

はじめに

ABC319のA,B,C,D問題をPython3で解きます。

A問題: Legendary Players

atcoder.jp

問題の概要

プレイヤー名とレーティングが事前に表として定義されている。あるプレイヤー名が与えられたとき、その人のレーティングを答えよ。

問題の考察

splitlinesを使うことでstr型の表の各行を読み込み、プレイヤー名をレーティングに変換するルックアップテーブル(LUT)を作っておきます。あとは入力されたプレイヤー名をLUTで変換すればよいです。

コード

def solve(S):
    text = """tourist 3858
ksun48 3679
Benq 3658
Um_nik 3648
apiad 3638
Stonefeang 3630
ecnerwala 3613
mnbvmar 3555
newbiedmy 3516
semiexp 3481
"""
    name2rate = {}
    for line in text.splitlines():
        name, rate = line.strip().split()
        name2rate[name] = rate

    return name2rate[S]


def main():
    S = input()
    ans = solve(S)
    print(ans)


if __name__ == "__main__":
    main()

B問題: Measure

atcoder.jp

問題の概要

何をやりたいのかよくわからなかった問題なため要約が難しく、要約をサボります。

問題の考察

① Nの約数 jである、② iが N / jの倍数である、という条件2つを満たす jの集合を1～9の範囲で求めます。集合が空ならハイフンを、そうでないなら集合の最小値を結合します。

コード

def solve(N):
    ans = []
    for i in range(N + 1):
        js = [j for j in range(1, 10) if N % j == 0 and i % (N // j) == 0]
        if js:
            ans.append(str(min(js)))
        else:
            ans.append("-")

    return "".join(ans)


def main():
    N = int(input())
    ans = solve(N)
    print(ans)


if __name__ == "__main__":
    main()

C問題: False Hope

atcoder.jp

問題の概要

B問題と違ってやりたいことは分かるのですが、そのまんますぎて省略しにくいため、要約をサボります。

問題の考察

マスを見ていく順番を全探索し、各探索毎にがっかりの有無を判定します。全探索には \mathcal{O}(9!)、がっかり判定に \mathcal{O}(9)だけ掛かり、全体としては \mathcal{O}(9 * 9!)だけ掛かります。

がっかり判定をうまく実装できればいいのですが、良い実装が思いつかなかったため愚直にマス毎のがっかり判定文を書き下しました。実装中は泣きそうになりました。

コード

from itertools import permutations
from math import factorial


def solve(C):
    def is_valid(order):
        knowns = set()
        for k in order:
            if k == 0:
                if 1 in knowns and 2 in knowns and C[1] == C[2]:
                    return False
                if 3 in knowns and 6 in knowns and C[3] == C[6]:
                    return False
                if 4 in knowns and 8 in knowns and C[4] == C[8]:
                    return False
            elif k == 1:
                if 0 in knowns and 2 in knowns and C[0] == C[2]:
                    return False
                if 4 in knowns and 7 in knowns and C[4] == C[7]:
                    return False
            elif k == 2:
                if 0 in knowns and 1 in knowns and C[0] == C[1]:
                    return False
                if 5 in knowns and 8 in knowns and C[5] == C[8]:
                    return False
                if 4 in knowns and 6 in knowns and C[4] == C[6]:
                    return False
            elif k == 3:
                if 4 in knowns and 5 in knowns and C[4] == C[5]:
                    return False
                if 0 in knowns and 6 in knowns and C[0] == C[6]:
                    return False
            elif k == 4:
                if 3 in knowns and 5 in knowns and C[3] == C[5]:
                    return False
                if 1 in knowns and 7 in knowns and C[1] == C[7]:
                    return False
                if 0 in knowns and 8 in knowns and C[0] == C[8]:
                    return False
                if 2 in knowns and 6 in knowns and C[2] == C[6]:
                    return False
            elif k == 5:
                if 3 in knowns and 4 in knowns and C[3] == C[4]:
                    return False
                if 2 in knowns and 8 in knowns and C[2] == C[8]:
                    return False
            elif k == 6:
                if 7 in knowns and 8 in knowns and C[7] == C[8]:
                    return False
                if 0 in knowns and 3 in knowns and C[0] == C[3]:
                    return False
                if 2 in knowns and 4 in knowns and C[2] == C[4]:
                    return False
            elif k == 7:
                if 6 in knowns and 8 in knowns and C[6] == C[8]:
                    return False
                if 1 in knowns and 4 in knowns and C[1] == C[4]:
                    return False
            else:
                if 6 in knowns and 7 in knowns and C[6] == C[7]:
                    return False
                if 2 in knowns and 5 in knowns and C[2] == C[5]:
                    return False
                if 0 in knowns and 4 in knowns and C[0] == C[4]:
                    return False
            knowns.add(k)

        return True

    ok = 0
    for order in permutations(range(9), 9):
        if is_valid(order):
            ok += 1

    ans = ok / factorial(9)

    return ans


def main():
    C = []
    for _ in range(3):
        line = list(map(int, input().split()))
        for c in line:
            C.append(c)
    ans = solve(C)
    print(ans)


if __name__ == "__main__":
    main()

D問題: Minimum Width

atcoder.jp

問題の概要

横幅が L_iの N個の単語について、改行または横幅1のスペースで順に繋げて M行以内のウィンドウに納めたい。ウィンドウの横幅としてありえる最小値を求めよ。

問題の考察

最大値の最小化に関する問題なため、二分探索で解けそうと分かります。

ウィンドウの横幅 Wを二分探索し、ある横幅のときに M行以内で収まるかを判定すればよいです。 Wについて、最大値としてあり得るのは N - 1 + \sum_{i=1}^N L_iで、どんなに小さくできても0以下になることはないため、 0 \lt W \le N - 1 + \sum_{i=1}^N L_iでの二分探索により、計算量は \mathcal{O} (\log (N + \sum_{i=1}^N L_i) )となります。ある横幅のときにM行以内で収まるかの判定は、先頭の単語だとスペースは不要でそれ以外だとスペースが必要なことに注意しながら愚直に実装すれば、 \mathcal{O} (N)となります。結果として、 \mathcal{O} (N \log (N + \sum_{i=1}^N L_i) )で解けました。

コード

def solve(N, M, L):
    def is_valid(W):
        m = 0
        i = 0
        w = 0
        while i < N:
            if m >= M:
                return False
            if w <= 0:
                w += L[i]
            else:
                w += L[i] + 1
            if w > W:
                w = 0
                m += 1
            else:
                i += 1

        return True

    ok = sum(L) + N - 1
    ng = 0
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if is_valid(mid):
            ok = mid
        else:
            ng = mid

    return ok


def main():
    N, M = map(int, input().split())
    L = list(map(int, input().split()))
    ans = solve(N, M, L)
    print(ans)


if __name__ == "__main__":
    main()

【AtCoder】PythonでABC318を解く

はじめに

ABC318のA,B,C,D問題をPython3で解きます。

A問題: Full Moon

atcoder.jp

問題の概要

満月が M日目に初めて見られて、以後は P日ごとに見られる。1日目から N日目までの間に満月が見られる回数を答えよ。

問題の考察

range(M, N + 1, P)の回数だけ数えます。

コード

def solve(N, M, P):
    ans = 0
    for _ in range(M, N + 1, P):
        ans += 1

    return ans


def main():
    N, M, P = map(int, input().split())
    ans = solve(N, M, P)
    print(ans)


if __name__ == "__main__":
    main()

B問題: Overlapping sheets

atcoder.jp

問題の概要

座標平面上に長方形が N個ある。 i番目の長方形は、 x軸の A_i \le x \le B_iと y軸の C_i \le y \le D_iをみたす領域を覆っている。1個以上の長方形に覆われている領域の面積を求めよ。

問題の考察

二次元配列で各グリッドを表し、そのグリッドが覆われていればTrue(1)を、そうでなければFalse(0)を代入し、最後に総和を取ります。

コード

from itertools import chain


def solve(N, A, B, C, D):
    X = [[False] * 100 for _ in range(100)]
    for a, b, c, d in zip(A, B, C, D):
        for x in range(a, b):
            for y in range(c, d):
                X[x][y] = True

    ans = sum(chain.from_iterable(X))

    return ans


def main():
    N = int(input())
    A, B, C, D = list(zip(*[list(map(int, input().split())) for _ in range(N)]))
    ans = solve(N, A, B, C, D)
    print(ans)


if __name__ == "__main__":
    main()

C問題: Blue Spring

atcoder.jp

問題の概要

N日間だけ鉄道で旅行する。 i日目の通常運賃は F_i円である。通常運賃とは別に1日周遊パスがあり、 D枚セットで P円で売られている。旅行で掛かるお金の最小値を求めよ。

問題の考察

通常運賃の高い日は周遊パスを使うのがよさそうです。通常運賃を降順に並び替えて D日間分ずつの通常運賃合計をみていき、それが P円以上ならば周遊パスを買い、未満ならば通常運賃で支払います。

ソートが必要になるため、計算量は \mathcal{O}(N \log N)となります。

コード

from heapq import heappop, heappush


def solve(N, D, P, F):
    heap = []
    for f in F:
        heappush(heap, -f)

    ans = 0
    cnt = 0
    total = 0
    while heap:
        f = heappop(heap)
        f = -f
        cnt += 1
        total += f
        if cnt >= D:
            if total >= P:
                ans += P
            else:
                ans += total
            cnt = 0
            total = 0

    if total >= P:
        ans += P
    else:
        ans += total

    return ans


def main():
    N, D, P = map(int, input().split())
    F = list(map(int, input().split()))
    ans = solve(N, D, P, F)
    print(ans)


if __name__ == "__main__":
    main()

D問題: General Weighted Max Matching

atcoder.jp

問題の概要

N頂点の重み付き無向完全グラフがある。頂点 uと頂点 vを結ぶ辺の重みは D_{u,v} \ge 1である。選んだ辺の端点はどの2個も相異なるように辺を選ぶとき、選んだ辺の重みの総和の最大値を求めよ。

問題の考察

Nは最大でも16であるため、全探索する方針を考えます。

①未使用頂点集合 Vから最小の頂点番号を取り出し、②それを残った Vに含まれる頂点との全てのペアを考えてペアになった頂点を取り出す、という①と②を Vが空になるまで続けると、 15 \times 13 \times \cdots \times 1の計算量で解けそうです。

なお、頂点の数が奇数だと未使用頂点集合が空になることがなくて処理が面倒なため、頂点の数が奇数の場合は各頂点と重み0で繋がった頂点を1つ追加することで、奇数か偶数かに関係なく同じように処理できるようになります。

コード

def solve(N, G):
    def dfs(total=0):
        if not not_used:
            yield total
            return

        u = min(not_used)
        not_used.discard(u)
        for v in list(not_used):
            not_used.discard(v)
            yield from dfs(total + G[u][v])
            not_used.add(v)
        not_used.add(u)

    not_used = set(range(N))
    ans = 0
    for total in dfs():
        ans = max(ans, total)

    return ans


def main():
    N = int(input())
    if N % 2 == 0:
        G = [[0] * N for _ in range(N)]
        for u in range(N - 1):
            D = list(map(int, input().split()))
            for v, w in enumerate(D, u + 1):
                G[u][v] = w
    else:
        N += 1
        G = [[0] * N for _ in range(N)]
        for u in range(N - 2):
            D = list(map(int, input().split()))
            D.append(0)
            for v, w in enumerate(D, u + 1):
                G[u][v] = w

    ans = solve(N, G)
    print(ans)


if __name__ == "__main__":
    main()

【AtCoder】PythonでABC317を解く

はじめに

ABC317のA,B,C,D問題をPython3で解きます。

A問題: Potions

atcoder.jp

問題の概要

N個の効き目順に並んだ傷薬があり、 i番目の傷薬を使うと体力が P_iだけ増加する。現体力が Hで傷薬を1つ使って体力を X以上するとき、その条件を満たす最も効き目の弱い傷薬の番号を答えよ。

問題の考察

H + P_i \ge Xを満たす最も効き目の弱い傷薬番号 iを答えます。

コード

def solve(H, X, P):
    for i, p in enumerate(P, 1):
        if H + p >= X:
            return i

    return len(P)


def main():
    N, H, X = map(int, input().split())
    P = list(map(int, input().split()))
    ans = solve(H, X, P)
    print(ans)


if __name__ == "__main__":
    main()

B問題: MissingNo.

atcoder.jp

問題の概要

N+1個の連続する整数のうちの一つをなくした。入力として与えられる残りの整数の列 A_1, A_2, \cdots, A_Nから、なくした整数を求めよ。ただし、なくした整数は一意に決まる入力のみが与えられる。

問題の考察

なくした整数は一意に決まる入力のみが与えられるという制約から、両端の整数以外がなくなるのだと分かります。両端の整数は必ず残っているため、集合 [ \min(A), \max(A) ]から A_iを除いていくと、残った1つがなくした整数に対応します。

コード

def solve(N, A):
    minA = min(A)
    maxA = max(A)
    V = set(range(minA, maxA + 1))
    for a in A:
        V.discard(a)

    return V.pop()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans = solve(N, A)
    print(ans)


if __name__ == "__main__":
    main()

C問題: Remembering the Days

atcoder.jp

問題の概要

N個の街と M本の道路がある。 i本目の道路は長さ C_iで街 A_iと街 B_iを双方向に結ぶ。好きな街からスタートして同じ街を通らずに移動するとき、通る道路の長さの和の最大値を求めよ。

問題の考察

Nが最大でも10と小さいため、深さ優先探索(DFS)による全探索もしくはbitDPで解けそうです。コンテスト中にはDFSによる方法しか思いつかなかったです。

スタートする街を全て試して同じ街を通らないようDFSすると、計算量は \mathcal{O}(N!)となります。なお、DFSを楽に実装できる再帰関数だとTLEが出てしまったため、再帰関数ではなくオイラーツアーで実装しました。

bitDPだと計算量は \mathcal{O}(M 2^N)となります。計算量的にはこちらの方がよいですが、実装にはやや慣れが必要かもしれません。

DFSで解く場合のコード

def solve(N, M, G):
    def dfs(start):
        lifo = [(~start, 0), (start, 0)]
        costs = [-1] * N
        costs[start] = 0
        used = set()
        while lifo:
            u, c = lifo.pop()
            if u >= 0:
                used.add(u)
                for v, w in G[u]:
                    cc = c + w
                    if v not in used:
                        lifo.append((~v, cc))
                        lifo.append((v, cc))
                        costs[v] = max(costs[v], cc)
            else:
                u = ~u
                used.discard(u)

        return costs

    ans = 0
    for start in range(N):
        costs = dfs(start)
        ans = max(ans, max(costs))

    return ans


def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        G[u].append((v, w))
        G[v].append((u, w))
    ans = solve(N, M, G)
    print(ans)


if __name__ == "__main__":
    main()

bitDPで解く場合のコード

from itertools import chain


def solve(N, M, G):
    dp = [[-float("inf")] * N for _ in range(1 << N)]
    for u in range(N):
        dp[1 << u][u] = 0

    for V in range(1 << N):
        for u in range(N):
            for v, w in G[u]:
                if (V >> v) & 1 == 0:
                    VV = V | (1 << v)
                    dp[VV][v] = max(dp[VV][v], dp[V][u] + w)

    ans = max(chain.from_iterable(dp))
    if ans == float("inf"):
        ans = -1

    return ans


def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        G[u].append((v, w))
        G[v].append((u, w))
    ans = solve(N, M, G)
    print(ans)


if __name__ == "__main__":
    main()

D問題: President

atcoder.jp

問題の概要

N個の選挙区において、 i番目の選挙区には X_i人の高橋派と Y_i人の青木派がおり、多数派がその区の Z_i議席を全て獲得する。選挙区全体として過半数を獲得した方が選挙に勝利するとき、高橋君が勝利するためには青木派から高橋派に最低何人を鞍替えさせる必要があるか。

問題の考察

ナップサック問題と同じ構造の問題であるため、動的計画法(DP)で解けそうです。 i番目の選挙区までをみたときに m議席だけ獲得するのに鞍替えが必要な最少人数を \mathrm{dp} [i] [m]とすれば、状態遷移を表せそうです。

i区で鞍替えを考慮する必要がない X_i > Y_iの場合、 \mathrm{dp} [i+1] [m + Z_i ] = \min( \mathrm{dp} [i+1] [m + Z_i ], \mathrm{dp} [i] [m])と配る緩和式を書けます。

それ意外の場合、 i区で議席を獲得するには S_i = \frac{X_i+Y_i + 1}{2} - X_iだけ鞍替えさせる必要があるため \mathrm{dp} [i+1] [m + Z_i ] = \min( \mathrm{dp} [i+1] [m + Z_i ], \mathrm{dp} [i] [m] + S_i)と、議席を獲得しないなら \mathrm{dp} [i+1] [m ] = \min( \mathrm{dp} [i+1] [m], \mathrm{dp} [i] [m])と、配る緩和式を書けます。

状態として iと mを持つため、 \mathcal{O}(N \sum_i Z_i)の計算量でこの問題は解けました。

コード

考察では状態として iを持たせていますが、なくても解けるため省略して解いています。

def solve(N, X, Y, Z):
    dp = [float("inf")] * 200001
    dp[0] = 0
    for x, y, z in zip(X, Y, Z):
        for m in range(100000, -1, -1):
            if x > y:
                dp[m + z] = min(dp[m + z], dp[m])
            else:
                sw = (x + y) // 2 + 1 - x
                dp[m + z] = min(dp[m + z], dp[m] + sw)

    majority = sum(Z) // 2 + 1
    ans = min(dp[majority:])

    return ans


def main():
    N = int(input())
    X = []
    Y = []
    Z = []
    for _ in range(N):
        x, y, z = map(int, input().split())
        X.append(x)
        Y.append(y)
        Z.append(z)
    ans = solve(N, X, Y, Z)
    print(ans)


if __name__ == "__main__":
    main()