結果
| 問題 |
No.204 ゴールデン・ウィーク(2)
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:05:03 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 41 ms / 1,000 ms |
| コード長 | 7,439 bytes |
| コンパイル時間 | 299 ms |
| コンパイル使用メモリ | 82,964 KB |
| 実行使用メモリ | 52,480 KB |
| 最終ジャッジ日時 | 2025-05-14 13:06:52 |
| 合計ジャッジ時間 | 3,703 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 46 |
ソースコード
import sys
def solve():
# Read D from input: the maximum number of consecutive weekdays we can convert to holidays.
D = int(sys.stdin.readline())
# Read the two lines representing the 14-day calendar period.
C1 = sys.stdin.readline().strip()
C2 = sys.stdin.readline().strip()
# Concatenate the two lines to get the full 14-day calendar string.
C = C1 + C2
# Create an extended calendar string `S_prime` by adding 'x' (weekday) at both ends.
# `S_prime[0]` represents the status of day 0.
# `S_prime[1]` to `S_prime[14]` represents the status of days 1 to 14 based on the input `C`.
# `S_prime[15]` represents the status of day 15.
# Days outside the range 1-14 are weekdays ('x'), so day 0 and day 15 are 'x'.
# Days before day 0 and after day 15 are also implicitly 'x'.
# This extended string helps simplify handling boundary conditions related to the infinite nature of the calendar.
S_prime = 'x' + C + 'x'
N_prime = len(S_prime) # The length of S_prime is always 14 + 2 = 16.
# Store information about consecutive blocks of identical characters ('x' or 'o') found in S_prime.
blocks = []
# Basic check: If N_prime is 2, it means the original calendar string C was empty.
# This case shouldn't happen based on the problem statement (14 days fixed), but added for robustness.
# If C was empty, all days are 'x', so we can take D consecutive holidays anywhere. Max length = D.
if N_prime == 2: # Equivalent to checking if C was empty string
print(D)
return
# Parse the extended string `S_prime` to identify all maximal consecutive blocks.
start_idx = 0
curr_char = S_prime[0]
# Iterate through S_prime to find blocks.
for i in range(1, N_prime):
# If the character changes, the previous block ends at i-1.
if S_prime[i] != curr_char:
# Record the found block: its type ('x' or 'o'), start/end indices, and length.
blocks.append({'type': curr_char, 'start': start_idx, 'end': i-1, 'len': i - start_idx})
# Start tracking the new block from index i.
start_idx = i
curr_char = S_prime[i]
# After the loop, record the last block which ends at N_prime-1.
blocks.append({'type': curr_char, 'start': start_idx, 'end': N_prime-1, 'len': N_prime - start_idx})
# Create dictionaries to quickly find the length of holiday ('o') blocks.
# `o_block_end_len[idx]` stores the length of the 'o' block ending at index `idx`.
# `o_block_start_len[idx]` stores the length of the 'o' block starting at index `idx`.
o_block_end_len = {}
o_block_start_len = {}
# Calculate the maximum length of any initial holiday block ('o') present in the calendar.
# This value serves as a baseline maximum length.
max_initial_o = 0
for block in blocks:
if block['type'] == 'o':
max_initial_o = max(max_initial_o, block['len'])
# Populate the lookup dictionaries.
o_block_end_len[block['end']] = block['len']
o_block_start_len[block['start']] = block['len']
# Initialize the overall maximum holiday length found so far.
# Start with the maximum length found in the initial calendar without using vacation days.
max_total_len = max_initial_o
# Iterate through all identified blocks. We are interested in modifying 'x' blocks.
for block in blocks:
# Process only weekday ('x') blocks.
if block['type'] == 'x':
# Get block details: start index i, end index j, length k within S_prime.
i = block['start']
j = block['end']
k = block['len']
# Determine the length of the holiday block immediately preceding this 'x' block (L_prev).
L_prev = 0
# Check if the index `i-1` is valid (i.e., `i > 0`).
if i > 0:
# Use dictionary lookup: If `S_prime[i-1]` was 'o', get its block length.
# `.get(key, 0)` returns 0 if `key` not found (i.e., `S_prime[i-1]` was 'x' or boundary).
L_prev = o_block_end_len.get(i-1, 0)
# Determine the length of the holiday block immediately following this 'x' block (L_next).
L_next = 0
# Check if the index `j+1` is valid (i.e., `j < N_prime - 1`).
if j < N_prime - 1:
# Use dictionary lookup: If `S_prime[j+1]` was 'o', get its block length. Otherwise defaults to 0.
L_next = o_block_start_len.get(j+1, 0)
# Calculate the potential maximum holiday length achievable by using vacation days on this 'x' block.
candidate = 0
# Case 1: The 'x' block starts at index 0.
# This block in S_prime represents the infinite sequence of weekdays ending at day 0.
if i == 0:
# The best use of D vacation days is to convert days `-D+1` to `0` into holidays.
# This creates a block of D holidays potentially merging with the holiday block starting at day 1 (index 1).
# The total length would be D + L_next. L_prev is implicitly 0 for this infinite block from the past.
candidate = D + L_next
max_total_len = max(max_total_len, candidate)
# Case 2: The 'x' block ends at index 15 (N_prime - 1).
# This block in S_prime represents the infinite sequence of weekdays starting at day 15.
elif j == N_prime - 1:
# The best use of D vacation days is to convert days `15` to `14+D` into holidays.
# This creates a block of D holidays potentially merging with the holiday block ending at day 14 (index 14).
# The total length would be L_prev + D. L_next is implicitly 0 for this infinite block into the future.
candidate = L_prev + D
max_total_len = max(max_total_len, candidate)
# Case 3: The 'x' block is finite and is fully contained within indices 1 to 14 of S_prime.
# This corresponds to a block of weekdays within the given 2-week period.
else: # This condition means 0 < i and j < N_prime - 1
# If the length k of the weekday block is less than or equal to D,
# we can convert all k weekdays to holidays. This connects the preceding (L_prev)
# and succeeding (L_next) holiday blocks, if they exist.
if k <= D:
candidate = L_prev + k + L_next
# If the length k is greater than D, we can only convert D consecutive weekdays.
# To maximize the resulting holiday length, we should attach these D days to the
# longer adjacent holiday block. This is captured by taking the maximum of
# extending the previous block (L_prev + D) or extending the next block (D + L_next).
else: # k > D
candidate = max(L_prev + D, D + L_next)
# Update the overall maximum length found so far.
max_total_len = max(max_total_len, candidate)
# Print the final maximum possible length of consecutive holidays after optimal use of vacation days.
print(max_total_len)
# Execute the solve function to run the program.
solve()