ABC412のC問題 Giant Domino
日本最強プログラマー学生選手権～Advance～ -予選- （AtCoder Beginner Contest 412）のC問題 Giant Dominoをコンテスト時間内に正解できなかったので、改めてチャレンジした。
C - Giant Domino
\(S_1\)から\(S_n\)のドミノが有る。\(S_1\)と\(S_n\)を固定して、その間を他のドミノで埋めて\(S_1\)から\(S_n\)まですべてのドミノが倒れる最小枚数を答える問題。ただし、ドミノは、2倍以下の大きさでないと倒すことができない。
考え方
すべて倒れる最小の枚数を求めるので、\(S_2\)から\(S_{n-1}\)までのドミノをできるだけ大きいドミノを倒すように並べれば良い。そこでドミノを大きさ順にソートして、倒せなくなったドミノの一つ前が倒せる最大のドミノとなる。これを繰り返すことで最小の並びを求められる。このアルゴリズムを貪欲法と呼ぶらしい。
技術的工夫
\(S_2\)から\(S_{n-1}\)までのドミノをすべて使うと、\(S_{n-1} = S_n\)となった時に上手く処理するプログラムを書けなかった。そこで\(S_1\)から\(S_n\)の間に来るドミノ\(S_i\)は、\((S_1 \lt S_i) \& (S_i \lt S_n)\)となるので、filter()を使って候補を絞ると同時に\(S_{n-1} = S_n\)となることを避けた。
Pythonではforループ内からbreakで抜けてきたかをelseを使って判断できる。breakすること無くforを全て回った時にはelseブロックが実行される。ここにcontinueを入れると外側のループに先頭に戻るため、elseブロックを出たところはbreakでforループを抜けてきたときだけ実行される。これによりbreakしたかのflagを使う必要が無くなる。
t = int(input())
for _ in range(t):
n = int(input())
s = list(map(int, input().split()))
s_1 = s[0]
s_n = s[-1]
# simplify S items and sort them
items = [s_1] + sorted(filter(lambda x: (x > s_1)
and (x < s_n), s[1:-1])) + [s_n]
placed = [s_1]
start_index = 0
start_size = s_1
if (items[0] * 2) < items[1]:
print(-1)
continue
# start from 2 beacause the item[1] is already confirmed above.
for i in range(2, len(items)):
if (start_size * 2) < items[i]:
# failed to push over a domino.
start_index = i - 1
start_size = items[start_index]
placed.append(start_size)
# confirm pushable over the next.
if (start_size * 2) < items[i]:
break
else:
# OK
pass
else:
# No break in for-loop.
placed.append(s_n)
print(len(placed))
continue
# failed to push over the next dominos.
print(-1)