AtCoderで公開されている、E869120さんの『競プロ典型90問』を解いていきます。
前回に引き続き、難易度★2を解いていきます。
$N$人の学生のテストの点数を順番に受け取り、その後$L_j$番目から$R_j$番目の指定された学生たちの点数の和をそれぞれ求めて出力します（$j = 1, 2, …, Q$）。
リンク先に飛んでより詳しく問題を見ていただければわかるように、実は$N$人の学生はそれぞれ1組と2組に分かれており、それぞれの組に対して和を求めなければなりません。
が、これは正直気にしなくていいです。
実際、例えば1組と2組の得点のリストをそれぞれ作り、$i(1, 2, …, N)$番目の学生が所属する組のリストの$i$番目にその得点を、そうでない組の$i$番目には$0$を追加することで表現できます。
cls1, cls2 = [], []
for i in range(N):
C, P = map(int, input().split())
if C == 1:
cls1.append(P)
cls2.append(0)
else:
cls1.append(0)
cls2.append(P)
では何が問題なのか。。。やはり、計算量でしょう。
言われた通り和を求めるのでは、TLEが出てしまいます。$Q$通りの指定に対していちいち$N$人のうちの$L$番目から$R$番目の点数の和を求める場合、
$$ O(Q) \times O(N) = O(Q \times N) $$となり、$Q \leq 10^5, N \leq 10^5$のもとでは改良案が必要だと言えます。
なお、リストに対する計算量については、参照が$O(1)$であることを覚えておけば
| 操作 | 計算量 | メモ | |
|---|---|---|---|
| len() | 長さを得る | $O(1)$ | かんたん |
| .append() | 末尾に加える | 他の要素に関与しない操作 | |
| .pop(-1) | 末尾を取り出す | ||
| .pop() | 末尾以外を取り出す | $O(n)$ | 他の要素もずれる |
| sum() | 全要素の和を求める | 参照$\times n$回 | |
| max() | 全要素の最大値を求める | ||
| min() | 全要素の最大値を求める | ||
| in | ある値がリストに含まれるか | ||
のように、比較的分かりやすい。問題によっては、inが$O(1)$で使える「set」や、リストに似ているが左右どちらも端の要素の追加、取り出しが$O(1)$で可能な「deque」も有用である。
前回と同じく、いちいち和を求めるのが非効率なら、あらかじめ求めておけばいいじゃない！
⇒
- $i$人目の点数をリストに保管するのではなく、$i$番目までの累計の点数を保管
- $R$番目までの和（参照）から$L-1$番目までの和（参照）を引けばよい（$O(1)$）
なお、$L=1$の場合に$L-1=0$番目までの和の参章が必要になるため、得点の累積和を保管するリストにはあらかじめ0点を入れておく。
N = int(input())
# S[i]は[1組, 2組]のi番目までの生徒の得点の和
S = [[0, 0]]
tmp1, tmp2 = 0, 0
for _ in range(N):
C, P = map(int, input().split())
if C == 1:
tmp1 += P
else:
tmp2 += P
S.append([tmp1, tmp2])
Q = int(input())
for _ in range(Q):
L, R = map(int, input().split())
print(S[R][0] - S[L-1][0], S[R][1] - S[L-1][1])
反省を活かしてなるべく短い行数にまとめようと工夫はしています。。。今後の学習で改善できるところが見つかれば、随時更新していこうと思います！
お読みいただきありがとうございました。
Views: 0
