結果

問題 No.332 数列をプレゼントに
ユーザー qwewe
提出日時 2025-05-14 13:23:07
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,768 bytes
コンパイル時間 153 ms
コンパイル使用メモリ 82,576 KB
実行使用メモリ 91,480 KB
最終ジャッジ日時 2025-05-14 13:25:07
合計ジャッジ時間 4,268 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 1 TLE * 1 -- * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Adjust recursion limit if necessary for deep stacks, though N=100 usually isn't an issue for path length.
# sys.setrecursionlimit(10**5) # Default is often 1000 or 3000. N=100 is fine.

def solve():
    N, X = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))

    # Container for the first found solution path (list to pass by reference-like behavior)
    solution_container = [None] 

    # current_path_chars is a list of 'x' or 'o' characters
    # k is the current index in A being considered
    # current_sum is the sum of elements chosen so far from A[0...k-1]
    def backtrack(k, current_sum, current_path_chars):
        # If a solution has already been found in another branch, stop exploring
        if solution_container[0] is not None:
            return

        # Base case: If current_sum matches X, a solution is found
        if current_sum == X:
            solution_container[0] = "".join(current_path_chars)
            return

        # Base case: If all elements are considered (k == N)
        # and current_sum is not X (checked by previous if), this path is not a solution.
        # Also, if k == N and current_sum == X, it's handled by the previous block.
        if k == N:
            return
        
        # Pruning: If current_sum already exceeds X, this path cannot lead to a solution
        # (since all A_i are natural numbers, i.e., A_i >= 1)
        if current_sum > X:
            return
        
        # --- More advanced pruning (optional, but can help) ---
        # If sum of remaining elements is not enough to reach X.
        # This requires precomputed suffix sums or calculating sum(A[k:]) each time.
        # For N=100, sum(A[k:]) is too slow if done repeatedly.
        # If precomputed: `if current_sum + suffix_sums[k] < X: return`
        # We'll omit this specific pruning for simplicity first, as basic pruning might be enough
        # for the given constraints if the test data structure allows.

        # Recursive step:

        # Option 1: Don't include A[k]
        current_path_chars[k] = 'x'
        backtrack(k + 1, current_sum, current_path_chars)
        
        # If a solution was found by not including A[k], stop further exploration
        if solution_container[0] is not None:
            return
        
        # Option 2: Include A[k]
        # Pruning: Only proceed if adding A[k] does not immediately exceed X
        if current_sum + A[k] <= X:
            current_path_chars[k] = 'o'
            backtrack(k + 1, current_sum + A[k], current_path_chars)
            
            # If a solution was found by including A[k], stop (already handled by global check)
            # if solution_container[0] is not None:
            #     return

        # Note on path character reset:
        # Since current_path_chars is modified in place and we return immediately
        # after finding a solution (solution_container[0] is not None),
        # the state of current_path_chars for elements > k in failed branches
        # doesn't affect the first found solution.
        # And for element k, its character ('x' or 'o') correctly reflects the choice made
        # for the specific recursive call. If that call returns without finding a solution,
        # the character for k might remain 'o' from the second choice, but that's fine
        # as this path segment (up to k-1 with A[k] as 'o') didn't lead to a solution.
        # The parent call will correctly explore its alternatives.

    initial_path_chars = ['x'] * N  # Initialize path: all elements not taken
    backtrack(0, 0, initial_path_chars)

    if solution_container[0] is not None:
        print(solution_container[0])
    else:
        print("No")

solve()
0