結果
| 問題 | No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！ |
| コンテスト | |
| ユーザー |
 hitonanode
|
| 提出日時 | 2025-12-25 21:19:10 |
| 言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
| 結果 |
AC
|
| 実行時間 | 4,828 ms / 5,000 ms |
| コード長 | 14,228 bytes |
| 記録 | |
| コンパイル時間 | 272 ms |
| コンパイル使用メモリ | 13,440 KB |
| 実行使用メモリ | 157,880 KB |
| スコア | 9,994,501 |
| 平均クエリ数 | 54.99 |
| 最終ジャッジ日時 | 2025-12-25 21:24:19 |
| 合計ジャッジ時間 | 290,446 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
"""
$ cat ./AGENTS.md
# Instruction
Heuristic Contest の問題を解くためのプログラムを作るリポジトリです。
## ディレクトリ構成
- 今回のコンテストの問題文は ./problem_statement.html です。
- ./main.py に解法を実装します。
- 使用して良いライブラリは、 Python 3.13 の標準ライブラリと、 NumPy 2.2.1, SciPy 1.14.1 のみです。
## コーディング規約
- 解答は Python で作成する。 main.py に全てを実装する
- 乱数の初期 seed は定数として埋め込んで、複数回の実行で再現性を担保する
- 問題を解く関数を実装する。
- 関数の引数に、ジャッジとのやり取りを行うコールバック関数を与える。これにより、ローカル実行と、実際の提出による実行の両方に利用できるようにする。
- 仮想的なジャッジも main.py に実装する。適当なコマンドライン引数とともに手元で実行すると、ランダム生成したデータを元に解法を実行し、どの程度のスコアが取れるのか確認できる
## 注意点
以下を厳守する。
- Chat は日本語で回答してください
- 指示・意図・仕様に関して不明な点があれば、実装に移る前に質問する
## アルゴリズムの方針
STRATEGY.md に詳細に記載されています。この方針に従ってください
$ cat STRATEGY.md
# 戦略
- 最初の 20 回は、これまでに与えたことのないランダムなクエリを与える。
- それ以降は、
- scipy.optimize.linprog を用いて以下の混合整数線形計画問題を考える（これが解を 1 個だけ持つならば、隠された文字列が全てわかったことになる）。
- 候補となる全ての文字列のうち、過去のクエリ結果から存在し得ないものを除いたもの s それぞれについて、 0 以上 1 以下の変数 x_s を生やす（これは、ジャッジがこの文字列を隠し持っているかどうかに相当する）。
- 過去のクエリ結果のうち、 t 回目のクエリに含まれる各 (h, b) についてその出現頻度を数え、その個数が s に対するクエリ結果が (h, b) となるような s 全てに対する x_s の総和と一致する、という等式制約を課す。
- なお、このとき、既に発見済みの文字列は適切に除外して考慮する。
- まずは上記の問題を、 x に対する整数制約を課さずに解く。
- 次に、いったん解いた結果の解について、 x_s の値が 0.9999 以上のものと 0.0001 未満のものしか存在しない場合、 x_s の値が 0.9999 以上の s の個数を k として、「これらの s に対する x_s の総和が k - 1 以下」という制約をさらに追加してもう一度 LP を解く。これで解なしになった場合、これら全ての s が隠された文字列であることが確定するので、これらを回答して終了する。
- x_s の値が 1e-5 以上のもののうち、最も値が大きい s を次のクエリとする。
- なお、既に判明した文字列に関しては (h, b) が (5, 0) で固定になるという仕様があるので、この点に気をつけて注意深く実装すること。
"""
import argparse
import itertools
import random
import sys
from typing import Callable, List, Sequence, Tuple
import numpy as np
from scipy.optimize import linprog
from scipy.sparse import csr_matrix
SEED = 12345
RNG = random.Random(SEED)
QUERY_LEN = 5
NUM_SECRETS = 30
def generate_all_strings() -> List[str]:
digits = "0123456789"
return ["".join(p) for p in itertools.permutations(digits, QUERY_LEN)]
def all_hb_pairs() -> List[Tuple[int, int]]:
pairs: List[Tuple[int, int]] = []
for h in range(QUERY_LEN + 1):
for b in range(QUERY_LEN - h + 1):
pairs.append((h, b))
return pairs
def hb_pair(s: str, q: str, q_set: set[str]) -> Tuple[int, int]:
hit = sum(1 for a, b in zip(s, q) if a == b)
blow = len(set(s) & q_set) - hit
return hit, blow
class QueryRecord:
def __init__(self, q: str, counts: List[int]) -> None:
self.q = q
self.q_set = set(q)
self.counts = counts
def pick_random_unasked(candidates: Sequence[str], asked: set[str]) -> str | None:
if len(asked) >= len(candidates):
return None
while True:
q = RNG.choice(candidates)
if q not in asked:
return q
def build_lp(
history: Sequence[QueryRecord],
candidates: Sequence[str],
candidate_sets: Sequence[set[str]],
found_set: set[str],
found_at: dict[str, int],
confirmed_not_secret: set[str],
pair_index: dict[Tuple[int, int], int],
pairs: Sequence[Tuple[int, int]],
) -> Tuple[csr_matrix, np.ndarray, List[int]] | None:
def is_feasible(i: int) -> bool:
s = candidates[i]
if s in found_set or s in confirmed_not_secret:
return False
for record in history:
hit = sum(1 for a, b in zip(s, record.q) if a == b)
blow = len(candidate_sets[i] & record.q_set) - hit
if record.counts[pair_index[(hit, blow)]] == 0:
return False
return True
unknown_indices = [i for i in range(len(candidates)) if is_feasible(i)]
if not unknown_indices:
return None
pair_count = len(pairs)
row_count = len(history) * pair_count + 1
data: List[int] = []
rows: List[int] = []
cols: List[int] = []
for qi, record in enumerate(history):
q = record.q
q_set = record.q_set
for col_idx, cand_idx in enumerate(unknown_indices):
s = candidates[cand_idx]
hit = sum(1 for a, b in zip(s, q) if a == b)
blow = len(candidate_sets[cand_idx] & q_set) - hit
hb_idx = pair_index[(hit, blow)]
rows.append(qi * pair_count + hb_idx)
cols.append(col_idx)
data.append(1)
sum_row = row_count - 1
for col_idx in range(len(unknown_indices)):
rows.append(sum_row)
cols.append(col_idx)
data.append(1)
a_eq = csr_matrix((data, (rows, cols)), shape=(row_count, len(unknown_indices)))
b_eq_list: List[int] = []
for qi, record in enumerate(history):
fixed_counts = [0] * pair_count
for s in found_set:
found_time = found_at[s]
if found_time <= qi:
pair = (5, 0)
else:
pair = hb_pair(s, record.q, record.q_set)
fixed_counts[pair_index[pair]] += 1
for pi in range(pair_count):
value = record.counts[pi] - fixed_counts[pi]
if value < 0:
return None
b_eq_list.append(value)
b_eq_list.append(NUM_SECRETS - len(found_set))
b_eq = np.array(b_eq_list, dtype=float)
return a_eq, b_eq, unknown_indices
def solve_strategy2(ask: Callable[[str], Sequence[Tuple[int, int]]]) -> None:
candidates = generate_all_strings()
candidate_sets = [set(s) for s in candidates]
pairs = all_hb_pairs()
pair_index = {pair: i for i, pair in enumerate(pairs)}
asked: set[str] = set()
found_set: set[str] = set()
found_at: dict[str, int] = {}
confirmed_not_secret: set[str] = set()
history: List[QueryRecord] = []
query_count = 0
def process_response(q: str, response: Sequence[Tuple[int, int]]) -> bool:
if not response:
return False
if response[0] == (-1, -1):
return False
counts = [0] * len(pairs)
for h, b in response:
counts[pair_index[(h, b)]] += 1
found_before = len(found_set)
if counts[pair_index[(5, 0)]] > found_before:
found_set.add(q)
found_at[q] = len(history)
else:
confirmed_not_secret.add(q)
history.append(QueryRecord(q, counts))
asked.add(q)
if response[0] == (5, 0):
return False
return True
for _ in range(25):
q = pick_random_unasked(candidates, asked)
if q is None:
return
query_count += 1
print(f"[query {query_count}] strategy2 random-initial q={q}", file=sys.stderr, flush=True)
if not process_response(q, ask(q)):
return
while True:
if len(found_set) >= NUM_SECRETS:
return
lp = build_lp(
history,
candidates,
candidate_sets,
found_set,
found_at,
confirmed_not_secret,
pair_index,
pairs,
)
if lp is None:
q = pick_random_unasked(candidates, asked)
if q is None:
return
query_count += 1
print(f"[query {query_count}] strategy2 random-no-lp q={q}", file=sys.stderr, flush=True)
if not process_response(q, ask(q)):
return
continue
a_eq, b_eq, unknown_indices = lp
bounds = [(0.0, 1.0)] * len(unknown_indices)
result = linprog(c=np.zeros(len(unknown_indices)), A_eq=a_eq, b_eq=b_eq, bounds=bounds, method="highs")
if not result.success or result.x is None:
q = pick_random_unasked(candidates, asked)
if q is None:
return
query_count += 1
print(f"[query {query_count}] strategy2 random-lp-fail q={q}", file=sys.stderr, flush=True)
if not process_response(q, ask(q)):
return
continue
x = result.x
near_one_cols: List[int] = []
binary_solution = True
for col_idx, value in enumerate(x):
if value >= 0.9999:
near_one_cols.append(col_idx)
elif value < 0.0001:
continue
else:
binary_solution = False
break
if binary_solution and near_one_cols:
a_ub = np.zeros((1, len(unknown_indices)))
for col_idx in near_one_cols:
a_ub[0, col_idx] = 1.0
b_ub = np.array([len(near_one_cols) - 1], dtype=float)
test = linprog(
c=np.zeros(len(unknown_indices)),
A_eq=a_eq,
b_eq=b_eq,
A_ub=a_ub,
b_ub=b_ub,
bounds=bounds,
method="highs",
)
if not test.success:
for col_idx in near_one_cols:
s = candidates[unknown_indices[col_idx]]
if s in asked:
continue
query_count += 1
print(f"[query {query_count}] strategy2 deduced-final q={s}", file=sys.stderr, flush=True)
if not process_response(s, ask(s)):
return
return
scored: List[Tuple[float, str]] = []
for col_idx, cand_idx in enumerate(unknown_indices):
if x[col_idx] < 1e-5:
continue
s = candidates[cand_idx]
if s in asked:
continue
scored.append((x[col_idx], s))
if scored:
q = max(scored)[1]
query_count += 1
print(f"[query {query_count}] strategy2 lp-top q={q}", file=sys.stderr, flush=True)
if not process_response(q, ask(q)):
return
continue
q = pick_random_unasked(candidates, asked)
if q is None:
return
query_count += 1
print(f"[query {query_count}] strategy2 random-fallback q={q}", file=sys.stderr, flush=True)
if not process_response(q, ask(q)):
return
class LocalJudge:
def __init__(self, secrets: Sequence[str]) -> None:
self.secrets = list(secrets)
self.found = set()
self.query_count = 0
def ask(self, q: str) -> List[Tuple[int, int]]:
self.query_count += 1
q_set = set(q)
response: List[Tuple[int, int]] = []
for s in self.secrets:
if s in self.found or s == q:
response.append((5, 0))
self.found.add(s)
continue
hit = sum(1 for a, b in zip(s, q) if a == b)
blow = len(set(s) & q_set) - hit
response.append((hit, blow))
response.sort()
return response
def is_solved(self) -> bool:
return len(self.found) == len(self.secrets)
def verify_solution(self) -> Tuple[bool, List[str], List[str]]:
secret_set = set(self.secrets)
missing = sorted(secret_set - self.found)
extra = sorted(self.found - secret_set)
return not missing and not extra, missing, extra
def interactive_ask(q: str) -> List[Tuple[int, int]]:
print(q)
sys.stdout.flush()
pairs: List[Tuple[int, int]] = []
for _ in range(NUM_SECRETS):
line = sys.stdin.readline()
if not line:
return []
h_str, b_str = line.split()
pairs.append((int(h_str), int(b_str)))
return pairs
def run_local() -> None:
candidates = generate_all_strings()
RNG.shuffle(candidates)
secrets = candidates[:NUM_SECRETS]
judge = LocalJudge(secrets)
solve_strategy2(judge.ask)
solved = judge.is_solved()
verified, missing, extra = judge.verify_solution()
if not solved:
print("warning: not all secrets were found", file=sys.stderr, flush=True)
if not verified:
if missing:
print(f"missing={missing}", file=sys.stderr, flush=True)
if extra:
print(f"extra={extra}", file=sys.stderr, flush=True)
score = 100000 - judge.query_count
print(f"queries={judge.query_count} score={score} solved={solved} verified={verified}", file=sys.stderr, flush=True)
def main() -> None:
parser = argparse.ArgumentParser()
parser.add_argument("--local", action="store_true",default=False)
args = parser.parse_args()
if args.local:
run_local()
else:
solve_strategy2(interactive_ask)
if __name__ == "__main__":
main()