atcoder練習(2024.11.12)

キーワード

Divide and Conquer, zip, 実行時間

問題

AtCoder 市では、N 種類のゴミを定期的に収集しています。
i(=1,2,…,N) 種類目のゴミは、日付を q_i で割ったあまりが r_i の日に収集されます。

Q 個の質問に答えてください。
j(=1,2,…,Q) 番目の質問では、d_j 日に t_j 種類目のゴミが出たときに、次にそれが収集される日を答えてください。

ただし、i 種類目のゴミが出た日が、i 種類目のゴミが回収される日であった場合、そのゴミは同じ日に収集されるとします。

制約
1≤N≤100
0≤r_i < q_i ≤ 10⁹

1≤Q≤100
1≤t_j ≤N
1≤d_j ≤ 10⁹

入力はすべて整数

入力
入力は以下の形式で標準入力から与えられる。

N
q1 r1
q2 r2
...
qN rN
Q
t1 d1
t2 d2
...
tQ dQ

出力
Q 行出力せよ。
j(1≤j≤Q) 行目には、j 番目の質問に対する答えを出力せよ。

入力例1

2
7 3
4 2
5
1 1
1 3
1 4
1 15
2 7

出力例1

3
3
10
17
10

解説

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

回答

N =int(input())
qr = [map(int, input().split()) for _ in range(N)]
q, r = zip(*qr)

Q = int(input())
td = [map(int, input().split()) for _ in range(Q)]
t, d = zip(*td)

for idx in range(Q):
    qi = q[t[idx] - 1]
    ri = r[t[idx] - 1]
    di = d[idx]
    
    next_collect = di + ((ri - di % qi) + qi) % qi
    print(next_collect)

参考

備考

• まず問題文を理解するのが難しかった。自然言語でコミニュケーションされている以上、自然言語で理解して、それをアルゴリズムに認識して、それをプログラム言語にするという三段階の構成がある。
• 実行時間制限に直面した。next_collectのところをwhileで書いていて、時間がかかっていた。やっぱりループを加えると計算時間は格段に増える。
• 入力例を通して、自分で問題文を確認して、頭の中の過程をよく理解することが、先述の自然言語での理解→アルゴリズムにするのに一助となる。
• 今回は入力の受け取りと、何種類かの認識、それに関する変数の取得、日にちの計算、それぞれを分割して個別に考えることでわかりやすくなった。「Divide and Conquer」めちゃんこ大事！