競プロ典型90問　★2問題コード解説[1]

記事の目的

Atcoderを始めまして、前回で初心者用の教材である「Atcoder Beginner Selection」を解きました。
次に何をしようかと思案してAtcoderの常設コンテストを覗いてみると「競プロ典型90問」というのが目につきました。

atcoder.jp

詳しいことは上記のリンクから見ていただくとして、製作者のE869120様の他にも様々な方が解説ブログを書いてくださっていて、非常に勉強しやすいです。

自分はPythonを使っていますので、こちらの方のGithubを参考にさせていただきました。

github.com

競プロ典型90問は★1から★7で構成されていて、数字が大きくなるほど難しくなっていきます。★2が「Atcoder Beginners Contest」の300点問題レベルだといわれていますので、まずは★2問題をすべて解けるように頑張っていきたいと思います。

004 - Cross Sum（★2）

問題文

要約すると、与えられた行列のすべての要素に対して、その要素を含む行と列にある要素の合計を求める、という問題ですね。
以下が解法になります。

h, w = map(int, input().split(" "))
a_list = []
for i in range(h):
    a_row = list(map(int, input().split(" ")))
    a_list.append(a_row)
 
row_sum = [sum(i) for i in a_list]
column_sum = []
for i in range(len(a_list[0])): 
    sum = 0
    for j in range(len(a_list)):
        sum += a_list[j][i]
    column_sum.append(sum)
    sum = 0
 
output_list = []
output_tmp = []
 
for i in range(len(row_sum)):
    for j in range(len(column_sum)):
        val = row_sum[i] + column_sum[j]
        val = val - a_list[i][j]
        output_tmp.append(val)
    output_list.append(output_tmp)
    print(" ".join(map(str, output_tmp)))
    output_tmp = []

かなりコードがごちゃついていますが、まずは与えられた行列について、「行の合計」と「列の合計」を前計算しています。　その要素が含まれる縦横の要素の合計は、
「行の合計」＋「列の合計」ー「その要素の値」
となります。「行の合計」にも「列の合計」にも「その要素の値」が含まれているので、１つ分を引く必要があります。

010 - Score Sum Queries

問題文

こちらの問題、N人分の名簿があって、Q個の質問がありますので、単純に２重ループかと思いきや、２重ループで解こうとするとTLE（タイムアウト）となります。
ですのでこちらの問題、各クラスの累積和を事前に計算します！

n = int(input())
c = [0 for i in range(n)]
p = [0 for i in range(n)]
 
for i in range(n):
    c[i], p[i] = map(int, input().split(" "))
 
score_sum_A = [0]
score_sum_B = [0]
nowA = 0
nowB = 0
 
for i in range(n):
    if c[i] == 1:
        nowA += p[i]
    else:
        nowB += p[i]
    score_sum_A.append(nowA)
    score_sum_B.append(nowB)
 
q = int(input())
for i in range(q):
    quest1, quest2 = map(int, input().split(" "))
    print(score_sum_A[quest2] - score_sum_A[quest1-1], score_sum_B[quest2] - score_sum_B[quest1-1])

始めのforループでは、学籍番号における各クラスの点数の累積和を保存しています。つまり以下の表のようになります。