from bisect import bisectright t = int(input()) for in range(t): n = int(input()) S =…
- User
from bisect import bisect_right
t = int(input()) for _ in range(t): n = int(input()) S = list(map(int, input().split()))
if n == 2: print('2' if S[0] * 2 >= S[1] else '-1') continue first = S[0] f = S[1] end = S[-1] e = S[-2] temp = sorted(S[1:-1]) now = first cnt = 0 while True: if 2 * now >= end: break idx = bisect_right(temp, 2 * now) if idx > 0: idx -= 1 if idx >= len(temp): break now = temp[idx] temp.pop(idx) cnt += 1 if cnt == 1: f = now e = now if 2 * first >= f: cnt += 1 else: print('-1') continue if 2 * e >= end: cnt += 1 else: print('-1') continue print(cnt)このコードに問題点はありますか?
Assistant
このコードにはいくつかの問題点や改善点が存在します。以下に詳細を述べます。
1. アルゴリズムの理解不足による誤り
このコードは、与えられた配列
Sの要素を操作し、特定の条件 (2 * 前の数 >= 次の数) を満たしながら末尾の数値まで到達するための最小操作回数を求めているようです。しかし、ロジックが複雑で一貫性に欠け、以下の点で誤りがあります。- 誤った仮定: コードは、配列の最初の2要素 (
first,f) と最後の2要素 (end,e) を特別扱いしています。しかし、途中の要素を昇順に辿って最後まで条件を満たすパスを見つけるという戦略が正しくありません。 - 不適切な
tempの使用:tempリストからbisect_rightで最大の満たす値を探し、popしていますが、この方法では最適解を保証できません。なぜなら、単に局所的に条件を満たす値を選んでいるだけで、全体の最適化を考慮していないからです。
2. コーナーケースの考慮漏れ
n == 1のケースが考慮されていません。n == 1なら即座に0を出力するべきです。- 空の入力 (
n == 0) への対応もありません。問題文に明記されていないなら不要かもしれませんが、エラー処理としては必要です。
3. 無駄な変数・処理
fとeという変数が何を意味しているのかロジックがわかりにくく、無駄な代入が含まれています。- 特に、
cnt == 1でf = nowとしていますが、この変数は後の条件式でしか使われていません。シンプルに書くべきです。
4. アルゴリズムの非効率性
- このコードは貪欲法のつもりかもしれませんが、途中で
temp.pop(idx)を行っているため、リストのサイズが大きい場合に O(n^2) の計算量が発生します。 bisect_rightは O(log n) ですが、その後のpop(idx)が O(n) となり、結果として効率が悪化します。
5. 条件分岐の冗長さ
最終的な判定部分:
if 2 * first >= f: cnt += 1 else: print('-1') continue if 2 * e >= end: cnt += 1 else: print('-1') continueこのロジックは不要に複雑です。以下の点が問題です:
- 配列の最初の要素と2番目以降の選んだ要素の大小チェック、および最後の2要素のチェックがバラバラに行われ、一貫性がありません。
2 * first >= fが成り立たないのに次の2 * e >= endをチェックするのは無意味です。
正しいアプローチ
この問題は典型的な貪欲法 (Greedy Algorithm) または 二分探索 + シミュレーション で解くべきです。
正解コードの方針:
- 配列
Sを昇順ソート する。 - 末尾から2番目の要素まで条件を満たしながら辿る。
- 各ステップで「現在の値の2倍以上」の最小値を選ぶ。
- これを 二分探索 (
bisect_left) で効率的に探す。
以下に修正版コードを示します。
from bisect import bisect_left def solve(): n = int(input()) S = list(map(int, input().split())) if n == 1: print(0) return if n == 2: print(2 if S[0] * 2 >= S[1] else -1) return S.sort() # 配列全体を昇順にソート target = S[-1] # 最終目標値 cnt = 0 current = S[0] # 現在の値 while current < target: # 現在の値の2倍以上の最小値を探索 idx = bisect_left(S, current * 2) if idx == n: # 条件を満たす値がもうない print(-1) return current = S[idx] # 次の値を更新 cnt += 1 print(cnt) # --- main --- t = int(input()) for _ in range(t): solve()修正ポイント:
- シンプルな貪欲法に変更: 常に「現在の2倍以上の最小値」を選ぶ。
- 事前に
S全体をソート: 二分探索が常に有効になるよう保証。 - 無駄な変数 (
f,e) を排除。 - コーナーケース (
n == 1) に対応。 - 計算量は O(n log n) (ソート + 二分探索の繰り返し) となり効率化。
このコードなら、AtCoder 等の競技プログラミングでも十分高速に動作します。元のコードはロジックが入り組んでいてバグの温床になっていたので、大幅に簡略化しました。必要ならさらにコメントしますが、まずはこの修正版で動かしてみてください。
- 誤った仮定: コードは、配列の最初の2要素 (
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.