AtCoderのABC309の解説 - rotti_coderのプログラミング

AtCoder Beginner Contest309のA~E問題までの解説を書いてみます。
質が…悪いと思うので…期待しないで…ください…
あと変数名がクソです。ごめんなさい。

コンテストのリンク→https://atcoder.jp/contests/abc309

A問題　Nine

少し場合分けをして考えます。
・A＜Bなので、Aが3,6,9のときは、Bの値によらず隣接していないとわかります。
・Aがそれ以外の値のときは、A

a,b=map(int,input().split())
if a==3 or a==6 or a==9:
  print("No")
else:
  if a+1==b:
    print("Yes")
  else:
    print("No")

B問題　Rotate

この問題は、特別なアルゴリズムは必要ありません。二次元リストに入力を格納して、まわりの値をひとつずつ時計回りにずらしていき、最後に二次元リストの中身を出力すればよいです。

pythonでの例（コードきれいじゃないとおもいます…）

n=int(input())
rotti = [[0] * 2 for i in range(n)]
def screen_out():
  global rotti
  for i in range(n):
    for ipp in range(n):
      print(rotti[i][ipp],end='')
    print()
for i in range(n):
  rotti[i]=list(input())
hako=rotti[0][0]
for i in range(n-1):
  hako2=rotti[0][i+1]
  rotti[0][i+1]=hako
  hako=hako2
for i in range(n-1):
  hako2=rotti[i+1][n-1]
  rotti[i+1][n-1]=hako
  hako=hako2
for i in range(n-1):
  hako2=rotti[n-1][n-2-i]
  rotti[n-1][n-2-i]=hako
  hako=hako2
for i in range(n-1):
  hako2=rotti[n-2-i][0]
  rotti[n-2-i][0]=hako
  hako=hako2
screen_out()

C問題　Medicine

最初に、１日目に飲むおくすりの量を計算します。その後、初日から近い順番に減っていくおくすりを減らして、K錠以下になるのが５日を計算します。
（説明が下手くそなので、例を使って説明します）
例えば、入力が以下の通りだったとします（入力例１と同じです）

このとき、それぞれのおくすりは何日目までのむ必要があるかというと
・１日間、９錠のおくすりを飲む必要がある
・２日間、５錠のおくすりを飲む必要がある
・４日間、２錠のおくすりを飲む必要がある
・６日間、３錠のおくすりを飲む必要がある

また、１日目は19錠のおくすりを飲む必要があります。
このとき、おくすりが減る日を順番に見ていくと

・二日目は、10錠のお薬を飲む必要がある
→ｋの値である８錠以下ではないので、答えは二日目ではない
・三日目は５錠のおくすりを飲む必要がある
→ｋの８錠以下なので、答えは三日目である

…説明になっているかどうかわからないのですが、とにかくこのように飲む必要のあるおくすりの量が減る日を見ていけば、答えがわかります。（飲む必要のあるおくすりが減る日も減らない日も見ていくと、TLEになってしまうので、そこは注意）

また、その日に飲む必要のあるおくすりの量をそれぞれ計算していてもTLEになるので、最初に計算してから、少しずつその値を減らしていくという方法でやる必要があります。

pythonでの例

n,k=map(int,input().split())
rotti = [[0] * 2 for i in range(n)]
amount=0
for i in range(n):
  rotti[i]=list(map(int,input().split()))
  amount+=rotti[i][1]
if k>=amount:
  print(1)
  exit()
rotti=sorted(rotti)
check=1
for i in range(n):
  amount-=rotti[i][1]
  if amount<=k:
    print(rotti[i][0]+1)
    break

D問題　Add One Edge

この問題は、幅優先探索というアルゴリズムを使います。頂点１からと、N１＋N２の頂点からそれぞれからBFS（幅優先探索）を行い、それぞれの最大値と、新しく付け足す辺１を足したのが、出力すべき答えとなります。
…しかし、幅優先探索について知らない人も多いと思います。そこで、幅優先探索について軽く説明したいと思います。（期待しないでね…）

幅優先探索は、グラフの問題のときなどに使うアルゴリズムです。何をするアルゴリズムなのかというと、ある頂点から、ある頂点まで、何回の移動で行くことができるのかを求めることができるアルゴリズムです。例を使って説明します。

このとき、Sの頂点がスタートする頂点です（もとからいる頂点）。最初からいるので、この頂点への移動回数は、最長でも０です。ですので、グラフにこう書き込みます。>

また、この頂点ととなりあっている頂点は、一回の移動で行くことができます。ですので、以下のように、０＋１の１を書き込んでいきます。

このように作業を続けていくと、下のような場面になります

