グラフ（隣接する頂点）

March 12, 2023

問題

頂点数 $N$、辺数 $M$ のグラフがあります。

頂点には $1$ から $N$ までの番号が付けられており、$i$ 番目の辺は頂点 $A_i$ と $B_i$ を双方向に結んでいます。

それぞれの頂点 $k$ について隣接している頂点の番号をすべて出力して下さい。

[制約]
🔹$ 2 \leqq N \leqq 100000 $
🔹$ 1 \leqq M \leqq 100000 $
🔹$ 1 \leqq A_i < B_i \leqq N $

解き方・ソースコード

この問題は、隣接リストを作成する問題です。

隣接リストは、各頂点に対して隣接する頂点のリストを記録する方法です。

隣接リストは、メモリ使用量が少ないことが大きな特徴です。

[Google Colaboratory]

#-------- 入力例１ ---------
N = 5       # 頂点の数
M = 4       # 辺の数
edges = [(1, 3), (2, 4), (3, 4), (3, 5)]    # 隣接する頂点の組み合わせ
#---------------------------
# 隣接リストの作成
G = [ list() for i in range(N + 1) ] # G[i] は頂点 i に隣接する頂点のリスト
for a, b in edges:
    G[a].append(b) # 頂点 a に隣接する頂点として b を追加
    G[b].append(a) # 頂点 b に隣接する頂点として a を追加

# 頂点ごとに隣接する頂点を出力
for i in range(1, N + 1):
    print('{}; [{}]'.format(i, ', '.join(map(str, G[i]))))

[実行結果（入力例１）]

1; [3]

2; [4]

3; [1, 4, 5]

4; [2, 3]

5; [3]

各頂点に隣接している頂点の番号（隣接リスト）を作成・表示することができました。

累積和（２次元）④

March 11, 2023

問題

２次元平面上に $N$ 個の点があり、$i$ 個めの点の座標は$(X_i,Y_i)$です。

『$x$ 座標が $a$ 以上 $c$ 以下であり、$y$ 座標が $b$ 以上 $d$ 以下である点は何個ありますか？』という質問が $ Q $ 個与えられますので、それぞれの質問に答えて下さい。

[制約]
🔹$ 1 \leqq N \leqq 100000 $
🔹$ 1 \leqq Q \leqq 100000 $
🔹$ 1 \leqq X_i,Y_i \leqq 1500 $

解き方・ソースコード

各座標に何個の点があるかを、２次元配列を使って記録し、２次元累積和をとって算出します。

[Google Colaboratory]

import random
#-------- 入力例１ ---------
N = 100000
X = [random.randint(1, 1500) for _ in range(N)] 
Y = [random.randint(1, 1500) for _ in range(N)] 
Q = 100000
A = [random.randint(1, 1500 - 1) for _ in range(Q)]
B = [random.randint(1, 1500 - 1) for _ in range(Q)]
C = [random.randint(A[i] + 1, 1500) for i in range(Q)]
D = [random.randint(B[i] + 1, 1500) for i in range(Q)]
#---------------------------
# 各座標にある点の数をカウント
S = [[0] * 1501 for i in range(1501)]
for i in range(N):
    S[X[i]][Y[i]] += 1

# ２次元累積和を算出
T = [[0] * 1501 for i in range(1501)]
for i in range(1, 1501):
    for j in range(1, 1501):
        T[i][j] = T[i][j - 1] + S[i][j]
for j in range(1, 1501):
    for i in range(1, 1501):
        T[i][j] = T[i - 1][j] + T[i][j]

# 答えを求める
for i in range(Q):
    print(f'質問{i + 1}番目の解：', T[C[i]][D[i]] + T[A[i] - 1][B[i] - 1] - T[A[i] - 1][D[i]] - T[C[i]][B[i] - 1], '個')

[実行結果（入力例１）]

質問1番目の解： 841 個

質問2番目の解： 3303 個

質問3番目の解： 1359 個

質問4番目の解： 12495 個

　　　　：

　　（中略）

　　　　：

質問99997番目の解： 86 個

質問99998番目の解： 2975 個

質問99999番目の解： 9480 個

質問100000番目の解： 24764 個

各座標に何個の点があるかを算出できました。

累積和（２次元）③

