結果
| 問題 |
No.1369 交換門松列・竹
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:10:11 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,333 ms / 2,000 ms |
| コード長 | 6,768 bytes |
| コンパイル時間 | 192 ms |
| コンパイル使用メモリ | 82,036 KB |
| 実行使用メモリ | 257,972 KB |
| 最終ジャッジ日時 | 2025-05-14 13:11:38 |
| 合計ジャッジ時間 | 11,211 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 33 |
ソースコード
import sys
# Function to check if a triplet (a, b, c) is a Kadomatsu sequence
def is_kadomatsu(a, b, c):
"""
Checks if the triplet (a, b, c) satisfies the Kadomatsu conditions:
1. All elements are distinct.
2. The middle element b is either strictly the maximum or strictly the minimum.
"""
# Check distinctness
if a == b or b == c or a == c:
return False
# Check if the middle element b is a local extremum
# This is true if b is greater than both neighbors OR b is less than both neighbors.
# Mathematically, this condition can be written as (b - a) * (b - c) > 0.
if (b > a and b > c) or (b < a and b < c):
return True
return False
# Main logic function to solve one test case
def solve():
"""
Solves a single test case. Reads input N and array A.
Determines if A can be made into a Kadomatsu sequence sequence by exactly one swap
of elements A[p] and A[q] where p != q and A[p] != A[q].
Prints "Yes" or "No".
"""
N = int(sys.stdin.readline())
# Read array elements into a list (mutable sequence needed for swapping)
A = list(map(int, sys.stdin.readline().split()))
# Identify indices of all "bad" triplets in the initial sequence A.
# A triplet starting at index i is (A[i], A[i+1], A[i+2]). Indices are 0-based.
# A triplet is "bad" if it's not a Kadomatsu sequence.
S = [] # List to store indices of bad triplets
for i in range(N - 2): # Iterate through all possible start indices for triplets
if not is_kadomatsu(A[i], A[i+1], A[i+2]):
S.append(i)
# Optimization based on the observation that a single swap (p, q) can affect
# at most 6 triplets (indices k in I_pq). For the sequence to become Kadomatsu,
# all initially bad triplets must be among those affected by the swap.
# This implies S must be a subset of I_pq. Since |I_pq| <= 6, we must have |S| <= 6.
if len(S) > 6:
print("No")
return
# Collect all indices involved in any bad triplet. The set B stores these indices.
# An index is involved if it's part of any bad triplet (A[i], A[i+1], A[i+2]) where i is in S.
# The indices are i, i+1, i+2.
B = set()
for i in S:
# Add indices i, i+1, i+2 to set B, ensuring they are valid array indices [0, N-1].
# The check `0 <= index < N` ensures validity, though for i in [0, N-3],
# indices i, i+1, i+2 are always within [0, N-1].
if 0 <= i < N: B.add(i)
if 0 <= i + 1 < N: B.add(i + 1)
if 0 <= i + 2 < N: B.add(i + 2)
# Flag to indicate whether a valid swap is found
found = False
# Set to store unique candidate swap pairs (p, q) with p < q. Using a set avoids redundant checks.
potential_swaps_set = set()
# Generate candidate swaps. A key insight is that for a swap (p, q) to fix all bad triplets,
# it must affect them. This implies that at least one of the swapped indices (p or q) must be
# 'close' to the indices involved in bad triplets. A simpler necessary condition is that
# at least one of p or q must be in B.
# We iterate through p in B and q over all possible indices [0, N-1].
# This covers all pairs (p, q) where at least one index is in B.
for p in B:
for q in range(N):
# Check swap validity conditions from the problem statement:
if p == q: continue # Indices must be different
if A[p] == A[q]: continue # Values at indices must be different
# Store the pair uniquely, sorted to treat (p, q) and (q, p) identically.
potential_swaps_set.add(tuple(sorted((p, q))))
# Check each unique candidate swap pair (p, q)
# Sorting the list of pairs ensures deterministic order, useful for debugging but not required for correctness.
for p, q in sorted(list(potential_swaps_set)):
# Calculate I_pq: the set of triplet indices k affected by swapping A[p] and A[q].
# A triplet starting at index k, i.e., (A[k], A[k+1], A[k+2]), is affected if
# the set of its element indices {k, k+1, k+2} intersects with the swapped indices {p, q}.
# This happens if k is 'near' p or q: k is in {p-2, p-1, p, q-2, q-1, q}.
I_pq = set()
potential_indices_near_swap = {p-2, p-1, p, q-2, q-1, q}
for k in potential_indices_near_swap:
# Check if k is a valid index for the start of a triplet [0, N-3].
if 0 <= k <= N - 3:
I_pq.add(k)
# Necessary condition check: S subseteq I_pq
# All originally bad triplets must be among the indices affected by the swap.
# If not, this swap cannot possibly fix all bad triplets.
is_subset = True
for bad_idx in S:
if bad_idx not in I_pq:
is_subset = False
break
if not is_subset:
continue # Try the next potential swap pair.
# If the condition S subseteq I_pq holds, simulate the swap and check its effect.
# Perform swap temporarily on the array A.
A[p], A[q] = A[q], A[p]
# Check if all potentially affected triplets (indices k in I_pq) are now Kadomatsu sequences.
# This includes checking if formerly bad triplets (k in S) become good,
# and formerly good triplets (k in I_pq \ S) remain good.
all_good_in_I_pq = True
for k in I_pq:
# Check the triplet (A[k], A[k+1], A[k+2]) after the swap.
if not is_kadomatsu(A[k], A[k+1], A[k+2]):
all_good_in_I_pq = False
break # Found a bad triplet within the affected range, this swap fails.
# IMPORTANT: Revert the swap to restore the original array state.
# This is crucial for correctly checking subsequent candidate swap pairs.
A[p], A[q] = A[q], A[p]
# If all checks passed for this swap (all affected triplets are now good),
# we have found a valid swap that makes the sequence a Kadomatsu sequence sequence.
if all_good_in_I_pq:
found = True
break # Exit the loop over potential swaps, as we only need to find one possibility.
# Output the final result for this test case based on whether a valid swap was found.
if found:
print("Yes")
else:
print("No")
# Read the total number of test cases
T = int(sys.stdin.readline())
# Process each test case by calling the solve function
for _ in range(T):
solve()