ABC308の解説

茶コーダーで需要ないとは思いますが、解説を書いてみようと思います。

A問題　New Scheme

この問題は特別なアルゴリズムは使いません。入力をリストなどで受け取って、一個ずつ見ていきます。見ていく点は以下の通りです（問題に乗ってる通りです）。

・n番目の値は、n-1番目の値と等しいか、大きいか。
・n番目の値は、100以上かつ675以下であるか。
・n番目の値は、必ず25の倍数であるか。

一つでもこの条件を満たしていない要素があれば「No」、すべての値が条件を満たしていれば「Yes」を出力すればよいのです。

Pythonの例

a=list(map(int,input().split()))
mae=a[0]
check=0
if mae>675 and mae<100:
  check=1
if mae%25!=0:
  check=1
for i in range(len(a)-1):
  if a[i+1] < mae or a[i+1] > 675 or a[i+1] < 100 or a[i+1]%25!=0:
    check=1
    break
  mae=a[i+1]
if check==0:
  print("Yes")
else:
  print("No")

B問題　Default Price

この問題も、特別なアルゴリズムは必要ありません。正しく動くプログラムを実装できるかが問題ですね！
↓やってること（当たり前だけど…）

・二次元リストなどに、どの皿の色が何円かを格納しておく。
・食べた皿を一枚ずつチェックしていく。その中に色で指定されて値段が決まっている皿があればその値段、そうでなければそれ以外の色の皿に適用される値段を足していく。
・それぞれの値段の合計を出力する。

Pythonの例

n,m=map(int,input().split())
rotti = [[0] * 2 for i in range(max(n,m))]
eat=list(input().split())
hako=list(input().split())
for i in range(m):
  rotti[i][0]=hako[i]
hako=list(map(int,input().split()))
irane=hako[0]
for i in range(m):
  rotti[i][1]=hako[i+1]
ans=0
for i in range(n):
  for ipp in range(m):
    if eat[i]==rotti[ipp][0]:
      ans+=rotti[ipp][1]
      break
  else:
    ans+=irane
print(ans)

C問題　Standings

まず、この問題を愚直に実装してみると以下のようになります。

愚直な実装

n=int(input())
rotti = [[0] * 2 for i in range(n)]
for i in range(n):
  a,b=map(int,input().split())
  rotti[i][1]=n-i
  rotti[i][0]=a/(a+b)
rotti=sorted(rotti,reverse=True)
for i in range(n):
  print(f"{n-rotti[i][1]+1} ",end='')
print()

このコードでは、いくつかのケースでWAが出てしまいます。それは、小数の範囲で誤差が発生してしまうからです。
実は、小数の範囲では誤差が出てしまうことはあっても、大きい整数の計算では誤差が出ません。ですから、確率を計算するときに、なるべく大きな値にし、小数になる範囲を少なくして、誤差が出ないようにしてあげるとうまくいきます。

Pythonの例

