問題

$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]

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

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

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

問題

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

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

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

解き方・ソースコード

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

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

[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

#-------- 入力例１ ---------
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] => 負け

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

問題

$ 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]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#-------- 入力例１ ---------
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 人です。

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

問題

ある旅館では、$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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#--------- 入力例 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人部屋

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

問題

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

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

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

解き方・ソースコード

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

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

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

問題

全長 $ L $ メートルのトンネルには、$ N $ 人の人がいます。

人 $ i $ はトンネルの西端から $ A_i $ メートルの位置にいて、方向 $ B_i $ （東または西）へ歩いています。

トンネルの幅は狭いため、２人が同じ位置にきたらお互い移動方向を変えます。

全員が秒速１メートルで歩くとき、最後の人がトンネルの外に出るのは何秒後になるでしょうか。

[制約]
🔹$ 1 \leqq N \leqq 200000 $
🔹$ 1 \leqq A_1 < A_2 < … < A_N < L \leqq 10^9 $

解き方・ソースコード

まずこの問題を解くために思いつくのは人の動きをシミュレーションすることですが、ケースによっては衝突回数が $ N^2 / 4 $ 程度になりとても時間がかかってしまいます。

そこで人同士を区別しないで考えてみると、２人が衝突して向きを変えることと２人がすれ違うことは同じことであるが分かります。

したがってこの問題は、以下のように言い換えることができます。

トンネルの幅は十分広いため、２人が同じ位置に来ても、すれ違ってそのまま進みます。

最後の人がトンネルの外に出るのは何秒後になるでしょうか。

言い換えた問題を考えると、人 $ i $ がトンネルの外に出るまでの時間は、移動方向が東の場合 $ L - A_i $秒、移動方向が西の場合 $ A_i $秒となりますので、その最大値を出力すればよいことになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#--------- 入力例1 ---------
N = 3                   # 人数
L = 100                 # トンネルの長さ（メートル）
A = [20, 50, 70]        # トンネルの西端からみた人の位置（メートル）
B = ['東', '東', '西']  # 向いている方向
#---------------------------
Answer = 0
for i in range(N):
    if B[i] == '東':
        Answer = max(Answer, L - A[i])
    if B[i] == '西':
        Answer = max(Answer, A[i])

print('解：', Answer)

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

解： 80

最後の人がトンネルから出るのは 80秒後 であることが確認できました。

問題

以下の操作を繰り返すことで、左から $ i $ 番目のタイルの色を文字 $ S_i$ （Rが赤、Bが青）にしたいです。

🔹連続する３つのタイルを赤色で塗り替える
🔹連続する３つのタイルを青色で塗り替える

目的を達成できる場合は“Yes”を、達成できない場合は“No”を出力して下さい。

[制約]
🔹$ 3 \leqq N \leqq 200000 $
🔹文字 $ S_i $ は R または B のいずれかである

解き方・ソースコード

この問題は、後ろから考えると容易に解くことができます。

まず最後の一手で塗り替えた３つのタイルの色は必ず同じになります。

つまり「連続する３つのタイルが同じ色である箇所」が存在しない場合、答えは”No”になります。

つぎに「連続する３つのタイルが同じ色である箇所」が存在する場合を考えます。

タイル $ p, p_+ 1, p + 2 $ が同じ色であるとき、以下の手順により目的を達成することができます。

🔹手順１：左から順に塗ることで、タイル $ p - 1 $ より左のタイルの色を確定させる。
🔹手順２：右から順に塗ることで、タイル $ p + 3 $ より右のタイルの色を確定させる。
🔹手順３：最後に、タイル $ p, p_+ 1, p + 2 $ を色 $ S_p $ で塗る。

以上のことから、連続する３つのタイルが同じ色である箇所があれば答えは“Yes”、そうでなければ答えは“No”となります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#--------- 入力例1 ---------
N = 7           # タイルの枚数
S = 'BBRRRBB'   # タイルの色(Rが赤、Bが青)
#--------- 入力例2 ---------
#N = 7           # タイルの枚数
#S = 'BBRRBRB'   # タイルの色(Rが赤、Bが青)
#---------------------------
# 答えを求める
Answer = False
for i in range(0, N - 2):
    if S[i] == 'R' and S[i + 1] == 'R' and S[i + 2] == 'R':
        Answer = True
    if S[i] == 'B' and S[i + 1] == 'B' and S[i + 2] == 'B':
        Answer = True

