コンテスト
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.
atcoder.jp
A問題
A - Nine
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
感想
少し悩んだ。
とりあえず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.
atcoder.jp
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.
atcoder.jp
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.
atcoder.jp
感想
これも少し手間取ってしまった。
添字や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.
atcoder.jp
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.
atcoder.jp
感想
比較的すんなり解けた。
$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.
atcoder.jp
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.
atcoder.jp
感想
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.
atcoder.jp
感想
親→子への有向グラフと考えると、ちょっと前のコンテストと同じようにして解ける。
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.
atcoder.jp
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.
atcoder.jp
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.
atcoder.jp
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.
atcoder.jp
反省
なんでもlistを使うのではなく、要素を変更しないのであればtupleを使う。
コメント