n = int(input())
x = []
for i in range(n):
    a, b = map(int, input().split())
    x.append((a * 10 ** 100 // (a + b), n-i))
x=sorted(x,reverse=True)
for i in range(n):
  print(f"{n-x[i][1]+1} ",end='')
print()

D問題　Snuke Maze

この問題は深さ優先探索（？）みたいな方法で解きました（深さ優先探索かどうかわからないのですが…）。
どのようなことをしているのかというと

・まず、最初にいる座標０，０をリストなどに格納しておく。
・そこから、行くことのできる座標を選ぶ（例えば、ｓの次はｎのところに行けるみたいな）
・行くことのできる座標をリストなどに格納して、またもう一回探索する（同時に何個もの座標を探索する）。
・最終的にゴールの地点にたどり着ければYes、たどりつけずにどこにもいけなくなったらbreakしてNoを出力する。

このとき気をつけるのは、一度行った座標には行かなようにするということです。そうしないと、いつまでたっても計算してTLEがになってしまいます（ゴールにたどりつけないケースの場合は）。

Pythonの例（ちなみに、再帰関数を使ってないので、ごちゃごちゃな実装になっているので、参考にならないかも）

h,w=map(int,input().split())
hako=[]
rotti = [[0] * w for i in range(h)]
for i in range(h):
  rotti[i]=list(input())
hako.append([0,0])
a=["s","n","u","k","e"]
irane=set()
check=1
count=0
for i in range(10000):
  if count==0:
    new=[]
    for ipp in range(len(hako)):
      if hako[ipp][0]>0 and rotti[hako[ipp][0]-1][hako[ipp][1]]==a[(i+1)%5] and not str(hako[ipp][0]-1)+"a"+str(hako[ipp][1]) in irane:
        new.append([hako[ipp][0]-1,hako[ipp][1]])
        irane.add(str(hako[ipp][0]-1)+"a"+str(hako[ipp][1]))
      if hako[ipp][0]+1<h and rotti[hako[ipp][0]+1][hako[ipp][1]]==a[(i+1)%5] and not str(hako[ipp][0]+1)+"a"+str(hako[ipp][1]) in irane:
        new.append([hako[ipp][0]+1,hako[ipp][1]])
        irane.add(str(hako[ipp][0]+1)+"a"+str(hako[ipp][1]))
      if hako[ipp][1]>0 and rotti[hako[ipp][0]][hako[ipp][1]-1]==a[(i+1)%5] and not str(hako[ipp][0])+"a"+str(hako[ipp][1]-1) in irane:
        new.append([hako[ipp][0],hako[ipp][1]-1])
        irane.add(str(hako[ipp][0])+"a"+str(hako[ipp][1]-1))
      if hako[ipp][1]+1<w and rotti[hako[ipp][0]][hako[ipp][1]+1]==a[(i+1)%5] and not str(hako[ipp][0])+"a"+str(hako[ipp][1]+1) in  irane:
        new.append([hako[ipp][0],hako[ipp][1]+1])
        irane.add(str(hako[ipp][0])+"a"+str(hako[ipp][1]+1))
    count+=1
    if [h-1,w-1] in new:
      check=0
      break
  else:
    hako=[]
    for ipp in range(len(new)):
      if new[ipp][0]>0 and rotti[new[ipp][0]-1][new[ipp][1]]==a[(i+1)%5] and not str(new[ipp][0]-1)+"a"+str(new[ipp][1]) in irane:
        hako.append([new[ipp][0]-1,new[ipp][1]])
        irane.add(str(new[ipp][0]-1)+"a"+str(new[ipp][1]))
      if new[ipp][0]+1<h and rotti[new[ipp][0]+1][new[ipp][1]]==a[(i+1)%5] and not str(new[ipp][0]+1)+"a"+str(new[ipp][1]) in irane:
        hako.append([new[ipp][0]+1,new[ipp][1]])
        irane.add(str(new[ipp][0]+1)+"a"+str(new[ipp][1]))
      if new[ipp][1]>0 and rotti[new[ipp][0]][new[ipp][1]-1]==a[(i+1)%5] and not str(new[ipp][0])+"a"+str(new[ipp][1]-1) in irane:
        hako.append([new[ipp][0],new[ipp][1]-1])
        irane.add(str(new[ipp][0])+"a"+str(new[ipp][1]-1))
      if new[ipp][1]+1<w and rotti[new[ipp][0]][new[ipp][1]+1]==a[(i+1)%5] and not str(new[ipp][0])+"a"+str(new[ipp][1]+1) in irane:
        hako.append([new[ipp][0],new[ipp][1]+1])
        irane.add(str(new[ipp][0])+"a"+str(new[ipp][1]+1))
    count-=1
    if [h-1,w-1] in hako:
      check=0
      break
if check==0:
  print("Yes")
else:
  print("No")

ちなみに、ぼくはE問題とF問題を公式の解説を見てACをコンテスト後に出しました。解説を見てアルゴリズムが分かればあんまり実装が難しくはないと思ったので、ぼくみたいにコンテスト中に解けなかった人でまだACを出していない人は、解いてみるのをおすすめします！

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

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