March 10, 2023

問題

ある地域を $ H \times W $ のマス目で表します。

最初は、どのマスにも雪が積もっていませんでしたが、これから $N$ 日間に渡って雪が降り続けます。

上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ とするとき、$ t $ 日目にはマス$ (A_t,B_t) $を左上とし、マス$(C_t,D_t)$を右下とする長方形領域の積雪が$1cm$だけ増加することが予想されています。

最終的な各マスの積雪を出力してください。

[制約]
🔹$ 1 \leqq H,W \leqq 1500 $
🔹$ 1 \leqq N \leqq 100000 $
🔹$ 1 \leqq A_i \leqq C_i \leqq H $
🔹$ 1 \leqq B_i \leqq D_i \leqq W $

解き方・ソースコード

この問題も累積和を使って、少ない計算量で解くことができます。

具体的には前の要素との差分を計算し、その累積和をとることで解いていきます。

🔹マス $(a,b)$ およびマス $(c+1,d+1)$ を $+1$ する。【ソースコード 14～15行目】
🔹マス $(a,d+1)$ およびマス $(c+1,b)$ を $-1$ する。【ソースコード 16～17行目】
🔹２次元累積和をとる。（左から右への横の累積和をとったあとに、上から下への縦の累積和をとる）【ソースコード 20～25行目】

前計算に $ O(N) $ かかり、２次元累積和をとる処理に $ O(HW) $ かかるので、プログラム全体の計算量は $ O(N+HW) $ となります。

[Google Colaboratory]

#-------- 入力例１ ---------
H = 5
W = 5
N = 3
A = [1, 3, 2]
B = [1, 3, 2]
C = [3, 5, 4]
D = [3, 5, 4]
#---------------------------
# 各日について加算
X = [ [ 0 ] * (W + 2) for i in range(H + 2) ]
Z = [ [ 0 ] * (W + 2) for i in range(H + 2) ]
for t in range(N):
    X[A[t]][B[t]] += 1
    X[C[t] + 1][D[t] + 1] += 1
    X[A[t]][D[t] + 1] -= 1
    X[C[t] + 1][B[t]] -= 1

# 二次元累積和を算出
for i in range(1, H + 1):
    for j in range(1, W + 1):
        Z[i][j] = Z[i][j - 1] + X[i][j]
for j in range(1, W+1):
    for i in range(1, H + 1):
        Z[i][j] = Z[i - 1][j] + Z[i][j]

# 出力
for i in range(1, H + 1):
    for j in range(1, W + 1):
        if j >= 2:
            print(' ', end='')
        print(Z[i][j], end='')
    print()

[実行結果（入力例１）]

各マスの積雪を表示することができました。

累積和（２次元）②

March 9, 2023

問題

２次元平面上に $ N $ 個の点があります。

$ i $ 個めの座標は $ (X_i,Y_i) $ です。

『$x$ 座標が $ a $ 以上 $ c $ 以下であり、$ y $ 座標が $ b $ 以上 $ d $ 以下であるような点は何個あるか』という質問が $ Q $ 個与えられるので、それぞれの質問に答えて下さい。

[制約]
🔹$ N \leqq 100000 $
🔹$ Q \leqq 100000 $
🔹$ 1 \leqq X_i,Y_i \leqq 1500 $

解き方・ソースコード

この問題ではまず、各座標に何個の点があるのかを、２次元配列を使って算出します。

次に横方向の累積和をとった後、縦方法の累積和をとり、最後に計算した２次元の累積和を使って、質問される座標範囲の合計値を求めます。

（合計値を算出する式は、前回記事をご参照ください。）

[Google Colaboratory]

import random
#--------- 入力例1 ---------
N = 100      # 座標の数
X = [random.randint(1, 1500) for _ in range(N)]     # 各X座標
Y = [random.randint(1, 1500) for _ in range(N)]     # 各Y座標

Q = 10      # 質問の数
A = [random.randint(1, 750) for _ in range(N)]     # 座標範囲の開始X座標
B = [random.randint(1, 750) for _ in range(N)]     # 座標範囲の開始Y座標
C = [random.randint(750, 1500) for _ in range(N)]  # 座標範囲の終了X座標
D = [random.randint(750, 1500) for _ in range(N)]  # 座標範囲の終了Y座標
#---------------------------
# 各座標にある点の数を数える
S = [[0] * 1501 for i in range(1501) ]
for i in range(N):
    S[X[i]][Y[i]] += 1

