ABC309感想戦

python

コンテスト

Tasks - Denso Create Programming Contest 2023 (AtCoder Beginner Contest 309)
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A問題

A - Nine
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

感想

少し悩んだ。
とりあえずAのことだけを考えてみると、A%3毎にB隣接がどの方向になるのかが変わることが分かる。なので、A%3が1,2,0それぞれについて、条件分岐して解いた。

コンテスト中提出コード

Submission #43341873 - Denso Create Programming Contest 2023 (AtCoder Beginner Contest 309)
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
import sys
import itertools
import math
import collections
import bisect
import heapq

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

INF = 10**18


def main():
    A, B = list(map(int, input().split()))
    if A % 3 == 1:
        if B == A+1:
            print("Yes")
        else:
            print("No")
    elif A % 3 == 2:
        if B == A+1 or B == A-1:
            print("Yes")
        else:
            print("No")
    else:
        if B == A-1:
            print("Yes")
        else:
            print("No")


main()

今になって考えてみると、A<Bなので、条件式”B == A-1″が満たされることはないので、無駄な分岐だった。
結局、A%3が0の時は確実に”No”、それ以外の時は、”B == A+1″であれば”Yes”になる。

改良コード

Submission #43341873 - Denso Create Programming Contest 2023 (AtCoder Beginner Contest 309)
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
import sys
import itertools
import math
import collections
import bisect
import heapq

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

INF = 10**18


def main():
    A, B = list(map(int, input().split()))
    if A % 3 == 0:
        print("No")
    else:
        if B == A+1:
            print("Yes")
        else:
            print("No")


main()
  

B問題

B - Rotate
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

感想

これも少し手間取ってしまった。
添字やrangeで出てくる値のパターンが多すぎて、バグってしまった。
基本方針としては、

  • まず外側のマス以外をBに代入
  • 1行目のA[i]をB[i+1]に代入して、B[0]は2行目から持ってくる
  • N行目のA[i]をB[i-1]に代入して、B[N-1]はN-1行目から持ってくる
  • 1列目、N列目も同様

コンテスト中提出コード

Submission #43357597 - Denso Create Programming Contest 2023 (AtCoder Beginner Contest 309)
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
import sys
import itertools
import math
import collections
import bisect
import heapq

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

INF = 10**18


def main():
    N = int(input())
    A = [list(input().strip()) for _ in range(N)]

    B = [[None] * N for _ in range(N)]

    for i in range(1, N-1):
        for j in range(1, N-1):
            B[i][j] = A[i][j]

    for j in range(N-1):
        B[0][j+1] = A[0][j]
    B[0][0] = A[1][0]

    for j in range(N-1):
        B[N-1][j] = A[N-1][j+1]
    B[N-1][N-1] = A[N-2][N-1]

    for j in range(1, N-1):
        B[j][0] = A[j+1][0]

    for j in range(1, N-1):
        B[j][N-1] = A[j-1][N-1]

    for i in B:
        print("".join(i))


main()

C問題

C - Medicine
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

感想

比較的すんなり解けた。
$a_i$日間飲む→$a_i+1$日目に飲む量が$b_i$錠減る。
辞書に何日目に何錠減るかカウントし、減らしていく。

コンテスト中提出コード

Submission #43363049 - Denso Create Programming Contest 2023 (AtCoder Beginner Contest 309)
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
import sys
import itertools
import math
import collections
import bisect
import heapq

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

INF = 10**18


def main():
    N, K = list(map(int, input().split()))
    ab = [list(map(int, input().split())) for _ in range(N)]

    dn = collections.defaultdict(int)
    s = 0
    for a, b in ab:
        s += b
        dn[a+1] += b

    if s <= K:
        print("1")
        exit()

    for d, n in sorted(dn.items()):
        s -= n
        if s <= K:
            print(d)
            break


main()

D問題

D - Add One Edge
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

感想

N1以下を含むグラフg1と、それ以外を含むグラフg2とする。
g1で1から始めて最長になる距離d1、g2でN1+N2から始めて最長になる距離d2とすると、d1+d2+1が答え。
初め、N1,N2個の頂点を含む2つのグラフを作って実装しようとしていたが添字が面倒で変更。
よく考えてみると、頂点1と頂点N1+N2は非連結だから、一つのグラフで、管理しても問題ない。
よって普通に一つのグラフで管理して、BFSを2回行って、d1,d2を算出する。

コンテスト中提出コード

import sys
import itertools
import math
import collections
import bisect
import heapq

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

INF = 10**18


