結果
| 問題 |
No.1371 交換門松列・松
|
| ユーザー |
 lam6er
|
| 提出日時 | 2025-04-09 20:59:58 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,748 bytes |
| コンパイル時間 | 413 ms |
| コンパイル使用メモリ | 82,340 KB |
| 実行使用メモリ | 270,628 KB |
| 最終ジャッジ日時 | 2025-04-09 21:00:54 |
| 合計ジャッジ時間 | 7,460 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 15 TLE * 1 -- * 13 |
ソースコード
import sys
def main():
sys.setrecursionlimit(1 << 25)
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
def is_valid(a, b, c):
if a == b or b == c or a == c:
return False
return (b > a and b > c) or (b < a and b < c)
# Precompute all positions which are peaks or valleys
is_mountain = [False] * N
for k in range(1, N-1):
left = A[k-1]
mid = A[k]
right = A[k+1]
if mid > left and mid > right:
is_mountain[k] = True
elif mid < left and mid < right:
is_mountain[k] = True
def check_swap(i, j):
B = A.copy()
B[i], B[j] = B[j], B[i]
# Determine all the k's to check
checked = set()
# After swapping, i and j are still at positions i and j. Check their surroundings
for k in [i-2, i-1, i, i+1]:
if 0 <= k <= N-3:
checked.add(k)
for k in [j-2, j-1, j, j+1]:
if 0 <= k <= N-3:
checked.add(k)
# Also check the original positions of A[i] and A[j] (they might have moved to j and i)
# This part might be redundant but just to cover all cases
# For any triplet involving i or j, but this is the same as the above checks
for k in checked:
a, b, c = B[k], B[k+1], B[k+2]
if not is_valid(a, b, c):
return False
return True
# Precompute candidates where the elements might be swappable
# This part tries to find elements that are peaks or valleys and their neighbors
candidate_pairs = 0
# We can only swap elements that are in peaks or valleys and their neighbors?
# Another idea: since the problem seems to have O(N) valid pairs, let's try all adjacent pairs and maybe some others
# However, this is not efficient, so instead, we look for elements that when swapped would not change the peaks/valleys structure
# Generate all possible candidate pairs (i,j)
# To make it efficient, consider all pairs where swapping them will not affect many triplets
# For example, pairs where the elements are in the same "wave" pattern
# Another idea: swap only pairs that are adjacent or have distance <= 3
# But N is up to 2e5, even this would be O(2e5 * 3) which is manageable
# Wait, no. If for each i, we check j in i+1 to i+3, that's O(4N) pairs. Which is manageable?
candidate = []
for i in range(N):
# j can be i+1, i+2, ..., min(i+4, N-1)
for j in range(i+1, min(i+4, N)):
candidate.append((i, j))
# Additionally, check the other pairs where elements are at peaks or valleys
# Or other criteria
# Also check pairs where the elements are both peaks or both valleys
peaks = []
valleys = []
for k in range(1, N-1):
if A[k] > A[k-1] and A[k] > A[k+1]:
peaks.append(k)
elif A[k] < A[k-1] and A[k] < A[k+1]:
valleys.append(k)
# Consider swapping two peaks or two valleys if possible
# Not sure
# But after checking the candidate adjacent pairs, need to check each pair
# However, the sample inputs require more than adjacent pairs
# Alternative approach: check all possible pairs but with early exit if checked triplets are invalid
# Given time constraints, let's use the following approach:
# For all possible pairs (i, j), if their distance is <=3, check them. But this is not sufficient.
# Alternatively, swap each possible pair, check all affected triplets. This is O(N^2) which is impossible for large N.
# Given the problem's time limit, the solution must have O(N) or O(N log N) time complexity.
# So, perhaps only certain pairs can be swapped, such as certain adjacent pairs
# After various failed attempts, the correct approach is to check all possible pairs where i and j are within a small window and use the precomputed peaks/valleys
# But to align with the sample input where the answer is larger than adjacent pairs, need to consider more.
# Time is limited. For submission, even though it's not optimal, we can proceed with the following code which may not pass large N cases but works for samples.
# However, the correct approach is to find all pairs (i, j) where all triplets affected by the swap are valid. But how?
# The correct way is to precompute for each position, the set of k's that are affected when swapped, and check those.
# Let's proceed with the initial approach but optimized.
# Precompute for all possible pairs (i,j)
# The answer counts the number of pairs (i < j) such that check_swap(i, j) is True
# For N=2e5, this is O(N^2) which is not feasible. Hence, we must find an optimized way.
# The correct observation is that swapping two elements will only affect the triplets that include either i or j and their nearby elements. Hence, the candidate pairs must have i and j such that swapping them doesn't alter the structure of the sequence outside these local changes.
# Thus, valid swaps must maintain the Kadomatsu property locally. For a pair (i,j), the only invalid triplets after swapping are those in the vicinity of i and j.
# Therefore, the solution involves checking all pairs (i,j) where the swap affects a small number of triplets around i and j, and each of these triplets remains valid.
# Given the time constraints, here's the code that would pass for small N, but not for large N. However, the optimal solution requires finding that valid pairs are only those which are adjacent or satisfy certain properties based on the peaks and valleys, which is non-trivial.
# For the purpose of this submission, the following code passes the sample inputs but may not handle large N efficiently:
# However, given that the problem statement requires handling up to N=2e5, this code is not feasible. Therefore, a correct solution is expected to recognize that valid swaps are minimal and can be checked in linear time.
# Due to the complexity, here's the code that follows the initial approach, but it may not pass large inputs:
count = 0
for i in range(N):
for j in range(i+1, N):
# Pruning: check if swapping i and j is possible
# To optimize, check if the elements are the same (impossible here as it's a permutation)
# Check surrounding triplets
if check_swap(i, j):
count +=1
print(count)
# However, this code is O(N^2) and not efficient. Hence, the correct approach is needed.
if __name__ == '__main__':
main()