結果

問題 No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
コンテスト
ユーザー LNG
提出日時 2025-12-25 15:21:56
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,906 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 344 ms
コンパイル使用メモリ 82,188 KB
実行使用メモリ 118,716 KB
スコア 9,892,415
平均クエリ数 75.85
最終ジャッジ日時 2025-12-25 15:29:27
合計ジャッジ時間 450,561 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 99 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
import math
import random
import itertools

def get_hb_code(q_d, q_mask, t_d, t_mask):
    h = 0
    if q_d[0] == t_d[0]: h += 1
    if q_d[1] == t_d[1]: h += 1
    if q_d[2] == t_d[2]: h += 1
    if q_d[3] == t_d[3]: h += 1
    if q_d[4] == t_d[4]: h += 1
    
    common = (q_mask & t_mask).bit_count()
    return h * 6 + (common - h)

def main():
    random.seed(42)
    
    all_patterns = []
    for p in itertools.permutations(range(10), 5):
        mask = 0
        for x in p:
            mask |= (1 << x)
        all_patterns.append({
            'd': p,
            'mask': mask,
            'id': len(all_patterns)
        })

    candidates = list(range(len(all_patterns)))
    is_solved = [False] * len(all_patterns)
    solved_count = 0

    nlogn_table = [0.0] * 30241
    for i in range(2, 30241):
        nlogn_table[i] = i * math.log2(i)

    while solved_count < 30:
        best_guess_idx = -1

        if len(candidates) <= (30 - solved_count) and len(candidates) > 0:
            best_guess_idx = candidates[0]
        elif solved_count == 0 and len(candidates) == 30240:
            for i, p in enumerate(all_patterns):
                if p['d'] == (0, 1, 2, 3, 4):
                    best_guess_idx = i
                    break
        else:
            max_entropy = -1.0
            turn_limit = 500 if len(candidates) > 1000 else 1500
            sample_size = min(len(candidates), 800)
            
            if len(candidates) <= sample_size:
                samples = candidates
            else:
                samples = random.sample(candidates, sample_size)

            for _ in range(turn_limit):
                if random.random() < 0.8:
                    q_idx = random.choice(candidates)
                else:
                    q_idx = random.randrange(len(all_patterns))
                
                if is_solved[q_idx]:
                    continue

                counts = [0] * 36
                q_p = all_patterns[q_idx]
                q_d = q_p['d']
                q_m = q_p['mask']
                
                for s_idx in samples:
                    s_p = all_patterns[s_idx]
                    code = get_hb_code(q_d, q_m, s_p['d'], s_p['mask'])
                    counts[code] += 1

                current_entropy = 0
                for count in counts:
                    if count > 0:
                        current_entropy -= nlogn_table[count]

                if current_entropy > max_entropy:
                    max_entropy = current_entropy
                    best_guess_idx = q_idx

        if best_guess_idx == -1:
            best_guess_idx = candidates[0]

        print("".join(map(str, all_patterns[best_guess_idx]['d'])), flush=True)

        current_res_freq = [0] * 36
        for _ in range(30):
            try:
                line = sys.stdin.readline().split()
                if not line: break
                h = int(line[0])
                if h == -1: return
                b = int(line[1])
                current_res_freq[h * 6 + b] += 1
            except EOFError:
                return

        new_total_hits = current_res_freq[30]
        if not is_solved[best_guess_idx] and new_total_hits > solved_count:
            is_solved[best_guess_idx] = True
        
        solved_count = new_total_hits
        if solved_count == 30:
            break

        next_candidates = []
        best_p = all_patterns[best_guess_idx]
        b_d = best_p['d']
        b_m = best_p['mask']
        
        for c_idx in candidates:
            if is_solved[c_idx]:
                continue
            
            c_p = all_patterns[c_idx]
            code = get_hb_code(b_d, b_m, c_p['d'], c_p['mask'])
            if code < 30 and current_res_freq[code] > 0:
                next_candidates.append(c_idx)
        
        candidates = next_candidates

if __name__ == "__main__":
    main()
0