ABC222のA,B,C,D問題を、Python3でなるべく丁寧に解説していきます。
ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。
- シンプル：余計なことを考えずに済む
- 実装が楽：ミスやバグが減ってうれしい
- 時間がかからない：パフォが上がって、後の問題に残せる時間が増える
ご質問・ご指摘はコメントかツイッター、マシュマロまでどうぞ！
Twitter: u2dayo
マシュマロ： https://marshmallow-qa.com/u2dayo
ほしいものリスト: https://www.amazon.jp/hz/wishlist/ls/2T9IQ8IK9ID19?ref_=wl_share
よかったらLGTMや拡散していただけると喜びます！
目次
ABC222 まとめ
A問題『Four Digits』
B問題『Failing Grade』
C問題『Swiss-System Tournament』
D問題『Between Two Arrays』
アプリ AtCoderFacts を開発しています
コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。
- レート別問題正解率
- パフォーマンス目安
- 早解きで上昇するパフォーマンス
今後も機能を追加していく予定です。使ってくれると喜びます。
ABC222 まとめ
全提出人数: 7180人
パフォーマンス
| パフォ | AC | 点数 | 時間 | 順位(Rated内) |
|---|---|---|---|---|
| 200 | AB------ | 300 | 9分 | 5404(5187)位 |
| 400 | AB------ | 300 | 3分 | 4466(4249)位 |
| 600 | ABC----- | 600 | 65分 | 3699(3484)位 |
| 800 | ABC----- | 600 | 37分 | 2918(2703)位 |
| 1000 | ABCD---- | 1000 | 87分 | 2198(1985)位 |
| 1200 | ABCD---- | 1000 | 54分 | 1601(1390)位 |
| 1400 | ABCD---- | 1000 | 30分 | 1136(931)位 |
| 1600 | ABCDE--- | 1500 | 83分 | 779(590)位 |
| 1800 | ABCDE--- | 1500 | 54分 | 518(347)位 |
| 2000 | ABCDEF-- | 2000 | 93分 | 319(188)位 |
| 2200 | ABCDEF-- | 2000 | 61分 | 196(94)位 |
| 2400 | ABCDE-G- | 2100 | 64分 | 111(44)位 |
色別の正解率
| 色 | 人数 | A | B | C | D | E | F | G | H |
|---|---|---|---|---|---|---|---|---|---|
| 灰 | 3052 | 98.8 % | 97.2 % | 30.5 % | 5.1 % | 0.6 % | 0.2 % | 0.2 % | 0.0 % |
| 茶 | 1322 | 99.4 % | 99.5 % | 75.1 % | 27.2 % | 1.6 % | 0.6 % | 0.8 % | 0.0 % |
| 緑 | 1024 | 99.8 % | 99.6 % | 94.1 % | 75.4 % | 10.7 % | 2.6 % | 1.7 % | 0.0 % |
| 水 | 651 | 99.4 % | 99.4 % | 98.2 % | 94.6 % | 51.0 % | 12.1 % | 4.3 % | 0.0 % |
| 青 | 366 | 99.2 % | 99.2 % | 98.9 % | 98.6 % | 84.4 % | 40.7 % | 11.5 % | 0.0 % |
| 黄 | 164 | 93.9 % | 93.3 % | 91.5 % | 93.3 % | 84.8 % | 54.3 % | 26.2 % | 0.0 % |
| 橙 | 32 | 96.9 % | 96.9 % | 96.9 % | 96.9 % | 93.8 % | 81.2 % | 62.5 % | 0.0 % |
| 赤 | 27 | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 92.6 % | 88.9 % | 96.3 % | 18.5 % |
※表示レート、灰に初参加者は含めず
A問題『Four Digits』
問題ページ：A - Four Digits
灰コーダー正解率：98.8 %
茶コーダー正解率：99.4 %
緑コーダー正解率：99.8 %
入力
$N$ : 整数
実装
色々な実装がありますが、$N$ を文字列で受け取り、N.zfill(4)で $4$ 桁のゼロ埋めされた文字列を出力するのが楽です。
コード
N = input()
print(N.zfill(4))
B問題『Failing Grade』
問題ページ：B - Failing Grade
灰コーダー正解率：97.2 %
茶コーダー正解率：99.5 %
緑コーダー正解率：99.6 %
入力
*$N$ : 人数
$P$ : 合格点
$a_i$ : 学生 $i$ の点数 *
考察
$a_i < P$ の要素がいくつあるか数える問題です。
実装
forループでひとつずつ確認すれば良いです。
コード
N, P = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
for x in A:
if x < P:
ans += 1
print(ans)
sum関数と内包表記を使う方法（おまけ）
わかるならこのように書いたほうが短くて楽かもしれません。
N, P = map(int, input().split())
A = list(map(int, input().split()))
print(sum(x < P for x in A)) # x < P なら Trueになります。Trueは1, Falseは0と同じものとして扱われるので、sum関数で足し合わせればいいです
C問題『Swiss-System Tournament』
問題ページ：C - Swiss-System Tournament
灰コーダー正解率：30.5 %
茶コーダー正解率：75.1 %
緑コーダー正解率：94.1 %
入力
$N$ : 参加人数
$M$ : じゃんけん大会のラウンド数
$A_{i,j}$ : 選手番号 $i$ の人が、ラウンド $j$ で出す手（G、C、Pのどれか）
考察
制約が小さいので、シミュレーションすることを考えます。
インデックスに合わせるため、一番上の順位を $1$ 位ではなく $0$ 位とします。ラウンドごとに、$0\le{i}\lt{N}$ について、$2i$ 位の人と $2i + 1$ 位の人をじゃんけんさせて、勝利数を更新します。
ラウンドが終了するごとに、勝利数が多い順、勝利数が同じなら選手の番号が小さい順にソートして、各プレイヤーの順位を求めます。
$M$ ラウンド終了したら、順位が上の順に選手番号を出力します。
実装
rankという配列を作ります。各要素は、$(勝利数, 選手の番号)$ のリストです。手前から2人ずつ取り出して、じゃんけんで勝ったほうの勝利数を増やします。あいこならどちらの勝利数も変更しません。
ラウンドがすべて終わったら、配列をソートして順位ごとに並び替えます。
ここで、勝った人に $+1$ ポイントするかわりに、 $-1$ ポイントすることにすると、普通にソートするだけで順位通りに並び替えてくれます。$+1$ ポイントにすると、選手の番号が小さい順にソートして、その後勝利数が大きい順にソートする必要があります。
コード
N, M = map(int, input().split())
hands = []
for _ in range(2 * N):
s = input()
hands.append(s)
rank = [[0, i] for i in range(2 * N)]
# D[h1][h2]: じゃんけんでh1, h2を出して、h1が勝つなら1, h2が勝つなら2
D = {"G": {"C": 1, "P": 2},
"C": {"P": 1, "G": 2},
"P": {"G": 1, "C": 2}}
for j in range(M):
for i in range(N):
p1 = rank[2 * i][1] # 2*i位の選手番号
p2 = rank[2 * i + 1][1] # 2*i+1位の選手番号
h1 = hands[p1][j] # p1がjラウンド目に出す手
h2 = hands[p2][j] # p2がjラウンド目に出す手
if h1 == h2: # あいこです
continue
else:
winner = D[h1][h2]
if winner == 1:
rank[2 * i][0] -= 1 # ここで勝ったほうの勝利カウントを-1すると、ソートが楽です
else:
rank[2 * i + 1][0] -= 1
rank.sort() # 勝利カウントが小さい順（＝勝利数が多い順）に並び替える、同じなら選手番号が小さい順が上
for i in range(2 * N):
print(rank[i][1] + 1)
勝利数カウントを+1にした場合
基本的には同じですが、ソート部分がやや面倒になります。
# 上は省略
if h1 == h2: # あいこです
continue
else:
winner = D[h1][h2]
if winner == 1:
rank[2 * i][0] += 1
else:
rank[2 * i + 1][0] += 1
rank.sort(key=lambda x: x[1]) # まず選手番号が小さい順に並び替える
rank.sort(key=lambda x: x[0], reverse=True) # その後、勝利数が大きい順に並び替える
D問題『Between Two Arrays』
問題ページ：D - Between Two Arrays
灰コーダー正解率：5.1 %
茶コーダー正解率：27.2 %
緑コーダー正解率：75.4 %
入力
$N$ : 数列の長さ
$a_i$ : 広義単調増加な長さ $N$ の数列 $A$ の、$i$ 番目の要素
$b_i$ : 広義単調増加な長さ $N$ の数列 $B$ の、$i$ 番目の要素（$a_i\le{b_i}$）
考察
動的計画法で解きます。
状態
$dp[i][c]$ : $i$ 番目まで決めて、最後が $c$ の数列の数
初期状態
$dp[0][0]=1$
$dp[i][c]=0$（それ以外）
遷移
$dp[i+1][c] = dp[i][0] + dp[i][1] + \dots + dp[i][c-1]+dp[i][c]$ （$a_{i+1}\le{c}\le{b_{i+1}}$）
$dp[i+1][c] = 0$ （それ以外の $c$ すべて）
長さ $i$ の数列に $c$ を付け加えて、長さ $i+1$ で最後が $c$ の数列にします。問題文の条件より、$a_{i+1}\le{c\le{b_{i+1}}}$ かつ $c_i\le{c_{i+1}}$ という条件を満たす数列が可能です。
実装
Pythonのコードで遷移を素直に実装すると、以下のコードになります。
dp[i+1][c] = sum(dp[i][:c+1]) % 998244353
しかし、この方法で動的計画法を実装すると、毎回sum(dp[i][:c+1]) を計算する部分の計算量が $O(C)$ （$C = 3000$）となるので、全体の計算量が $O(NC^2)$となり、TLEになります。
そこで、累積和の考えを使ってDPを高速化します。s = sum(dp[i][:c])が既に求まっていれば、sum(dp[i][:c+1]) = s + dp[i][c] という関係を使って、$O(1)$ で求めることができます。こうすることで、全体の計算量が $O(NC)$ となり間に合います。
コード
Pythonだと実行時間制限がギリギリ（$1800$ ms程度）なので、PyPy（$250$ ms程度）で出したほうがいいです。
def main():
MOD = 998244353
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
CONST = 3001
dp = [[0] * CONST for _ in range(N + 1)]
dp[0][0] = 1
for i in range(N):
a = A[i]
b = B[i]
s = sum(dp[i][:a]) % MOD # dp[i]のa未満の総和です
for c in range(a, b + 1):
s += dp[i][c] # sum(dp[i][:c+1])を毎回計算する代わりに、既に求まっているsum(dp[i][:c])にdp[i][c]を足します
s %= MOD
dp[i + 1][c] = s
print(sum(dp[N]) % MOD)
if __name__ == '__main__':
main()
1次元配列2つで高速化
$dp[i+1][c]$ を求めるのに必要なのは $dp[i]$ だけなので、二次元配列の代わりに一次元配列 $2$ つを使うことで少し高速になります。（Pythonで $1100$ ms程度）
def main():
MOD = 998244353
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
CONST = 3001
prev = [0] * CONST
prev[0] = 1
for i in range(N):
curr = [0] * CONST
a = A[i]
b = B[i]
s = sum(prev[:a]) % MOD
for c in range(a, b + 1):
s += prev[c]
s %= MOD
curr[c] = s
prev = curr
print(sum(curr) % MOD)
if __name__ == '__main__':
main()