Atcoder 備忘録_一次元の累積和_問題B06

概要

• 競技プログラミングを始めてみた。
  せっかくなので１テーマごとに解法と学びをアウトプットしてみる。

取り組む内容

• 鉄則本[https://atcoder.jp/contests/tessoku-book] に沿って実施する。
• 
• 言語は Python
• 今回テーマは「一次元の累積和」

問題文

太郎君はくじをN回引き，i回目の結果はAiでした．
Ai=1のときアタリ,Ai=0のときハズレを意味します．「L回目からR回目までの中では，アタリとハズレどちらが多いか？」という形式の質問がQ個与えられるので，それぞれの質問に答えるプログラムを作成してください

制約

• 1≤N,Q≤10^5
• 0≤Ai≤1
• 1≤Li≤Ri≤N
• 入力はすべて整数

出力

i=1,2,3,…,Q それぞれについて，アタリの方が多い場合winを，ハズレの方が多い場合loseを，アタリとハズレが同じ場合drawを,一行ずつ総計Q行に出力してください．

解法

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

L = [None] * Q
R = [None] * Q

for i in range(Q):
  L[i], R[i] = map(int, input().split())

S = [None] * (N+1)
S[0] = 0
for j in range(N):
  S[j+1] = S[j] + A[j]
  
for k in range(Q):
  win = S[R[k]] - S[L[k]-1]
  lose = R[k] - L[k] + 1 - win
    
  if win > lose:
      print("win")
  elif win == lose:
      print("draw")
  else:
      print("lose")

結果

• AC
• Runtime： 201 ms
• メモリ：21184 KB

振り返り

思想

• Qが少なければ逐一winの数をカウントしてもよいが、多い場合は同じ計算を繰り返すことになる（O(L(i))）ため最初に累積和を作ってやって、差分を計算するだけで済むようにする(O(1))

学び

• リストを足していくとき、append使いがちだったが[i+1] = [i] + α って形にすれば読みやすいコードになるなと思った
• リストのindexなどpythonは0始まりで現実世界では1始まりが多いと思うが、pythonリスト側のindex0をなんらか数値やNullなどで埋めてやってindexを合わせると読みやすいしindexズレが起こることも防げるので良いなと思った

感想

• こういう問題集って章ごとのトピックを知って問題を解くから、今回でいうと「累積和を使うんだろうな」って思って解くけど、実務の際に気づくことができるのだろうか？頑張れ自分