問題

$ 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人の生徒が参加できるということが分かりました。

問題

対応の取れているカッコ列 $ S $ があります。

$ S $ の何文字目と何文字目が対応しているかを、すべて出力して下さい。

解き方・ソースコード

この問題はスタックを使って簡単に解くことができます。

スタックとは、次の３種類のクエリを処理することができるデータ構造です。

🔹クエリ１：スタックの一番上に要素 $ x $ を追加する。
🔹クエリ２：スタックの一番上の要素を取得する。
🔹クエリ３：スタックの一番上の要素を削除する。

与えられたカッコ列 $ S $ を左から順番に見ていき開きカッコが何文字目にあるかをスタックに記録していきます。

閉じカッコが見つかった場合、スタックの一番上の開きかっこが対応するものとなります。

[Google Colaboratory]

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

#--------- 入力例1 ---------
S = '(())()'
#--------- 入力例2 ---------
# S = 'list(map(int, input().split()))'
#---------------------------
# 左から順番に見ていく
# 文字列は 0 文字目から始まることに注意
Stack = []
for i in range(len(S)):
    if S[i] == '(':
        Stack.append(i + 1)
    if S[i] == ')':
        print('{}文字目と{}文字目'.format(Stack.pop(), i + 1))

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

2文字目と3文字目
1文字目と4文字目
5文字目と6文字目

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

20文字目と21文字目
28文字目と29文字目
9文字目と30文字目
5文字目と31文字目

開きカッコと閉じカッコの対応関係を確認することができました。

問題

$ 1 $ 以上 $ N $ 以下の整数のうち、$3, 5,7$ のいずれかで割り切れるものは何個ありますか。

[制約]
🔹$ 1 \leqq N \leqq 10^{12} $

解き方・ソースコード

この問題は包除原理を使うと簡単に解くことができます。

包除原理は要素数に関する等式で、集合$P,Q,R$ の和集合の要素数は下記の式で表せます。

 [集合P,Q,Rの和集合の要素数] = [集合Pの要素数] + [集合Qの要素数] + [集合Rの要素数] 

                            - [集合P,Qの共通部分の要素数] 

                            - [集合Q,Rの共通部分の要素数] 

                            - [集合P,Rの共通部分の要素数] 

                            + [集合P,Q,Rの共通部分の要素数]

集合が３つ以上になるとプラスするかマイナスするか少々分かりにくくなるかもしれませんが、重なりが奇数個の場合はプラス、重なりが偶数個の場合はマイナスと考えると分かりやすくなります。

[Google Colaboratory]

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

#-------- 入力例１ ----------
N = 10
#-------- 入力例２ ----------
# N = 30
#-------- 入力例３ ----------
# N = 100000000000
#----------------------------
# 計算
A1 = (N //   3); # 3 で割り切れるものの個数
A2 = (N //   5); # 5 で割り切れるものの個数
A3 = (N //   7); # 5 で割り切れるものの個数
A4 = (N //  15); # 3, 5 で割り切れるもの（= 15 の倍数）の個数
A5 = (N //  21); # 3, 7 で割り切れるもの（= 21 の倍数）の個数
A6 = (N //  35); # 5, 7 で割り切れるもの（= 35 の倍数）の個数
A7 = (N // 105); # 3, 5, 7 で割り切れるもの（= 105 の倍数）の個数

print('解：', A1 + A2 + A3 - A4 - A5 - A6 + A7)

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

解： 6

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

解： 17

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

解： 54285714286

問題

縦 $ H $ 行、横 $ W $ 列のマス目があります。

上から $ i $ 行目、左から $ j $ 列目のマス $ (i,j) $ の色は $ c_{i,j} $ であり、$ c_{i,j} $ が . ならば白、 # ならば黒で塗られおり、黒マスは通ることができません。

マス $ (1,1) $ から出発し、右方向または下方向の移動をくりかえしてマス $ (H,W) $ まで行く方法は何通りありますか。

[制約]
🔹$ 2 \leqq H \leqq 30 $
🔹$ 2 \leqq W \leqq 30 $
🔹スタート地点 $ (1,1) $ とゴール地点 $ (H,W) $ は白マス

解き方・ソースコード

まず動的計画法で管理する配列を以下のように定義します。

🔹$ dp[i][j] $ ：マス $ (1,1) $ から $ (i,j) $ まで移動する方法の数

マス $ (i,j) $ に移動するには次の２つのパターンがあります。

🔹マス $ (i-1,j) $ ⇒ マス $ (i,j) $ に直接移動
🔹マス $ (i,j-1) $ ⇒ マス $ (i,j) $ に直接移動

黒マスがない状態で考えると次の式が成り立ちます。

🔹$ dp[i][j] = dp[i-1][j] + dp[i][j-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

#--------- 入力例 ----------
H = 4   # 縦の行数
W = 8   # 横の列数
c = [
    ['.', '.', '.', '.', '#', '.', '.', '.'],
    ['.', '.', '.', '.', '.', '.', '#', '.'],
    ['.', '.', '#', '.', '.', '.', '#', '.'],
    ['#', '.', '.', '.', '.', '.', '.', '.'],
]
#---------------------------
# 確認のためにマス目の状態を出力
print('【マス目の状態】')
for i in range(H):
    for j in range(W):
      print(c[i][j], end='')
    print()
print()

# 動的計画法
dp = [ [ 0 ] * (W + 1) for i in range(H + 1) ]
for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            dp[i][j] = 1
        else:
            dp[i][j] = 0
            if i >= 1 and c[i - 1][j]=='.':
                dp[i][j] += dp[i - 1][j]
            if j >= 1 and c[i][j - 1] == '.':
                dp[i][j] += dp[i][j - 1]

print('【移動する方法の数（マス目ごと）】')
for i in range(H):
    for j in range(W):
      print(f'{dp[i][j]:02d}', end=' ')
    print()
print()

# 出力
print('解：', dp[H - 1][W - 1])

[実行結果]

【マス目の状態】
....#...
......#.
..#...#.
#.......

【移動する方法の数（マス目ごと）】
01 01 01 01 01 00 00 00 
01 02 03 04 04 04 04 00 
01 03 06 04 08 12 12 00 
01 03 03 07 15 27 27 27 

解： 27

今回の入力例に関しては、27通りのルートがあることを導き出すことができました。

問題

$ 1 $ 以上 $ N $ 以下の整数のうち、$3, 5$のいずれかで割り切れるものは何個ありますか。

[制約]
🔹$ 1 \leqq N \leqq 10^{12} $

解き方・ソースコード

この問題は包除原理を使うと簡単に解くことができます。

包除原理は要素数に関する等式で、集合$P,Q$ の和集合の要素数は下記の式で表せるというものです。

$ [集合P,Qの和集合の要素数] = [集合Pの要素数] + [集合Qの要素数] - [集合P,Qの共通部分の要素数] $

包除原理を、今回の問題に当てはまると次のようになります。

$ [3の倍数の個数] + [5の倍数の個数] - [15の倍数の個数] $

また、$ 1 $ 以上 $ N $ 以下の整数のうち $ x $ の倍数の個数を求めるには $ N / x $ で求めることができます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11

#-------- 入力例１ ----------
N = 10
#-------- 入力例２ ----------
# N = 30
#-------- 入力例３ ----------
# N = 100000000000
#----------------------------
A1 = (N //  3) # 3 で割り切れるものの個数
A2 = (N //  5) # 5 で割り切れるものの個数
A3 = (N // 15) # 3, 5 両方で割り切れるもの（= 15 の倍数）の個数
print('解：', A1 + A2 - A3)

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

解： 5

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

解： 14

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

解： 46666666667