FUNCoder-第4回活動
第4回活動 2024/05/22 18:15~19:45 @593教室
/icons/hr.icon
問題一覧
/icons/hr.icon
$ N枚の赤いカードと$ N枚の青いカードの組み合わせは$ N^2通りあるのでこれを全探索します。
これは$ 2重 for 文を用いることで実装することができます。
code:Python
for i in range(N): # 赤いカードを全探索
for j in range(N): # 青いカードを全探索
これは計算量が$ O(N^2)になります。
これを踏まえて、以下のようにして解くことができます。
解答例
count で条件を満たすものの個数を数え上げる方法
code:Python
N, K = map(int, input().split())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
count = 0 # Pi + Qj == K を満たすものの個数 for i in range(N): # P の配列を全列挙
for j in range(N): # Q の配列を全列挙
count += 1
if count >= 1:
print("Yes")
else:
print("No")
bool で管理する方法
code:Python
N, K = map(int, input().split())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
flag = False # 条件を満たす組があるかどうか
for i in range(N): # P の配列を全列挙
for j in range(N): # Q の配列を全列挙
flag = True
if flag == True:
print("Yes")
else:
/icons/hr.icon
$ 10進数の値を$ 2進数に変換する方法はいくつかありますが、Python には自動で変換してくれる便利な関数が存在します。
それが bin 関数と呼ばれるものです。bin 関数に整数$ Nを渡すと、文字列型で$ 2進数に変換した結果が返ってきます。
また、$ 2進数を表す 0b が先頭に付くので$ 2進数の値のみを取得したければ文字列なので$ 2文字目以降をスライスすることで取得することができます。
code:Python
N = int(input()) # 10進数の値を入力として受け取る
S = bin(N) # 10進数 N を 2 進数に変換する
S = S2: # 先頭 2 文字の 0b は不要なのでスライスを用いて削除する print(S) # 2進数に変換した値を出力する
解答例
bin 関数を用いて$ 2進数に変換する方法
code:Python
N = int(input())
ans = bin(N)2: # 2進数に変換して先頭の 0b を削除 l = len(ans) # 2進数の文字列の長さを取得する
print("0"*(10 - l) + ans)
bin 関数を使用せず、数学的に$ 2進数に変換する方法
code:Python
N = int(input())
M = 10 # 桁数
for i in range(M):
if N % 2 == 1:
N //= 2
ans.reverse() # 2 進数に変換した際の先頭から求めているので文字列を反転させる
print(*ans) # 配列の要素のみを出力する
/icons/hr.icon
長さ$ Nの配列$ Aから$ 2項ずつ取得しそれらを掛け算する組み合わせは下記のように$ N - 1通りあります。
$ A[0] \times A[1]
$ A[1] \times A[2]
$ A[2] \times A[3]
$ \vdots
$ A[N - 3] \times A[N - 2]
$ A[N - 2] \times A[N - 1]
※プログラムでは一般に先頭を$ 0、末尾を$ N - 1で捉えることに注意しましょう。
したがって、これらの値を$ i = 0, 1, \dots, N - 2まで for 文を用いて$ N - 1回ループさせ、あらかじめ用意しておいた空の配列$ Bに対して要素を追加（append）していくことで解くことができます。
解答例
空の配列$ Bを用意して append していく方法
code:Python
N = int(input())
A = list(map(int, input().split()))
B = []
for i in range(N - 1):
print(*B) # 配列 B の要素を空行区切りで出力する
/icons/hr.icon
この問題は入力の受け取り方で工夫をする必要があります。
いつも通り、文字列なので S = input()と受け取って答えを求めることも当然できますが、実装が重くなってしまい大変です。
ここで、この問題の制約に着目してみると、$ 2つ目の制約に「$ Sは |をちょうど$ 2個含む」と書かれているので、.split('|')をすることで|ごとに区切って$ Sを取得することができます。
code:Python
S = input().split('|') # | ごとに分割する
すると、文字列の長さは制約より必ず$ 3になるので後は先頭の要素と末尾の要素を足すことで答えを求めることができます。
解答例
code:Python
S = input().split('|')
print(S0 + S2) # | ごとに分割した後、先頭の要素と末尾の要素を足した文字列を出力する /icons/hr.icon
$ \dfrac{B}{A}の切り捨ては$ \left\lfloor \dfrac{B}{A} \right\rfloorで表され、切り上げは$ \left\lceil \dfrac{B}{A} \right\rceilで表されます（解説によくこれらの記号が用いられるので慣れましょう）。
前者について、Python であれば // 演算子を用いることで解くことができます。
code:python
A, B = map(int, input().split())
print(B // A) # 切り捨て除算
ただし、後者については / 演算子を用いてしまうと誤差が出てしまうため、非推奨となっています。
そこで切り上げを // 演算子のみで行うには以下のようにして解くことができます。
code:python
A, B = map(int, input().split())
print((A + B - 1) // A) # 切り上げ除算
つまり、$ \left\lceil \dfrac{B}{A} \right\rceil = \left\lfloor \dfrac{A + B - 1}{A} \right\rfloorで求めることができます。
※上記の式が成り立つ証明は高校数学までの範囲で出来るので余力のある方は挑戦してみましょう。
解答
code:Python
X = int(input())
print((X + 10 - 1) // 10)
/icons/hr.icon
仮に全探索をした場合の計算量を考えてみます。
各色に対してカードのパターンは$ N通りあるのでそれが$ 3つだと$ N^3通り存在することがわかります。
ここでこの問題の制約に着目すると$ 1 \leq N \leq 3000となっています。
したがって、$ N = 3000の場合を考えると、$ N^3 = 3000^3 = 27 \times 10^9 \fallingdotseq 3 \times 10^{10}通りあることがわかります。
一応、TLE しますが答えが合うコードも下記に示しておきます（$ O(N^3)解法）。
code:Python
N, K = map(int, input().split())
cnt = 0
for red in range(1, N + 1): # 赤を全探索
for blue in range(1, N + 1): # 青を全探索
for white in range(1, N + 1): # 白を全探索
if red + blue + white == K: # 3枚のカードの合計が K であれば答えに 1 を加える
cnt += 1
print(cnt)
Python の場合$ 2秒で行える計算回数は精々$ 10^8回程度です。
したがって、$ 10^{10}回も計算をすると、$ 2 \mathrm{s} \times \dfrac{10^{10}}{10^8} = 2 \mathrm{s} \times 10^2 = 200 \mathrm{s}なので$ 3分以上もかかってしまいます。
なので$ N^3通りの組み合わせを工夫して$ N^2通りにできないか考えてみます。
まず赤・青について全探索を行います。
code:Python
for red in range(1, N + 1): # 赤のカードの組みを全探索
for blue in range(1, N + 1): # 青のカードの組みを全探索
num = red + blue # 赤と青のカードの合計
このようなコードを記述することで赤と青の合計を求めることができます。
この時、白のカードは合計が$ Kである必要があるため、$ K - (\mathrm{red} + \mathrm{blue})で求めることができます。
後は、この値が条件である$ 1以上$ N以下を満たしているか確認し、条件を満たしている場合は答えに$ 1を加えることでこの問題を解くことができます。
解答例
code:Python
N, K = map(int, input().split())
cnt = 0
for red in range(1, N + 1): # 赤を全探索
for blue in range(1, N + 1): # 青を全探索
# 白の可能性を求める
white = K - (red + blue)
# 白が条件を満たしていれば数える
if 1 <= white <= N:
cnt += 1
print(cnt)
/icons/hr.icon
この問題は bisect ライブラリを用いて二分探索を行う必要があります。
あらかじめ配列$ Aをソートし、bisect.bisect_leftを用いると配列$ Aの$ X以下の個数を取得することができます。
ソートの計算量は$ O(N \log N)、bisect.bisect_leftの計算量は$ 1回あたり$ \log Nかかるので、
全体としての計算量は、$ O(N \log N + Q \log N) = (N + Q) \log Nで求めることができます。
※この問題は上記の$ 6問と比べると一気に難易度が跳ね上がるため、詳しく知りたいという方は個別に連絡してください。
解答例
code:Python
import bisect
N = input()
A = list(map(int, input().split()))
A.sort()
Q = int(input())
for _ in range(Q):
X = int(input())
t = bisect.bisect_left(A, X)
print(t)
/icons/hr.icon