ABC290 A-D問題の解説（Python）

はじめに

AtCoder Beginner Contest（略称：ABC）とは、AtCoderが週末に開催している、初級者向け？の競技プログラミングコンテストのことです。

参加者はレーティングによってランク分けされます。私は8ランクあるうち、下から2番目のランク（茶色）のため、まだまだひよっこです。一つ上のランク（緑色）を目指して、現在精進しています。

ABCでは毎回8題の問題が出題され、後半の問題ほど、難易度が高くなります。ここでは私が戦える前半4題について、自身の復習も兼ねて説明できればと思います。誤った記述やより良い解法などあれば、コメントをいただけると幸いです。

ABC290

A – Contest Result

問題

A問題

各問題の配点と、どの問題に正解したかの情報から、合計点を求める問題です。

解説

正解した問題の点数をscoreに足していくだけです。

コード

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

score = 0
for num in B:
    score += A[num - 1]
print(score)

B – Qual B

問題

B問題

コンテストの順位と決勝への参加希望から、誰が決勝に進むかを求める問題です。

解説

順位の小さい人から順に、決勝の定員に達するまで、決勝参加希望者を○とすればよいです。○をつけた数をcountしていくことで、定員に達しているかどうかを確認できるようにします。

コード

N, K = map(int, input().split())
S = input()

ans = ""
count = 0

for char in S:
    if char == "o" and count < K:
        ans += "o"
        count += 1
    else:
        ans += "x"

print(ans)

C – Max MEX

問題

C問題

一見ややこしい問題文ですが、要は、0からどれだけ数字の連鎖を繋げられるかといった問題です。

解説

問題文さえ理解できれば難しくはありません。「順序を保ったまま抜き出す」なども気にする必要ないですね。

0から順に、その数が整数列Aに含まれるか調べるのみです。ただし、取り出すのはK要素なので、答えは最大でもKであることに注意しましょう。

コード

N, K = map(int, input().split())
A = set(map(int, input().split()))

count = 0

for i in range(K):
    if i in A:
        count += 1
    else:
        break

print(count)

D – Marking

問題

D問題

横一列に並んだNマスをDマスごとにマーキングしていく問題です。端まで行くとループします。また、マーキング対象が既にマーキングされている場合は、その隣のマスをマーキングします。

解説

難しい問題ですね……。問題理解のため、まずは実験をしてみます。

N=6, D=1のとき、0→1→2→3→4→5

N=6, D=2のとき、0→2→4→0 1→3→5

N=6, D=3のとき、0→3→0 1→4→1 2→5

N=6, D=4のとき、0→4→2→0 1→5→3

N=6, D=5のとき、0→5→4→3→2→1

N=6, D=6のとき、0→0 1→1 2→2 3→3 4→4 5

K回目でどのマスをマーキングするかは、「マーキング対象が既にマーキングされている場合は、その隣のマスをマーキングする」を無視すれば、D × (K – 1) (mod N)です。

つまり、後は「隣のマスをマーキング」が何回起きるかさえ、考えればよいです。

上の例を観察していると、色んなことが分かります。

N=6, D=2のときは、6÷2=3の周期で「隣のマスをマーキングする」が起きている？
N=6, D=4のときは、N=6, D=2の同じ周期で「隣のマスをマーキングする」が起きている？
N=6, D=5のときは、「隣のマスをマーキングする」が起きていない？

N=6, D=2のときとN=6, D=4のときで周期が同じになることから、重要なのは（NとDの最大公約数）であることが分かります。

Nを（NとDの最大公約数）で割った数が、「隣のマスをマーキングする」が起こる周期となります。周期が分かれば回数も分かりますので、そこから答えが導けます。

コード

from sys import stdin
import math
T = int(input())
l = [list(map(int, stdin.readline().split())) for _ in range(T)]

for test in l:
    N, D, K = test[0], test[1], test[2]
    # 隣のマスをマーキングする周期
    period = N // math.gcd(N, D)
    # 隣のマスをマーキングする回数
    count = (K - 1) // period
    # 進んだ合計マス（mod N）
    print((D * (K - 1) + count) % N)