AtCoder ABC422 振り返り(PythonでABC+D問題)

ABC422を振り返ります

今回はABCまで3問解答でした。

順位が2700番台だったので、「これはもしかして水色パフォ...」と思ったんですが、茶色パフォでした。
ただ単に変則的な日程(日曜13:10開始)だったので、参加者が少なかっただけのようです。

完璧な糠喜びです。

---

C問題で条件を見落としており、2ミスしています。
D問題は、考え方はあっていたのですが1行だけミスがあり、そのせいでTLEが解決できませんでした。惜しかった...。

A - Stage Clear

スーパーマリオのステージの問題のようでした。x-8だったら、次のステージは(x+1)-1になる、という問題です。

S = input()
x, y = S.split("-")
x = int(x)
y = int(y)

if y == 8:
    # yが8だったら、xを1増やしてyを1にする
    x += 1
    y = 1
else:
    # それ以外だったら、yを1増やす
    y += 1
print(str(x) + "-" + str(y))

B - Looped Rope

ひたすら愚直に、#のマスだったら、上下左右を見て#の数を数えます。
工夫として、マップの周りを空白で囲んでおくことで、境界条件を気にせずに済むようにしています。

H, W = map(int, input().split())

S = []
S.append(' ' * (W + 2))
for _ in range(H):
    S.append(' ' + input() + ' ')
S.append(' ' * (W + 2))

for i in range(1, H + 1):
    for j in range(1, W + 1):
        if S[i][j] == '#':
            count = 0
            if S[i - 1][j] == '#':
                count += 1
            if S[i + 1][j] == '#':
                count += 1
            if S[i][j - 1] == '#':
                count += 1
            if S[i][j + 1] == '#':
                count += 1
            if count == 2 or count == 4:
                continue
            else:
                print('No')
                exit()
print('Yes')

C - AtCoder AAC Contest

"A?C"の文字列を作るなら、AとCは必ず一つずつ必要です。ですので、最大に作れる数はmin(A, C)です。
余分なAとCを真ん中に使って文字列を作れば、文字列を作れそうです...。

例：
(A, B, C) = (30, 1, 20) のとき、
Aを17個、Cを17個、真ん中を(A13個 + B1個 + C3個)使って、"A?C"を17個作れます。

計算の仕方は、まずAとCの余りを全部に足します。
(A, B, C) = (30, 1, 20) -> (20, 11, 20)

次に、AとCから1個ずつBに補充する操作をできるだけ多く行います。
(20, 11, 20) -> (19, 13, 19) -> (18, 15, 18) -> (17, 17, 17)

こうすることで、最大値が求まります。

あと、下のプログラムで candidate2と謎の計算をしているのは、(A, B, C) = (30, 2, 20) のようなとき対応です。

この場合以下の計算になるのですが、
(30, 2, 20) -> (20, 12, 20) -> (19, 14, 19) -> (18, 16, 18)
これだと答えが16個？なってしまいます。

実は(18, 16, 18) → (17, 17, 18) とすれば、17個作れるのです。
これを求めるために candidate2 = min(A - 1, B + 1, C) としています。

今考えれば、(18, 16, 18) → (17, 18, 17) としても良いので、このほうが単純にできたかも。。。

T = int(input())
for _ in range(T):
    A, B, C = map(int, input().split())
    
    min_ac = min(A, C) # A?Cを最大に作れる数は、min(A, C)

    amari_a = A - min_ac # 余りのA
    amari_c = C - min_ac # 余りのC
    if amari_a + B + amari_c < min_ac:
        # 余りのAとCとBを全部真ん中に使っても、A?Cをmin_ac個作れない場合
        A = min_ac
        C = min_ac
        B += amari_a + amari_c # 余りのAとCをBに足す

        # AとCから1個ずつBに補充する操作を、できるだけ多く行う
        diff = A - B
        count = diff // 3
        A -= count
        C -= count
        B += count * 2
        candidate1 = min(A, B, C)
        candidate2 = min(A - 1, B + 1, C)
        print(max(candidate1, candidate2))

    else:
        # この場合は、A?Cをmin_ac個作れる
        print(min_ac)

D - Least Unbalanced (解説AC)

操作を逆に考えて、Kの数を2分割していくことを考えます(２分木を作っていくイメージ)。
親要素の数値を半分ずつに分けていけばXが小さくなりそうなので、そのようにします。

見直してみたら単純な操作ですね...。
実戦では、プログラムのミスでTLEになってしまい、解決できませんでした。

N, K = map(int, input().split())


a_list = [[] for _ in range(N + 1)]
a_list[0].append(K) # 最初はKが一つだけ

x_list = []

for i in range(1, N + 1):
    # 各数字を２分割していく
    for j in range(len(a_list[i-1])):
        value = a_list[i-1][j] // 2
        
        # ２分割のうち、ひとつ追加
        a_list[i].append(value)

        # ２分割のうち、もうひとつを追加
        if a_list[i-1][j] % 2 == 1:
            # ２で割り切れなかったら、もう一つの方に足しとく
            a_list[i].append(value + 1)
        else:
            a_list[i].append(value)

    # i回目の操作でのXを計算しておく
    x_list.append(max(a_list[i]) - min(a_list[i]))

# x_listを逆順にして、最大値を求める
x_list.reverse()
x = 0
for i in range(len(x_list)):
    x = max(x, x_list[i])

print(x)
print(*a_list[N])