ABC222のA-D問題の解説。
目次
A - Four Digits
B - Failing Grade
C - Swiss-System Tournament
D - Between Two Arrays
A - Four Digits
必要な知識
- zfill()
- f文字列
解説
与えられた整数を4桁になるように、0を加える問題。
Pythonでは、指定した桁数を0で埋めてくれるzfill()というものがあるので、こちらを使うとかんたんにACできる。
コード1
def main():
n = input()
print(n.zfill(4))
if __name__ == '__main__':
main()
また、f文字列を使う方法もある。
コード2
def main():
n = int(input())
print(f'{n:04d}')
if __name__ == '__main__':
main()
B - Failing Grade
必要な知識
- for
- (filter)
解説
学生の点数aから、P未満の点数をとった人数を数える問題。
これは、forとifを使うことでACできる。
コード1
def main():
n, p = map(int, input().split())
alist = list(map(int, input().split()))
cnt = 0
for a in alist:
if p > a:
cnt += 1
print(cnt)
if __name__ == '__main__':
main()
また、filter()を用いても求めることができる。
コード2
def main():
n, p = map(int, input().split())
alist = list(map(int, input().split()))
ans = len(list(filter(lambda x: x < p, alist)))
print(ans)
if __name__ == '__main__':
main()
C - Swiss-System Tournament
必要な知識
- sort()
- 二重ループ
- 2次元配列
解説
1位, 2位 と 3位, 4位...と連続する順位の人同士でじゃんけんさせて、勝利した方に+1ポイントをあたえる。その後、「勝数が多い」または「番号が小さい」人を上位として並び替えをし、同じことを繰り返す。
連続する人同士のじゃんけんは2倍したインデックス番号とそれに1を足したインデックス番号の手を参照してくれば良い。
問題なのが並び替えだ。勝数が多い、はかんたんに並び替えできるが、番号が小さいとなると同時に並び替えができなくなる。ここで、番号が小さい順番にソートする頃を前提に、勝数が多い順にするのではなく、勝数をマイナスの値にして並び替えすると、どちらも小さい順番に並び替えするだけでいい。
コード
def main():
n, m = map(int, input().split())
alist = []
for i in range(2*n):
temp = list(input())
alist.append(temp)
person = [[0, i] for i in range(2*n)]
for i in range(m):
person.sort()
for j in range(n):
right = alist[person[2*j][1]][i]
left = alist[person[2*j+1][1]][i]
if right == 'G' and left == 'C':
person[2*j][0] -= 1
elif right == 'C' and left == 'P':
person[2*j][0] -= 1
elif right == 'P' and left == 'G':
person[2*j][0] -= 1
elif right == left:
pass
else:
person[2*j+1][0] -= 1
person.sort()
for i in range(2*n):
print(person[i][1]+1)
if __name__ == '__main__':
main()
D - Between Two Arrays
必要な知識
- DP
- 累積和
- （MODで割ったあまり）
解説
与えられたaとbの間の数字から、[1, 2, 3, 3, 4, ...]のような右側に一方的に増加する数列は何個あるかを求める問題。
普通に全通りやろうと思うと、最悪計算量が$3000^{3000}$で確実に間に合わない。そこで、DPを活用する。今回は、1, 2, 3, ..のように単調に増加するかどうかだけを判断すればいいので、ひとつ前の値がわかれば、答えを導き出すことができる。
コードの解説をする。まず、DPの配列、そして、その次の値を保持する配列nxtを用意する。一番外側のループは、Cの配列の長さ分回す。次のループは、aからbの値に対して、後に求める1つ前の累積和dpをみて、aからbに当たる値をnxtに保存する。この配列をdpとして渡し、累積和をとる。ここで累積和を取る理由は、先程にも述べたとおり、1つ前までの値を参照すれば良いので、その値までの値の個数で答えとなるCの数列の個数が決まるからである。
最終的な答えは、Cの一番最後の値を答えてあげればAC。
コード
def main():
MOD = 998244353
n = int(input())
alist = list(map(int, input().split()))
blist = list(map(int, input().split()))
m = 3000
dp = [1] * (m+1)
for i in range(n):
nxt = [0]*(m+1)
for j in range(alist[i], blist[i]+1):
# 1つ前の累積和を見て
# aからbに当たる値をnxtに保存
nxt[j] = dp[j]
dp = nxt
# 累積和
# 1つ前の値までに値が何個あるかで数列の個数が決まる
for i in range(m):
dp[i+1] += dp[i]
dp[i+1] %= MOD
print(dp[m])
if __name__ == '__main__':
main()
編集後記
DPの解説記事をおいおい出そうかな
自分でもまだ全然なれてない部分がある...