# 累積和をとる
T = [[0] * 1501 for i in range(1501) ]
for i in range(1, 1501):
    for j in range(1, 1501):
        T[i][j] = T[i][j - 1] + S[i][j]
for j in range(1, 1501):
    for i in range(1, 1501):
        T[i][j] = T[i - 1][j] + T[i][j]

# 答えを算出する
for i in range(Q):
    print('座標({}, {})から座標({}, {})の範囲にある点の数は{}個'.format(
           A[i], B[i], C[i], D[i],
           T[C[i]][D[i]] + T[A[i] - 1][B[i] - 1] - T[A[i] - 1][D[i]] - T[C[i]][B[i] - 1]))

[実行結果（入力例１）]

座標(635, 592)から座標(1075, 1360)の範囲にある点の数は16個

座標(705, 478)から座標(905, 1136)の範囲にある点の数は7個

座標(7, 491)から座標(952, 1227)の範囲にある点の数は32個

座標(593, 550)から座標(1028, 1242)の範囲にある点の数は11個

座標(597, 673)から座標(1340, 1455)の範囲にある点の数は22個

座標(584, 473)から座標(765, 1237)の範囲にある点の数は9個

座標(366, 521)から座標(1207, 756)の範囲にある点の数は11個

座標(642, 504)から座標(1254, 1057)の範囲にある点の数は12個

座標(543, 538)から座標(1180, 801)の範囲にある点の数は7個

座標(633, 394)から座標(1059, 1114)の範囲にある点の数は14個

各座標の範囲にある点の数を求めることができました。

（各座標はランダムに生成しているため、実行するたびに結果は変わります。）

累積和（２次元）

March 8, 2023

問題

$ H \times W $ のマス目があります。

上から $ i $ 行目、左から $ j $ 列目にあるマス $ (i,j) $ には、整数 $ X_{i,j} $ が書かれています。

このマス目ついて、以下の $ Q $ 個の質問に答えて下さい。

🔹質問１：左上 $ (A_1,B_1) $ 右下 $ (C_1,D_1) $ の長方形領域に書かれた整数の和を表示する。
🔹質問２：左上 $ (A_2,B_2) $ 右下 $ (C_2,D_2) $ の長方形領域に書かれた整数の和を表示する。
　　　・
　　　・
🔹質問Ｑ：左上 $ (A_Q,B_Q) $ 右下 $ (C_Q,D_Q) $ の長方形領域に書かれた整数の和を表示する。

[制約]
🔹$ 1 \leqq H \leqq 1500 $
🔹$ 1 \leqq W \leqq 1500 $
🔹$ 1 \leqq Q \leqq 100000 $
🔹$ 0 \leqq X_{i,j} \leqq 9 $
🔹$ 1 \leqq A_i \leqq C_i \leqq H $
🔹$ 1 \leqq B_i \leqq D_i \leqq W $

解き方・ソースコード

累積和は、１次元の配列だけではなく、２次元のマス目に対しても使うことができます。

２次元の累積和 $ Z_{i,j} $ はマス $ (1,1) $ を左上とし、マス $ (i,j) $ を右下とする長方形領域の総和です。

横方向の累積和をとった後、縦方法の累積和をとると効率的に計算することができます。

２次元の累積和を使って、長方形領域の合計値を求めるには、マス $ (a,b) $ を左上とし、マス $ (c,d) $ を右下とすると、次の式で求めることができます。

$$ Z_{c,d} + Z_{a-1,b-1} - Z_{a-1,d} - Z_{c,b-1} $$

２次元累積和を計算するのに $ O(HW) $ かかり、質問に答えるのに $ O(Q) $ かかるので、全体の計算量は $ O(HW+Q) $ となります。

[Google Colaboratory]

#-------- 入力例１ ---------
H, W = 5, 5      # マス目の高さと幅
X = [            # マス目に書かれている数字 
    [5, 3, 0, 5, 1],
    [1, 0, 3, 8, 0],
    [8, 0, 5, 0, 2],
    [4, 3, 0, 4, 5],
    [0, 9, 2, 7, 2]
]

