問題

以下の操作を繰り返すことで、左から $ 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

問題

$ N $ 個の草が一列に並んでいて、$ 1 $ から $ N $ までの番号がつけられています。

各草の高さは $ 1 $以上の整数値で表され、それについて次の情報 $ S_1,S_2,…, S_{N-2} $ が分かっています。

🔹$ S_i = A $ のとき、草 $ i $ より草 $ i + 1 $ の方が高い。
🔹$ S_i = B $ のとき、草 $ i $ より草 $ i + 1 $ の方が低い。

$ N $ 個の草の高さの合計として考えられる最小値を求めて下さい。

[制約]
🔹$ 2 \leqq N \leqq 3000 $

解き方・ソースコード

この問題は、まず $ 1 $ から $ N $ まで $’A’$ の連続回数を数えます。

次に$ N $ から $ 1 $ まで $’B’$ の連続回数を数えます。

そしてそれぞれの連続回数の大きいほうを選択し、合計したものが各草の高さの合計として最小となります。

[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

#--------- 入力例 -----------
N = 7           # 草の数
S = ['A', 'A', 'B', 'A', 'B', 'B']  # 隣合う草の高低情報
#----------------------------
# 配列の準備
ret1 = [ None ] * N
ret2 = [ None ] * N

# 1からNへ'A'の連続数を数える
sa = 1  # 'A'の連続回数
ret1[0] = 1
for i in range(N - 1):
    if S[i] == 'A':
        sa += 1
    if S[i] == 'B':
        sa = 1
    ret1[i + 1] = sa
print('ret1', ret1)

# Nから1へ'B'の連続数を数える
sa = 1  # 'B'の連続回数
ret2[N - 1] = 1
for i in reversed(range(N - 1)):
    if S[i] == 'A':
        sa = 1
    if S[i] == 'B':
        sa += 1
    ret2[i] = sa
print('ret2', ret2)

# 連続数の多いほうを選ぶ
ret3 = [max(a, b) for a, b in zip(ret1, ret2)]
print('ret3', ret3)

print('解：', sum(ret3))

[実行結果]

ret1 [1, 2, 3, 1, 2, 1, 1]

ret2 [1, 1, 2, 1, 3, 2, 1]

ret3 [1, 2, 3, 1, 3, 2, 1]

解： 13

草の高さの合計値として考えられる最小値は 13 ということが分かりました。

問題

Ａ君は今後 $ D $ 日間の労働計画を立てることにしました。

Ａ君はとにかくより多く働きたいと思っています。

しかし、働きすぎると怒られてしまうため $ i=1,2,…,N $ 日目に対して以下の条件満たす必要があります。

🔹条件 $ i $ ：$ L_i ～ R_i $ 日目について、最も多く働いた日でも労働時間を $ H_i $ 時間以下にする

Ａ君の $ D $ 日間の合計労働時間として考えられる最大値は何時間でしょうか。

[制約]
🔹$ 1 \leqq D \leqq 365 $
🔹$ 0 \leqq N \leqq 10000 $
🔹$ 1 \leqq L_i \leqq R_i \leqq D $
🔹$ 9 \leqq H_i \leqq 24 $

解き方・ソースコード

この問題では「$ L ～ R $日目について最も多く働いた日でも$ H $時間以下」という条件が与えられます。

この条件は「$ L ～ R $日目の労働時間はすべて $ H $ 時間以下」と言い換えることができます。

$ d $ 日目の労働時間の上限を $ LIM[d] $ とすると、この値は次のように計算することができます。

🔹手順１：1日は24時間なので、$ LIM[d]=24 $ に初期化する。
🔹手順２：$ i=1,2,…,N $ 日目に対して以下の処理を行う。
　・$ L_i \leqq d \leqq R_i $に対して、$ LIM[d] $ を $ min(LIM[d], H_i) $ に更新する。

上記で求めた上限値は $ N $ 個すべての条件を満たします。

したがって$ LIM[1] $ から $ LIM[D] $ までの総和を出力すると、正解となります。

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

[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

#--------- 入力例 -----------
D = 5           # 労働計画を立てる日数
# 労働条件
COND = [
    {'L':1, 'R':2, 'H':22}, # 1日目から2日目について最も多く働いた時間は22時間以下
    {'L':2, 'R':3, 'H':16}, # 2日目から3日目について最も多く働いた時間は16時間以下
    {'L':3, 'R':5, 'H':9}   # 3日目から5日目について最も多く働いた時間は9時間以下
]

#----------------------------
# 配列の初期化（1 日は 24 時間）
LIM = [ 24 ] * (D + 1)

# 上限値を求める
for i, cond in enumerate(COND):
    for j in range(cond['L'], cond['R'] + 1):
        LIM[j] = min(LIM[j], cond['H'])

# 答えを出力
Answer = 0
for i in range(1, D + 1):
    print('{}日目に働ける最大時間数：{}'.format(i, LIM[i]))
    Answer += LIM[i]
print('解：', Answer)

[実行結果]

1日目に働ける最大時間数：22

2日目に働ける最大時間数：16

3日目に働ける最大時間数：9

4日目に働ける最大時間数：9

5日目に働ける最大時間数：9

解： 65

Ａ君が働ける最大時間数は65時間であることが分かりました。