結果
| 問題 |
No.1460 Max of Min
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:05:35 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,440 bytes |
| コンパイル時間 | 145 ms |
| コンパイル使用メモリ | 82,376 KB |
| 実行使用メモリ | 61,924 KB |
| 最終ジャッジ日時 | 2025-05-14 13:07:07 |
| 合計ジャッジ時間 | 4,184 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | TLE * 1 -- * 90 |
ソースコード
# -*- coding: utf-8 -*-
import sys
# Use fast I/O provided by sys.stdin.readline
input = sys.stdin.readline
def solve():
# Read K and N
K, N = map(int, input().split())
# Read initial A values (A_0 to A_{K-1})
A = list(map(int, input().split()))
# Read B values (B_0 to B_{K-1})
B = list(map(int, input().split()))
# If N is less than K, A_N is one of the initial given values.
if N < K:
print(A[N])
return
# The recurrence relation A_i = max(min(A_{i-K+j}, B_j) for 0 <= j < K) implies that
# any A_i for i >= 0 must be one of the values from the initial A sequence or the B sequence.
# Collect all unique initial values from A and B.
possible_values = set(A) | set(B)
# Sort these unique values to enable binary search.
sorted_distinct_values = sorted(list(possible_values))
m = len(sorted_distinct_values) # Number of distinct possible values
# Memoization dictionaries to cache results of matrix transpose and matrix power calculations.
# This can significantly speed up computations if the same matrices or powers are needed multiple times.
memo_transpose = {}
memo_mat_pow = {}
# Define matrix multiplication over the Boolean semiring (OR for addition, AND for multiplication).
# Matrices are represented as lists of integers, where each integer is a bitmask representing a row.
# K is the dimension of the square matrix.
def mat_mul(mat1, mat2, K):
# Use tuple representation of mat2 as key for memoizing its transpose.
mat2_key = tuple(mat2)
# Check cache for the transpose of mat2.
if mat2_key in memo_transpose:
mat2_T = memo_transpose[mat2_key]
else:
# If not cached, compute the transpose of mat2.
# mat2_T[c] will store column c of mat2 as a bitmask.
mat2_T = [0] * K
for r in range(K):
val_mat2_r = mat2[r] # Get the integer representing row r of mat2
for c in range(K):
# Check if the c-th bit is set in row r.
if (val_mat2_r >> c) & 1:
# If yes, set the r-th bit in column c representation (mat2_T[c]).
mat2_T[c] |= (1 << r)
# Cache the computed transpose.
memo_transpose[mat2_key] = mat2_T
# Compute the resulting matrix product (mat1 * mat2).
res = [0] * K
for r in range(K):
val_mat1_r = mat1[r] # Get the integer representing row r of mat1
# Optimization: if row r of mat1 is all zeros, the r-th row of the result is all zeros.
if val_mat1_r == 0:
res[r] = 0
continue
row_res = 0 # Accumulator for the resulting row r bitmask
for c in range(K):
# The (r, c) entry of the result is 1 iff the dot product of row r of mat1
# and column c of mat2 is non-zero (in Boolean semiring: OR sum of AND products is 1).
# This is equivalent to checking if the bitwise AND of mat1[r] and mat2_T[c] is non-zero.
if (val_mat1_r & mat2_T[c]) != 0:
# If non-zero, set the c-th bit in the resulting row r bitmask.
row_res |= (1 << c)
res[r] = row_res
return res
# Define matrix power using binary exponentiation (also known as exponentiation by squaring).
def mat_pow(base, exp, K):
# Use tuple representation of base matrix and exponent as key for memoization.
base_key = tuple(base)
state = (base_key, exp)
# Return cached result if available.
if state in memo_mat_pow:
return memo_mat_pow[state]
# Initialize result matrix 'res' as the identity matrix.
res = [0] * K
for i in range(K):
res[i] = (1 << i)
temp_base = base # Temporary variable to hold powers of base (base, base^2, base^4, ...)
current_exp = exp # Current exponent value
# Standard binary exponentiation loop.
while current_exp > 0:
# If the current exponent is odd, multiply the result by the current base power.
if current_exp % 2 == 1:
res = mat_mul(res, temp_base, K)
# Square the current base power for the next iteration.
temp_base = mat_mul(temp_base, temp_base, K)
# Halve the exponent (integer division).
current_exp //= 2
# Cache the computed result before returning.
memo_mat_pow[state] = res
return res
# The problem asks for A_N. We use binary search on the possible values C.
# For a given C, we check if A_N >= C. This check can be done using matrix exponentiation.
# The state transition for the boolean sequence a_i = (A_i >= C) is linear over the Boolean semiring.
# We need to compute the state M = N - K + 1 steps from the initial state.
steps = N - K + 1
if steps < 0: steps = 0 # This should not happen for N >= K
# This variable will store the index of the largest value C in sorted_distinct_values
# for which the check A_N >= C returns true. Initialize to -1 (or another sentinel).
current_best_idx = -1
# Perform an initial check with the minimum possible value C_min = sorted_distinct_values[0].
# We expect A_N >= C_min to be true based on the analysis that A_i values are bounded below.
C_min = sorted_distinct_values[0]
# Compute the boolean vector b where b_j = (B_j >= C_min).
b_min = [(1 if B[j] >= C_min else 0) for j in range(K)]
# Construct the transition matrix M_min for C_min.
M_min = [0] * K
for r in range(K - 1): M_min[r] = (1 << (r + 1)) # Shift rows
row_K_minus_1_min = 0
for j in range(K):
if b_min[j]: row_K_minus_1_min |= (1 << j) # Last row depends on b_min
M_min[K-1] = row_K_minus_1_min
# Compute the initial boolean state vector s0_min where s0_min_j = (A_j >= C_min).
a0_min = [(1 if A[j] >= C_min else 0) for j in range(K)]
s0_val_min = 0
for j in range(K):
if a0_min[j]: s0_val_min |= (1 << j)
# Calculate the state after 'steps' transitions.
if steps == 0:
# If N = K-1, the result A_N is A_{K-1}. Check its boolean value a_{K-1}.
final_state_last_comp_val_min = (s0_val_min >> (K-1)) & 1
else:
# Compute M_min ^ steps
memo_transpose.clear() # Clear transpose cache before matrix power calculation
M_pow_steps_min = mat_pow(M_min, steps, K)
# The last component of the final state vector is a_N.
# Calculate it as (last row of M_min^steps) AND s0_min, check if non-zero.
final_state_last_comp_val_min = (M_pow_steps_min[K-1] & s0_val_min) != 0
# If A_N >= C_min is true, set the initial best index to 0.
if final_state_last_comp_val_min:
current_best_idx = 0
else:
# This indicates a potential issue with the theory or implementation, as A_N should be >= min value.
# For safety, output the minimal value found.
print(sorted_distinct_values[0])
return
# Perform binary search over the indices [0, m-1] of sorted_distinct_values.
# We aim to find the largest index `mid_idx` such that A_N >= sorted_distinct_values[mid_idx].
low = current_best_idx # Start search from the minimum index known to work (initially 0).
high = m - 1
while low <= high:
mid_idx = (low + high) // 2
C = sorted_distinct_values[mid_idx] # The candidate value to check
# Construct the boolean transition matrix M for this C.
b = [(1 if B[j] >= C else 0) for j in range(K)]
M = [0] * K
for r in range(K - 1): M[r] = (1 << (r + 1)) # Shift rows
row_K_minus_1 = 0
for j in range(K):
if b[j]: row_K_minus_1 |= (1 << j) # Last row depends on b
M[K-1] = row_K_minus_1
# Construct the initial boolean state vector s0 for this C.
a0 = [(1 if A[j] >= C else 0) for j in range(K)]
s0_val = 0
for j in range(K):
if a0[j]: s0_val |= (1 << j)
# Calculate the state after 'steps' transitions and find a_N.
if steps == 0:
# N = K-1 case
final_state_last_comp_val = (s0_val >> (K-1)) & 1
else:
# Compute M^steps
memo_transpose.clear() # Clear transpose cache before matrix power calculation
M_pow_steps = mat_pow(M, steps, K)
# Check the value of a_N
final_state_last_comp_val = (M_pow_steps[K-1] & s0_val) != 0
# Update binary search range based on the result.
if final_state_last_comp_val:
# If A_N >= C is true, C is a possible answer. Record this index.
# Try potentially larger values C (increase lower bound).
current_best_idx = mid_idx
low = mid_idx + 1
else:
# If A_N >= C is false, C is too high.
# Need to check smaller values C (decrease upper bound).
high = mid_idx - 1
# After binary search, current_best_idx holds the index of the largest C for which A_N >= C was true.
# This C is the value of A_N.
print(sorted_distinct_values[current_best_idx])
# Execute the solve function
solve()