AtCoder ABC099 を Python3 で解く

ちょっと順番が前後しますが順に過去に向かっても掘り下げていこうかと思います
公式の解説はこちら
https://img.atcoder.jp/abc099/editorial.pdf

A. ABD

数字までprint しなきゃいけないかと思ってたら違いました。 問題文良く読めという話

  • 1, 2… 999 のとき “ABC”
  • 1000, 1001…のとき “ABD”

を出力すれば良いので解法は正直に考えれば
input() を int に変換して大小を比較する方法でしょうか。
str のまま受け取って len(str) で比較しても良いですけど……

Accepted Code [A. ABD]

1
2
3
4
5
6
7
input_num = int(input())

if input_num < 1000:
    print("ABC")

else:
    print("ABD")

B. Stone Monument

与えられた2つの「雪より出てる部分の高さ」から、雪の積もった高さが等しいことを利用すると、
2つの塔の高さの差がわかります。すると、例えば
1+2+3+4 1+2+3+4+5 となる2つの塔の差が5 になる というように例を考えていけば、
(低い方の塔の高さ) = 1+2+...+(塔の高さの差 - 1)
となります

さて、塔の高さが求まればあとは簡単な話で
(雪の深さ) + (塔の雪から出ている部分) = (塔の高さ)
を低い方か高い方、どちらかの塔に対して計算すれば良いです。今回は低い方で考えています

Accepted Code [B. Stone Monument]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def delta2lower_height(arg_num):
    height = 0
    for i in range(1, arg_num):
        height += i
    return height


# main
input_line = input().split()

higher_margin = int(input_line[0])
lower_margin = int(input_line[1])

delta = higher_margin - lower_margin

lower_height = delta2lower_height(delta)
snow_height = lower_height - lower_margin

print(str(snow_height))

C. Strange Bank

こんな銀行預けたくない さて、考えていきましょう……
6^n 円引き出す時を考えると、6^n 円 を引き出す動作 * 6回は、明らかに
6*6^n = 6^(n+1) となるため、6^(n+1) 円 1回 を引き出す動作と金額が等しくなり、
5回分を無駄に使うことになってしまいます。よって、
6^n 円を引き出す動作はすべての n∈(自然数) に対して5回までと制限することができます。
同様のことは9^n 円についても言えます (8回まで)

また、問題条件より額が100000円を下回ることから、

  • 6^7 = 279936 円
  • 9^6 = 531441 円
    これ以上の引き出しはできないことになります。

よって、引き出しの動作としては以下のものが挙げられます

  • 1 円
  • 6^1, 6^2, 6^3, 6^4, 6^5, 6^6 円
  • 9^1, 9^2, 9^3, 9^4, 9^5 円

引き出し全体としては、これらの引き出しが0回以上組み合わされると考えられます。
ところで、6^n 円の引き出し系統の回数が定められた時、
残る動作は 9^n 円の引き出しと1円の引き出しのため、最適な引き出し方法が一意に定まります。

よって、6^1… 6^6 円 について 0回以上5回以下 = 6 * 6 * 6 パターンについて調べる方法で
十分に短い時間で全ての(最適な)組み合わせについて調べることができます。

Accepted Code [C. Strange Bank]

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
input_num = int(input())

combinations = [(pow1, pow2, pow3, pow4, pow5, pow6)
                for pow1 in range(0, 6)
                for pow2 in range(0, 6)
                for pow3 in range(0, 6)
                for pow4 in range(0, 6)
                for pow5 in range(0, 6)
                for pow6 in range(0, 6)]

num_withdraw_list = []
for combination in combinations:
    pow1, pow2, pow3, pow4, pow5, pow6 = combination
    withdraw6 = 6 ** 1 * pow1 + 6 ** 2 * pow2 + \
                6 ** 3 * pow3 + 6 ** 4 * pow4 + \
                6 ** 5 * pow5 + 6 ** 6 * pow6

    if withdraw6 > input_num:
        continue
    else:
        rest = input_num - withdraw6
        num_withdraw = sum(combination)
        for i in reversed(range(1, 6)):
            withdraw_i = rest // 9 ** i
            rest -= 9 ** i * withdraw_i
            num_withdraw += withdraw_i
        num_withdraw += rest
        num_withdraw_list.append(num_withdraw)

print(str(min(num_withdraw_list)))

D. Good Grid

Accepted Code [D. Good Grid]

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
import copy


input_line = input().split()
grid_size = int(input_line[0])
num_color = int(input_line[1])

differential_cost = {}
for color_from in range(1, num_color + 1):
    input_line = input().split()
    for color_to in range(1, num_color + 1):
        differential_cost[(color_from, color_to)] = int(input_line[color_to-1])

color_map = {}
for x in range(1, grid_size + 1):
    input_line = input().split()
    for y in range(1, grid_size + 1):
        color_map[(x, y)] = int(input_line[y-1])

current_color_dict = {}
for color in range(1, num_color+1):
    current_color_dict[color] = 0

current_color_mod0 = copy.deepcopy(current_color_dict)
current_color_mod1 = copy.deepcopy(current_color_dict)
current_color_mod2 = copy.deepcopy(current_color_dict)

for index, color in color_map.items():
    x, y = index
    if (x + y) % 3 == 0:
        current_color_mod0[color] += 1
    elif (x + y) % 3 == 1:
        current_color_mod1[color] += 1
    elif (x + y) % 3 == 2:
        current_color_mod2[color] += 1

combinations = [(color_mod0, color_mod1, color_mod2)
                for color_mod0 in range(1, num_color+1)
                for color_mod1 in range(1, num_color+1)
                for color_mod2 in range(1, num_color+1)]

cost_list = []
for combination in combinations:
    color_mod0, color_mod1, color_mod2 = combination
    if color_mod0 == color_mod1 or color_mod0 == color_mod2 or color_mod1 == color_mod2:
        continue

    cost = 0
    for color_from in range(1, num_color+1):
        cost += differential_cost[(color_from, color_mod0)] * current_color_mod0[color_from]
        cost += differential_cost[(color_from, color_mod1)] * current_color_mod1[color_from]
        cost += differential_cost[(color_from, color_mod2)] * current_color_mod2[color_from]

    cost_list.append(cost)

print(str(min(cost_list)))

ABC099 の軌跡

ABC099 の提出記録です。実行時間や使用メモリもわかります。銀行恨むぞ
https://beta.atcoder.jp/contests/abc099/submissions?f.Task=&f.Language=&f.Status=&f.User=nuekodory