ABC333 A~E問題

ABC333

atcoder.jp

A問題　Three Threes

愚直に実行！

python

n=int(input())
for i in range(n):
  print(str(n),end='')
print()

B問題　Pentagon

気合で条件分岐しました。
Twitterなどで見かけましたが、いい感じの文字列を作り与えられた入力が部分文字列化どうかで判定するスマートなやり方もあるそうですね。

Python

a=list(input())
a=sorted(a)
hako=""
for i in range(2):
  hako+=a[i]
a=0
if hako=="AB":
  a=1
elif hako=="AE":
  a=1
elif hako=="AC":
  a=2
elif hako=="AD":
  a=2
elif hako=="BC":
  a=1
elif hako=="BD" or hako=="BE":
  a=2
elif hako=="CD":
  a=1
elif hako=="CE":
  a=2
elif hako=="DE":
  a=1
b=list(input())
b=sorted(b)
hako=""
for i in range(2):
  hako+=b[i]
b=a
a=0
if hako=="AB":
  a=1
elif hako=="AE":
  a=1
elif hako=="AC":
  a=2
elif hako=="AD":
  a=2
elif hako=="BC":
  a=1
elif hako=="BD" or hako=="BE":
  a=2
elif hako=="CD":
  a=1
elif hako=="CE":
  a=2
elif hako=="DE":
  a=1

if a==b:
  print("Yes")
else:
  print("No")

C問題　Repunit Trio

全列挙が間に合う制約です。

rotti=[]
count=1
for i in range(100):
  rotti.append(count)
  count*=10
  count+=1

hako=[]
for i in range(100):
  for ipp in range(100):
    hako.append(rotti[i]+rotti[ipp])
hako2=[]
for i in range(len(hako)):
  for ipp in range(len(rotti)):
    hako2.append(hako[i]+rotti[ipp])
hako2=sorted(list(set(hako2)))
n=int(input())
print(hako2[n-1])

D問題　Erase Leaves

１から出ている木それぞれをまるごと消すのに何回操作する必要があるかを計算し、一番操作が必要な木ひとつを除き、全て削除すればいいです。

何回操作する必要があるかを求めるには、端の葉からDPを行えばよいです。

n=int(input())
rotti=[[]*1 for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  rotti[a-1].append(b)
  rotti[b-1].append(a)
if len(rotti[0])==1:
  print(1)
  exit()
iti=0
amount=[[1,0]*1 for i in range(n)]
stack=[]
irane=set()
ans=[]
for i in range(1,n):
  if len(rotti[i])==1:
    stack.append(i+1)
    irane.add(i+1)
while len(stack)>iti:
  hako=stack[iti]
  if hako==1:
    iti+=1
    continue
  for i in range(len(rotti[hako-1])):
    if rotti[hako-1][i] in irane:
      continue
    if rotti[hako-1][i]==1:
      ans.append(amount[hako-1][0])
      continue
    amount[rotti[hako-1][i]-1][0]+=amount[hako-1][0]
    amount[rotti[hako-1][i]-1][1]+=1
    if amount[rotti[hako-1][i]-1][1]==len(rotti[rotti[hako-1][i]-1])-1 and rotti[hako-1][i]!=1:
      stack.append(rotti[hako-1][i])
      irane.add(rotti[hako-1][i])
  iti+=1
ans=sorted(ans)
print(sum(ans)-ans[len(ans)-1]+1)

E問題　Takahashi Quest

先に入力をすべて受けとり、ポーションとモンスターで分けてそれぞれのタイプごとにいつ発生するかを配列などにまとめておきます。

一度に持つ量の最大値を最小化するのが目標なので、できるだけ一つのポーションをもっている時間を短くしたいです。ですから、タイプXのモンスターが発生する時、それよりも前の中で一番最近でポーションを入手できるときに入手するようにします。

このような貪欲で解くことができます。

import bisect
n=int(input())
potion=[[]*1 for i in range(n)]
monster=[[]*1 for i in range(n)]
hako2=[]
for i in range(n):
  a,b=map(int,input().split())
  if a==1:
    potion[b-1].append(i)
    hako2.append(i+1)
  else:
    monster[b-1].append(i)
check=0
ans=[]
for i in range(n):
  if len(monster[i])==0:
    continue
  if len(monster[i])>len(potion[i]):
    check=1
    break
  a=len(monster[i])-1
  hako=len(potion[i])
  for ipp in range(len(potion[i])):
    if potion[i][hako-ipp-1]<monster[i][a]:
      ans.append([potion[i][hako-ipp-1],1])
      ans.append([monster[i][a],2])
      a-=1
      if a==-1:
        break
  if a>=0:
    check=1
    break
if check==1:
  print(-1)
  exit()
ans=sorted(ans)
count=0
rotti=0
for i in range(len(ans)):
  if ans[i][1]==1:
    count+=1
    rotti=max(rotti,count)
  else:
    count-=1
print(rotti)
rotti=set()
for i in range(len(ans)):
  if ans[i][1]==1:
    rotti.add(ans[i][0]+1)
ans=[]
for i in range(len(hako2)):
  if hako2[i] in rotti:
    ans.append(1)
  else:
    ans.append(0)
print(*ans)

ちなみに二分探索を使いました。

rotti-coder.hatenablog.com