[Python] ABC412 C Giant Domino

[Python] ABC412 C - Giant Domino

問題

https://atcoder.jp/contests/abc412/tasks/abc412_c

自分の回答

• 最初のドミノと最後のドミノだけ最初に確保し、ドミノ2 ~ ドミノN-1 までを候補としてソートして貪欲
  • 次のドミノでも倒せそうなら何もしない
  • 最後の候補ではない and 次のドミノでもいい場合も何もしない
  • 最終的に倒せたかどうかチェックする

t = int(input())


def ans():
    n = int(input())
    s = list(map(int, input().split()))

    base = s[0]
    candi = s[1 : n - 1]
    last = s[-1]

    candi.sort()
    ans = []

    # 最初から一つ目のドミノで最後のドミノが倒せるならそれでOK
    if base * 2 >= last:
        print(2)
        return

    for i in range(len(candi)):

        # このドミノが倒せない場合は何もしない
        if base * 2 < candi[i]:
            continue
    
        # 次のドミノを確認して、次のドミノでも倒せるなら何もしない
        if i != len(candi) - 1:
            if candi[i + 1] <= base * 2:
                continue

        # ここまでで、ドミノiが倒せない/次のドミノでもOKの場合を排除したので候補に追加
        ans.append(candi[i])
        base = candi[i]

        if ans[-1] * 2 >= last:
            break

    # 最後においたドミノで、最初に確保したドミノNが倒せるならドミノの個数、
    # 倒せないなら-1を出力
    if base * 2 >= last:
        print(len(ans) + 2)
    else:
        print(-1)


for _ in range(t):
    ans()

https://atcoder.jp/contests/abc412/submissions/67150090

疑問 - 二分探索と貪欲、どちらの解法が適切だったのか？

• 自分の理解だと貪欲の方が良かったと思う
• 二分探索するにしろ、貪欲するにしろ、ソートは必須。
  • 二分探索で条件を満たす一番大きいものを選ぼうとすると1個探すために複数Step踏む必要がある。
  • 今回の問題の場合ではNが大きくなるたび探索回数が増える（はず）
  • 対して、貪欲の場合はすでにいらないもの（＝さらに適切なドミノがあり使わないもの）に関しては一度見たら二度と見る必要がないため、感覚的には早く感じる
• 変わりゆく条件に対して都度適切な値を見つける必要がある場合には二分探索、条件は一定の場合に貪欲法と使い分けるのがいいのかもと思った