ABC315の解説 - rotti_coderのプログラミング

ABC315のA～C、E問題の解説

A問題　tcdr

この問題は、まずは入力を受け取り、その後一文字ずつ見ていきます。もしt,c,d,rだった場合は出力しないようにします。
僕は、一文字ずつ出力していき、t,c,d,rだった場合は出力せずにcontinueとしました。

a=["a","e", "i", "o", "u"]
a=set(a)
s=list(input())
for i in range(len(s)):
  if s[i] in a:
    continue
  print(s[i],end='')
print()

B問題　The Middle Day

まず先に、一年の日数を計算します。そして、ちょうど半分の日は何日目かをもとめます。
あとは愚直に計算していきます。次の月の間に目的の日がなければ、その月をスルー、もし目的の日があれば答えを出力…みたいなかんじにします。

この問題も、けっこう”やるだけ”という感じがします。

Pythonの例

m=int(input())
d=list(map(int,input().split()))
a=sum(d)//2
for i in range(m):
  if a-d[i]>=0:
    a-=d[i]
  else:
    iti=i
    break
print(iti+1,a+1)

C問題　Flavors

全探索しなきゃ…と思った人もいるかもしれませんが、この問題はそんなことをしなくても解けるのです。

まず、それぞれのアイスをオイシイ順番に並び替えます。この時、一番おいしいアイスと二番目においしいアイスの味が違う場合は、そのおいしさの合計が最高のおいしさになるので、それを出力し、プログラムを終了させます。

もし一番おいしいアイスと二番目においしいアイスの味が同じだった場合は、他によりおいしく食べられる方法があるかもしれません。

この時、もし他においしいアイスの味があるのなら、一番おいしいアイスを使ったのが一番おいしくなります（説明するのが難しくて…でもよく考えてみたらわかると思います!!）。

ですから、一番おいしいアイスと味が違う中でいちばんおいしさの値が高いアイスを食べるようにすれば、最高のおいしさがわかります。

（なんかおいしさと味の使い分けがうまくいってないかも…）
Pythonの例

n=int(input())
rotti=[[0] * 2 for i in range(n)]
for i in range(n):
  a,b=map(int,input().split())
  rotti[i][0]=b
  rotti[i][1]=a
rotti=sorted(rotti)
if rotti[n-1][1]!=rotti[n-2][1]:
  print(rotti[n-1][0]+rotti[n-2][0])
  exit()
saidai=rotti[n-1][0]+rotti[n-2][0]//2
hako=rotti[n-1][1]
for i in range(n):
  if rotti[n-1-i][1]!=hako:
    saidai=max(saidai,rotti[n-1-i][0]+rotti[n-1][0])
    break
print(saidai)

E問題　Prerequisites

※僕は非再帰でやっているのでもしかしたら普通の解き方ではないかもしれません…

この問題は、まずはDFSをして、読む必要のある本の番号を入手します。

その後、逆向きにDFSをします。この時、スタートする地点をあらかじめ設定しておきます。
スタートする地点は、他の本を読まなくても、その本を読むことができるという本です。

ここからDFSをしていくのですが、その時進んでいく本にも気を付けます。
もし、その本を読むには必要な前提知識が足りてない状態でいってしまうと、めんどうなことになるので、その本に行く前に他に読むことが必要な本をすべて読んでおきます。

ですから、DFSをしたときに、行った頂点（本）からつながりのある本のうち、もうすでに読むことができるようになった頂点（本）しか行かないようにします。

こうすることによってうまくいきます！！

とにかく説明が下手くそな気がしますが…なんとなく参考にでもなれば…

Pythonの例

n=int(input())
rotti=[[] * 1 for i in range(n)]
for i in range(n):
  a=list(map(int,input().split()))
  for ipp in range(1,a[0]+1):
    rotti[i].append(a[ipp])
#幅優先探索
stack=[1]
iti=0
irane=set(stack)
while len(stack)>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])
  iti+=1
amount=[0]*n
task=[]
stack=[]
for i in range(n):
  if not i+1 in irane:
    task.append(100000000000000000000)
    continue
  
  task.append(len(rotti[i]))
  if task[i]==0 and i+1 in irane:
    stack.append(i+1)

iti=0

#逆に幅優先探索するための二次元配列の作成
rotti2=[[] * 1 for i in range(n)]
for i in range(len(rotti)):
  for ipp in range(len(rotti[i])):
    rotti2[rotti[i][ipp]-1].append(i+1)

while len(stack)>iti:
  for i in range(len(rotti2[stack[iti]-1])):
    amount[rotti2[stack[iti]-1][i]-1]+=1
    if amount[rotti2[stack[iti]-1][i]-1]==task[rotti2[stack[iti]-1][i]-1]:
      stack.append(rotti2[stack[iti]-1][i])
  iti+=1
print(*stack[0:len(stack)-1])

最後までありがとうございました！今回も説明が下手くそだった気がしますが、すこしでもみんなの役にたてばうれしいです！！

また、D問題はもう少しで解けそうなので、解説を追加するかもしれないです～

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

ABC315のA～C、E問題の解説

A問題 tcdr

B問題 The Middle Day

C問題 Flavors

E問題 Prerequisites

A問題　tcdr

B問題　The Middle Day

C問題　Flavors

E問題　Prerequisites