結果
| 問題 |
No.719 Coprime
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:20:23 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,232 bytes |
| コンパイル時間 | 1,341 ms |
| コンパイル使用メモリ | 81,944 KB |
| 実行使用メモリ | 272,452 KB |
| 最終ジャッジ日時 | 2025-05-14 13:21:43 |
| 合計ジャッジ時間 | 16,452 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 52 TLE * 1 -- * 8 |
ソースコード
import sys
import math
# Set a higher recursion depth limit. The problem constraints might lead to deep recursion.
# N up to 1262 means the maximum number of odd numbers is about 630.
# The recursion depth could potentially reach this value in the worst case.
# We set it to 2000 to be safe.
try:
sys.setrecursionlimit(2000)
except Exception as e:
# In some environments, setting recursion depth might fail.
# We print a warning to stderr but continue. The default limit might be sufficient.
# print(f"Warning: Could not set recursion depth: {e}", file=sys.stderr) # Commented out for final submission
pass
# Memoization dictionary to store results of computed subproblems.
# Keys will be tuples representing sorted subsets of candidate numbers.
memo = {}
# Adjacency list to represent the conflict graph.
# An edge exists between two numbers if their greatest common divisor (GCD) is greater than 1.
adj_all = {}
# Function to build the adjacency list `adj_all` for numbers from 2 to N.
def build_adj(N):
"""Builds the adjacency list for numbers 2 to N based on gcd > 1."""
# Create a list of numbers from 2 to N.
nums = list(range(2, N + 1))
# Initialize an empty list for each number in the adjacency list dictionary.
for x in nums:
adj_all[x] = []
# Iterate through all unique pairs of numbers (i, j) where i < j.
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
# Calculate the greatest common divisor (GCD) of the pair.
# Use Python's built-in math.gcd for efficiency.
if math.gcd(nums[i], nums[j]) > 1:
# If GCD > 1, they conflict. Add an edge between them in the graph.
adj_all[nums[i]].append(nums[j])
adj_all[nums[j]].append(nums[i])
# Recursive function to find the Maximum Weight Independent Set (MWIS).
# Uses backtracking with memoization.
# `candidates_tuple` must be a tuple of candidate numbers, sorted in ascending order.
def max_weight_independent_set(candidates_tuple):
"""Computes the maximum weight independent set sum for a given tuple of candidates."""
# Base case: If there are no candidates left, the sum is 0.
if not candidates_tuple:
return 0
# Use the sorted tuple of candidates as the state key for memoization.
# This ensures that the same subset of candidates, regardless of order arrived,
# maps to the same state.
state = candidates_tuple
if state in memo:
# If this state has been computed before, return the cached result.
return memo[state]
# Branching step: Choose a vertex to make a decision on (include or exclude).
# Strategy: Pick the vertex with the largest value. Since the tuple is sorted,
# this is the last element. This heuristic can sometimes prune the search faster.
k = candidates_tuple[-1]
# Convert the tuple to a set for efficient membership checking and element removal.
candidates_set = set(candidates_tuple)
# --- Option 1: Include vertex k in the independent set ---
# If k is included, we cannot include any of its neighbors.
# Find neighbors of k that are present in the current set of candidates.
neighbors_of_k_in_candidates = []
# Check if k has any neighbors recorded in the full adjacency list.
# k should always be in adj_all since N >= 2 implies k >= 2
# Small optimization: check if k has neighbors before iterating
if k in adj_all and adj_all[k]:
for neighbor in adj_all[k]:
# Check if this neighbor is among the current candidates.
if neighbor in candidates_set:
neighbors_of_k_in_candidates.append(neighbor)
# Create the set of remaining candidates for the recursive call when k is included:
# Start with a copy of the current candidates set.
remaining_candidates1_set = candidates_set.copy()
# Remove k itself.
remaining_candidates1_set.remove(k)
# Remove all neighbors of k found within the current candidates set.
for neighbor in neighbors_of_k_in_candidates:
# Need to check if neighbor is still in the set, as it might have been removed if it was equal to k
# (not possible here since k != neighbor) or if it was also a neighbor of a previously removed node
# (not applicable in this step, but good practice for general MWIS).
# More simply, check if it's present before removing to avoid errors.
if neighbor in remaining_candidates1_set:
remaining_candidates1_set.remove(neighbor)
# Recursively call the function for the remaining candidates.
# The result for this branch is k (value of included vertex) plus the result of the subproblem.
# Pass the remaining candidates as a sorted tuple to maintain canonical state representation.
sum1 = k + max_weight_independent_set(tuple(sorted(list(remaining_candidates1_set))))
# --- Option 2: Exclude vertex k from the independent set ---
# If k is excluded, we simply remove k and proceed with the rest of the candidates.
# Create the set of remaining candidates for the recursive call when k is excluded.
remaining_candidates2_set = candidates_set.copy()
remaining_candidates2_set.remove(k)
# Recursively compute the max weight sum for this subset.
# Pass the remaining candidates as a sorted tuple.
sum2 = max_weight_independent_set(tuple(sorted(list(remaining_candidates2_set))))
# --- Combine results ---
# The maximum weight for the current state is the maximum of the two options: including k or excluding k.
result = max(sum1, sum2)
# Store the computed result in the memoization table before returning.
memo[state] = result
return result
# Main function to coordinate the solving process.
def solve():
"""Reads input N, orchestrates the MWIS computation, and prints the final result."""
# Read integer N from standard input.
N = int(sys.stdin.readline())
# Handle the base case N=2 where the only card is 2. Max sum is 2.
if N == 2:
print(2)
return
# Precompute the adjacency list representing conflicts (GCD > 1).
build_adj(N)
# Partition the numbers from 2 to N into even and odd lists.
# This is key because at most one even number can be in a valid set (due to factor 2).
evens = []
odds = []
for x in range(2, N + 1):
if x % 2 == 0:
evens.append(x)
else:
odds.append(x)
# Clear the memoization cache before starting the main computation phase.
memo.clear()
# Case 1: The maximum sum is achieved using only odd numbers.
# Compute the MWIS sum for the set of all odd numbers.
odds_tuple = tuple(sorted(odds)) # Use sorted tuple for canonical state representation.
max_sum_odds_only = max_weight_independent_set(odds_tuple)
# Initialize the overall maximum sum found so far with this value.
max_total_sum = max_sum_odds_only
# Case 2: The maximum sum is achieved using exactly one even number `e` and a subset of compatible odd numbers.
# Iterate through each even number `e`.
for e in evens:
# Identify the subset of odd numbers `O_e` that are coprime to `e` (i.e., gcd(e, o) == 1).
O_e = []
for o in odds:
if math.gcd(e, o) == 1:
O_e.append(o)
# Compute the MWIS sum for this compatible subset `O_e`.
O_e_tuple = tuple(sorted(O_e)) # Use sorted tuple state.
# Important: The memoization cache `memo` is shared across these calls.
# If MWIS is computed for the same subset of odds multiple times (for different `e`),
# the cached result is reused.
current_max_sum_for_O_e = max_weight_independent_set(O_e_tuple)
# Update the overall maximum sum if including `e` plus the best compatible odds subset sum
# yields a higher total sum.
max_total_sum = max(max_total_sum, e + current_max_sum_for_O_e)
# Print the final maximum possible sum.
print(max_total_sum)
# Execute the main solver function when the script is run.
solve()