ABC308

今日も参加できましたので、反省会します。
自分がテストしているタイミングではサーバーも元気でしたので運営さんの対策がうまくいってそうでよかったです。
今回はABC308( https://atcoder.jp/contests/abc308 )。

A

与えられた長さ8の数列が条件を満たすかを判定する。条件はすべて網羅しているか、確認しましょう(1敗)

l = list(map(int, input().split()))
pre = l[0]
ans = "Yes"
for i in l:
  if pre < 100 or pre%25 != 0:
    ans = "No"
    break
  if i >= pre and i <= 675 and i%25 == 0:
    pre = i
    continue
  else:
    ans = "No"
    break
print(ans)

B

食べたお寿司の値段を調べる。皿の色Dと、それに対する値段Pが与えられ、それに対して実際に食べた皿の色Cが与えられるため、それらを使って計算する。皿の色とその値段が別々になっている部分がややこしくしていると感じたため、辞書式配列をつかい、一つにまとめた。また、Dに存在しない色もあるためそのための処理を計算部分では加えた。

N, M = map(int, input().split())
C = list(map(str, input().split())) #食べた皿の色
D = list(map(str, input().split())) #値段が異なる皿の色のリスト
P = list(map(int, input().split())) #値段リスト
C_P = {}
for i in range(M): #皿の色と値段の紐付け
  C_P[D[i]] = P[i+1]
ans = 0

for i in C: #精算
  if i in C_P: #リストに皿の色が存在する
    ans += C_P[i]
  else: #存在しない
    ans += P[0]
print(ans)

C

コイントスの成功率(表が出る割合)が高い人順に表記する。同じ成功率では若い番号の人を優先的に。計算した成功率を保存する配列ans_lと、成功率と番号を紐付けた辞書式配列ansを用意し、入力からそれぞれを計算し処理を行う。その後、成功率の配列ans_lを降順にソートし、ansのkeyは成功率で設定したため、ans_lの要素をそのままkeyに使い、順番に番号を表示した。

1度目の実装では、decimalを使わなかったため誤差が生じたのかWAとなった。一方でdecimalを使った場合、時間がかかりTLEとなった。そこからの手の付け所が分からず終わってしまったが、コンテスト後に試しにPyPy3ではなくPythonの方でテストをしたところ1400ms前後で成功した。細かい仕様はわからないが、ライブラリを使っていく場合では、PyPy3よりもPythonのほうが良いのかもしれない。

import decimal

decimal.getcontext().prec =20

N = int(input())
ans = {}
ans_l = []

for i in range(N):
  a, b = map(int, input().split())
  a = decimal.Decimal(a)
  b = decimal.Decimal(b)
  rate = decimal.Decimal(a / (a + b))
  if rate in ans: #rateが既出であるため、同じ割合の配列に追加
    ans[rate].append(i+1)
  else:　#rateが既出でないため、rateをkeyとして新しい配列を用意
    ans[rate] = [i+1]
    ans_l.append(rate) #同時に割合配列に追加

# 回答処理
ans_l.sort(reverse=True)
for i in ans_l:
  a = ans[i]
  for j in a:
    print(j, end=" ")

D

与えられた地図から指定された文字順(snuke)を通り答えにたどり着けるかを判定する。幅優先探索を使って判定を行った。まずsnukeを文字列として入れておき、与えられる地図Mと同時に0を未到達、1を到達済みとした地図r_Mを作る(今回は指定文字列に同じ文字が存在しないため、同じ場所に到達する必要はない)。その後、遷移先用配列pを作成する。この時に(0,0)を初期値として与えるが、M[0][0]がsでなければその時点でアウトなので、その部分の判定も行う。あとは、順番に遷移可能であるかを判定しながらpに追加していくが、この時に遷移回数としてtを持たせておくことで簡単に次に行くべき文字をmojiとして得ることができる。また、このtをもとにpに追加してある、次の遷移座標を格納する配列を指定する。
言葉にすると難しめ。

H, W = map(int, input().split())
s = "snuke"
M = []
r_M = []
for i in range(H): #地図取得かつ到達地図生成
  M.append(input())
  r_M.append([0]*W)

if M[0][0] == "s":
  p = [[(0,0)]] #初期位置を与えた遷移先用配列
  r_M[0][0] = 1
else:
  p = []
t = 1
ans = "No"

for i in p:
  if len(i) == 0: #遷移先がないため終了
    break
  p.append([]) #遷移先用配列生成
  moji = s[t%5]　#遷移先文字取得

  for j in i:
    #---------到達判定---------------
    h = j[0]
    w = j[1]
    if h != 0:
      if M[h-1][w] == moji and r_M[h-1][w] == 0:
        p[t].append((h-1,w))
        r_M[h-1][w] = 1
    if h != H-1:
      if M[h+1][w] == moji and r_M[h+1][w] == 0:
        p[t].append((h+1,w))
        r_M[h+1][w] = 1
    if w != 0:
      if M[h][w-1] == moji and r_M[h][w-1] == 0:
        p[t].append((h,w-1))
        r_M[h][w-1] = 1
    if w != W-1:
      if M[h][w+1] == moji and r_M[h][w+1] == 0:
        p[t].append((h,w+1))
        r_M[h][w+1] = 1
    #----------------------------------
  t += 1 #遷移先文字更新

  if r_M[-1][-1] == 1:# ゴール到達判定
    ans = "Yes"
    break
print(ans)

反省・感想

今回もCでこけてしまって悔しいコンテストでした。PyPyとPythonの違いはしっかり認識するべきかもしれませんね。
最近はDをしっかり解けるようになってきているので少しだけ成長を感じています。数をこなして、幅優先、動的計画法、二分探索あたりは使えるようにしていきたいです。
次回も頑張りましょう。

現在レート:732 → 735