Q = 2           # 質問の数
A = [2, 1]      # 左上の縦位置
B = [2, 1]      # 左上の横位置
C = [4, 5]      # 右下の縦位置
D = [5, 5]      # 右下の横位置
#---------------------------
# 累積和を求めるための配列
Z = [ [ 0 ] * (W + 1) for i in range(H + 1) ]
# 横方向の累積和を計算
for i in range(1, H + 1):
    for j in range(1, W + 1):
        Z[i][j] = Z[i][j - 1] + X[i - 1][j - 1]

# 縦方向の累積和を計算
for j in range(1, W + 1):
    for i in range(1, H + 1):
        Z[i][j] = Z[i - 1][j] + Z[i][j]

# 答えを求める
for i in range(Q):
    print(' 解：', Z[C[i]][D[i]] + Z[A[i] - 1][B[i] - 1] - Z[A[i] - 1][D[i]] - Z[C[i]][B[i] - 1])

[実行結果（入力例１）]

 解： 30

 解： 77

２次元の累積和を使って、各長方形領域に書かれた整数の総和を求めることができました。

累積和（１次元）③

March 7, 2023

問題

$D$日間に渡ってあるイベントが開催され、$N(=len(member))$ 人が出席します。

参加者 $ member_i(i=1,2,…,N) $ は $ member_i[‘start’] $ 日目から $ member_i[‘end’] $ 日目まで出席する予定です。

各日のa出席者数を出力してください。

[制約]
🔹$ 1 \leqq D \leqq 100000 $
🔹$ 1 \leqq N(=len(member)) \leqq 100000 $
🔹$ 1 \leqq member[‘start’] \leqq member[‘end’] \leqq D $

解き方・ソースコード

累積和を使ってこの問題を解いていきます。

まず、出席者数の前日比を計算します。

次に前日比の累積和を計算することで、各日の出席者数を求めることができます。

累積和で出席者数が求められる理由は、以下の通りです。

🔹１日目の出席者数は１日目の前日比と一致する。
🔹$d(\geqq 2)$ 日目の出席者数は$d-1$日目の出席者数と $d$ 日目の前日比を足した値と一致する。

[Google Colaboratory]

#-------- 入力例１ ---------
D = 8        # イベント開催日数
# 参加者ごとの出席期間
member = [
    {'start':2, 'end':3},
    {'start':5, 'end':6},
    {'start':2, 'end':7},
    {'start':3, 'end':5},
    {'start':1, 'end':5}
] 
#---------------------------
# 前日比の算出
B = [0] * (D + 2)
for i, x in enumerate(member):
    B[x['start']] += 1
    B[x['end'] + 1] -= 1

# 累積和を計算
Answer = [ None ] * (D + 2)
Answer[0] = 0
for d in range(1, D + 1):
    Answer[d] = Answer[d - 1] + B[d]

# 出力
for d in range(1, D + 1):
    print('{}日目の参加人数は {}人'.format(d, Answer[d]))

[実行結果（入力例１）]

1日目の参加人数は 1人

2日目の参加人数は 3人

3日目の参加人数は 4人

4日目の参加人数は 3人

5日目の参加人数は 4人

6日目の参加人数は 2人

7日目の参加人数は 1人

8日目の参加人数は 0人

イベントの各日ごとの参加人数をカウントすることができました。

累積和（１次元）②

March 6, 2023

問題

くじを $ N $ 回引き、$i$ 回目の結果は $ A_i $ でした。

$ A_i = 1 $ のときアタリ、$ A_i = 1 $ のときハズレを意味します。

$L$ 回目から $R$ 回目までの中では、アタリとハズレのどちらが多いか？という形式の質問が $Q$ 個与えられるので、それぞれの質問に答えて下さい。

解き方・ソースコード

この問題は、アタリとハズレの累積和を求めることで、より少ない計算量で解くことができます。

くじを引いた回数ごとのアタリとハズレの累積回数を比較し、アタリが多い場合は“勝ち”、ハズレが多い場合は“負け”、アタリとハズレの回数が同じ場合は“引き分け”を出力します。

[Google Colaboratory]

