初めに
AtCoderに参加した記録を残します。どのような考察をしながら問題に取り組んだかを記録していますので、必ずしも教育的なコードとは限りません。
始めたばかりの人など、どなたかの助けになれば嬉しいです。
コメントなどいただけると嬉しいです！！
成績
ABC309 4冠。
久々にDまで解けた気がする。
目次
A - Nine
B - Rotate
C - Medicine
D - Add One Edge
E - Family and Insurance
A - Nine
問題ページ
1〜9までの数字が左上から右下にかけて規則正しく並んでいる様な場合に、1〜9の異なる数字X, Yは左右に隣り合っているかを判定する問題。
コンテスト中の考察
盛大に読み飛ばして上下左右だと思っていたせいで1〜9をkey、その隣接をvalueにする辞書作ってめちゃくちゃなことしていたんだが、途中で気がついてmod3の結果で処理を変えるコードに変更しAC。
A%3==1（左端）ならBはA+1しか許さない、といった様にAをmodで分類すればBは一意に定まることがわかる。
余計なことしてたせいでA問題で9分も使った…
コンテスト中のコード
A, B = map(int, input().split())
if A % 3 == 1:
if B == A+1:
print('Yes')
else:
print('No')
elif A % 3 == 2:
if abs(A-B) == 1:
print('Yes')
else:
print('No')
else:
if B+1 == A:
print('Yes')
else:
print('No')
改善点
着想面
問題文読み返したら A<B だった...。
この制約の下ではAがBの右端にあることしか許さないので、賢いことはやらずにパターン全部列挙するのが賢いかもしれない。
コード面
A, B = map(int, input().split())
if (A,B) in {(1,2),(2,3),(4,5),(5,6),(7,8),(8,9)}:
print('Yes')
else:
print('No')
B - Rotate
問題ページ
N×Nの行列の一番外枠の要素だけ時計回りに回転させる問題。
コンテスト中の考察
いやぁ、一番難しかったまである。30分くらいかかりました。
A問題と似た感じで、Nでmodを取った結果で処理を変更 した。i, jに対してmodNの結果が0かN-1かで左端, 右端, 上端, 下端 を分類可能。
これに気づくまでにも少し時間かかったし、何より実装でindexが頭の中で爆発した。もう少し効率の良い方法は流石にありそう。
コンテスト中のコード
import copy
N = int(input())
A = [list(map(int, input())) for _ in range(N)]
B = copy.deepcopy(A)
for i in range(N):
for j in range(N):
if i % N == 0:
if j % N == 0:
B[i][j] = A[i+1][j]
else:
B[i][j] = A[i][j-1]
elif i % N == N-1:
if j % N == N-1:
B[i][j] = A[i-1][j]
else:
B[i][j] = A[i][j+1]
elif j % N == 0:
B[i][j] = A[i+1][j]
elif j % N == N-1:
B[i][j] = A[i-1][j]
for i in range(N):
print(*B[i], sep = '')
改善点
着想面
参考tweet
2Dゲームのノウハウを活用すると効率的に解けたっぽい。
これめっちゃ頭いいな。座標を全部舐めるのではなく、外周を一周する感じで開店後行列を埋めていく感じなんだが、directionでループ回すことによって余計な場合わけを防ぐことができている。
コード面
import copy
N = int(input())
A = [list(map(int, input())) for _ in range(N)]
B = copy.deepcopy(A)
x = 0
y = 0
dx = [1,0,-1,0]
dy = [0,1,0,-1]
for d in range(4):
while 1:
nxt_x = x + dx[d]
nxt_y = y + dy[d]
if nxt_x < 0 or nxt_x >= N or nxt_y < 0 or nxt_y >= N:
break
B[nxt_y][nxt_x] = A[y][x]
x, y = nxt_x, nxt_y
for i in range(N):
print(*B[i], sep = '')
C - Medicine
問題ページ
N種類の薬それぞれの継続して飲まなければいけない日数と錠数が与えられ、飲むべき薬の錠数がK以下になる日数を求める問題。
コンテスト中の考察
着想は結構わかりやすかったと思う。日数で昇順sortして、
(薬の総数-飲まなくて良くなった錠数)<= K
になったらその日数を出力すれば良い。特定の軸でのsortはkeyを指定することで実装可能。
最初の段階で飲むべき錠数が既にK以下の場合もあるのでその処理だけ注意。
これ、二分探索でもいけたっぽい。
コンテスト中のコード
N, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
n_med = 0
for i in range(N):
n_med += AB[i][1]
AB = sorted(AB, key=lambda x: x[0])
if n_med <= K:
print(1)
exit()
for i in range(N):
day = AB[i][0]+1
n_med -= AB[i][1]
if n_med <= K:
print(day)
exit()
改善点
着想面
特になし
コード面
特になし
D - Add One Edge
問題ページ
1〜N_1までのノードによる連結グラフとN_1+1〜N_2までのノードによる連結グラフが与えられ、この二つの連結グラフに一つ辺を加えた場合のノード1からノードN_1+N_2までの最短距離を最大化する問題。
コンテスト中の考察
最初UnionFindかなぁとか思ったけど、最短経路とか書いてあるし違うなってなった。
問題を読み直してよくよく考えると、最短距離の最大化なので既に与えられている2つの連結グラフ（1〜N_1の連結グラフをG1、N_1+1〜N_2の連結グラフをG2とする）は最短で移動するしか選択肢がなく、最大化はG1とG2のどの頂点を選んで連結させるかに依存している。つまり、G1とG2それぞれで、最短経路を選択してもなお最も効率の悪いノード同士を連結させればいいことがわかる。最終的にはノード1からノードN_1+N_2までの最短経路を求めたいので、G1ではノード1から最も到達効率の悪いノード 、G2ではノードN1_+N_2から最も到達効率の悪いノード を連結すれば最短経路の最大化ができることがわかる。
G1, G2の到達効率はそれぞれノード1, ノードN_1+N_2を開始点とするBFSで計算可能である。
コンテスト中のコード
from collections import deque
N1, N2, M = map(int, input().split())
G = [[] for _ in range(N1+N2)]
for _ in range(M):
a, b = map(int, input().split())
G[a-1].append(b-1)
G[b-1].append(a-1)
D = [-1]*(N1+N2)
D[0] = 0
q = deque([0])
while q:
u = q.popleft()
for v in G[u]:
if D[v] == -1:
D[v] = D[u]+1
q.append(v)
d1 = 0
for i in range(N1):
d1 = max(d1, D[i])
D[N1+N2-1] = 0
q = deque([N1+N2-1])
while q:
u = q.popleft()
for v in G[u]:
if D[v] == -1:
D[v] = D[u]+1
q.append(v)
d2 = 0
for i in range(N1, N1+N2):
d2 = max(d2, D[i])
print(d1+d2+1)
改善点
着想面
特になし
コード面
特になし
E - Family and Insurance
問題ページ
親と子の関係が与えられ、人xがy世代先まで保証される保険に入る場合、何人に保険が適用されるかを求める問題。
コンテスト中の考察
木を辿っていけば普通にいけそうじゃね？と思ったけど、普通にやると多分効率悪すぎてTLEするからメモ化再帰的なことをしなきゃいけない気がするんだが、何世代先までみたいなパラメータがあるせいで既に見ているからbreak！みたいなことができなくてうまく効率化できなさそうだったので諦め。
改善点
着想面
余裕があったら記事修正するかも。
コード面
終わりに
書き始めたばかりで拙い部分も多いですが、みなさんと楽しく盛り上がれたらいいなと思っていますので、今後ともよろしくお願いいたします！
いいね等していただけるととても励みになります！