問題

対応の取れているカッコ列 $ 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時間であることが分かりました。

問題

$ N $ 個の整数があります。

整数は小さい順に $ A_1,A_2,…,A_N $ と並んでいます。

異なる２つの整数のペアを選ぶ方法は全部で $ N(N-1)/2 $ 通りありますが、その中で差が $ K $ 以下であるような選び方は何通りあるでしょうか。

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

解き方・ソースコード

$ A_t \leqq A_i + K $ を満たす最大の $ t $ を $ R_i $ とし、$ R_i $ の値を次のように計算します。

🔹手順１　$ i = 1 $ であれば $ R_i = 1 $ から、そうでなければ $ R_i = R_{i-1} $ からスタートする。
🔹手順２　差分 $ A_{R_{i}} - A_i $ が $ K $ を超えないギリギリまで、$ R_i $ を１増やす操作を繰り返す。

求めるペアの個数は $ (R_i - i) $ 通りで、答えは次式で計算できます。

$$ (R_1 - 1) + (R_2 - 2) + … + (R_{N-1} - (N -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

#--------- 入力例 -----------
N = 7       # 整数の数
K = 10      # 差をK以下にする
A = [9, 10, 14, 20, 25, 26, 29]     # 小さい順に並んだ整数
#----------------------------
# 配列の準備（R は 0 番目から始まる）
R = [ None ] * N

# しゃくとり法
for i in range(0, N - 1):
    # スタート地点を決める
    if i == 0:
        R[i] = 0
    else:
        R[i] = R[i - 1]

    # ギリギリまで増やしていく
    while R[i] < N - 1 and A[R[i] + 1]-A[i] <= K:
        R[i] += 1
    print(R)

# 出力
Answer = 0
for i in range(0, N - 1):
    Answer += (R[i] - i)
print('解：', Answer)

このアルゴリズムは、しゃくとり虫の動きにたとえてしゃくとり法と呼ばれています。

$ R_i $ を増やす操作は合計 $ N - 1 $ しか行われないので、計算量は $ O(N) $ となります。

[実行結果]

[2, None, None, None, None, None, None]

[2, 3, None, None, None, None, None]

[2, 3, 3, None, None, None, None]

[2, 3, 3, 6, None, None, None]

[2, 3, 3, 6, 6, None, None]

[2, 3, 3, 6, 6, 6, None]

解： 11

整数のペアの差が10以下になる組み合わせは、11通りあることを導き出すことができました。

問題

正の整数 $ N $ が与えられます。

$ x^3 + x = N $ を満たす正の実数 $ x $ を求めて下さい。

ただし絶対誤差が $ 0.01 $ 以下であれば正解とします。

解き方・ソースコード

$ f(x) = x^3 + x $ は単調な増加関数です。

$ x $ が増えると $f(x) $ も増えます。

二分探索を使って、$ x $ の範囲を次第にせまくしていくことにより正の整数 $ N $ に答えを近づけていきます。

今回は実行回数を20回としていますが、許容できる誤差の範囲に応じて調整しましょう。

[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

#--------- 入力例 -----------
N = 99      # 正の整数
#----------------------------
def f(x):
    return x * x * x + x

# 二分探索
Left = 0.0
Right = 100.0
for i in range(20):
    Mid = (Left + Right) / 2
    val = f(Mid)
    print(Mid, val)

    # 探索範囲を絞る
    if val > N:
        Right = Mid     # 左半分に絞られる
    else:
        Left = Mid      # 右半分に絞られる

# 出力
print('解：', Mid)
print('x={}のときf(x)は{}'.format(Mid, f(Mid)))

[実行結果]

50.0 125050.0

25.0 15650.0

12.5 1965.625

6.25 250.390625

3.125 33.642578125

4.6875 107.684326171875

3.90625 63.510894775390625

4.296875 83.63065719604492

4.4921875 95.14340162277222

4.58984375 101.28254741430283

4.541015625 98.1804946437478

4.5654296875 99.7233574045822

4.55322265625 98.94989057502244

4.559326171875 99.33611444539565

4.5562744140625 99.1428752093725

4.55474853515625 99.04635107764648

4.553985595703125 98.99811287402898

4.5543670654296875 99.02222998759483

4.554176330566406 99.01017093377199

4.554080963134766 99.0041417796431

解： 4.554080963134766

x=4.554080963134766のときf(x)は99.0041417796431

解は4.554080963134766となりました😊

実際に計算式 $ x^3 + x = N $ に当てはめると結果は99.0041417796431となり、許容誤差の0.01以下となります。

問題

$ N $ 台のプリンターがあり、$ 1 $ から $ N $ までの番号がつけられています。

プリンター $ i $ は $ A_i $ 秒ごとに１枚印刷できます。

つまりスイッチを入れてから $ A_i $ 秒後に１枚、$ 2A_i $ 秒後にもう１枚・・・と印刷可能です。

全てのプリンターのスイッチを同時に入れたとき、$ K $ 枚目が印刷されるのは何秒後でしょうか。

[制約]
🔹$ 1 \leqq N \leqq 100000 $
🔹$ 1 \leqq K \leqq 10^9 $
🔹$ 1 \leqq A_i \leqq 10^9 $
🔹答えは $ 10^9 $ 以下

解き方・ソースコード

この問題では、答えに対して二分探索を行うと効率的に解くことができます。

答えが１秒後から８秒後までのいずれかであると仮定してみます。

答えの候補の中央は４秒後ですので、答えが４秒以下かどうか？を考えます。

下記ソースの入力例を考えると、４秒後までに印刷される枚数は８枚であり $ K=10 $ 枚未満なので質問の答えはNoとなります。

この時点で、答えの候補が５秒後から８秒後までの範囲に絞られます。

この処理を探索範囲の左端(Left)と右端(Right)が同じになるまで繰り返します。

[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

#--------- 入力例 ----------
N = 4      # プリンターの数
K = 10     # 印刷したい枚数
A = [1, 2, 3, 4]
#----------------------------
# 答えがx以下かを判定し、YesであればTrue、No あればFalseを返す
def check(x, N, K, A):
    sum = 0
    for i in range(N):
        sum += x // A[i] # 「x ÷ A[i]」の小数点以下切り捨て
    print('{}秒後に印刷できる枚数は{}'.format(x, sum))
    if sum >= K:
        return True
    else:
        return False

# Left は探索範囲の左端、Right は探索範囲の右端を表す
Left = 1
Right = 10 ** 3
while Left < Right:
    Mid = (Left + Right) // 2
    Answer = check(Mid, N, K, A)

    if Answer == False:
        Left = Mid + 1  # 答えが Mid+1 以上である
    if Answer == True:
        Right = Mid     # 答えが Mid 以下である

# 出力（このとき Left=Right になっている）
print('解：', Left)

[実行結果]

500秒後に印刷できる枚数は1041

250秒後に印刷できる枚数は520

125秒後に印刷できる枚数は259

63秒後に印刷できる枚数は130

32秒後に印刷できる枚数は66

16秒後に印刷できる枚数は33

8秒後に印刷できる枚数は16

4秒後に印刷できる枚数は8

6秒後に印刷できる枚数は12

5秒後に印刷できる枚数は9

解： 6

この処理を繰り返すと6秒後に印刷される枚数が12枚となり、6秒後が正解となります。

問題

小さい順に並べられている要素数 $ N $ の配列 $ A = [A_1, A_2, …, A_N] $ があります。

要素 $ X $ は配列 $ A $ の何番目に存在するかを求めて下さい。

この問題は全探索でも解くことができますが、今回は二分探索を使って実装して下さい。

[制約]
🔹$ 1 \leqq N \leqq 100000 $
🔹$ 1 \leqq A_1 < A_2 < … < A_N \leqq 10^9 $
🔹探す整数 $ X $ は $ A_1,A_2,…,A_N $ のいずれかである

解き方・ソースコード

二分探索では、探索範囲の左側を $ L $ 番目、右端を $ R $ 番目とするとき、次のような処理によって探索範囲を半分に絞っていきます。

🔹$ M=(L+R)/2 $ とする（割り切れない場合は切り捨てる）
🔹$ X < A_M $ の場合：探索範囲を左半分にする（$ R $ の値を $ M - 1 $ にする）
🔹$ X = A_M $ の場合：答えは $ M $ である
🔹$ X > A_M $ の場合：探索範囲を右半分にする（$ L $ の値を $ M + 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

#--------- 入力例１ ---------
N = 15      # 要素数
X = 47      # 探す要素
A = [8, 13, 17, 19, 24, 27, 33, 37, 41, 43, 47, 53, 59, 61, 68]
#--------- 入力例２ ---------
# N = 10      # 要素数
# X = 80      # 探す要素
# A = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
#----------------------------
# 整数 x が何番目に存在するかを返す関数
def search(x, A):
    L = 0
    R = N - 1
    while L <= R:
        M = (L + R) // 2
        if x < A[M]:
            print('求める要素{}は、要素{}({}番目)より小さい'.format(x, A[M], M))
            R = M - 1
        if x == A[M]:
            print('求める要素{}は、要素{}({}番目)と同じ'.format(x, A[M], M))
            return M
        if x > A[M]:
            print('求める要素{}は、要素{}({}番目)より大きい'.format(x, A[M], M))
            L = M + 1
    return - 1 # 整数 x が存在しない（注：この問題の制約で -1 が返されることはない）

# 二分探索を行う
Answer = search(X, A)
print('解：', Answer + 1)  # 配列が 0 番目から始まるので、答えに 1 を足す

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

求める要素47は、要素37(7番目)より大きい

求める要素47は、要素53(11番目)より小さい

求める要素47は、要素43(9番目)より大きい

求める要素47は、要素47(10番目)と同じ

解： 11

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

求める要素80は、要素50(4番目)より大きい

求める要素80は、要素80(7番目)と同じ

解： 8

二分探索では１回の判定で探索範囲が半分になるので、配列の長さを $ N $ とするとき、$ \log_2 N $ の比較を行うことになります。

つまり計算量は $ O(\log N) $ となります。