# 出力
print('Yes' if Answer else 'No')

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

Yes

以下のような操作を行えば目的が達成できます。

🔹タイル１，２，３を青色で塗る（青青青白白白白）
🔹タイル５，６，７を青色で塗る（青青青白青青青）
🔹タイル３，４，５を青色で塗る（青青赤赤赤青青）

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

No

連続する３つのタイルが同じ色である箇所がありませんので、どのように操作しても目的のタイルの色にすることはできません。

問題

$ N $ 個のマスのすごろくがあり、スタートから順に $1$ から $N$ までの番号が付けられています。

このすごろくでは、マス$ i(1 \leqq i \leqq N -1) $ にいるとき、次の２種類の行動のうち一方を選ぶことができます。

🔹マス $A_i$ に進み、スコア100を得る。
🔹マス $B_i$ に進み、スコア150を得る。

ゴールにたどり着くまでに得られる合計スコアの最大値を出力してください。

なお、ゴールから遠ざかる移動をすることはありません。

[制約]
🔹$ 2 \leqq N \leqq 100000 $
🔹$ i + 1 \leqq A_i \leqq B_i \leqq N $

解き方・ソースコード

マス $i$ から移動するときの１つ先の行動として考えられるものは次の２種類です。

🔹スコア100を得てマス $ A_i $ に進む
🔹スコア150を得てマス $ B_i $ に進む

マス $i$ まで進んだ時点で得られるスコアの最大値を $dp[i]$ とするとき、本題の答えである $dp[N]$ の値は以下のように計算することができます。

$dp[1] = 0$ とし $i=1,2,…,N$ の順に以下のことを行う。
🔹$dp[A_i]$の値を $max(dp[A_i],dp[i]+100)$ に更新する
🔹$dp[B_i]$の値を $max(dp[B_i],dp[i]+150)$ に更新する

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#--------- 入力例 ----------
N = 7
A = [2, 4, 4, 7, 6, 7]
B = [3, 5, 6, 7, 7, 7]
#---------------------------
# 配列の初期化
dp = [ -(10 ** 9) ] * (N + 1)
dp[1] = 0

# 動的計画法
for i in range(1, N):
    dp[A[i - 1]] = max(dp[A[i - 1]], dp[i] + 100)
    dp[B[i - 1]] = max(dp[B[i - 1]], dp[i] + 150)
print(dp)

# 出力
print('解：', dp[N])

[実行結果]

[-1000000000, 0, 100, 150, 250, 250, 350, 500]

解： 500

合計スコアの最大値は500であることが確認できました。

問題

$ N $ 枚のカードがあり、$ i $ 枚目のカードの表には整数 $ A_i $、裏には整数 $ B_i $ が書かれています。

カードを何枚か選び、次のように定義するスコアを最大にしたいです。

[スコア] = [選んだカードにおける表の総和の絶対値] + [選んだカードにおける裏の総和の絶対値]

スコアとして考えられる最大値はいくつになるでしょうか。

[制約]
🔹$ 1 \leqq N \leqq 100000 $
🔹$ -10^9 \leqq A_i \leqq 10^9 $
🔹$ -10^9 \leqq B_i \leqq 10^9 $

解き方・ソースコード

この問題では「表の総和を正／負のどちらにするか」「裏の総和を正／負のどちらにするか」を全探索することで解くことができます。

計算量は $ O(4N) $ となります。

