AtCoder Beginner Contest (ABC) 222 PythonでC問題解いてみた
前回解いたやつ
こんにちは。めりーです。
ブログを１か月ほどさぼり、その間valorantやってました。
おかげで、ゴールドまで行けたのですが、ここ最近寒くなり、手が冷えてまともにAIMできない問題が発生しました。
今、このブログも、キーボードの入力がだいぶ遅い状態に・・・
最高気温11℃、最低気温3℃とは・・・・
というわけで今日も元気にAtCoder Beginner Contest (ABC) 222 のC問題解いていきます。
言語はPython、提出はPyPyです。
目次
C問題 考察編
問題文
スイスドローを行ったときの順位問題ですね。
カードゲーム好きな人なら分かると思いますけど、ポケカとか遊戯王の公式大会とかってこの方式でやってますよね。
強い人は強い人同士、弱い人は弱い人同士で当たるので、何回戦か繰り返していくと運に左右されにくい順位になるんですよね。便利。
よくある言い訳の、「手札事故が何回も起こる」は運負けではなく、デッキの構築ミス派です。
方針を立てましょう。
1. 順位表を作る。
2. 順位表の上から２人づつをバトルさせていく。
3. バトルの結果をメモる。
4. その結果をもとに、新しい順位表を作る。
5. Mラウンド繰り返し、順位表を出力。
という方針で行きましょう。
全探索でいけますね。
C問題 実装編
というわけで実装。
公式解説を滅茶苦茶参考にしました。
これ↓
Editorial - Exawizards Programming Contest 2021（AtCoder Beginner Contest 222）
n,m = map(int,input().split())
a = []
for i in range(2*n):
A = input()
a.append(A)
rank = [[0,i] for i in range(2*n)]
def judge(a,b):
# 引き分けで-1、前者勝ちで0、後者勝ちで1
if a == b: return -1
if a == 'G' and b == 'P': return 1
if a == 'C' and b == 'G': return 1
if a == 'P' and b == 'C': return 1
return 0
# ラウンド数のカウント
for j in range(m):
# そのラウンドの対戦者のカウント
for i in range(n):
# rank[2*i] vs rank[2*i+1]
p1 = rank[2*i][1]
p2 = rank[2*i+1][1]
res = judge(a[p1][j],a[p2][j])
# 勝った方から-1引く
if res != -1:
rank[2*i+res][0] -= 1
rank.sort()
for i in range(len(rank)):
print(rank[i][1]+1)
というわけで解説を。
リストのrankは、rank[n][0]に勝敗、rank[n][1]に選手番号-1を格納している。
rank[n][0]に勝敗を格納しないと、sortが面倒なので、先に格納。その後、勝敗の判定を行う関数、judgeを実装。
judgeのa,bに入るのはG、C、Pの三種類のみ。
前者勝ち、後者勝ちの数値をこの値に設定しているのは、この後のrankを更新するときに便利なので。詳しくは後程。
なお、引き分けの場合は、ifがすべて反応せず、最後のreturnのみ反応する。
returnは反応した時点でその関数は終了。その後のループでは、jがラウンド数の管理を、iが各対戦を管理。
各対戦の選手番号をp1、p2に格納。
その勝敗をresに格納。その後、勝った方から-1を引くのは、その後のsortのせい。
sortは、小さい数字順に並べるため、勝った方を+1すると、勝った方が最後に並んでしまう。
それを避けるため、勝った方から-1を引くことで、勝った方が先に並ぶ。引き分けの場合は何も減らさないので、何もしない。
また、rank[2*i+res]とすることで、どっちが勝ったのか場合分けせずに済む。
これじゃない場合は、前者が勝った場合にrank[2*i]、後者が勝った場合にrank[2*i+1]と場合分けが必要になる。そして最後にrankの上から順に選手番号を表示していき、終了。
なお、選手番号は0始まりなので注意。
という感じで終了。
これくらいなら解説を見ずに書けるようになりたいっすね。
目指せ茶色！！
では。