このように、一つの頂点に対して、二通りの行き方があることがあります。今回は、最小の移動方法を求める必要があるので、短い方の「２」を採用します。すると、最終的に

となり、３回が最長の長さだとわかります（最短の方法で移動したとき）。
これを、N1+N2の頂点からも行うことによって、答えを求めることができます。
pythonでの例

a,b,m=map(int,input().split())
rotti = [[] * 1 for i in range(a+b)]
for i in range(m):
  x,y=map(int,input().split())
  rotti[x-1].append(y)
  rotti[y-1].append(x)
#頂点1からの最長パス
hako=[1000000]*a
hako[0]=0
stack=[1]
iti=0
irane=set()
irane.add(1)
while len(stack)-1>=iti:
  for i in range(len(rotti[stack[iti]-1])):
    if not rotti[stack[iti]-1][i] in irane:
      irane.add(rotti[stack[iti]-1][i])
      stack.append(rotti[stack[iti]-1][i])
      hako[rotti[stack[iti]-1][i]-1]=hako[stack[iti]-1]+1
  iti+=1
hako=sorted(hako)
amount=hako[len(hako)-1]
#頂点最大からの最長パス
hako=[1000000]*b
hako[b-1]=0
stack=[a+b]
iti=0
irane=set()
irane.add(a+b)
while len(stack)-1>=iti:
  for i in range(len(rotti[stack[iti]-1])):
    if not rotti[stack[iti]-1][i] in irane:
      irane.add(rotti[stack[iti]-1][i])
      stack.append(rotti[stack[iti]-1][i])
      hako[rotti[stack[iti]-1][i]-1-a]=hako[stack[iti]-1-a]+1
  iti+=1
hako=sorted(hako)
print(amount+hako[len(hako)-1]+1)

E問題　Family and Insurance

※ますます説明がクソになっている気がします。ごめんなさい

この問題は、D問題を解けた人なら大体解けると思います。この問題も、D問題を解くときに使用したDFS（幅優先探索）というアルゴリズムを使用するからです。

まず最初に、標準入力を整理します。それぞれの頂点からかけた保険の中で、一番先の世代まで有効な保険だけをまとめます。
↓こんな感じ

n,m=map(int,input().split())
p=list(map(int,input().split()))
saidai=[-1]*n
for i in range(m):
  x,y=map(int,input().split())
  saidai[x-1]=max(saidai[x-1],y)
print(saidai)

また、入力例１はこのようになっています。

7 3
1 2 1 3 3 3
1 1
1 2
4 3

このコードを、入力例１に使うと、以下の通りに出力されます。

[2, -1, -1, 3, -1, -1, -1]

人ｎに保険がかけられていない場合、ｎ番目の値は−１になっています。また、人１には、２つの保険がかけられていますが、２世代先までが対象となっている保険のほうが、対象とする世代数が大きいので、１番目の値は２になっています。
この配列を使っていきます。

問題文の制約にも書いてありますが、人ｎの親は必ずｎよりも小さい値の人です。グラフは親から子へしか向いていないので、値の大きいところから順番に処理していってよいのです。
流れ的にはだいたいこんなイメージです↓
・人１にかかってる保険をDFSする。D問題とは違って、値をどんどん減らしていく（↓こんな感じに）

・DFSでたどりついた頂点（人）に、保険がかかっていた場合、対象となる世代数が大きかった方を採用する（頂点に書き込んでいる数）。
・最終的に、０以上の値が書き込まれた頂点（人）には保険がかかっている事がわかる。

実際にグラフを書いて、数字を書き込んでみるのもいいかもしれないです。

pythonの例

n,m=map(int,input().split())
p=list(map(int,input().split()))
dfs=[]
rotti = [[] * 1 for i in range(n)]
for i in range(len(p)):
  rotti[p[i]-1].append(i+2)
saidai=[-1]*n
for i in range(m):
  x,y=map(int,input().split())
  saidai[x-1]=max(saidai[x-1],y)
#ここから、DFSをしまくる
for i in range(len(saidai)):
  if saidai[i]==-1:
    continue
  for ipp in range(len(rotti[i])):
    saidai[rotti[i][ipp]-1]=max(saidai[rotti[i][ipp]-1],saidai[i]-1)
amount=0
for i in range(len(saidai)):
  if saidai[i]>=0:
    amount+=1
print(amount)

ありがとうございました

↓↓自分の書いたページをまとめてるところ
rotti-coder.hatenablog.com

A問題 Nine

B問題 Rotate

C問題 Medicine

D問題 Add One Edge

E問題 Family and Insurance

A問題　Nine

B問題　Rotate

C問題　Medicine

D問題　Add One Edge

E問題　Family and Insurance