def main():
    N1, N2, M = list(map(int, input().split()))
    ab = [list(map(int, input().split())) for _ in range(M)]

    g = [[] for _ in range(N1+N2)]

    for a, b in ab:
        g[a-1].append(b-1)
        g[b-1].append(a-1)
    todo = collections.deque()
    todo.append([0, 0])
    done = [False] * (N1+N2)
    d1m = 0
    while todo:
        cur, dist = todo.popleft()
        if done[cur] is True:
            continue
        done[cur] = True
        d1m = max(d1m, dist)
        for ad in g[cur]:
            if done is True:
                continue
            todo.append()

    todo = collections.deque()
    todo.append([N1+N2-1, 0])
    d2m = 0
    while todo:
        cur, dist = todo.popleft()
        if done[cur] is True:
            continue
        done[cur] = True
        d2m = max(d2m, dist)
        for ad in g[cur]:
            if done is True:
                continue
            todo.append()

    print(d1m+d2m+1)


main()

E問題

E - Family and Insurance
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

感想

親→子への有向グラフと考えると、ちょっと前のコンテストと同じようにして解ける。
https://atcoder.jp/contests/abc305/tasks/abc305_e

ある人xにおいて、y世代先までの保険とz世代までの保険があったとする。この時、yとzの内大きい方の保険のみを探索すれば良い。このようなコードを実行するには、優先度の大きい順に探索しする。xに一度訪れたなら、そこからは探索しない。なぜなら、最初に訪れた時が一番優先度が高いから。このコードは、それぞれの頂点で一回ずつ、分岐は合計でM回あり、分岐のたびheqppushを行うので$log(M)$書いになる。なのでO(N+MlogM)になるので十分間に合う。

はずだった。。
提出してみると、TLEになった。

コンテスト中提出TLEコード

Submission #43377857 - Denso Create Programming Contest 2023 (AtCoder Beginner Contest 309)
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
import sys
import itertools
import math
import collections
import bisect
import heapq

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

INF = 10**18


def main():
    N, M = list(map(int, input().split()))
    p = list(map(int, input().split()))
    xy = [list(map(int, input().split())) for _ in range(M)]

    g = [[] for _ in range(N)]

    for i, pi in enumerate(p):
        g[pi-1].append(i+1)

    q = []
    for x, y in xy:
        heapq.heappush(q, [y*-1, x-1])

    done = [False] * N
    while q:
        y, x = heapq.heappop(q)
        if done[x] is True:
            continue
        done[x] = True
        for ad in g[x]:
            if done is True:
                continue
            if y != 0:
                heapq.heappush(q, [y+1, ad])

    ans = 0
    for i in range(N):
        if done[i] is True:
            ans += 1

    print(ans)


main()

色々試行錯誤して提出してなんとかACした。

コンテスト中提出コード

Submission #43388510 - Denso Create Programming Contest 2023 (AtCoder Beginner Contest 309)
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
import sys
import itertools
import math
import collections
import bisect
import heapq

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

INF = 10**18


def main():
    N, M = list(map(int, input().split()))
    p = list(map(int, input().split()))
    xy = [list(map(int, input().split())) for _ in range(M)]

    g = collections.defaultdict(list)

    for i, pi in enumerate(p):
        g[pi-1].append(i+1)

    q = []
    ns = [INF] * N
    xy.sort(key=lambda t: t[1], reverse=True)
    for x, y in xy:
        if ns[x-1] > (y*-1):
            heapq.heappush(q, (y*-1, x-1))
            ns[x-1] = y*-1

    done = [False] * N
    ans = 0
    while q:
        y, x = heapq.heappop(q)
        if done[x] is True:
            continue
        done[x] = True
        ans += 1
        for ad in g[x]:
            if done is True:
                continue
            if ns > y+1 and y != 0:
                ns = y+1
                heapq.heappush(q, (y+1, ad))

    print(ans)


main()

結局何が問題だったのか。

ギリギリで提出できたコードではtodoの中のlistをtupleに変更した。
上に載せた”コンテスト中提出TLEコード”のlistをtupleに変更してみると、ACした。
つまり、listだと遅く、tupleだと早いということが分かった。

list版
Submission #43377857 - Denso Create Programming Contest 2023 (AtCoder Beginner Contest 309)
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
tuple版
Submission #43401901 - Denso Create Programming Contest 2023 (AtCoder Beginner Contest 309)
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

反省

なんでもlistを使うのではなく、要素を変更しないのであればtupleを使う。

コメント

タイトルとURLをコピーしました