結果
新年初のABC。ノーペナ4完でした。
温まったので良し。
各問題の感想・解法
A問題
誤読してました。
文字列の中で、最後に現れる2023を2024に変換かと勘違いしてました。
そのせいで少し時間食ったの勿体ない。
以下コード
s = input() tmp = 0 for i in range(len(s)-3): if s[i:i+4] == '2023': tmp = i print(s[:tmp]+"2024"+s[tmp+4:])
B問題
制約小さいので全探索をそのまま書きました。
以下コード
def II(): return int(input()) n = II() for i in range(n+1): for j in range(n+1): for k in range(n+1): if i+j+k <= n: print(i,j,k)
C問題
頭に追従して体は動くことから、頭の動きのみシミュレーションすればよい。
また、各パーツと頭との距離の分だけ、遡った座標がパーツの座標と一致する。
普段の二次元平面探索時の上下左右の座標の差分と異なっていたため、その修正も必要で少してこずった。
以下コード
def MII(): return map(int, input().split()) n,q = MII() a = [] for i in range(n,0,-1): a.append((i,0)) around4 = ((0,1), (0, -1), (-1, 0), (1, 0)) UDLR = {"U":0,"D":1,"L":2,"R":3} x,y = 1,0 for i in range(q): u,v = input().split() if u == "1": v = UDLR[v] a.append((x+around4[v][0],y+around4[v][1])) x += around4[v][0] y += around4[v][1] if u == "2": print(*a[int(v)*-1])
D問題
サンプルに実質答えがあり、それを頑張って実装する。
右->下->左->上の動きをN//2回繰り返せば良いので、指定した方向にぶつかるまで更新を続ける関数を作って、それを各方向に呼び出すことで実装した。
以下コード
around4 = ((-1, 0), (1, 0), (0, -1), (0, 1)) # 上下左右 def II(): return int(input()) n = II() ans = [["T"]*n for _ in range(n)] def guru(x,y,vec): num = ans[x][y] while is_not_Index_Er(x+around4[vec][0],y+around4[vec][1],n,n) and ans[x+around4[vec][0]][y+around4[vec][1]] == "T": ans[x+around4[vec][0]][y+around4[vec][1]] = num+1 num += 1 x,y = x+around4[vec][0],y+around4[vec][1] return x,y ans[0][0] = 1 x,y = 0,0 for i in range(n//2): x,y = guru(x,y,3) x,y = guru(x,y,1) x,y = guru(x,y,2) x,y = guru(x,y,0) for i in ans: print(*i)
E問題
とりあえずDFSで実装->TLE->知ってた。
使ったことはなかったが、名前は知っていたのでダイクストラのコードをqiitaからコピペして修正してみる。色々と直しているうちにサンプルは通る->提出->TLE。
それ以外の解法は思いつかないので、高速化を試みる。
最初は無方向グラフとして入力されたものを全て隣接リストに保存していたが、広義増加していない場合は保存しないようにする。->少なからず高速化はできているはずだがTLE。
コンテスト時間はこれで終了。
解説を読むとDPのようだが、読んでも理解できないし、水上位パフォということで解説ACは諦め、どうにかダイクストラで通せないか考えてみる。
heapqから取り出したノードの持つ整数の種類数が、そのノードの持つ現時点でベストな整数の種類数未満の場合、探索を続ける意義がないので、その場合はその時点で探索を打ち切ることで、無事AC。
何とか通せたものの、ダイクストラをほぼ理解できていないまま適当に実装したものが何故か通った、というのが率直な感想なので、ダイクストラ法についても追々勉強しようと思います。
以下コード
def MII(): return map(int, input().split()) def LMII(): return list(map(int, input().split())) n,m = MII() a = LMII() dd = defaultdict(list) for i in range(m): u,v = MII() if a[v-1] >= a[u-1]: dd[u].append((v,a[v-1])) if a[u-1] >= a[v-1]: dd[v].append((u,a[u-1])) import heapq def dijkstra(edges, num_node): node = [0] * num_node node[0] = 1 node_name = [] #頂点の値、場所、種類数 heapq.heappush(node_name, [a[0],1,1]) while len(node_name) > 0: print(node_name) #ヒープから取り出し val, pos,num = heapq.heappop(node_name) if num < node[pos-1]: continue for factor in edges[pos]: goal = factor[0] #次の頂点 cost = factor[1] #頂点の値 #更新条件 if val < cost and node[goal-1] <= num : node[goal-1] = num + 1 #更新 #ヒープに登録 heapq.heappush(node_name, [a[goal-1], goal,num+1]) elif val == cost and node[goal-1] < num: node[goal-1] = num heapq.heappush(node_name, [a[goal-1], goal,num]) return node print(dijkstra(dd,n)[-1])
