動的計画法（部下の人数）

問題

ある会社には $ N $ 人の社員がいて、地位順に $1$ から $N$ までの番号が付けられています。

社長（社員番号 $1$）以外には直属の上司が１人いて、社員 $i$ の直属の上司は社員 $A_i$ です。

各社員について、部下が何人いるかを出力してください。

ただし、社員 $y$ が社員 $x$ の部下であることは、$ x \neq y$ であり、なおかつ社員 $y$ の直属の上司をたどって社員 $x$ に到達できることを意味します。

[制約]
🔹$ 2 \leqq N \leqq 100000 $
🔹$ 1 \leqq A_i \leqq i-1 (2 \leqq i \leqq N) $

解き方・ソースコード

動的計画法を使って、この問題を解いていきます。

まず、社員の数 $N$ と直属の上司のリスト $A$ を定義します。

次に、隣接リスト G を作成します。

隣接リストは、それぞれの社員が持つ部下の社員番号を管理します。

具体的には、社員 $i$ の持つ部下の社員番号が $j_1, j_2, \ldots, j_k$ である場合、$G[i]$ には $[j_1, j_2, \ldots, j_k]$ というリストが格納されます。

次に、動的計画法を用いて各社員が持つ部下の数を求めます。

具体的には、各社員の持つ部下の数を $dp$ というリストに保存します。

最初は全員が部下を持たないものとして、全ての要素を $0$ に初期化しています。

そして、社員 $i$ の持つ部下の数を計算するために、G[i] の要素（つまり社員 $i$ の部下の社員番号）を順番に取り出して、その社員が持つ部下の数を dp から参照して加算します。

最後に、$dp[i]$ に $1$ を加えることで、社員 $i$ の直属の部下の数を $dp$ に追加しています。

この処理を、社員 $i$ が社長（社員番号１）である場合まで繰り返します。

最後に、$dp$ の各要素を順番に出力することで、各社員が何人の部下を持つかを表示します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#-------- 入力例１ ---------
N = 7                   # 社員数
A = [1, 1, 3, 2, 4, 5]  # 社員番号２から社員番号７の直属の上司の社員番号
#---------------------------
# 隣接リストの作成
G = [list() for i in range(N + 1)]
for i in range(2, N + 1):
    G[A[i - 2]].append(i) # 上司 → 部下の方向に方向に辺を追加

# 動的計画法（dp[x] は社員 x の部下の数）
dp = [0] * (N + 1)
for i in range(N, 0, -1):
    for j in G[i]:
        dp[i] += (dp[j] + 1)

for i in range(1, N + 1):
    print(f'社員 {i} の部下の数は {dp[i]} 人')

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

社員 1 の部下の数は 6 人

社員 2 の部下の数は 2 人

社員 3 の部下の数は 2 人

社員 4 の部下の数は 1 人

社員 5 の部下の数は 1 人

社員 6 の部下の数は 0 人

社員 7 の部下の数は 0 人

各社員について、部下が何人いるかを出力することができました。

ダイクストラ法②（最短経路）

問題

次のような重み付き無向グラフが与えられます。

🔹頂点数は $N$、辺の数は $M$ です。
🔹$i$ 番目の辺は頂点 $ A_i $ と頂点 $ B_i $ を結び、長さは $ C_i $ です。

頂点 $1$ から頂点 $N$ までの具体的な最短経路を１つ出力して下さい。

解き方・ソースコード

前回記事では、グラフにおける最短経路長を求めましたが、今回は最短経路（道筋）を求めます。

まず、与えられた辺の情報を使ってグラフを表現するために、隣接リスト g を作成します。このリストは、各頂点につながる辺の情報を保持するために使用されます。

次に、最短経路を求めるための初期化を行います。

ここでは、距離を表す cost リストと、最短経路の復元に使用する back リストを作成し、それぞれ無限大と -1 で初期化します。

また、探索を行うためのキュー q を作成し、スタート地点となる頂点の情報をキューに追加します。

その後、以下の処理をキューが空になるまで繰り返します。

1. キューから距離が最小の頂点を取り出す。
2. 取り出した頂点に隣接する頂点について、距離を更新する必要がある場合は、push 関数を呼び出して距離を更新し、キューに頂点の情報を追加する。

この push 関数は、最短経路探索中に頂点に訪れる部分を関数化したものです。

