🤣

継続して勉強しないとな

2024/11/09に公開

Python

AtCoder

b問題

tech

今回は，AtCoder Beginner Contest 378 B 問題を解いた際のメモを残しておきます．
久しぶりに AtCoder に取り組んだのですが，やはり継続して勉強しないといけないなと感じました．
解き方を理解できても，それをコードに落とし込むのは難しいですね．今回はできませんでした 😭

AtCoder Beginner Contest 378 B

回答

公式の回答にコメントを追加しておきます．

# 1. 入力を受け取る
N = int(input()) # ゴミの種類数
q = [0] _ N # 各ゴミの収集間隔
r = [0] _ N # 各ゴミの最初の収集日

# 2. 各ゴミの収集スケジュールを受け取る
for i in range(N):
q[i], r[i] = map(int, input().split())

# 3. 質問の数を受け取る
Q = int(input())

# 4. 各質問に答える
for _ in range(Q): # ゴミの種類と出す日を受け取る
    t, d = map(int, input().split())
    t -= 1 # 0 から始まるインデックスに調整

    # dをqで割った商と余りを計算
    b, c = divmod(d, q[t])

    # 余り(c)と最初の収集日(r)を比較
    if c <= r[t]:
        a = b  # その周の収集日
    else:
        a = b + 1  # 次の周の収集日
    ans = a * q[t] + r[t]

    # 答えを出力
    print(ans)

例題の解説

例題として下記の入力例を考えます．

出力は次のようになります．

1 番目の質問：1 種類目のゴミが 1 日以降に初めて回収されるのは 3 日です。
2 番目の質問：1 種類目のゴミが 3 日以降に初めて回収されるのは 3 日です。
3 番目の質問：1 種類目のゴミが 4 日以降に初めて回収されるのは 10 日です。
4 番目の質問：1 種類目のゴミが 15 日以降に初めて回収されるのは 17 日です。
5 番目の質問：2 種類目のゴミが 7 日以降に初めて回収されるのは 10 日です。

考え方

1. 数学的な考え方

収集日は「aq + r」という形で表せます
- q: 収集の間隔（例：7 日ごと）
- r: 最初の収集日（例：3 日目）
- a: 何周目か（0,1,2...）

2. ゴミを出した日(d)の分解

d を q で割ると、商(b)と余り(c)が出てきます
つまり、d = bq + c

例：8 日目にゴミを出した場合（q=7, r=3）

8 ÷ 7 = 1 余り 1
d = 8
b = 1 （商）
c = 1 （余り）

この場合，商の 1 は種類 1 （例え）のゴミを回収するのに，1 週（今回の場合は，q=7 なので７日間）かかることを意味します．

3. 次の収集日を決める規則

ケース 1: c ≤ r のとき（余りが最初の収集日以下）

答え = bq + r
（その周の収集日）

例：8日目にゴミを出した場合（q=7, r=3）
b = 1, c = 1, c < r なので
答え = 1×7 + 3 = 10日目

ケース 2: c > r のとき（余りが最初の収集日より大きい）

答え = (b+1)q + r
（次の周の収集日）

例：12日目にゴミを出した場合（q=7, r=3）
b = 1, c = 5, c > r なので
答え = (1+1)×7 + 3 = 17日目

具体例で確認（入力例 1 の質問 1）：

d = 1（1日目にゴミを出す）
q = 7（7日ごとの収集）
r = 3（3日目から収集開始）

1. 1÷7を計算
   b = 0（商）
   c = 1（余り）

2. c(1) ≤ r(3) なので、
   a = b = 0

3. 答え = 0×7 + 3 = 3

更に詳しく

準備：

1 番目のゴミ：q₁=7, r₁=3
2 番目のゴミ：q₂=4, r₂=2

質問 1： (1 日目に 1 番目のゴミ)

d = 1, q = 7, r = 3

1. 1÷7の計算
   b = 0 (商)
   c = 1 (余り)

2. c(1) ≤ r(3) なので
   a = b = 0

3. 答え = a×q + r
       = 0×7 + 3
       = 3

→ 3日目に収集

質問 2： (3 日目に 1 番目のゴミ)

d = 3, q = 7, r = 3

1. 3÷7の計算
   b = 0 (商)
   c = 3 (余り)

2. c(3) ≤ r(3) なので
   a = b = 0

3. 答え = a×q + r
       = 0×7 + 3
       = 3

→ その日（3日目）に収集

質問 3： (4 日目に 1 番目のゴミ)

d = 4, q = 7, r = 3

1. 4÷7の計算
   b = 0 (商)
   c = 4 (余り)

2. c(4) > r(3) なので
   a = b + 1 = 1

3. 答え = a×q + r
       = 1×7 + 3
       = 10

→ 10日目に収集

質問 4： (15 日目に 1 番目のゴミ)

d = 15, q = 7, r = 3

1. 15÷7の計算
   b = 2 (商)
   c = 1 (余り)

2. c(1) ≤ r(3) なので
   a = b = 2

3. 答え = a×q + r
       = 2×7 + 3
       = 17

→ 17日目に収集

質問 5： (7 日目に 2 番目のゴミ)

d = 7, q = 4, r = 2

1. 7÷4の計算
   b = 1 (商)
   c = 3 (余り)

2. c(3) > r(2) なので
   a = b + 1 = 2

3. 答え = a×q + r
       = 2×4 + 2
       = 10

→ 10日目に収集

最終的な出力：

このように、各質問について：

まず d を q で割って商(b)と余り(c)を求める
余り(c)と最初の収集日(r)を比較して、a を決める
最後に「a×q + r」で答えを計算

という手順で解いていきます。

上記の計算を見ると：

ゴミを出した日が収集日と同じか前なら、その周の収集日
ゴミを出した日が収集日より後なら、次の周の収集日

というパターンがよく分かりますね！

このように、ゴミを出した日を数学的に分解して、次の収集日を計算しています！

むずかしいですね 😭

AtCoder Beginner Contest 378 B

回答

例題の解説

考え方

Discussion