ABC317

ABC317のA~C、E問題までの解説

D問題は後からぜったいに追加します。ちょっと今は忙しくて……説明を書くのが大変で…
毎回のことながらコードはむちゃくちゃ読みにくいと思います……それに解説も……

A問題　Potions

最初に、最小の値を格納する変数を用意しておきます。
その後、一つずつポーションを見ていきます。それぞれのポーションを見ていくとき、下のような処理をします。
・このポーションを使うと体力はＸ以上になるのか。
→もし体力がＸ以上になるのなら、最小値の値を格納している変数とくらべ、より小さいほうをまた格納します　　min(saisyou,p[i]).....みたいな。

最終的に、体力がX以上になるポーションの中で、一番回復量が少ないポーションの番号を出力すればよいです。

Pythonの例

import bisect
n,h,x=map(int,input().split())
p=list(map(int,input().split()))
saisyou=100000000000000000000000
a=x-h
for i in range(n):
  if p[i]>=a and p[i]<saisyou:
    ans=i+1
    saisyou=p[i]
print(ans)

B問題　MissingNo.

与えられた配列をソートします。その後、ひとつずつ見ていきます。
もし、場所はひとつずれているだけなのに、値が１以上差がある場合、その中間の値がなくした値です。
そこを探し出し、出力すればよいです。

Pythonの例

n=int(input())
a=sorted(list(map(int,input().split())))
mae=a[0]
for i in range(1,n):
  if mae+1!=a[i]:
    print(mae+1)
    exit()
  mae=a[i]

C問題　Remembering the Days

この問題は、ぼくは公式の解説に乗っていない方法で解きました。
というのも、この問題はどうやらDFSで解く問題のようですが、ぼくは非再帰のDFSしか書いたことがなく、この問題では解けない感じでした。
ですから、別の方法をやらないといけなかったんです（僕の場合）。

そこで、どのような方法で解いたかというと、「行く頂点の順番を先に全部出しておいて、ひとつずつ確認していく」と、いうものです。

ぼくのコードにも書いてあるんですが、下のようなコードによって、それを出力できます。一度、ローカルの環境などで実行して、出力してみると、どんなものかよくわかると思います。

import itertools
box=list(itertools.permutations([i for i in range(n)]))

行く頂点の順番がわかったら、今度はそれを実装するだけでいいです。もし、途中でどうしても次の頂点に行くことができなくなったら、そこで処理を中断したりします。
そして、いままで確認してきた中で一番長さの長いものを格納する変数を作って、どんどん更新していけば最終的な答えがわかります。

n,m=map(int,input().split())
import itertools
box=list(itertools.permutations([i for i in range(n)]))

rotti=[[-1] * n for i in range(n)]


for i in range(m):
  a,b,c=map(int,input().split())
  rotti[a-1][b-1]=c
  rotti[b-1][a-1]=c


saidai=0
for i in box:
  count=0
  now=i[0]
  for ipp in range(1,len(i)):
    if rotti[now-1][i[ipp]-1]==-1:
      break
    count+=rotti[now-1][i[ipp]-1]
    now=i[ipp]
  saidai=max(saidai,count)
print(saidai)

D問題　President

この問題はDPを使って解くことができます。
（説明書き途中）

E問題　Prerequisites

この問題は、diffなどが高かったですが、ぼくはそんなこと全然ないと思っています。けっこう簡単だと思います。

どうやって解くのかというと、まず最初に障害物があったり、人の目線があったりして通ることのできないグリッドを書き出してみます。
そして、そこを通ることのできない壁としてとらえ、迷路のDFSを行います。

……おしまい

また、自分のコードではこれまた再帰関数ではなく、非再帰で書いてしまいました。ごめんなさい。（しかもキューの代わりにリストを使ってます）

h,w=map(int,input().split())
rotti=[[] * 1 for i in range(h)]
for i in range(h):
  rotti[i]=list(input())

kinsi=set(["#","^",">","v","<"])

check=1

stack=[]
for i in range(h):
  for ipp in range(w):
    if rotti[i][ipp]=="^":
      a=i-1
      b=ipp
      while a>=0 and not rotti[a][b] in kinsi:
        rotti[a][b]="!"
        a-=1
    elif rotti[i][ipp]==">":
      a=i
      b=ipp+1
      while b<w and not rotti[a][b] in kinsi:
        rotti[a][b]="!"
        b+=1
    elif rotti[i][ipp]=="v":
      a=i+1
      b=ipp
      while a<h and not rotti[a][b] in kinsi:
        rotti[a][b]="!"
        a+=1
    elif rotti[i][ipp]=="<":
      a=i
      b=ipp-1
      while b>=0 and not rotti[a][b] in kinsi:
        rotti[a][b]="!"
        b-=1
    elif rotti[i][ipp]=="S":
      stack.append([i,ipp])
      rotti[i][ipp]=0
kinsi.add("!")
iti=0


while len(stack)>iti:
  a=stack[iti][0]
  b=stack[iti][1]
  if a-1>=0 and rotti[a-1][b]==".":
    rotti[a-1][b]=rotti[a][b]+1
    stack.append([a-1,b])
    

  if b+1<w and rotti[a][b+1]==".":
    rotti[a][b+1]=rotti[a][b]+1
    stack.append([a,b+1])
    
  if a+1<h and rotti[a+1][b]==".":
    rotti[a+1][b]=rotti[a][b]+1
    stack.append([a+1,b])

  if b-1>=0 and rotti[a][b-1]==".":
    rotti[a][b-1]=rotti[a][b]+1
    stack.append([a,b-1])



  
  if a-1>=0 and rotti[a-1][b]=="G":
    check=0
    print(rotti[a][b]+1)
    break

  if b+1<w and rotti[a][b+1]=="G":
    check=0
    print(rotti[a][b]+1)
    break

  if a+1<h and rotti[a+1][b]=="G":
    check=0
    print(rotti[a][b]+1)
    break

  if b-1>=0 and rotti[a][b-1]=="G":
    check=0
    print(rotti[a][b]+1)
    break
  iti+=1
if check==1:
  print(-1)

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

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