この関数では、新たな頂点に到達した場合に距離を更新し、その頂点を探索するためにキューに情報を追加します。

最短経路探索が終了したら、back リストを使って、スタート地点から終点までの最短経路を復元します。

最後に、求めた最短経路を順番に出力します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#-------- 入力例１ ---------
N = 6       # 頂点数
M = 7       # 辺の数
# つながっている頂点とその距離
edges = [
    (1, 2, 14),
    (1, 4, 22),
    (2, 3, 62),
    (2, 5, 5),
    (3, 6, 52),
    (4, 5, 38),
    (5, 6, 18)
]
#---------------------------
from heapq import heappush, heappop

g = [[] for _ in range(N)]
for A, B, C in edges:
    A -= 1
    B -= 1
    g[A].append((B, C))
    g[B].append((A, C))

INF = 1 << 61
cost = [INF] * N
back = [-1] * N
q = []

# 頂点に訪れる部分を関数化
def push(prev, i, c):
    if cost[i] <= c:
        return
    cost[i] = c
    back[i] = prev
    heappush(q, (c, i))

# 復元の都合上後ろから ダイクストラ法を行う
push(-1, N - 1, 0)
while q:
    c, x = heappop(q)
    if cost[x] != c:
        continue # 同じ頂点から複数回探索しない
    for j, d in g[x]:
        push(x, j, c + d)

# 最短経路を復元
ans = [0]
while ans[-1] != N - 1:
    ans.append(back[ans[-1]])

for x in ans:
    print(x + 1)

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

1

2

5

6

最短経路（道筋）は【頂点１➡頂点２➡頂点５➡頂点６】であることが確認できました。

ダイクストラ法①（最短経路長）

問題

次のような重み付き無向グラフが与えられます。

🔹頂点数は $N$、辺の数は $M$ です。
🔹$i$ 番目の辺は頂点 $ A_i $ と頂点 $ B_i $ を結び、長さは $ C_i $ です。

このグラフに対して最短経路長を求めて下さい。

出力形式として、各頂点への最短距離を頂点 $1$ から頂点 $N$ まで順番に出力して下さい。

移動できない頂点の場合は、$-1$ を出力してください

[制約]
🔹$ 2 \leqq N \leqq 100000 $
🔹$ 1 \leqq M \leqq min(100000,N(N-1))/2 $
🔹$ 1 \leqq A_i < B_i \leqq N $
🔹$ 1 \leqq C_i \leqq 10000 $

解き方・ソースコード

ダイクストラ法を使ってこの問題を解いていきます。

ソースコードの冒頭で、グラフの情報を設定しています。

ここでは、頂点数、辺の数、および各辺の情報をタプルとしてリストに格納しています。

次に、隣接リストを作成しています。

このようにしておくことで、後続の処理で各頂点からつながっている辺を効率的に参照できるようになります。

また、このコードではPythonの組み込みモジュールheapqを使って優先度付きキューを実装しています。

これにより、次に探索すべき頂点を常に距離の短い順に処理することができます。

ダイクストラ法の実装部分では、優先度付きキューから取り出した要素が確定済みの頂点(kakutei変数)である場合はスキップしています。

また、確定していない隣接頂点について、現在の距離よりも短い経路が存在する場合は、その距離を更新し、優先度付きキューに加えます。

この処理を、優先度付きキューが空になるまで繰り返します。

最後に、各頂点までの最短距離を出力しています。

頂点までの最短距離が存在しない場合は-1を出力するようにしています。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#-------- 入力例１ ---------
N = 6       # 頂点数
M = 7       # 辺の数
# つながっている頂点とその距離
edges = [
    (1, 2, 14),
    (1, 4, 22),
    (2, 3, 62),
    (2, 5, 5),
    (3, 6, 52),
    (4, 5, 38),
    (5, 6, 18)
]
#---------------------------
import heapq

# 隣接リストの作成
# 重み付きグラフなので、各辺について (隣接頂点, 重み) のタプルを記録
G = [list() for i in range(N + 1)]
for a, b, c in edges:
    G[a].append((b, c))
    G[b].append((a, c))

# 配列・キューの初期化
# キューには (距離, 頂点番号) のタプルを記録
kakutei = [ False ] * (N + 1)
cur = [float('inf')] * (N + 1)  # 距離の暫定値
cur[1] = 0
Q = []
heapq.heappush(Q, (cur[1], 1))

