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

問題

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

🔹頂点数は $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 個

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

累積和（２次元）③

問題

ある地域を $ 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]

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
#-------- 入力例１ ---------
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()

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

1 1 1 0 0

1 2 2 1 0

1 2 3 2 1

0 1 2 2 1

0 0 1 1 1

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

累積和（２次元）②

問題

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

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
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個

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

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