ABC319の解説

ABC319のA~D問題の解説

A問題　Legendary Players

この問題は愚直に組むしかありません。いかに早く解くか…がコンテストでは大事でした。

（ちなみにぼくは、めちゃくちゃぐだって12分かかった上に、ペナを一つもつけてしまいました…）

Pythonの例

s=input()
if s=="tourist":
  print(3858)
if s=="ksun48":
  print(3679)
if s=="Benq":
  print(3658)
if s=="Um_nik":
  print(3648)
if s=="apiad":
  print(3638)
if s=="Stonefeang":
  print(3630)
if s=="ecnerwala":
  print(3613)
if s=="mnbvmar":
  print(3555)
if s=="newbiedmy":
  print(3516)
if s=="semiexp":
  print(3481)

B問題　Measure

少し問題を読むのが難しかったです。すべての数字を全探索していけばよいです。

n=int(input())
rotti=[]
for i in range(1,10):
  if n%i==0:
    rotti.append(i)
print(1,end='')
for i in range(1,n+1):
  for ipp in rotti:
    if i%(n//ipp)==0:
      print(ipp,end='')
      break
  else:

    print("-",end='')
print()

C問題　False Hope

少し解き方を思いつくのが難しかったです。難しいアルゴリズムは考えずに、置き方を全探索していけばよいです。

D問題　Minimum Width

この問題は二分探索で解くことができます。

ウィンドウの横幅として、ある数値がM行に収まるかどうか…ということを繰り返していきます

n,m=map(int,input().split())
p=list(map(int,input().split()))
#二分探索
a=max(p)
b=sum(p)+n+500000000000
if m==len(p):
  print(max(p))
  exit()
for i in range(1999999999999999999999999999999999999999):
  mokuteki=(a+b)//2
  count=p[0]
  line=1
  check=0
  for ipp in range(1,len(p)):
    if count+1+p[ipp]>mokuteki:
      count=p[ipp]
      line+=1
      if line>m:
        check=1
        break
    else:
      count=count+p[ipp]+1
  if line>m:
    a=mokuteki
  elif line<=m:
    b=mokuteki
  if a+1==b:
    break
ans=b
#ここから下げられるかチャレンジ
check=0
mokuteki=ans-1
a=max(p)
while check==0:
  count=p[0]
  line=1
  for i in range(1,len(p)):
    if count+p[i]+1>mokuteki:
      count=p[i]
      line+=1
      if line>m:
        print(ans)
        exit()
    else:
      count+=1+p[i]
  ans=mokuteki
  mokuteki-=1
  if mokuteki<a:
    print(ans)
    exit()

ぼくはこのコンテストでは、A問題とB問題とC問題すべてで死ぬほどぐだって、その後D問題とE問題見たとき全然解き方がわからなくって死ぬほどつらかったです。Perfがとても低くて、このままだとレートがめちゃくちゃ下がってしまう…と、死ぬ気でE問題の解き方を考えて、なんとか二分探索の解き方を思いつきました。ACが出たときは死ぬほど嬉しかったです〜

最後までありがとうございました。

rotti-coder.hatenablog.com