FUNCoder-第5回活動
第5回活動 2024/05/29 18:15~19:45 @593教室
/icons/hr.icon
基本的な標準入力から計算量を工夫しないと解けない問題まで幅広く出題されるのでこれを全て解くのを目標に頑張りましょう！
問題一覧
/icons/hr.icon
今更感はありますが、基本問題です。
迷ってしまった方は標準入力の受け取り方に慣れていない、理解できていない可能性があるので自分の過去に書いた 記事 でも参考にしてみてください。 わからなければ遠慮せず聞いてください。
解答例
code:Python
a = int(input())
b, c = map(int, input().split())
s = input()
print(a + b + c, s)
/icons/hr.icon
これもまた基本問題です。
$ 2つの値の積が偶数か奇数かを判定する問題です。
情報表現入門のチェックテストでも頻出の問題なので必ずできるようにしましょう。
偶数か奇数かの判定は、$ 2で割った余りが$ 0ならば偶数、$ 1ならば奇数として判定することができます。
一般に、$ Nを$ Kで割った余りは N % K で求めることができるので、ここまでわかれば後は実装するだけです。
解答例
code:Python
a, b = map(int, input().split())
if a * b % 2 == 1:
print("Odd")
else:
print("Even")
/icons/hr.icon
for 文を用いて$ 3回ループさせ、$ 1が何回現れたか解く方法が１つとして挙げられます。
他にも Python には count 関数が存在するので、引数に渡した値を数えて返してくれる便利な関数があるのでこれを用いて解くこともできます。
解答例
$ 1の個数を count 関数を用いて解く方法
code:Python
s = input()
cnt = s.count('1') # 文字列 s に含まれる 1 の個数をカウントする
print(cnt)
$ 1の個数をカウントする方法
code:Python
s = input()
cnt = 0 # 1 の個数をカウントする変数
for i in s:
if i == '1': # 1 ならば答えに 1 を加える
cnt += 1
print(cnt)
/icons/hr.icon
この問題は各$ A[i] に対して何回$ 2で割れるかを問う問題です。
$ A[i] が$ 2で割れるかどうかは if A[i] % 2 == 0 で判定ができます。
なのでこれを各$ i \: (0 \leq i \leq N - 1)に対して、割り切れるまで while 文で判定し、最も少ない割り切れる回数を求めることで解くことができます。
配列の中の最小値を取り出す場合には min 関数を用いましょう。
解答例
code:Python
N = int(input())
A = list(map(int, input().split()))
cnt = 0*N # cnti := Ai が何回 2 で割り切れるかを管理する配列 for i in range(N):
num = 0
while True:
num += 1
else: # Ai が 2 で割り切れない場合は break する break
cnti = num # Ai が 2 で割り切れた回数を cnti に入れる print(min(cnt)) # 2 で割り切れる最小値を出力する
/icons/hr.icon
この問題は全探索に慣れる問題です。
まずは$ 500円玉と$ 100円玉と$ 50円玉のそれぞれ使用する枚数を全探索します。
これは$ 3重 for 文を用いることで実現できます。
for 文を重ねていく場合、先週の数え上げお姉さんでも見たように、計算回数が爆発的に増えることがあるので見積もることが重要です。
今回も計算回数を見積もってみましょう。
持っている硬貨は制約より最大でもそれぞれ$ 50枚です。
全通りの組み合わせは$ 0枚使用する可能性も考慮すると、$ (A + 1)(B + 1)(C + 1)通りあります。
したがって、最大でも$ 51 \times 51 \times 51 = 132651 \fallingdotseq 10^5回程度なので十分高速であることがわかります。
なのでこの問題は、各硬貨の使用する枚数を全探索することで解くことができます。
解答例
code:Python
# 入力を受け取る
A = int(input())
B = int(input())
C = int(input())
X = int(input())
cnt = 0 # X 円の組み合わせをカウントする変数
for i in range(A + 1): # 500 円玉の使用する枚数を全探索
for j in range(B + 1): # 100 円玉の使用する枚数を全探索
for k in range(C + 1): # 50 円玉の使用する枚数を全探索
# 各組み合わせに対する金額を計算する
money = 500*i + 100*j + 50*k
# 金額が X 円であれば答えに 1 を加える
if money == X:
cnt += 1
# 答えを出力する
print(cnt)
/icons/hr.icon
この問題は少し癖のある問題ですね。
まず桁和を求める必要があります。
ここで、コードを実装する際に意識して欲しいのが$ 1以上$ N以下の整数全てに対して桁和を求める場合、同じ処理（桁和を求めるという処理）を$ N回行うことになるので、これは関数にして管理してあげると、わかりやすいコードを書くことができます。
整数$ xの桁和を求める関数$ f(x)を用意します。
$ xの桁和を求める手順は以下の通りです。
1. 整数$ xの桁和を求める変数$ \mathrm{sum\_}を用意する
2. 整数$ xの桁数を文字列に変換し len 関数を用いて取得する（$ \mathrm{len\_}）
3. for 文を用いて各桁の値を int に再変換して$ \mathrm{sum\_}に足す
4. $ \mathrm{sum\_}の値を return する
後は、$ f(x)の返り値が$ A以上$ B以下であれば、整数$ iを答えに加えることで総和を求めることができます。
実装は以下の解答例を参考にしてみてください。
解答例
code:Python
def f(x: int) -> int:
""" int 型の整数 x の桁和を求める関数（返り値は int）"""
sum_ = 0 # 桁和を管理する変数
len_ = len(str(x)) # 整数 x の桁数
for i in range(len_):
# x を文字列に変換し、先頭から i 番目の文字（数字）を int に再変換して足す
return sum_ # x の桁和を return する
N, A, B = map(int, input().split())
ans = 0 # 条件を満たす総和を求める変数
# 1 以上 N 以下の整数に対して全探索を行う
for i in range(1, N + 1):
digit_sum = f(i) # 整数 i の桁和を digit_sum の変数に入れる
# A 以上 B 以下であれば総和に i を加える
if A <= digit_sum <= B:
ans += i
print(ans)
/icons/hr.icon
続いてはゲームの問題ですね。競プロでは$ 2人が対戦形式で最適な行動をしていきどちらが勝つか、を問う問題がよく出題されます。これはその入門です。
お互いが存在するカードの中で最大なものを取って行くことがお互いにとっての最大化なのでまずは配列$ aを降順にソートします。
昇順ではなく降順にするには sort 関数の引数に reverse=True を記述することで降順に並べ替えることができます。
あとは偶奇ごとにどちらのターンなのかを調べながらお互いに点数を加えていくことで、答えを求めることができます。
解答例
code:Python
N = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True) # 降順にソートする
Alice, Bob = 0, 0
for i in range(N):
if i % 2 == 0: # Alice のターン
elif i % 2 == 1: # Bob のターン
print(Alice - Bob)
/icons/hr.icon
少し問題文が複雑ですね。
要約してやりたいことを落とし込むと以下の問題に帰着できます。
$ N個の整数$ d_i \: (0 \leq i \leq N - 1)が与えられます。
配列$ dの要素の種類数を出力せよ。
同じ大きさの鏡餅を乗せることはできないので大きさが少しでも違う鏡餅があればそれを昇順（小さい順）にソートする（並び替える）ことで理論値の鏡餅を作り上げることができます。
なので種類数がこの問題では鍵となります。
種類数を管理する際に便利なのが set と呼ばれるデータ構造です。
set を用いることで要素の重複を管理する必要がなくなるので種類数を容易に求めることができます。
set のデータ構造に対して要素を追加したい際には add 関数を用います。
配列に対しては append 関数を用いますが、set に対しては add を用いるので注意しましょう。
解答例
code:Python
N = int(input())
s = set() # 重複を管理しない集合 s
for i in range(N):
s.add(di) # s に要素 di を追加する print(len(s)) # 配列 d の要素の種類数を出力する
/icons/hr.icon
今日のメインです！これは頑張って解いてみてほしいです。
まずは、$ 10000円札の枚数、$ 5000円札の枚数、$ 1000円札の使用する枚数をそれぞれ全探索することを考えます。
制約より、合計は$ N枚になる必要があるので、それぞれのお札は最大でも$ N枚しか使用しません。
したがって、各組み合わせは$ N^3通りあります。制約より、$ N \leq 2000から最大の計算回数を求めてみます。
$ 2000^3 = 8 \times 10^9 \fallingdotseq 10^{10}回かかってしまうのでこれはとても間に合いません。
TLE しますが、上記の解法のコードを下記に示します。
code:Python
N, Y = map(int, input().split())
for i in range(2001): # 10000 円札の枚数を全探索
for j in range(2001): # 5000 円札の枚数を全探索
for k in range(2001): # 1000 円札の枚数を全探索
# 合計金額
money = 10000*i + 5000*j + 1000*k
# 合計金額が Y 円かつお札の合計枚数が N 枚かどうかを判定する
if (i + j + k) == N and money == Y:
# 答えを出力する
print(i, j, k)
exit()
では$ O(N^3)をなんとか$ O(N^2)に落とせないか考えてみます。
これらの問題のように$ 3つの合計が$ Kにしたい、のような問題は$ 2つを全探索することで残りは必然的に求まりますよね。
これは競プロではよく出題される計算量改善の問題なので必ず抑えておきましょう。
今回の問題は$ 10000円札の枚数と$ 5000円札の枚数のみを全探索します。
この時点での合計金額は、それぞれの使用する枚数を$ i枚、$ j枚とすると、$ \mathrm{money} = 10000 \times i + 5000 \times jになります。
code:Python
for i in range(2001): # 10000 円札の枚数を全探索
for j in range(2001): # 5000 円札の枚数を全探索
money = 10000*i + 5000*j # 10000 円札と 5000 円札で払う合計金額
合計を$ Y円にしたいため、この時$ 1000円札で$ Y - \mathrm{money}円を払う必要があります。
ここで必要条件としてこの値は$ 1000で割り切れる必要があります。
例えば$ Y - \mathrm{money}が$ 3501円とかの場合、どうやっても$ 1000円札のみで払うことはできませんよね...
なのでこの条件を調べるためには$ 1000で割った余りを調べれば良いです。
これは何回か出てきてるので覚えましょう。$ \%を使用することで求めることができます。
また、負の値になってもいけないのでそれも注意しましょう。
ここまで調べて問題がなければ$ 1000円札の枚数を求めます。
最後に札の枚数の合計が$ N枚であれば答えを出力してプログラムを終了させます（exit 関数）
解答例
code:Python
N, Y = map(int, input().split())
for i in range(2001): # 10000 円札の枚数を全探索
for j in range(2001): # 5000 円札の枚数を全探索
money = 10000*i + 5000*j # 10000 円札と 5000 円札で払う合計金額
# 1000 の倍数でなければ continue する
if (Y - money) % 1000 != 0:
continue
# 負の値であれば continue する
if (Y - money) < 0:
continue
# 1000 円札の枚数
k = (Y - money) // 1000
# 枚数が N 枚でなければ continue する
if (i + j + k) != N:
continue
# 答えを出力する
print(i, j, k)
exit()
# 解がない場合は (-1, -1, -1) を出力する
print(-1, -1, -1)
/icons/hr.icon
ここら辺の問題から難易度がかなり上がります。
dream, dreamer, erase, eraser のいずれかと一致しれいれば消すことができます。
しかし、dreameraseみたいな文字列があった場合には先頭から一致するか調べる場合、dream なのか dreamer なのか判別することができません。
したがって、この問題は与えられた入力に対して逆から操作していくことで問題を解くことができます。
$ S = \mathrm{dreamerase} \rightarrow \mathrm{esaremaerd}のようにすることで、後ろから見ることで、実は一意に定まります。
したがって、後ろから見ていき条件を満たす場合はスライス等を用いて削除していき、最終的に文字列長が$ 0になれば条件を満たすため Yes になります。
これは while 文を用いることで解くことができます。
解答例
code:Python
while True:
else:
break
print("YES" if len(s) == 0 else "NO")
/icons/hr.icon
最後の問題です、解説書くの疲れてきました（）
これは問題はシンプルですが、閃きというか、しっかりとロジックを組む必要があるのでそこが難問になっています。
このように Yes, No を出力させるような問題では、条件を満たしていない時に No を出力して exit() 関数を用いてプログラムを終了させ、全ての条件を最後まで満たしていれば Yes を出力するという解法がオススメです。
以下は疑似コードになります。
code:Python
for i in range(N):
if （条件を満たしていない場合）:
# 条件を満たしてない場合は No を出力してプログラムを終了させる
print("No")
exit()
# 最後まで条件を満たしていれば Yes を出力させる
print("Yes")
では、問題に戻ります。
ここで No となる条件は何でしょうか？
まず思いついて欲しいのが次の時刻までにそこに行けない場合です。
毎時刻$ 1しか進むことができないので、時刻$ t_iから時刻$ t_{i+1} \: (0 \leq i \leq N - 2)に進める距離は$ t_{i+1} - t_iで求まります（その場にとどまることができないことに注意してください。）
次に目的地までの距離を考えます。
$ (x_i, y_i)から$ (x_{i + 1}, y_{i + 1})までの距離はマンハッタン距離で求まります。
$ \mathrm{dist} = |x_i - x_{i+1}| + |y_i - y_{i + 1}|
これはマンハッタン距離と呼ばれ、競プロでは頻出なので必ず抑えましょう。
したがって、$ t_{i + 1} - t_i \lt distの時は、どのように最適な行動をしても必ず目的地に着くことができません。
この場合は No にする必要があります。
それでは$ \mathrm{dist} \leq t_{i + 1} - t_iを満たしていれば必ず目的地に着けるでしょうか？
実はそうではないのがこの問題の難しいところになります。
結論から言うと、$ t_{i + 1} - t_iと$ \mathrm{dist}の偶奇が異なる場合にはどう頑張っても目的地と$ 1ずれた場所にしか辿り着くことができません。
なので偶奇が一致しているかつ距離が目的地までの時刻以下の時は Yes、そうでない場合は No となりこの問題を解くことができました。
解答例
code:Python
N = int(input())
l = 0, 0, 0 + l
for i in range(N):
now_t, now_x, now_y = li # 今いる時刻・座標 nxt_t, nxt_x, nxt_y = li + 1 # これから向かう時刻・座標 dist = abs(now_x - nxt_x) + abs(now_y - nxt_y)
time = nxt_t - now_t
# 距離と偶奇が同じ かつ 距離 <= 時間
if not (dist % 2 == time % 2 and dist <= time):
print("No")
exit()
print("Yes")
/icons/hr.icon