#-------- 入力例１ ---------
N = 10
A = [random.randint(0, 1) for _ in range(N)] 
Q = 5
L = [1,  3, 8, 3, 6]
R = [4, 10, 9, 4, 9]
#---------------------------
print('くじの全結果', A)

# アタリの個数・ハズレの個数の累積和を算出
Atari = [ 0 ] * (N + 1)
Hazre = [ 0 ] * (N + 1)
for i in range(1, N + 1):
    # アタリの計算
    Atari[i] = Atari[i - 1]
    if A[i - 1] == 1:
        Atari[i] += 1
    # ハズレの計算
    Hazre[i] = Hazre[i - 1]
    if A[i - 1] == 0:
        Hazre[i] += 1

# 質問に答える
for i in range(Q):
    NumAtari = Atari[R[i]] - Atari[L[i] - 1]
    NumHazre = Hazre[R[i]] - Hazre[L[i] - 1]
    print('{}回目～{}回目の結果'.format(L[i], R[i]), A[L[i] - 1:R[i]], end=' => ')
    if NumAtari > NumHazre:
        print("勝ち")
    elif NumAtari == NumHazre:
        print("引き分け")
    else:
        print("負け")

[実行結果（入力例１）]

くじの全結果 [1, 1, 1, 1, 1, 1, 0, 0, 0, 0]

1回目～4回目の結果 [1, 1, 1, 1] => 勝ち

3回目～10回目の結果 [1, 1, 1, 1, 0, 0, 0, 0] => 引き分け

8回目～9回目の結果 [0, 0] => 負け

3回目～4回目の結果 [1, 1] => 勝ち

6回目～9回目の結果 [1, 0, 0, 0] => 負け

くじを引いた回数の範囲に応じて、勝ち負けを判定することができました。

累積和（１次元）

March 5, 2023

問題

$ N $ 日間のイベントが開催され、$ i $ 日目には $ A_i $ 人が来場しました。

以下のような $ Q $ 個の質問に答えて下さい・

🔹質問１：$ L_1 $ 日目から $ R_1 $ 日目までの総来場者数は何人ですか。
　　　・
　　　・
🔹質問Ｑ：$ L_q $ 日目から $ R_q $ 日目までの総来場者数は何人ですか。

[制約]
🔹$ 1 \leqq N \leqq 100000 $
🔹$ 1 \leqq Q \leqq 100000 $
🔹$ 1 \leqq A_i \leqq 10000 $
🔹$ 1 \leqq L_q \leqq R_q \leqq N $

解き方・ソースコード

累積和を使うと、$L$日目から$R$日目までの総来場者数は下記の計算式で求めることができます。

$$ (R日目までの累計来場者数) - (L-1日目までの累計来場者数) $$

また累積和は、以下のように計算すると計算量$ O(N) $で求めることができます。

🔹$S_0 = 0$とする。
🔹$i=1,2,3,…,N$の順に、$S_i=S_{i-1} + A_i$とする。

累積和の計算に $O(N)$、質問に答える処理に $O(Q)$ かかるので、プロブラム全体の計算量は $O(N+Q)$ となります。

[Google Colaboratory]

#-------- 入力例１ ---------
N = 15          # イベント開催日数
Q = 3           # 質問の数
# イベント日ごとの来場者数
A = [621, 652, 410, 143, 260, 101, 158, 464, 573, 182, 198, 107, 134, 102, 449]
L = [4, 3, 2]       # カウントする期間の開始日
R = [13, 10, 15]    # カウントする期間の終了日
#---------------------------
S = [ None ] * (N + 1)
S[0] = 0
for i in range(N):
    S[i + 1] = S[i] + A[i]
 
for j in range(Q):
    print('{}日目から{}日目までの総来場者数は {} 人です。'.format(L[j], R[j], S[R[j]] - S[L[j] - 1]))

[実行結果（入力例１）]

4日目から 13日目までの総来場者数は 2320 人です。

3日目から 10日目までの総来場者数は 2291 人です。

2日目から 15日目までの総来場者数は 3933 人です。

期間ごとの総来場者数をカウントすることができました。

累積最大値（旅館の工事）

March 4, 2023

問題

ある旅館では、$1$ 号室から $ N $ 号室まで $ N $ 個の部屋があります。

$ i $ 号室は$ A_i $ 人部屋となっています。

