Codeforces #816 (Div. 2) D. 2+ doors 解法にたどりつくまでは早かったのにTLEが取れなくて3時間溶かした…。
数列$ aの長さ$ nと、$ a_iと$ a_jのORが$ q個与えられるので、それを満たす$ \{a_n\}の辞書順で最小のものを出力せよという問題。
簡単のために$ 1ビットの数で考えてみると、ORの値が$ 0のところは両者が$ 0で確定。$ 1のところはどちらか片方が$ 1であればよいので、両方が未定なら若い要素を$ 0に老いた方を$ 1に固定してしまえばよいことがわかる。ただし、すでに片方が$ 0の場合はもう片方は$ 1に確定する。
これをもうすこしよく考えると、つぎのアルゴリズムでいける：
まずすべてを$ 1で初期化する
つぎにORが$ 0のペアをすべて探し、両端を$ 0にする
つぎに要素を若い方から見ていき、つぎの条件を満たすときに$ 0にする
$ 0でなく、かつ
自分自身とORが$ 1で繋がっていなく、かつ
ORが$ 1で繋がっている先が$ 1
時間オーダーは$ O(n + q)で、ビット数はたかだか$ 30なので、各ピットでこれをやっても大丈夫そう。
で、書いたのがこれ。
code:java
int n = scanner.nextInt();
int q = scanner.nextInt();
List<Edge>[][] edges = new List30n; ビットごとに結果と辺を保持しておこうとした。$ nが$ 10^5のオーダーで、ArrayListがだいたい$ 100バイトなので、edgesだけで$ 10^8バイト、すなわち$ 300メガバイトくらいになる。とうぜんMLEになるかと思いきやTLEになったので、無駄に悩んでしまった。
書き直したのがこちら。毎回bitの位置に1が立っているかどうかで辺の種類を確認しているが、しかたない。
code:java
public static void main(String[] args) {
FastScanner scanner = new FastScanner();
int n = scanner.nextInt();
int q = scanner.nextInt();
List<Edge>[] edges = new Listn; for (int i = 0; i < n; i++) edgesi = new ArrayList<>(); for (int k = 0; k < q; k++) {
int i = scanner.nextInt() - 1;
int j = scanner.nextInt() - 1;
int x = scanner.nextInt();
edgesi.add(new Edge(j, x)); edgesj.add(new Edge(i, x)); }
for (int i = 0; i < 30; i++) compute(i, a, edges, n);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) sb.append(ai).append(" "); System.out.println(sb);
}
private static void compute(int bit, int[] a, List<Edge>[] edges, int n) {
boolean[] abits = new booleann; Arrays.fill(abits, true);
for (int i = 0; i < n; i++)
if ((edge.value & 1 << bit) == 0) {
break;
}
loop:
for (int i = 0; i < n; i++) {
for (Edge edge : edgesi) { if ((edge.value & 1 << bit) != 0) {
if (edge.to == i || !abitsedge.to) continue loop; }
}
}
for (int i = 0; i < n; i++) {
if (abitsi) ai ^= 1 << bit; }
}
private static class Edge {
private final int to;
private final int value;
private Edge(int to, int value) {
this.to = to;
this.value = value;
}
}