# ダイクストラ法
while len(Q) > 0:
    # 次に確定させるべき頂点を求める
    # 優先度付きキュー Q の最小要素を取り除き、その要素の 2 番目の値（頂点番号）を pos に代入
    pos = heapq.heappop(Q)[1]

    # Q の最小要素が「既に確定した頂点」の場合
    if kakutei[pos] == True:
        continue

    # 暫定値 cur[x] の値を更新する
    kakutei[pos] = True
    for e in G[pos]:
        # pos = e[0], cost = e[1] で対応
        if cur[e[0]] > cur[pos] + e[1]:
            cur[e[0]] = cur[pos] + e[1]
            heapq.heappush(Q, (cur[e[0]], e[0]))

# 答えを出力
for i in range(1, N + 1):
    if cur[i] == float('inf'):
        print('頂点 {} までの最短距離 {}'.format(i, -1))
    else:
        print('頂点 {} までの最短距離 {}'.format(i, cur[i]))

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

頂点 1 までの最短距離 0

頂点 2 までの最短距離 14

頂点 3 までの最短距離 76

頂点 4 までの最短距離 22

頂点 5 までの最短距離 19

頂点 6 までの最短距離 37

各頂点への最短距離を求めることができました。

幅優先探索（Depth First Search）②

問題

$ H \times W $ のマス目で表される迷路があります。