[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

import random
#--------- 入力例 ----------
N = 5           # カードの枚数
A = [random.randint(-20, 20) for i in range(N)]
B = [random.randint(-20, 20) for i in range(N)]
#---------------------------
print('【入力データの確認】')
print('A', A)
print('B', B)
print()

# omote=True のとき表の総和が正、ura=True のとき裏の総和が正
# omote=False のとき表の総和が負、ura=False のとき裏の総和が負
def solve(omote, ura, A, B):
    sum = 0
    for i in range(N):
        card1 = A[i] if omote else -A[i]
        card2 = B[i] if ura else -B[i]
        # カード i は選ぶべきかどうか？
        if card1 + card2 >= 0:
            sum += (card1 + card2)
            print('選択したカード：', card1, card2)
    print('　合計：', sum)
    print('---------------------')
    return sum

# 表の総和の正負と、裏の総和の正負を全探索
Answer1 = solve(True, True, A, B);
Answer2 = solve(True, False, A, B);
Answer3 = solve(False, True, A, B);
Answer4 = solve(True, True, A, B);

# 出力
print('【解】', max(Answer1, Answer2, Answer3, Answer4))

[実行結果]

【入力データの確認】
A [7, -16, 10, -13, 12]

B [18, -13, -14, 4, 18]


選択したカード： 7 18

選択したカード： 12 18

　合計： 55
---------------------

選択したカード： 10 14

　合計： 24
---------------------

選択したカード： -7 18

選択したカード： 16 -13

選択したカード： 13 4

選択したカード： -12 18

　合計： 37
---------------------

選択したカード： 7 18

選択したカード： 12 18

　合計： 55
---------------------

【解】 55

問題

$ N $ 人の生徒がいます。

各生徒には体力と気力を表す整数値が定めてられており、生徒 $ i (1 \leqq i \leqq N) $ の体力は $ A_i $、気力は $ B_i $ です。

生徒のうち何人かを選んでバスケットボールをすることにしました。

もし参加者のレベル差が大きい場合、一部の人だけが活躍してもつまらないので、次の条件を満たすようにすることにしました。

🔹どの２人の参加者も、体力の差が $ K $ 以下である。
🔹どの２人の参加者も、気力の差が $ K $ 以下である。

最大何人でバスケットボールをすることができるのかを求めて下さい。

[制約]
🔹$ 1 \leqq N \leqq 300 $
🔹$ 1 \leqq K \leqq 100 $
🔹$ 1 \leqq A_i \leqq 100 $
🔹$ 1 \leqq B_i \leqq 100 $

解き方・ソースコード

この問題では、参加者の選び方を $ 2^N $ 通り全探索する方法が思いつきますが、計算量を考えると現実的ではありません。

そこで、参加者の体力の下限値 $ a $、参加者の気力の下限値 $ b $ を仮に決めてみます。

このとき、以下の２つの条件を満たす生徒だけがバスケットボールに参加することができます。

🔹体力が $ a $ 以上 $ a + K $ 以下である。
🔹気力が $ b $ 以上 $ b + K $ 以下である。

整数の組 $ (a,b) $ を全探索し、その中で参加可能な生徒数が最大となるものを解とします。

制約から $ A_i, B_i $ とも $ 100 $以下ですので、$ (a,b) $ の組としては $ 100 \times 100 = 10000 $ 通りを全探索すれば十分だということになります。

単純に全探索すると計算量が膨大になってしまう問題でも、何を全探索するか（どの値を固定して考えるか）を変えるだけで、とても効率がよくなることがあります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#--------- 入力例 ----------
N = 4       # 生徒数
K = 30      # 体力と気力の差
A = [20, 10, 50, 30]    # 生徒の体力
B = [30, 40, 10, 60]    # 生徒の気力
#---------------------------
# 整数の組 (a, b) が決まったときの、参加可能な生徒数を求める
def GetScore(a, b, A, B, K):
    cnt = 0
    for i in range(N):
        if a <= A[i] <= a + K and b <= B[i] <= b + K:
            cnt += 1
    return cnt
# (a, b) の組を全探索
Answer = 0
for a in range(1, 101):
    for b in range(1, 101):
        Score = GetScore(a, b, A, B, K)
        Answer = max(Answer, Score)
# 出力
print('解：', Answer)

[実行結果]

解： 3

上記の入力例だと、最大3人の生徒が参加できるということが分かりました。