結果
| 問題 | No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！ |
| コンテスト | |
| ユーザー |
 kencho
|
| 提出日時 | 2025-12-25 03:23:35 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 2,021 ms / 5,000 ms |
| コード長 | 19,841 bytes |
| 記録 | |
| コンパイル時間 | 3,372 ms |
| コンパイル使用メモリ | 89,372 KB |
| 実行使用メモリ | 83,792 KB |
| スコア | 9,995,574 |
| 平均クエリ数 | 44.26 |
| 最終ジャッジ日時 | 2025-12-25 03:26:18 |
| 合計ジャッジ時間 | 160,031 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
// Main.java
import java.io.*;
import java.util.*;
/**
* Parallel Hit & Blow (interactive) solver.
*
* Public API:
* - interface Oracle
* - static class Solver
*
* Local tests can implement Oracle and call:
* Solver solver = new Solver(seed);
* solver.selector.setParams(...); // optional
* int queries = solver.run(oracle);
*
* For yukicoder submission, main() uses StdIOOracle (interactive).
*/
public class Main {
// ---------- Fast Scanner (interactive) ----------
private static final class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
FastScanner(InputStream in) {
this.in = in;
}
private int readByte() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0)
return -1;
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c;
do {
c = readByte();
if (c == -1)
return Integer.MIN_VALUE;
} while (c <= ' ');
int sign = 1;
if (c == '-') {
sign = -1;
c = readByte();
}
int val = 0;
while (c > ' ') {
val = val * 10 + (c - '0');
c = readByte();
}
return val * sign;
}
}
// ---------- Code space (10P5) ----------
public static final class CodeSpace {
public static final int N = 30240;
public static final int RESP_BINS = 36; // id = 6*H + B
public final int[] pack = new int[N]; // 5 nibbles packed in 20 bits
public final short[] mask = new short[N]; // 10-bit digit set mask
public final byte[] d0 = new byte[N];
public final byte[] d1 = new byte[N];
public final byte[] d2 = new byte[N];
public final byte[] d3 = new byte[N];
public final byte[] d4 = new byte[N];
// map packed(20-bit) -> codeId (or -1 if not in space)
public final int[] packToId = new int[1 << 20];
public CodeSpace() {
Arrays.fill(packToId, -1);
int idx = 0;
for (int a = 0; a < 10; a++) {
for (int b = 0; b < 10; b++)
if (b != a) {
for (int c = 0; c < 10; c++)
if (c != a && c != b) {
for (int d = 0; d < 10; d++)
if (d != a && d != b && d != c) {
for (int e = 0; e < 10; e++)
if (e != a && e != b && e != c && e != d) {
int p = (a) | (b << 4) | (c << 8) | (d << 12) | (e << 16);
int m = (1 << a) | (1 << b) | (1 << c) | (1 << d) | (1 << e);
pack[idx] = p;
mask[idx] = (short) m;
d0[idx] = (byte) a;
d1[idx] = (byte) b;
d2[idx] = (byte) c;
d3[idx] = (byte) d;
d4[idx] = (byte) e;
packToId[p] = idx;
idx++;
}
}
}
}
}
if (idx != N)
throw new AssertionError("code space size mismatch: " + idx);
}
public int respId(int sId, int qId) {
int hit = 0;
if (d0[sId] == d0[qId])
hit++;
if (d1[sId] == d1[qId])
hit++;
if (d2[sId] == d2[qId])
hit++;
if (d3[sId] == d3[qId])
hit++;
if (d4[sId] == d4[qId])
hit++;
int common = Integer.bitCount((mask[sId] & mask[qId]) & 0x3FF);
int blow = common - hit;
return hit * 6 + blow;
}
public String toStringCode(int id) {
char[] cs = new char[5];
cs[0] = (char) ('0' + d0[id]);
cs[1] = (char) ('0' + d1[id]);
cs[2] = (char) ('0' + d2[id]);
cs[3] = (char) ('0' + d3[id]);
cs[4] = (char) ('0' + d4[id]);
return new String(cs);
}
}
// ---------- Response (judge -> solver) ----------
public static final class Response {
public final int solvedCount; // # of (5,0) among 30 lines
public final boolean invalid; // (-1,-1) signal or EOF
public final int remaining; // R = 30 - solvedCount
public final int[] c = new int[CodeSpace.RESP_BINS]; // counts for remaining only (exclude (5,0))
public Response(int solvedCount, boolean invalid) {
this.solvedCount = solvedCount;
this.invalid = invalid;
this.remaining = 30 - solvedCount;
}
}
// ---------- Oracle API ----------
public interface Oracle {
Response ask(int qId) throws Exception;
}
// ---------- StdIO Oracle (interactive) ----------
public static final class StdIOOracle implements Oracle {
private final FastScanner fs;
private final PrintWriter out;
private final CodeSpace space;
public StdIOOracle(InputStream in, OutputStream out, CodeSpace space) {
this.fs = new FastScanner(in);
this.out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(out)));
this.space = space;
}
@Override
public Response ask(int qId) throws Exception {
out.println(space.toStringCode(qId));
out.flush();
int solved = 0;
boolean invalid = false;
int[] cnt = new int[CodeSpace.RESP_BINS];
// read 30 lines (Hi, Bi). Always consume all lines.
for (int i = 0; i < 30; i++) {
int h = fs.nextInt();
int b = fs.nextInt();
if (h == Integer.MIN_VALUE || b == Integer.MIN_VALUE) {
invalid = true;
h = -1;
b = -1;
}
if (h == -1 && b == -1)
invalid = true;
if (h == 5 && b == 0) {
solved++;
} else if (!invalid) {
int id = h * 6 + b;
if (0 <= id && id < CodeSpace.RESP_BINS)
cnt[id]++;
}
}
Response r = new Response(solved, invalid);
System.arraycopy(cnt, 0, r.c, 0, cnt.length);
return r;
}
}
// ---------- Weight model ----------
private static final class WeightModel {
final int n;
final double[] w;
int R; // remaining secrets count
WeightModel(int n, int initialR) {
this.n = n;
this.R = initialR;
this.w = new double[n];
reset(initialR);
}
void reset(int initialR) {
this.R = initialR;
double init = (double) initialR / n;
Arrays.fill(w, init);
}
void exclude(int id) {
w[id] = 0.0;
}
int argMaxNotZero(boolean[] asked) {
int best = -1;
double bestW = -1;
for (int i = 0; i < n; i++) {
if (asked[i])
continue;
double wi = w[i];
if (wi > bestW) {
bestW = wi;
best = i;
}
}
return best;
}
double maxNotZero(boolean[] asked) {
double bestW = 0;
for (int i = 0; i < n; i++) {
if (asked[i])
continue;
bestW = Math.max(bestW, w[i]);
}
return bestW;
}
void normalizeToR() {
double sum = 0.0;
for (int i = 0; i < n; i++)
sum += w[i];
if (sum <= 0)
return;
double mul = (double) R / sum;
for (int i = 0; i < n; i++)
w[i] *= mul;
}
void updateByRegionScaling(CodeSpace space, int qId, int[] c, int newR, double eta) {
this.R = newR;
double[] W = new double[CodeSpace.RESP_BINS];
for (int s = 0; s < n; s++) {
double ws = w[s];
if (ws == 0.0)
continue;
int rid = space.respId(s, qId);
W[rid] += ws;
}
final double eps = 1e-12;
double[] factor = new double[CodeSpace.RESP_BINS];
for (int r = 0; r < CodeSpace.RESP_BINS; r++) {
double num = c[r] + eps;
double den = W[r] + eps;
factor[r] = Math.pow(num / den, eta);
}
for (int s = 0; s < n; s++) {
double ws = w[s];
if (ws == 0.0)
continue;
int rid = space.respId(s, qId);
double nw = ws * factor[rid];
if (nw < 0)
nw = 0;
if (nw > 5.0)
nw = 5.0;
w[s] = nw;
}
normalizeToR();
}
}
// ---------- Weighted sampler ----------
private static final class Sampler {
final int n;
final double[] prefix;
Sampler(int n) {
this.n = n;
this.prefix = new double[n];
}
void build(double[] w) {
double sum = 0.0;
for (int i = 0; i < n; i++) {
sum += w[i];
prefix[i] = sum;
}
}
int sampleOne(SplittableRandom rng, double total) {
double x = rng.nextDouble() * total;
int lo = 0, hi = n - 1;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (prefix[mid] >= x)
hi = mid;
else
lo = mid + 1;
}
return lo;
}
int[] sampleMany(SplittableRandom rng, double[] w, int T) {
build(w);
int[] s = new int[T];
double total = prefix[n - 1];
if (total <= 0) {
for (int i = 0; i < T; i++)
s[i] = rng.nextInt(n);
return s;
}
for (int i = 0; i < T; i++)
s[i] = sampleOne(rng, total);
return s;
}
}
// ---------- Query selection (approx Max-Entropy via Gini on samples)
// ----------
public static final class QuerySelector {
final CodeSpace space;
final WeightModel model;
final SplittableRandom rng;
// tunables
int K = 500; // candidates per step
int T = 2048; // weighted samples per step
int TOP = 80; // always include top-weight codes
double eta = 0.7; // update learning rate
double pickThreshold = 0.60; // collection start threshold
// stamping to avoid clearing boolean[] each time
final int[] seenStamp = new int[CodeSpace.N];
int stamp = 1;
QuerySelector(CodeSpace space, WeightModel model, long seed) {
this.space = space;
this.model = model;
this.rng = new SplittableRandom(seed);
}
public void setParams(int K, int T, int TOP, double eta, double pickThreshold) {
if (K > 0)
this.K = K;
if (T > 0)
this.T = T;
if (TOP >= 0)
this.TOP = TOP;
if (eta > 0)
this.eta = eta;
if (pickThreshold >= 0)
this.pickThreshold = pickThreshold;
}
int select(boolean[] asked) {
double mx = model.maxNotZero(asked);
if (mx >= pickThreshold || (model.R <= 6 && mx >= 0.35)) {
int best = model.argMaxNotZero(asked);
if (best != -1)
return best;
}
Sampler sampler = new Sampler(CodeSpace.N);
int[] samples = sampler.sampleMany(rng, model.w, T);
int[] candidates = buildCandidates(asked);
int bestQ = candidates[0];
long bestScore = Long.MAX_VALUE; // minimize sumSq
int[] cnt = new int[CodeSpace.RESP_BINS];
for (int qId : candidates) {
Arrays.fill(cnt, 0);
for (int sId : samples) {
int rid = space.respId(sId, qId);
cnt[rid]++;
}
long sumSq = 0;
for (int r = 0; r < CodeSpace.RESP_BINS; r++) {
long v = cnt[r];
sumSq += v * v;
}
if (sumSq < bestScore) {
bestScore = sumSq;
bestQ = qId;
}
}
return bestQ;
}
private int[] buildCandidates(boolean[] asked) {
stamp++;
if (stamp == Integer.MAX_VALUE) {
Arrays.fill(seenStamp, 0);
stamp = 1;
}
int[] top = topKNotAsked(asked, TOP);
int[] cand = new int[K];
int sz = 0;
for (int id : top) {
if (id < 0)
continue;
if (asked[id])
continue;
if (seenStamp[id] == stamp)
continue;
seenStamp[id] = stamp;
cand[sz++] = id;
if (sz >= K)
break;
}
while (sz < K) {
int id = rng.nextInt(CodeSpace.N);
if (asked[id])
continue;
if (model.w[id] == 0.0)
continue;
if (seenStamp[id] == stamp)
continue;
seenStamp[id] = stamp;
cand[sz++] = id;
}
if (sz < K)
cand = Arrays.copyOf(cand, sz);
return cand;
}
private int[] topKNotAsked(boolean[] asked, int k) {
if (k <= 0)
return new int[0];
int[] ids = new int[k];
double[] val = new double[k];
Arrays.fill(ids, -1);
Arrays.fill(val, -1);
for (int i = 0; i < CodeSpace.N; i++) {
if (asked[i])
continue;
double wi = model.w[i];
if (wi <= val[k - 1])
continue;
int pos = k - 1;
while (pos > 0 && wi > val[pos - 1]) {
val[pos] = val[pos - 1];
ids[pos] = ids[pos - 1];
pos--;
}
val[pos] = wi;
ids[pos] = i;
}
return ids;
}
}
// ---------- History Item ----------
private static final class HistoryItem {
final int qId;
final int[] c; // copy of response counts
final int time;
HistoryItem(int qId, int[] c, int time) {
this.qId = qId;
this.c = Arrays.copyOf(c, c.length);
this.time = time;
}
}
// ---------- Solver (public API) ----------
public static final class Solver {
public final CodeSpace space = new CodeSpace();
private final WeightModel model = new WeightModel(CodeSpace.N, 30);
private final boolean[] asked = new boolean[CodeSpace.N];
public final QuerySelector selector;
private final List<HistoryItem> history = new ArrayList<>();
// secretFoundTime[sId] = time step when sId was found (or -1)
private final int[] secretFoundTime = new int[CodeSpace.N];
public int queries = 0;
public int solvedCount = 0;
public Solver(long seed) {
this.selector = new QuerySelector(space, model, seed);
Arrays.fill(secretFoundTime, -1);
}
/**
* Run until completion or oracle invalid. Returns number of queries performed.
*/
public int run(Oracle oracle) throws Exception {
while (true) {
int qId = selector.select(asked);
if (qId < 0)
return queries;
asked[qId] = true;
model.exclude(qId); // never ask again / never be a remaining secret
queries++;
Response resp = oracle.ask(qId);
if (resp == null || resp.invalid)
return queries;
if (resp.solvedCount > solvedCount) {
secretFoundTime[qId] = queries;
}
if (resp.solvedCount == 30)
return queries;
history.add(new HistoryItem(qId, resp.c, queries));
int newR = 30 - resp.solvedCount;
solvedCount = resp.solvedCount;
// Update model using counts for remaining secrets only (exclude (5,0))
// Iteratively apply history updates
// Reset model to uniform distribution for remaining count
model.reset(30);
// Re-apply exclusion for already asked queries
for (int i = 0; i < CodeSpace.N; i++) {
if (asked[i])
model.exclude(i);
}
// Temp buffer for adjusted counts
int[] cAdj = new int[CodeSpace.RESP_BINS];
for (HistoryItem item : history) {
System.arraycopy(item.c, 0, cAdj, 0, CodeSpace.RESP_BINS);
// Remove counts corresponding to found secrets
// But ONLY if the secret was found AFTER this history item
for (int sId = 0; sId < CodeSpace.N; sId++) {
if (secretFoundTime[sId] != -1 && secretFoundTime[sId] > item.time) {
// This sId was part of the 'remaining' secrets when item was recorded
int rid = space.respId(sId, item.qId);
if (cAdj[rid] > 0) {
cAdj[rid]--;
}
}
}
model.updateByRegionScaling(space, item.qId, cAdj, newR, selector.eta);
}
if (queries >= 30240)
return queries;
}
}
}
// ---------- Interactive entry point ----------
public static void main(String[] args) throws Exception {
long seed = 523;
Solver solver = new Solver(seed);
solver.selector.setParams(
500, // K candidates
2048, // T samples
80, // TOP
1.0, // eta
0.05 // pickThreshold
);
StdIOOracle oracle = new StdIOOracle(System.in, System.out, solver.space);
solver.run(oracle);
System.out.flush();
}
}