迷路の情報は文字列のリストとして表され、各文字は壁(‘#’) または 通過できる場所(‘.’)となります。

スタート座標からゴール座標までの最短移動回数を求めて下さい。

[制約]
🔹$ 1 \leqq H \leqq 100000 $
🔹$ 1 \leqq W \leqq 100000 $

解き方・ソースコード

前回記事と同様に幅優先探索を使ってこの問題を解いていきます。

前回記事ではqueueを使いましたが、今回はリストで代用します。

また、キューに格納したマス情報は削除せずに、追加した順番にキューの最後までチェックします。

上下左右にマスに移動する処理は関数化（push関数）し、壁の場合はパスし、通過できるマスの場合はコストを１つ増やして、そのマスをキューに追加しています。

cost配列（移動回数を管理）のインデックスは、0からではなく1から始まっています。

このため、push関数で引数に渡す座標値を $sx - 1, sy - 1, gx - 1, gy - 1$ にする必要があります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#-------- 入力例１ ---------
H, W = 7, 8     # 高さ、横幅
sx, sy = 2, 2   # スタート地点の x,y 座標
gx, gy = 4, 5   # ゴール地点の x,y 座標
# 迷路
S = [
  '########',
  '#......#',
  '#.######',
  '#..#...#',
  '#..##..#',
  '##.....#',
  '########'
]
#-------- 入力例２ ---------
H, W = 5, 8     # 高さ、横幅
sx, sy = 2, 2   # スタート地点の x,y 座標
gx, gy = 2, 4   # ゴール地点の x,y 座標
# 迷路
S = [
  '########',
  '#.#....#',
  '#.###..#',
  '#......#',
  '########'
]

#---------------------------
# マスごとの移動回数
cost = [[float('inf')] * W for _ in range(H)]

q = [] # queue は list で代用

# マスに移動する部分を関数化
def push(x, y, c):
    if S[x][y] == '#':  # 壁なので移動できない
        return
    if cost[x][y] <= c: # より少ない移動回数で移動済み（設定済み）
        return
    cost[x][y] = c
    q.append((x, y))

# 幅優先探索
push(sx - 1, sy - 1, 0)
for x, y in q:
    # コストを１つ増やす
    c2 = cost[x][y] + 1
    # 上下左右をチェック
    push(x - 1, y, c2)
    push(x, y - 1, c2)
    push(x + 1, y, c2)
    push(x, y + 1, c2)

print('解：', cost[gx - 1][gy - 1])

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

解： 11

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

解： 10

迷路に対する最短移動回数を求めることができました。

幅優先探索（Breadth First Search）

問題

次のような重みなし無向グラフに対して、頂点１から各頂点までの最短経路長を求めて下さい。

🔹頂点数は $N$、辺の数は $M$
🔹結びつく２つの頂点はリスト型に格納(edges変数)

[制約]
🔹$ 1 \leqq N \leqq 100000 $
🔹$ 0 \leqq M \leqq min(100000,N(N-1)/2) $
🔹$ 1 \leqq A_i < B_i \leqq N $

解き方・ソースコード

この問題を幅優先探索で解いてきます。

幅優先探索は、スタートに近い頂点から順番に探索していくアルゴリズムです。

今回は、キューを使った方法で幅優先探索を行います。

手順は以下の通りです。

手順１：頂点 $1$ から頂点 $x$ までの最短経路長の確定値を、$dist[x]=-1$ に初期化する。
手順２：キューに頂点 $1$ を追加し、$dist[1]=0$ にする。
手順３：キューが空になるまで、以下の手続きを繰り返す。
　🔹キューの先頭要素 $pos$ を取得し、それをキューから削除する。
　🔹$pos$ と隣接するすべての未確定頂点 $to$ に対し、$ dist[to] = dist[pos] + 1 $ を設定し、キューに $to$ を追加する。
　　（未確定頂点とは $ dist[x]=-1 $ となっている頂点のことです。）

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#-------- 入力例１ ---------
N = 6       # 頂点数
M = 5       # 辺の数
# 頂点同士のつながり情報
edges = [(1, 2), (1, 3), (2, 4), (3, 4), (4, 6)]
#---------------------------
from collections import deque

# 隣接リストの作成
G = [ list() for i in range(N + 1) ]
for a, b in edges:
    G[a].append(b)
    G[b].append(a)

# 幅優先探索の初期化（dist[i] = -1 で初期化）
dist = [-1] * (N + 1)
dist[1] = 0
Q = deque()
Q.append(1)

# 幅優先探索
while len(Q) > 0:
    pos = Q.popleft() # キュー Q の先頭要素を取り除き、その値を pos に代入する
    for nex in G[pos]:
        if dist[nex] == -1: # まだチェックしてない頂点
            dist[nex] = dist[pos] + 1
            Q.append(nex)

# 頂点 1 から各頂点までの最短距離を出力
for i in range(1, N + 1):
    print('頂点 1 から頂点 {} までの最短経路は {}'.format(i, dist[i]))

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

頂点 1 から頂点 1 までの最短経路は 0

頂点 1 から頂点 2 までの最短経路は 1

頂点 1 から頂点 3 までの最短経路は 1

頂点 1 から頂点 4 までの最短経路は 2

頂点 1 から頂点 5 までの最短経路は -1

頂点 1 から頂点 6 までの最短経路は 3

頂点１から各頂点への最短経路長を求めることができました。

深さ優先探索②（Depth First Search）

問題

頂点数 $ N $、辺数 $ M $ の連結グラフが与えられます。

このグラフについて、頂点 $1$ から 頂点 $N$ までの単純パスを１つ出力してください。

解き方・ソースコード

この問題は、移動経路の軌跡をどうやって記録するかがポイントになります。

まず前回記事で実施したように隣接リストを作成してから、深さ優先探索を行います。

その過程でどの頂点をたどっているのかを $path$ に記録していき、ゴール（目的となる頂点）にたどり着いた時点で、記録してきた $path$ を出力します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#-------- 入力例１ ---------
N = 5
M = 4
edges = [(1, 3), (2, 4), (3, 4), (3, 5)]
#---------------------------
# 隣接リストを作成
g = [[] for _ in range(N)]
for edge in edges:
    a = edge[0] - 1
    b = edge[1] - 1
    g[a].append(b) # 頂点 a に隣接する頂点として b を追加
    g[b].append(a) # 頂点 b に隣接する頂点として a を追加

# 深さ優先探索
visited = [False] * N   # チェック済の頂点かどうかを管理
path = []               # 辿ってきたパスを管理

def dfs(i):
    path.append(i)      # 確認する頂点をパスに記録
    # ゴール地点にたどり着いた場合
    if i == N - 1:
        # これまでたどってきた頂点を順番に出力
        for x in path:
            print(x + 1)
        exit(0)

    # ゴールに辿りついていない場合
    visited[i] = True
    for j in g[i]:          # その頂点からつながっている頂点をチェック
        if not visited[j]:  # まだ確認していない頂点の場合
            dfs(j)          # 深さ優先探索でチェック
    path.pop()              # 一旦戻るのでチェックした頂点をパスから消去

dfs(0)

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

1

3

5

頂点１⇒頂点３⇒頂点５の経路で目的の頂点に辿りつけることが確認できました。

深さ優先探索（Depth First Search）

問題

頂点数 $N$、辺数 $M$ のグラフが与えられます。

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

グラフ全体が連結であるかどうかを判定して下さい。

連結とは、グラフがどの頂点間も行き来可能であることを意味します。

[制約]
🔹$ 1 \leqq N \leqq 100000 $
🔹$ 0 \leqq M \leqq min(100000, N(N-1)/2 $
🔹$ 1 \leqq A_i < B_i \leqq N $

解き方・ソースコード

深さ優先探索とは、『進めるだけ進み、行き詰ったら一歩戻る』という考えに基づいてグラフを探索していくアルゴリズムです。

深さ優先探索を使うと、次のようにしてグラフの連結判定を行うことができます。

訪問した頂点には青色の印をつけていくことにします。

🔹【手順１】最初に、全ての頂点の色を白色に塗っておく。
🔹【手順２】頂点１を訪問して青色で塗る。その後、以下の行動を繰り返す。
　・隣接する白色頂点がある場合⇒現在位置に隣接する白色の頂点を１つ選び、その頂点に移動し青色で塗る。
　・隣接する白色頂点がない場合⇒一歩戻る。ただし頂点１にいる場合は戻れないので行動終了。
🔹【手順３】行動が終わった時点で全頂点が青色で塗られていたら、グラフは連結となる。

深さ優先探索は、再帰関数を使って次のように実装します。

🔹ある頂点に移動するときはdfs関数を再帰呼び出しする。
🔹一歩戻るときはreturnする。

プロブラムの計算量は $ O(N+M) $ となります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#-------- 入力例１ ---------
N = 6       # 頂点の数
M = 6       # 辺の数
# 各辺が結ぶ頂点の情報
edges = [
    (1, 2),
    (1, 3),
    (2, 4),
    (3, 4),
    (4, 5),
    (4, 6)
]
#-------- 入力例２ ---------
# N = 6       # 頂点の数
# M = 6       # 辺の数
# # 各辺が結ぶ頂点の情報
# edges = [
#     (1, 2),
#     (1, 3),
#     (2, 4),
#     (3, 4),
#     (4, 5)
# ]
#---------------------------
# 深さ優先探索を行う関数（pos は現在位置、visited[x] は頂点 x が青色かどうかを表す真偽値）
def dfs(pos, G, visited):
    visited[pos] = True
    for i in G[pos]:
        if visited[i] == False:
            dfs(i, G, visited)

# 隣接リストの作成
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 を追加

# 深さ優先探索
visited = [ False ] * (N + 1)
dfs(1, G, visited)
print('各頂点の判定結果', visited[1:], '=> 全ての結果をまとめた判定', all(visited[1:]))

# 答えの出力
print("このグラフは連結です。" if all(visited[1:]) else "このグラフは連結ではありません。")

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

各頂点の判定結果 [True, True, True, True, True, True] => 全ての結果をまとめた判定 True

このグラフは連結です。

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

各頂点の判定結果 [True, True, True, True, True, False] => 全ての結果をまとめた判定 False

このグラフは連結ではありません。

グラフが連結となっているかどうかを判定することができました。

グラフ（友達関係）

問題

ある学校のクラスには $N$ 人の生徒が在籍しており、$1$ から $N$ までの番号が付けられています。

このクラスには $M$ 個の友達関係があり、各 $i(1 \leqq i \leqq M)$ について、生徒 $A_i$ と生徒 $B_i$ が互いに友達です。

最も友達の多い生徒の番号を出力してください。

該当者が複数いる場合は、該当者をすべて出力してください。

解き方・ソースコード

この問題は、生徒を頂点、友達関係を辺に置き換えたグラフと見なして解いていきます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#-------- 入力例１ ---------
N = 5           # 生徒数
edges = [(1, 3), (2, 4), (3, 4), (3, 5)]    # 友達関係
#---------------------------
# 友達の数を数える
friend = [0] * N
for a, b in edges:
    friend[a - 1] += 1
    friend[b - 1] += 1

mx = max(friend)
for f in friend:
    if f == mx:
        print(f'最も友達が多い生徒の番号は {ans + 1} です。')

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

最も友達が多い生徒の番号は 3 です。

最も友達が多い生徒の番号を表示することができました。

グラフ（隣接する頂点）

問題

頂点数 $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]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#-------- 入力例１ ---------
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]

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

累積和（２次元）④

問題

２次元平面上に $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]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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 個

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