ABC309

今日も反省します。
今回はABC309(https://atcoder.jp/contests/abc309).

A

1から9までの数字が書かれた3×3の盤面で与えられた2つの数字が左右で隣り合うかの判定問題。商とあまりを計算して、処理した。左右なので、上下の隣り合いは含まれないので注意。

A, B = map(int,input().split())

a_r = (A-1) // 3
a_c = (A-1) % 3
b_r = (B-1) // 3
b_c = (B-1) % 3

if a_r == b_r:
  if A+1 == B:
    print("Yes")
  else:
    print("No")
else:
  print("No")

B

与えられたN×Nの行列に対し、外側の部分(1行目、N行目、1列目、N列目)を時計回りに一つずつ動かす。Nも大きくて100め、単純に答え用配列にずらしたものを愚直にループを使って格納して最後に表示した。

N = int(input())
l = [input() for _ in range(N)]
ans = []
for i in range(N):
  a = ""
  if i == 0:
    a += l[1][0]
    for j in range(N-1):
      a += l[0][j]
  elif i == N-1:
    for j in range(N-1):
      a += l[-1][j+1]
    a += l[-2][-1]
  else:
    a += l[i+1][0]
    for j in range(N-2):
      a += l[i][j+1]
    a += l[i-1][-1]
  ans.append(a)
for a in ans:
  print(a)

C

渡された薬の服用日数と1日あたりの服用個数をもとに、条件として与えられた服用個数以下になるのは何日目かを答える。辞書式配列と普通の配列を作り、辞書式配列には服用日数とその個数を紐付け、普通の配列には服用日数のみを格納した。辞書式配列でわざわざ紐付けた理由としては、同じ服用日数のものをまとめて処理するため。その後、服用日数を格納した配列で昇順にソートし、合計数から引いていくことで、条件を満たすのが何日目かを判定した。

N, K = map(int, input().split())
M = 0 #初期最大個数
l = {}
key = []
for i in range(N):
  a, b = map(int, input().split())
  M += b
  if a in l:
    l[a] += b
  else:
    key.append(a)
    l[a] = b
key.sort()
if M <= K: #初日から条件を満たしていた時
  print(1)
else:
  for i in key:
    M -= l[i]
    if M <= K:
      print(i+1)
      break

D

二つの無向グラフが与えられ、それぞれのグラフで指定された頂点の最短経路が最大となるように二つのグラフを連結させる辺を加えたとき、その最大値はいくつかを調べる問題。各グラフで最短経路が最長となる頂点を結べばよいため、方針としてはそれを調べていくことになる。コンテスト中は、幅優先で求めていこうとしたが、最短経路に必要な辺の数をどのようにカウントするかわからず、それっぽいものを作ったが実行時間エラーによって不正解となった。
解説をもとに以下のコードで実行時間エラーを解消できた。辺の数を求める方法として、頂点の数の長さを持つ配列(今回はa_p)を作り、初期値として各要素に-1を与え、開始地点に0を与える。その後、辞書型配列lとして作った到達可能なリストをもとに幅優先探索を行う。この時に、未到達の頂点に到達した場合にa_pを更新を行うことで、各頂点への最短経路を求める。例えば、頂点xから頂点yに移動した場合、頂点yが未到達(つまりa_p[y]=-1)だった時、頂点xまでの最短経路(a_p[x])に1を加えたものが最短経路となる。それぞれのグラフについて求めたのち、それらと、グラフをつなげる辺1つの和が答えとなる。

X, Y, M = map(int, input().split())
l = {1:[], X+Y:[]}
#経路リスト生成
for i in range(M):
  a,b = map(int, input().split())
  if a in l:
    l[a].append(b)
  else:
    l[a] = [b]
  if b in l:
    l[b].append(a)
  else:
    l[b] = [a]

#最長最短経路導出
p_list = [1]
a_p = [-1 for _ in range(X+Y+1)]
a_p[1] = 0
for p in p_list:
  for np in l[p]:
    if a_p[np] == -1:
      a_p[np] = a_p[p] + 1
      p_list.append(np)
cnt_s = max(a_p)

p_list = [X+Y]
a_p = [-1 for _ in range(X+Y+1)]
a_p[X+Y] = 0
for p in p_list:
  for np in l[p]:
    if a_p[np] == -1:
      a_p[np] = a_p[p] + 1
      p_list.append(np)
cnt_e = max(a_p)

print(cnt_s+cnt_e+1)

解説をもとに作成したが、最初は実行エラーがいくつか出てしまった。理由としては、経路リストの辞書型配列に1とX+Yの初期値を与えていなかったため、1やX+Yにつながる経路が存在しなかった場合に最短経路導出の段階で参照元に到達できずエラーになっていたと考えられる。そのため、2行目のように直すことで動作することを確認できた。

反省・感想

Aで勝手に上下の条件を付けて3回WAだしたせっかちさに自分でもさすがに引きました。そのほかは、Dが悔しかったなと。到達判定と、辺の数を同時に行っていくあたり賢いなと感心していました。コンテスト中は、到達済みリストを作って検索して判定したり、辺の数ごとに配列でまとめてpop用のリストに入れて何とか辺の数を求めていましたので、それは時間かかりますよね。。。
柔軟に対応できるように頭を柔らかくして、次回も頑張ります。

現在レート:735 → ???? (まぁさがります。はい。)