PythonでAtCorder256 (A〜D)｜タムタムのアウトプット

先週末のAtCorder 256に参加しました。

A, B、Cの3完でした。Cが解けた後に時間が少しあったのでDにチャレンジしてみたが正解に至りませんでした。

Contents

【A】 2^N
【B】 Batters
Filling 3×3 array
【D】 Union of Interval
まとめ

【A】 2^N

提出したコードはこちら

N = int(input())
print(2**N)

かつてないぐらい簡単なA問題だと思います。

【B】 Batters

提出したコードはこちら

N = int(input())
A = list(map(int, input().split()))

p = 0
koma = []  # コマがいるマスindex
for a in A:  # O(1000)
    # 既存コマ
    new_koma = []
    for k in koma:  # O(4)
        if k + a >= 4:
            p += 1
        else:
            new_koma.append(k + a)

    # コマ=0
    if a == 4:
        p += 1
    else:
        new_koma.append(a)

    koma = new_koma
print(p)

問題は理解しやすく実現したいことは明確だけど、コードに落とすのはちょっと大変という感じで、良問だと思います。

Filling 3×3 array

提出したコードはこちら

def solution(hw):
    ans = 0

    # 1行目
    h1 = hw[0]
    masu_1_lines = []
    for i in range(1, h1 + 1):  # O(30)
        for j in range(1, h1 + 1):  # O(30)
            if h1 - i - j <= 0:
                break
            else:
                masu_1_lines.append([i, j, h1 - i - j])

    # 2行目
    h2 = hw
    masu_2_lines = []
    for i in range(1, h2 + 1):  # O(30)
        for j in range(1, h2 + 1):  # O(30)
            if h2 - i - j <= 0:
                break
            else:
                masu_2_lines.append([i, j, h2 - i - j])

    # masu_linesを結合して条件を満たすか確認
    for m1 in masu_1_lines:
        for m2 in masu_2_lines:
            m3 = [
                hw - m1[0] - m2[0],
                hw - m1 - m2,
                hw[5] - m1 - m2
            ]
            if m3[0] > 0 and m3 > 0 and m3 > 0 and sum(m3) == hw:
                ans += 1
    return ans


hw = list(map(int, input().split()))
print(solution(hw))
# print(solution())
# print(solution())
# print(solution([5, 13, 10, 6, 13, 9]))
# print(solution([20, 25, 30, 22, 29, 24]))

これも問題自体は明確でわかりやすかったです。

一工夫が必要な全探索のパターンですね。まともに全探索やったら計算量的にNGですが、途中までやれば残りの値が決まるので、計算量を減らすことができるタイプの全探索です。

AtCorderの非公式(?)の最初の10問で、同じパターンの問題がありました。お年玉のやつです。
https://qiita.com/drken/items/fd4e5e3630d0f5859067#5-%E9%81%8E%E5%8E%BB%E5%95%8F%E7%B2%BE%E9%81%B8-10-%E5%95%8F

同じような問題をやったことがあったので、この問題は無事、解くことができました。

【D】 Union of Interval

珍しくC問題のあとに時間があまったので、Dnimoチャレンジしてみました。が、正解にはいたらず・・・

途中まで考えていた回答はこちら

def solution(LR):
    ans = []  # [[L, R], [L,R]...]
    for lr in LR:
        start = int(lr.split()[0])
        end = int(lr.split())

        if len(ans) == 0:
            ans.append([start, end])
            continue

        new_ans = []
        for a in ans:
            if a[0] <= start <= a:
                new_ans.append([a[0], max(end, a)])
            else:
                new_ans.append(ans)

            if a < start:
                new_ans.append([start, end])
        ans = new_ans
    print(ans)
    for i, v in enumerate(ans):
        if i == 0:
            print(*v[0])
        else:
            print(*v)


# N = int(input())
# LR = [(input()) for _ in range(N)]
# solution(LR)
LR = ["10 20", "20 30", "40 50"]
solution(LR)
LR = ["10 40", "30 60", "20 50"]
solution(LR)

答えらしき値は出せていましたが、ansの配列の中身が違ってで正しく出力できず。まあこの問題が解決できていたとしても、正解だったのかどうか怪しいですね。。。

解説見たところ、ソートしてしまえば、今いるレンジとかぶるか、完全に外かを調べれば良いということがわかりました。

で、解説見た後、クリアできたコードはこちら

def solution(LR):
    # LRは要素が文字列で正しくsortできないのでintのlistに変換
    intLR = []
    for lr in LR:
        int_lr = tuple(map(int, lr.split()))
        intLR.append(int_lr)

    ans = []  # [[L, R], [L,R]...]
    intLR.sort()

    # 現在区間 sortすれば、現座区間に含まれるかそれよりあとの2択になる
    # これが拡張されるから分離されるか調べていく
    start = intLR[0][0]
    end = intLR[0]

    for lr in intLR:
        l = lr[0]
        r = lr

        if l > end:  # 現在の位置より後なので新区間になる
            # endが更新されることはないので現在区間を確定
            ans.append([start, end])

            # 新区間
            start = l
            end = r
            continue

        if r > end:  # 現在の区間を拡張
            end = r
    else:
        # last区間
        ans.append([start, end])

    for a in ans:
        print(*a)


N = int(input())
LR = [(input()) for _ in range(N)]
solution(LR)
# LR = ["10 20", "20 30", "40 50"]
# solution(LR)
# LR = ["10 40", "30 60", "20 50", "5 15"]
# solution(LR)

別解のimos法とやらは、よく見ても理解できませんでした。今回の問題では、ベストマッチしているアルゴリズムではなさそうなので、とりえず理解は諦めました・・・