AtCoder Beginners Contest 321 (ABC321) をPythonで解きました。
見やすいコードを書く練習も兼ねてます。
A - 321-like Checker
問題ページ
考察
問題文がややこしいですが、要するに、
与えられる数 $N$ を1桁ずつ分解します。例えば、$N=64310$ のとき、 $[6,4,3,1,0]$ とします。
隣り合った2つの数を見て、 $(左側の数) \leqq (右側の数)$ になっているところが1つもないなら "Yes" 、それ以外は "No" を出力してください。
という問題です。
いつも通り $N$ を数値として受け取ると実装がややこしくなります。
文字列として入力を受け取ってから、左右のケタの文字を数値に変換して大小比較をすると、実装がすこし簡単になります。
コード
N = input() # N = int(input())とすると、このあとの実装がちょっとしんどい
ans = "Yes"
for i in range(len(N) - 1):
if int(N[i]) <= int(N[i + 1]):
ans = "No"
print(ans)
B - Cutoff
問題ページ
考察
スコアは$0$～$100$点の$101$通りしかありません。これくらいのパターン数なら、全パターン列挙して試してみるのがラクです。
- $0$ 点を取ったときに、最終結果が $X$(←入力で与えられている) 以上になっていたら、 $0$ を出力しておしまい。
- $1$ 点を取ったときに、最終結果が $X$ 以上になっていたら、 $1$ を出力しておしまい。
- $\cdots$
- $100$ 点を取ったときに、最終結果が $X$ 以上になっていたら、 $100$ を出力しておしまい。
- まだコードが終わってなかったら、何点をとっても最終結果が $X$ 以上にならないということになるので、 $-1$ を出力しておしまい。
と、全パターン試してみます。
最終結果の計算だけ関数化しておくと、実装がラクになっていいのかなと思います。
コード
def score(lst):
sorted_lst = sorted(lst)
return sum(sorted_lst[1:N - 1]) # 半開区間[1,N-1) の要素の総和
N, X = map(int, input().split())
A = list(map(int, input().split()))
ans = -1
for i in range(101):
if score(A + [i]) >= X:
ans = i
break
print(ans)
C - 321-like Searcher
問題ページ
考察
競プロでとりあえず考えてみた方がいいことの1つに、「最悪のケースはどんなものになるか」があります。
ということで、いったん321-like Numberの最大値を考えてみます。
桁数を最大にすればいいので、 $9876543210$ が最大です。 $10$ 桁の数はこれ以外にはありません。
$9$ 桁の321-like Numberはどうでしょうか。$987654321$ や $987543210$ などがあります。 $10$桁の唯一の321-like Numberである $9876543210$ から1桁だけ削除した数が $9$ 桁の321-like Numberなので、個数は $10$ 個です。
思ってるよりも多くなさそうなのが直感で分かります。
実際の321-like Numberの個数は $1022$ 個で、全列挙する方針が簡単そうです。
下のコードは、深さ優先探索DFSで全列挙しています。
コード
def dfs(str_num):
good_number.append(int(str_num))
# 末尾の数よりも小さい数を新たに付け加える
if len(str_num) > 0:
tail = int(str_num[-1])
else:
tail = 10
for i in range(0, tail):
nex = str_num + str(i)
dfs(nex)
good_number = []
for i in range(1, 10):
dfs(str(i))
good_number.sort()
K = int(input())
print(good_number[K - 1])
別解
bit全探索をつかった解法
$9876543210$ から、各桁について「残す」or「削除する」を選択することで321-like Numberをつくることができます。この選択を全パターン試して321-like Numberを全列挙する方針です。 この考え方から、全パターンを列挙しても $1022$ 通りだということが分かります(なにも選ばないのと、 $0$ のパターンを除くので $2^{10}-2=1022$ 通り)。bit全探索はitertoolsにあるproductが便利です。
"""itertools.productの使用例"""
from itertools import product
arr = []
for pro in product((0, 1), repeat=3):
arr.append(pro)
print(arr) # [(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)]
また、この別解の解答例コードではzip関数もつかっています。便利でオススメです。
"""zip関数の使用例"""
lst1 = [3, 6, 9]
lst2 = [2, 10, 90]
for a, b in zip(lst1, lst2):
print(a, b)
# 出力結果
# 3 2
# 6 10
# 9 90
bit全探索の解答例コードです。
"""bit全探索の解答例"""
from itertools import product
good_number = []
A = "9876543210"
for pro in product((0, 1), repeat=10):
if sum(pro) == 0:
continue
now_num = ""
for a, pr in zip(A, pro):
if pr == 1:
now_num += a
now_num = int(now_num)
if now_num >= 1:
good_number.append(now_num)
good_number.sort()
K = int(input())
ans = good_number[K - 1]
print(ans)
非再帰で書く方法
Pythonは、あまり再帰がはやくありません。
なので、スタックを用いて再帰関数をつかわずに解くと実行時間が短くなることが多いです。
(今回の問題は実行時間にかなり余裕があって、再帰関数でも通ります。)
stack = [str(i) for i in range(1, 10)]
good_number = []
while stack:
str_num = stack.pop()
good_number.append(int(str_num))
tail = int(str_num[-1])
for nex_tail in range(0, tail):
nex_str_num = str_num + str(nex_tail)
stack.append(nex_str_num)
good_number.sort()
K = int(input())
ans = good_number[K - 1]
print(ans)
D - Set Menu
問題ページ
考察
主菜と副菜の価格の和を $s$ としたとき、定食の価格は $\min (s, P)$ です。
↑ 問題文のこの部分がポイントです。
価格の和をそのまま定食の価格にしてくれません。
なので、主菜と副菜のペアを全通り見て、それぞれで $\min(s,P)$ を求めてみたくなります。
しかし、それだと計算量は $O(NM)$ でTLEしてしまいます。
重要なのは、主菜の価格 $a$ と副菜の価格 $b$ の和 $a+b$ が $P$ 以上かどうかだけです。
数式にすると、 $a+b \leqq P$ が成り立つかどうかです。
この式を変形して、 $b \leqq P-a$ としてみます。
価格が $a$ の主菜に対して、副菜の価格が $P-a$ より大きいかどうかが重要だということが、この式から分かります。
厳密な書き方ではないけれど、副菜の価格が小さかったら定食の価格は $P$ で固定で、そこから副菜の価格を上げていくとどこかで定食の価格が $a+b$ になって、さらに副菜の価格を上げても $a+b$ の式のままです。
この構造のときにつかえるのが2分探索です。
2分探索の前準備で、副菜の価格のリスト $B$ を昇順(小さいもの順)に並べておきます。
主菜それぞれについて、2分探索をつかって定食の価格が $P$ で固定になるものの個数を求めます。
残りの定食の価格が $a+b$ になる分については、あらかじめ 副菜の価格のリスト$B$ の累積和を求めておくと、 $O(1)$ で価格全体を計算できます。(下のコードも参考にしてください。)
コード
from bisect import bisect_left
from itertools import accumulate # 累積和を取る関数
N, M, P = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
B.sort()
B_acc = [0] + list(accumulate(B)) # 累積和
ans = 0
for a in A:
idx = bisect_left(B, P - a)
ans += P * (M - idx) # 価格がPで固定になってしまう分
ans += idx * a + B_acc[idx] # 価格が(主菜の価格)+(副菜の価格)になる分
print(ans)