Supershipの名畑です。公開されたてほやほやの「TVアニメ『ヒプノシスマイク-Division Rap Battle-』Rhyme Anima ＋ OPテーマ「RISE FROM DEAD」 MV」大好きです。
こちらは競プロ Advent Calendar 2023の3日目の記事となります。
Twitterでのハッシュタグは#競プロAdCです。
はじめに
前も触れましたが、AtCoderでは、競技プログラミングの世界で有名なE869120さん執筆の書籍「問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本」の演習問題集が公開されています。
今回の記事ではこのうちの2章「アルゴリズムのための数学の基本知識」と3章「基本的なアルゴリズム」の全問題をPythonで解いてみたので、そのコードを残します。数学の復習に良さそうです。一部の問題はプログラミング初心者にも良さそうです。
学習目的のコンテンツのため、基本的にモジュールのimportは抜きで書きます。1問だけ使っていますが、それも使わない場合の方法を後述します。
2章「アルゴリズムのための数学の基本知識」
変数と定数の加算
Nに5を足して出力します。
N = int(input())
print(5 + N)
3個の変数の加算
A1、A2、A3の和を出力します。
A1, A2, A3 = map(int, input().split())
print(A1 + A2 + A3)
N個の変数の加算
配列の合計値を出力します。
N = int(input())
A = list(map(int, input().split()))
print(sum(A))
3個の変数の乗算
A1、A2、A3の積を出力します。
A1, A2, A3 = map(int, input().split())
print(A1 * A2 * A3)
剰余
配列の合計値を100で割った余りを出力します。
N = int(input())
a = list(map(int, input().split()))
print(sum(a) % 100)
1次式
Nを2倍して3を足した結果を出力します。
N = int(input())
print(2 * N + 3)
倍数と最小公倍数
N以下の整数の中でXあるいはYの倍数がいくつあるかを出力します。
Xの倍数の個数とYの倍数の個数を足し、そこからXとYの公倍数の個数を引きます。
lcmは最小公倍数を求める関数です。lcmを用いずに最小公倍数を求める方法は後述の「N個の整数での最小公倍数」で取り上げます。
import math
N, X, Y = map(int, input().split())
print(N // X + N // Y - N // math.lcm(X, Y))
全探索
2枚のカードにそれぞれ1以上N以下の整数を書き、その合計がS以下になる組み合わせの数を求めます。
総当たりです。
N, S = map(int, input().split())
answer = 0
for i in range(1, N + 1):
for j in range(1, N + 1):
if i + j <= S:
answer += 1
print(answer)
bit全探索と動的計画法
1≦N≦20について解けると部分点として500点となり、N≦60までを解けると1000点となります。下記は500点となるコードと1000点となるコードの両方を記載します。過去記事で解説した内容と同様です。
動的計画法については後述の問題でもいくつも出てきますが、詳しくは過去記事「動的計画法の基本を理解するためのAtCoder問題5選とPython解答例」をご覧いただけますと幸いです。
bit全探索による500点のコード
たとえばNが3で、各カードをA0、A1、A2とします。
このときとりうるカードの組み合わせは
- A0
- A1
- A1 + A0
- A2
- A2 + A0
- A2 + A1
- A2 + A1 + A0
の7パターンです。(問題文においてSは1以上のため、カードを選ばないことはない）
2進数で記すなら
- 001
- 010
- 011
- 100
- 101
- 110
- 111
と書けます。左から順にそれぞれの桁がA2、A1、A0の有無を示しているとします。
コードにすると下記です。2進数各桁の取得は右シフトしつつ1との論理積をとっています。1との論理積をとれば下1桁の値になります。
N, S = map(int, input().split())
A = list(map(int, input().split()))
for i in range(1, 2 ** N):
total = 0
for j in range(N):
total += A[j] * ((i >> j) & 1) # 2進数にした各桁が1のときだけAを足す
if total == S:
print('Yes')
exit()
print('No')
計算量がNの2乗に比例するため、Nが大きくなると1000msecを超えてTLE(Time Limit Exceeded)です。
動的計画法(DP)による1000点のコード
たとえばNが2で、各カードをA0、A1とします。
そしてA0が2、A1が3だとします。
1枚目のカードとしてA0を選んだとき、その時点での合計値は2です。選ばなければ0です。
つまり、A0だけしかカードがなかった場合、0と2がとりうる数です。
さらに、A1を選ぶか選ばないかまで考えると
- 0 + 0 = 0
- 0 + 3 = 3
- 2 + 0 = 2
- 2 + 3 = 5
この4パターンです。つまり、A0とA1の2枚のカードしかなかった場合、0、2、3、5の4つがとりうる値となります。
Sがこの中にあればYes、なければNoという考え方です。
N, S = map(int, input().split())
A = list(map(int, input().split()))
dp = [False] * (S + 1) # 0〜Sまでの値をとりうるかを格納する配列
dp[0] = True # 0のみTrueにしておく
for i in range(N): # 0枚目から順番にカードを見ていく
for j in reversed(range(0, S)): # dpの値が途中で変わらないようにreversedしている
if dp[j] and j + A[i] <= S:
dp[j + A[i]] = True
if dp[S]: # Sをとりうるか判定する
print('Yes')
else:
print('No')
階乗
Nの階乗を求めます。
N = int(input())
ans = 1
for i in range(1, N + 1):
ans *= i
print(ans)
素数の列挙
N以下の素数を出力します。
総当たりをしています。
N = int(input())
answer = []
for i in range(2, N + 1):
for j in range(2, i):
if i % j == 0:
break
else:
answer.append(i)
answer.sort()
[print(i, end=' ') for i in answer]
3章「基本的なアルゴリズム」
ここから3章です。
素数判定
Nが素数かの判定を行います。
無駄は多いですが、総当たりでも間に合います。
2以外の偶数を省く等をした方がより効率的です。
繰り返しは√Nまで(1/2乗)としています。
√Nまでで割り切れなければ、それより大きいN以外の数で割り切れることはないため。
N = int(input())
if N == 1:
print('No')
exit()
for i in range(2, int(N ** 0.5) + 1):
if N % i == 0:
print('No')
exit()
print('Yes')
約数の列挙
Nの約数を列挙します。
これもほぼ総当たりですが繰り返しは√Nまでとしています。
たとえばNが6であれば、約数は1、2、3、6です。√6は2.449...ですので3以降が含まれませんが、その代わりに
- 1で割り切れる時は6 / 1の答えである6も約数に加える
- 2で割り切れる時は6 / 2の答えである3も約数に加える
ということをしています。iで割り切れるならば、Nをiで割った数も約数となるからです。
N = int(input())
ans = []
for i in range(1, int(N ** 0.5) + 1):
if N % i == 0:
ans.append(i)
if i != N // i:
ans.append(N // i)
[print(i) for i in ans]
素因数分解
nを素因数分解します。
2から順番に割っていくだけです。
計算量を減らすため、ループを回す条件を div <= int(n ** 0.5) として、残ったnをanswerに追加します。
これも偶数は2以外を見る必要はないですが、時間的には下記のような総当たりでも充分に間に合います。
n = int(input())
answer = []
div = 2
while div <= int(n ** 0.5):
if n % div == 0:
answer.append(div)
n //= div # 小数にならないように切り捨て
else:
div += 1
if n > 1:
answer.append(n)
[print(i, end=' ') for i in answer]
2個の整数での最大公約数
AとBの最大公約数を求めます。
ユークリッドの互除法を使います。
A, B = map(int, input().split())
a, b = max([A, B]), min([A, B])
while b > 0:
a, b = b, a % b
print(a)
N個の整数での最大公約数
N個になってもやることは1つ前の問題と同じです。順番に最大公約数を求めていきます。
N = int(input())
A = list(map(int, input().split()))
a = A[0]
for i in range(1, N):
a, b = max([a, A[i]]), min([a, A[i]])
while b > 0:
a, b = b, a % b
print(a)
N個の整数での最小公倍数
最小公倍数はa * b / 最大公約数で求められます。
N = int(input())
A = list(map(int, input().split()))
a = A[0]
for i in range(1, N):
a_temp = a
a, b = max([a, A[i]]), min([a, A[i]])
while b > 0:
a, b = b, a % b
a = a_temp * A[i] // a
print(a)
組み合わせ 1
100円、200円、300円、400円の4種類の商品が合計でN個あり、その中から合計で500円になる組み合わせの数を求めるというものです。
100円と400円あるいは200円と300円の組み合わせのみが500円となります。
N = int(input())
A = list(map(int, input().split()))
print(A.count(100) * A.count(400) + A.count(200) * A.count(300))
組み合わせ 2
Aという配列に1、2、3のいずれかの値が格納され、同じ数のペアがどれだけ作れるかという問題です。
N = int(input())
A = list(map(int, input().split()))
red = A.count(1)
yellow = A.count(2)
blue = A.count(3)
answer = 0
if red > 0:
answer += red * (red - 1) // 2
if yellow > 0:
answer += yellow * (yellow - 1) // 2
if blue > 0:
answer += blue * (blue - 1) // 2
print(answer)
組み合わせと動的計画法
整数が書かれたカードがN枚あり、これを5枚組み合わせて合計が1000になる組み合わせがいくつあるかという問題です。
dp[選んだカードの枚数][合計値] の配列を用意します。たとえば dp[3][500] が3であれば「3枚のカードを選んで500になる組み合わせが3つある」となります
N = int(input())
A = list(map(int, input().split()))
dp = [[0] * 1001 for i in range(6)] # dp[6][1001]
dp[0][0] = 1 # 0枚目で合計が0を1としておく
for i in range(N):
for j in reversed(range(1001)): # reversedにして同じカードが複数回選ばれないようにする
for k in reversed(range(5)): # reversedにして同じカードが複数回選ばれないようにする
if dp[k][j] > 0 and j + A[i] < 1001:
dp[k + 1][j + A[i]] += dp[k][j]
print(dp[5][1000])
組み合わせ 3
組み合わせを求める問題です。
組み合わせの公式をそのままコードにすると下記です。
n, r = map(int, input().split())
answer = 1
for i in range(0, r):
answer *= n - i
for i in range(1, r + 1):
answer //= i
print(answer)
組み合わせ 4
ペアにすると和が100000となるカードの組み合わせの数を求める問題です。
配列cardを用意します。cardは要素数が100001で、その数字のカードが何枚あるかを格納します。たとえば card[3000] の値は、3000のカードが何枚あるかです。
カードを選ぶ度に、そのカードと組み合わせて100000になるカードがこれまでに何枚あるかを変数answerに足しながら、cardの値を加算していきます。
N = int(input())
A = list(map(int, input().split()))
card = [0] * 100001
answer = 0
for i in range(N):
if card[100000 - A[i]] > 0:
answer += card[100000 - A[i]]
card[A[i]] += 1
print(answer)
確率と期待値 1
BとRの2つのサイコロの出目の期待値を求める問題です。
すべての目が等確率で出るので、BとRのそれぞれの合計値をNで割れば期待値となります。
N = int(input())
B = list(map(int, input().split()))
R = list(map(int, input().split()))
print(sum(B) / N + sum(R) / N)
確率と期待値 2
P個の選択肢で配点がQのテストがある場合の期待値を求める問題です。
正解の確率は1/Pとなります。
当たったときの点数はQのため、各問題での期待値はQ/Pです。
これを合計します。
N = int(input())
answer = 0
for i in range(N):
P, Q = map(int, input().split())
answer += Q / P
print(answer)
確率と期待値 3
サイコロで1か2が出た場合はAが適用され、3〜6が出た場合はBが適用される場合の期待値を求める問題です。
1か2が出る確率は1/3で、3〜6が出る確率は2/3です。Aに1/3をかけ、Bに2/3をかけていきます。
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
answer = 0
for i in range(N):
answer += A[i] / 3 + 2 * B[i] / 3
print(answer)
確率と期待値 4
N種類のうちの1つがランダムで出るコインを全て揃えるためにかかる試行回数の期待値を求める問題です。
数式的には 1/N、1/(N-1)、1/(N-2)...1/1の合計値にNをかければ求められます。
詳しい証明は検索していただければと思うのですが、つまりは以下のような感じです。
たとえば4枚のコインがあった場合、1枚目のコインはどれが出ても欲しいコインです。
つまり当たる確率は4/4です。
次が当たる確率(まだ出ていないコインである確率)は3/4になります。
さらに次は2/4で、最後は1/4です。
この逆数が必要な試行回数の期待値となるため、4/4 + 4/3 + 4/2 + 4/1です。
つまりは 4 * (1/4 + 1/3 + 1/2 + 1/1) となります。
コードにすると下記です。
N = int(input())
p = 0
for i in range(1, N + 1):
p += 1 / i
print(N * p)
再帰とマージソート
sortを呼び出してしまえば終わりなのでしょうが、それだと学習にならないため、マージソートのコードを記載します。
全体を分割し、並べ替えながら結合していくというものです。
# すでに昇順となっている二つの配列を受け取って昇順に並べる
def merge(left, right):
il = 0
ir = 0
result = []
while True:
if left[il] < right[ir]:
result.append(left[il])
il += 1
else:
result.append(right[ir])
ir += 1
if il >= len(left):
result += right[ir:]
return result
elif ir >= len(right):
result += left[il:]
return result
# 配列を真ん中で二つに分割し、分割した二つを引数として自らを呼び出し、最後にmergeを呼び出す
def divide(arr):
len_arr = len(arr)
if len_arr <= 1:
return arr
left = arr[:len_arr // 2]
right = arr[len_arr // 2:]
left = divide(left)
right = divide(right)
return merge(left, right)
N = int(input())
A = list(map(int, input().split()))
answer = divide(A)
print(*answer)
動的計画法 部分和問題 1
- 問題：028 - Frog 1
N個の足場があり、それぞれの高さはhという配列に格納されています。
カエルは一つ先の足場か二つ先の足場にのみ移動でき、その際のコストは今いる足場との高さの差です。
カエルがN個目の足場にたどり着くまでのコストの総和の最小値を求めるという問題です。
1個目の足場にたどり着くまでのコストの最小値、2個目の足場にたどり着くまでのコストの最小値……N個目の足場にたどり着くまでのコストの最小値を順番に求めていきます。
下記はコードです。コードを簡潔にしたかったため足場を0〜N-1としてあるのでご注意ください。
N = int(input())
h = list(map(int, input().split()))
# i個目の足場にたどり着くまでのコストの最小値を格納する配列
dp = [float('inf')] * N # 初期値として無限大を入れておきます
dp[0] = 0 # 最初にいる足場までのコストを0とする
for i in range(0, N - 1): # 最初の足場から最後の1個前の足場まで
for dist in [1, 2]: # 1つ先の足場に移動した時と2つ先の足場に移動した時のコストの最小値を記録する
if i + dist < N: # 移動可能である
diff = abs(h[i + dist] - h[i]) # 高さの差
if dp[i] + diff < dp[i + dist]: # 最小値である
dp[i + dist] = dp[i] + diff
print(dp[N - 1]) # 最後の足場にいるときの最小値を出力する
動的計画法 部分和数え上げ問題
階段を同時に1段か2段だけ上れます。N段目にたどり着くまでのパターン数を求める問題です。
stepという配列にパターン数を記録していきます。
たとえばstep[1]なら1段目までのパターン数を格納します。これは0段目から1段上がったときの1パターンしかありません。
N = int(input())
step = [0] * (N + 2) # i+2の計算ではみ出たときのために+2としている
step[0] = 1
for i in range(N):
step[i + 1] += step[i]
step[i + 2] += step[i]
print(step[N])
動的計画法 最適化問題
重さwと価値vが割り当てられたN個の品物があります。
許容重量がWのナップサックに価値が最大化するように品物を入れてくださいという問題です。
いわゆるナップサック問題というやつです。
dp[N+1][W+1] の配列を用意します。
たとえば dp[3][2] ならば3番目の品物までで許容重量が2までの場合の価値の最大値を示します。
コードにすると下記です。
N, W = map(int, input().split())
v = [0] * N
w = [0] * N
for i in range(N):
w[i], v[i] = map(int, input().split())
# 2次元配列を初期値0で用意する
dp = [[0 for i in range(W + 1)] for j in range(N + 1)]
for i in range(N): # N個の荷物を順番に見る
for j in range(W + 1): # ナップサックの許容重量を0〜Wと仮定する
if w[i] <= j: # i番目の品物がナップサックの許容重量以下である
# ナップサックに入れた方が価値が上がるかどうかを求める
dp[i + 1][j] = max(dp[i][j - w[i]] + v[i], dp[i][j])
else: # ナップサックに入れられないのでi-1番目の品物までの時の価値をそのまま用いる
dp[i + 1][j] = dp[i][j]
print(dp[N][W])
動的計画法 部分和問題 2
先述の「bit全探索と動的計画法」と同様です。
動的計画法 部分和問題 3
Aという配列から連続しないように値を選択した場合の合計の最大値を求める問題です。
dp[i][0] はi番目を選択しなかったときの最大値、dp[i][1] はi番目を選択したときの最大値を示すとします。
dp[i][0] は dp[i-1][0] と dp[i-1][1] の大きい方となります。選択をしていないため、前日の [0] の要素か [1] のいずれかのままとなるからです。
dp[i][0] は dp[i-1][0] と A[i] の和となります。2連続で選択することはできないため、前日の [0] の要素との和になります。
N = int(input())
A = list(map(int, input().split()))
dp = [[0] * 2 for i in range(N + 1)]
for i in range(1, N + 1):
dp[i][0] = max([dp[i - 1][0], dp[i - 1][1]])
dp[i][1] = dp[i - 1][0] + A[i - 1]
print(max([dp[N][0], dp[N][1]]))
二分探索
Xが配列Xの中に存在するかを求める問題です。
下記のようにinだけで終わります。
N, X = map(int, input().split())
A = list(map(int, input().split()))
if X in A:
print('Yes')
else:
print('No')
ただ、問題としては二分探索を使うことを期待しています。
二分探索を使うと下記のコードです。
N, X = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
n = 1
low = 0
high = N - 1
while n > 0:
n = (low + high) // 2
if A[n] == X:
print('Yes')
exit()
if A[n] < X:
if low == n:
break
low = n
else:
if high == n:
break
high = n
print('No')
最後に
良い頭の体操になりました。
私はSupershipグループ Advent Calendar 2023でも25日目に投稿予定です。盛り上がれー。
宣伝
SupershipのQiita Organizationを合わせてご覧いただけますと嬉しいです。他のメンバーの記事も多数あります。
Supershipではプロダクト開発やサービス開発に関わる方を絶賛募集しております。
興味がある方はSupership株式会社 採用サイトよりご確認ください。