AtCoder「アルゴリズムと数学 演習問題集」を全部解く!!!
はじめに
AtCoderの常設中コンテストの中に「アルゴリズムと数学 演習問題集」というものがあります。この記事では、そのコンテストの問題の解説を書いていきます！コードはPythonで書きます。全部で104問とかなりボリューミーなので、気合い入れてやっていきます!!
コンテストのURLはこちらです。https://atcoder.jp/contests/math-and-algorithm
なお、各問題の番号をクリックすると、問題のURLに飛びます！
001 - Print 5+N
問題文
りんごが5個あり、みかんがN個あります。
整数Nが与えられるので、りんごとみかんを合わせて何個あるかを出力するプログラムを作成してください。
みかんの個数を変数Nで受け取り、N+5を出力すればよさそうです！
N = int(input())
print(N+5)
002 - Sum of 3 Integers
問題文
3つの整数A_1, A_2, A_3が与えられます。
A_1 + A_2 + A_3を出力してください。
３つの整数A_1, A_2, A_3をA_1, A_2, A_3という変数で受け取り、それらを足して出力します。
入力を受け取る部分のコードmap(int, input().split())をもう少し詳しく説明します。
まず、input()で標準入力を文字列で受け取ります。
次に、input().split()とすることで、文字列を空白で分割し、リスト化することができます。
最後に、map関数を使うことで文字列から整数に変換しています。
A_1, A_2, A_3 = map(int, input().split())
ans = A_1 + A_2 + A_3
print(ans)
003 - Sum of N Integers
問題文
整数NとN個の整数A_1, A_2, ... , A_Nが与えられます。
A_1 + A_2 + ･･･ + A_Nを出力して下さい。
整数NをNという変数で受け取り、N個の整数A_1, A_2, ... , A_NをリストAで受け取ります。
その後、リストAに入っている数字を合計します。(このやり方だとNを使わないですね笑)
N = int(input())
A = list(map(int, input().split()))
ans = 0
for a in A:
ans += a
print(ans)
004 - Product of 3 Integers
問題文
3つの整数A_1, A_2, A_3が与えられます。
A_1A_2A_3を出力するプログラムを作成して下さい。
３つの整数A_1, A_2, A_3をA_1, A_2, A_3という変数で受け取り、それらをかけ算して出力します。
A_1, A_2, A_3 = map(int, input().split())
print(A_1 * A_2 * A_3)
005 - Modulo 100
問題文
N個の整数a_1, a_2, ... a_Nが与えられます。
(a_1 + a_2 + ･･･ + a_N) mod 100の値を出力して下さい。
整数NをNという変数で受け取り、N個の整数A_1, A_2, ... , A_NをリストAで受け取ります。
その後、リストAに入っている数字を合計し、totalという変数に代入します。最後に、100で割ったときの余りを出力すれば完了です！
N = int(input())
A = list(map(int, input().split()))
total = 0
for a in A:
total += a
print(total % 100)
006 - Print 2N+3
問題文
整数Nが与えられます。2N+3の値を出力して下さい。
整数NをNという変数で受け取り、2N+3を出力します。
N = int(input())
print(2 * N + 3)
007 - Number of Multiples 1
問題文
N以下の正の整数の中で、Xの倍数またはYの倍数であるものの個数はいくつありますか？
まず、N, X, Yを受け取ります。その後、N以下の正の整数iが「Xの倍数またはYの倍数」という条件に合っているかどうかを判定します。条件に合っている場合は、ansという変数に1を足しカウントします。
N, X, Y = map(int, input().split())
ans = 0
for i in range(1, N + 1):
if i % X == 0 or i % Y == 0:
ans += 1
print(ans)
008 - Brute Force 1
問題文
赤・青のカードが各1枚ずつあり、あなたはそれぞれのカードに1以上N以下の整数を1つ書き込みます。
カードに書かれた整数の合計がS以下となる書き方は、いくつありますか？
赤のカードに書かれている数字は1以上N以下のN通りの可能性があり、青のカードに書かれている数字も1以上N以下のN通りの可能性があります。
赤のカードと青のカードに書かれている数字の組み合わせを全て試し、もし合計がS以下である場合は、カウントするという方針でコーディングしました！
N, S = map(int, input().split())
ans = 0
for red in range(1, N+1):
for blue in range(1, N+1):
total = red + blue
if total <= S:
ans += 1
print(ans)
009 - Brute Force 2
問題文
N枚のカードが横一列に並べられています。左からi番目(1<=i<=N)のカードには整数A_iが書かれています。
カードの中からいくつかを選んで、合計がちょうどSとなるようにする方法はいくつありますか。
カードの選び方を全て試し、合計がちょうどSとなるようにする方法が何通りあるかを求めることができます。
ただこの方法を用いると計算量がすごいことになるため、満点を取ることができません。
import itertools
N, S = map(int, input().split())
A = list(map(int, input().split()))
flag = 1
comb_all = []
for n in range(1,len(A)+1):
for comb in itertools.combinations(A, n):
comb_all.append(list(comb))
for comb in comb_all:
if sum(comb) == S:
print("Yes")
flag = 0
break
if flag:
print("No")
そこで別のアプローチ(動的計画法)を試します。
左からi番目までのカードを用いて、合計がちょうどjとなるようにする方法があるかどうかを表す変数をC[i][j]とします。C[i][j]はtureかfalseを表しており、C[i][j]=trueのとき、左からi番目までのカードを用いて、合計がちょうどjとなるようにする方法があるということになります。
i番目のカードを用いてC[i][j]=trueとなるには、(i-1)番目までのカードの合計がj-A_iである必要があります。すなわち、C[i-1][j-A_i]=trueである必要があります。
また、i番目のカードを用いずにC[i][j]=trueとするには、(i-1)番目までのカードの合計がjである必要があります。すなわち、C[i-1][j]=trueである必要があります。
したがって、C[i][j]=trueとなる条件は、C[i-1][j-A_i]=trueまたはC[i-1][j]=trueであることが分かります。
少し分かりにくいので言葉で説明すると、左からi番目までのカードを用いて合計をちょうどjにするには、
「左からi-1番目までのカードの合計をj-A_iにして、i番目のカードの数字A_iを合わせて合計値をjにする」
または
「左からi-1番目までのカードの合計をjにして、i番目のカードは選ばない」
という2つの方法があるということです！
ここから、コーディングの解説をしていきます！
まず、カード枚数は0以上N以下、合計は0以上S以下であるため、(N+1)×(S+1)の2次元配列Cを定義します。
ここで、カード枚数が0枚のときは、合計が0となります。したがって、C[0][0] = true、C[0][j] = false(1<=j<=S)となります。
次に、カード枚数が1枚以上の場合、C[i][j]=trueとなる条件は、C[i-1][j-A_i]=trueまたはC[i-1][j]=trueとなります。
ただし、j < A_iの場合、j-A_i < 0となってしまうため、C[i][j]=trueとなる条件はC[i-1][j]=trueとなります。
以上の内容を踏まえると、下記のようなコードになります。(難しいですね～)
N, S = map(int, input().split())
A = list(map(int, input().split()))
C = [[None] * (S+1) for i in range(N+1)]
C[0][0] = True
for j in range(1, S+1):
C[0][j] = False
for i in range(1, N+1):
for j in range(S+1):
if j < A[i-1]:
C[i][j] = C[i-1][j]
else:
C[i][j] = C[i-1][j-A[i-1]] or C[i-1][j]
if C[N][S]:
print("Yes")
else:
print("No")
010 - Factorial
問題文
N!の値を求めて下さい。
ansという変数を用意して、1で初期化します。その後、ansに対して、1, 2, 3, ... , Nを掛けていけば、N!を求めることができます！
N = int(input())
ans = 1
for i in range(1, N+1):
ans *= i
print(ans)
011 - Print Prime Numbers
問題文
N以下の素数を、小さい順に出力して下さい。
まず素数かどうかを判定する関数isPrimeを定義します。素数は「1とその数以外で割り切れない整数」であるため、2以上N-1以下の整数で割っていき、1回でも割り切れた場合は素数ではなく、1回も割り切れなかった場合は素数ということになります。isPrime関数はnumが素数のときTrueを返し、素数ではないときFalseを返す関数となっています。
def isPrime(num):
flag = True
for i in range(2, num):
if num % i == 0:
flag = False
return flag
N = int(input())
A = []
for i in range(2, N+1):
if isPrime(i):
A.append(i)
print(*A)
おわりに
まだ11問しか取り組めていないため、104問終わるまで頑張って更新したいと思います！
Discussion