この旅館では$ D $日間の工事が行われる予定で、$d$日目は$ L_d $号室から$ R_d $号室までを使うことができません。

$ d=1,2,…,D $のそれぞれの工事日について、稼働できる部屋のうち最も大きい部屋が何人部屋かを求めて下さい。

[制約]
🔹$ 3 \leqq N \leqq 100000 $
🔹$ 1 \leqq D \leqq 100000 $
🔹$ 1 \leqq A_i \leqq 100 $
🔹$ 2 \leqq L_d \leqq R_d \leqq N - 1 $

解き方・ソースコード

まずは、for文を使って泊まれる人数の最大値を計算する方法が思い浮かびますが、計算量が$ O(ND) $ となり実行するのに時間がかかってしまいます。

計算量を減らすために、$L$ 号室から $R$ 号室まで以外の部屋が使えるとき「最も大きい部屋は何人部屋か」を次の式で計算します。

$$ max(1～(L-1)号室の最大人数, (R+1)～N号室の最大人数) $$

１号室から$i$号室までの最大人数$ P_i $、および$i$号室から$N$号室までの最大人数$Q_i$を求めると、$d$日目の答えは$ max(Q_{L_d - 1},Q_{R_d + 1}) $で計算することができます。

次に、$P_i,Q_i$を求めるために、累積和と同じような方法を使うことができます。

$P_i$については先頭要素$A_i$から累積的に最大値を計算し、$Q_i$については最終要素$A_N$から累積的に最大値を計算しておくと、計算量$O(N)$でそれぞれの値を求められます。

[Google Colaboratory]

#--------- 入力例 1 ---------
N = 7                       # 部屋の数
A = [1, 2, 5, 5, 2, 3, 1]   # 部屋ごとの宿泊できる人数
D = 2                       # 工事する日数
L = [3, 5]                  # 工事する部屋の番号（開始位置）
R = [4, 6]                  # 工事する部屋の番号（終了位置）
#----------------------------
# P[i] を求める（配列は0からスタート）。最初の部屋から最後の部屋へ向かっての累積[最大値]
P = [ None ] * N
P[0] = A[0]
for i in range(1, N):
    P[i] = max(P[i - 1], A[i])

# Q[i] を求める（配列は0からスタート）。最後の部屋から最初の部屋へ向かっての累積[最大値]
Q = [ None ] * N
Q[N - 1] = A[N - 1]
for i in reversed(range(0, N - 1)):
    Q[i] = max(Q[i + 1], A[i])

# それぞれの日について答えを算出（配列は0からスタート）
for d in range(D):
    print('工事{}日目に使える最も大きい部屋数は{}人部屋'.format(d + 1, max(P[(L[d] - 1) - 1], Q[(R[d] + 1) - 1])))

[実行結果（入力例１）]

工事1日目に使える最も大きい部屋数は3人部屋

工事2日目に使える最も大きい部屋数は5人部屋

工事日ごとに使える部屋のうち、最も大きい部屋が何人部屋かを求めることができました。

問題を言い換える（クイズ大会）

March 3, 2023

問題

$ N $ 人の生徒がクイズ大会に参加しました。

この大会では $ M $ 問が出題され、$ i $ 問目では$ A_i $ 番目の生徒を除く全員が正解しました。

各生徒の最終的な正解数を求めて下さい。

解き方・ソースコード

この問題は、正解数を求めるよりも不正解数をカウントして、最後に質問数から不正解数を引いた方が簡単に解けます。

[Google Colaboratory]

#--------- 入力例1 ---------
N = 4       # 人数
M = 7       # 質問数
A = [2, 3, 3, 1, 4, 1, 1] # 不正解となる生徒の番号
#---------------------------
# 配列の準備（生徒ごとの不正解数）
Incorrect = [0] * (N + 1)

# 不正解数を求める
for i in range(M):
    Incorrect[A[i]] += 1

# 答えを出力
for i in range(1, N + 1):
    print('生徒{}の正解数 {}'.format(i, M - Incorrect[i]))

[実行結果（入力例１）]

生徒1の正解数 4

生徒2の正解数 6

生徒3の正解数 5

生徒4の正解数 6

各生徒の最終的な正解数をカウントすることができました。