図表とざっくりとした解説はこちらからどうぞ。
https://img.atcoder.jp/abc100/editorial.pdf
A. Happy Birthday!
図をよーく見れば、1人が9切れ以上取ることができないことが分かります。
隣接しない = 最低でも1つ間隔を開けなければならない
ということは、8切れ取った時1つ間隔で取ることになりこれが最大です。
全部で16個から8個ずつ取っても問題ないので、全体のケーキの残りについては考える必要がなく、1人最大8切れを守れば良いことになります。
(マイナスの入力は条件から存在しません)
よって、A, B が8以下であることが Yay! の条件ですので、
1
2
3
4
| if A <= 8 and B <= 8:
print("Yay!")
else:
print(":(")
|
となるように設計すれば良いことになります。
Accepted Code [A. Happy Birthday!]:
1
2
3
4
5
6
7
8
9
| input_line = input().split()
cake_a = int(input_line[0])
cake_b = int(input_line[1])
if cake_a > 8 or cake_b > 8:
print(":(")
else:
print("Yay!")
|
B. Ringo’s Favorite Numbers
色々な解法がありますが、ここでは D = 0 or 1 or 2 ということを利用して解きます(場合分け)
D == 0
“100でちょうど0回割り切れる” == “100で割り切れない”
と考えると解けるかと思います。
コードにすると
1
2
| if number % 100 != 0:
do
|
ということですね。
ここで N < 100 であれば単純に答えが N で終わりなのですが、
N <= 100 なので N == 100 について分ける必要があります。
愚直に N == 100 を場合分けしても良いですし、
100の倍数について無視してカウントするようにしても良いです(今回はこちらを採用)
D == 1
“100でちょうど1回割り切れる” == “100で割り切れて、10000で割り切れない”
よってD == 0 の時と同様に N == 100 についてのみ場合分けをするか、
10000の倍数を無視してカウントするようにすれば良いです(今回はこちらを採用)
D == 2
“100でちょうど2回割り切れる” == “10000で割り切れて、1000000で割り切れない”
よってD == 0, 1 の時と同様に N == 100 についてのみ場合分けをするか、
1000000の倍数を無視してカウントするようにすれば良いです(今回はこちらを採用)
Accepted Code [B. Ringo’s Favorite Numbers]:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| input_line = input().split()
num_divide = int(input_line[0])
smallest_of = int(input_line[1])
if num_divide == 0:
counter = 0
current_num = 0
while counter < smallest_of:
current_num += 1
if current_num % 100 == 0:
continue
else:
counter += 1
elif num_divide == 1:
counter = 0
current_num = 0
while counter < smallest_of:
current_num += 100
if current_num % 10000 != 0 and current_num % 1000000 != 0:
counter += 1
else:
counter = 0
current_num = 0
while counter < smallest_of:
current_num += 10000
if current_num % 1000000 != 0:
counter += 1
print(str(current_num))
|
C. *3 or /2
“3倍する” or “2で割り切る” の操作をするのですが、
“3倍する” のはまあ何回でもできますよね。
というわけでネックになるのは “2で割り切る” ことです。
“2で割り切る” 動作は数列に対して 1回の操作で1つ以上適用しなければならないので、
1回の操作で1つを “2で割り切る” と考えます。
するとこの問題は “2で何回割り切れるか” という問題になりますので、
数列のそれぞれの数について “2で何回割り切れるか” を調べます。
いくつか方法はありますが、2進法に変換して0が続く桁数を調べるのが良いでしょう(多分)
Accepted Code [C. *3 or /2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| array_length = int(input())
input_line = input().split()
array_int = list(map(int, input_line))
array_bin = list(map(bin, array_int))
array_bin_str = list(map(str, array_bin))
array_dividable = []
for i in range(0, array_length):
if array_int[i] == 0:
array_dividable.append(0)
else:
target_line = array_bin_str[i]
count_dividable = 0
for j in range(1, len(target_line)):
target_char = target_line[-j]
if target_char == '1':
break
elif target_char == 'b':
break
else:
count_dividable += 1
array_dividable.append(count_dividable)
if sum(array_dividable) == 0:
print("0")
else:
print(str(sum(array_dividable)))
|
D. Patisserie ABC
全ての場合についてスコアを出そうとすると、ケーキ1000個から500個を取り出すときに計算量が最大で、このとき
C(1000, 500) = 2.702882409E+299
よってこんなんでfor を回すと帰ってこない(計算が終了しない)ので別の方法を考えます。
ところで、スコアは絶対値を採用するわけですが、
絶対値というのは max(number, -number) と等価です。
よってこの場合、単純にスコアを足していったあとのことを考えると、
「綺麗さ」「おいしさ」「人気度」の数値が beauty, yummy, popular だったとして
1
2
3
4
5
6
7
8
| + beauty + yummy + popular
+ beauty + yummy - popular
+ beauty - yummy + popular
- beauty + yummy + popular
- beauty - yummy + popular
+ beauty - yummy - popular
- beauty + yummy - popular
- beauty - yummy - popular
|
の8パターンのうち、最大のものが
1
| abs(beauty) + abs(yummy) + abs(popular)
|
と等しいとわかります。
すると、絶対値で考えなくても単純に足していって最後にmaxを出せば良いことがわかります。
さて、ここまできたところでもう一度上の8例について見てみます。
+ beauty - yummy + popular で考えてみましょう。
これを最大化させるためには + beauty - yummy + popular を各ケーキに対して算出し、大きいものから順番にケーキの個数だけ取れば良いことに気がつくでしょうか。
すると8パターン全てに対して同じことが言えるのですから、これを計算してmax を取ればスコアが最大であると言えます。
Accepted Code [D. Patisserie ABC]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| input_line = input().split()
total_cake = int(input_line[0])
select_cake = int(input_line[1])
cake_scores = []
for i in range(0, total_cake):
input_line = input().split()
beauty = int(input_line[0])
yummy = int(input_line[1])
popular = int(input_line[2])
cake_scores.append((beauty, yummy, popular))
scores_p_p_p = []
scores_p_p_n = []
scores_p_n_p = []
scores_n_p_p = []
scores_n_n_p = []
scores_p_n_n = []
scores_n_p_n = []
scores_n_n_n = []
for i in range(0, total_cake):
beauty, yummy, popular = cake_scores[i]
scores_p_p_p.append(beauty + yummy + popular)
scores_p_p_n.append(beauty + yummy - popular)
scores_p_n_p.append(beauty - yummy + popular)
scores_n_p_p.append(-beauty + yummy + popular)
scores_n_n_p.append(-beauty - yummy + popular)
scores_p_n_n.append(beauty - yummy - popular)
scores_n_p_n.append(-beauty + yummy - popular)
scores_n_n_n.append(-beauty - yummy - popular)
scores_p_p_p.sort(reverse=True)
scores_p_p_n.sort(reverse=True)
scores_p_n_p.sort(reverse=True)
scores_n_p_p.sort(reverse=True)
scores_n_n_p.sort(reverse=True)
scores_p_n_n.sort(reverse=True)
scores_n_p_n.sort(reverse=True)
scores_n_n_n.sort(reverse=True)
score_p_p_p = sum(scores_p_p_p[0:select_cake])
score_p_p_n = sum(scores_p_p_n[0:select_cake])
score_p_n_p = sum(scores_p_n_p[0:select_cake])
score_n_p_p = sum(scores_n_p_p[0:select_cake])
score_n_n_p = sum(scores_n_n_p[0:select_cake])
score_p_n_n = sum(scores_p_n_n[0:select_cake])
score_n_p_n = sum(scores_n_p_n[0:select_cake])
score_n_n_n = sum(scores_n_n_n[0:select_cake])
print(str(max(score_p_p_p, score_p_p_n, score_p_n_p, score_n_p_p,
score_n_n_p, score_p_n_n, score_n_p_n, score_n_n_n)))
|
ABC100 の軌跡
ABC100 の提出記録です。実行時間や使用メモリもわかります
https://beta.atcoder.jp/contests/abc100/submissions?f.Task=&f.Language=&f.Status=&f.User=nuekodory