CavePassage解けた

昨日の続き。

これまでの実装だと、もう最短経路ではないと分かっている要素もキューに追加されていってたので、それを抑制したらかなりの時間短縮になりました。システムテストの一番遅いやつで500ms弱。よしよし。

しかしこの量のアルゴリズムを制限時間内に考えて実装するのはなかなかできなかろう。きっと上位の人たちは、ダイクストラ法だということが浮かんだら、あとは定跡に従ってもっとすっきりしたコードをさくさくっと書いてしまうのでしょう。上手い人のコードを読まにゃ。

最終形を貼っときます。うーん汚いコードだなあ。少しコメント付けました。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class CavePassage {

  int[] w;
  int[] t;
  String[] table;
  int st;
  int[] group;

  public int minimalTime(int[] weights, int[] times, String[] table,
      int strength) {
    int N = weights.length;
    this.w = weights;
    this.t = times;
    this.table = table;
    this.st = strength;
    this.group = new int[1 << N];
    // 可能な全ての組み合わせを求め、移動時間をgroupに保持しておく
    for (int i = 0; i < 1 << N; i++) {
      ArrayList<Integer> list = new ArrayList<Integer>();
      for (int j = 1, c = 0; c < N; j <<= 1, c++) {
        if ((i & j) > 0) {
          list.add(c);
        }
      }
      if (list.size() == 1) {
        if (w[list.get(0)] <= st) {
          group[i] = t[list.get(0)];
        }
      } else {
        if (!trust(list)) {
          continue;
        }
        int sum = 0;
        for (int n : list) {
          sum += w[n];
        }
        if (sum > st) {
          continue;
        }
        int max = 0;
        for (int n : list) {
          max = Math.max(max, t[n]);
        }
        group[i] = max;
      }
    }

    // 各人がどちら側にいるか・mapがどちらにあるかをN+1ビットの状態で管理
    // 最上位ビットがmap用。entrance側が0、exit側が1。

    int[] min = new int[1 << (N + 1)];
    Arrays.fill(min, Integer.MIN_VALUE);
    min[0] = 0;
    // queueに必要以上addしないよう、現時点での最短を覚えておく用
    int[] cand = new int[1 << (N + 1)];
    Arrays.fill(cand, Integer.MIN_VALUE);
    cand[0] = 0;
    PriorityQueue<Item> q = new PriorityQueue<Item>(100000);
    for (int i = 0; i < (1 << N); i++) {
      if (group[i] > 0) {
        cand[i | (1 << N)] = group[i];
        q.add(new Item(i | (1 << N), group[i]));
      }
    }
    while (min[(1 << N + 1) - 1] < 0) {
      Item item = q.poll();
      if (item == null) {
        return -1;
      }
      if (min[item.end] >= 0) {
        continue;
      }
      min[item.end] = item.time;
      if ((item.end & 1 << N) > 0) {
        // 出口→入口の移動を検索
        int oldState = item.end & ((1 << N) - 1);
        for (int i = 0; i < oldState; i++) {
          if ((i | oldState) != oldState) {
            continue;
          }
          int move = i ^ oldState; // これで移動した人だけの集合が取れる
          if (group[move] > 0
              && min[i] < 0
              && (cand[i] < 0 || cand[i] > min[item.end]
                  + group[move])) {
            cand[i] = min[item.end] + group[move];
            q.add(new Item(i, min[item.end] + group[move]));
          }
        }
      } else {
        // 入口→出口の移動を検索
        for (int i = item.end + 1; i < 1 << w.length; i++) {
          if ((item.end | i) != i) {
            continue;
          }
          int move = i ^ item.end;
          int newEnd = i | (1 << N);
          if (group[move] > 0
              && min[newEnd] < 0
              && (cand[newEnd] < 0 || cand[newEnd] >= min[item.end]
                  + group[move])) {
            cand[newEnd] = min[item.end] + group[move];
            q.add(new Item(newEnd, min[item.end] + group[move]));
          }
        }
      }
    }
    return min[(1 << N + 1) - 1];
  }

  boolean trust(ArrayList<Integer> list) {
    for (int i : list) {
      boolean found = false;
      for (int j : list) {
        if (i == j) {
          continue;
        }
        if (table[i].charAt(j) == 'Y') {
          found = true;
          break;
        }
      }
      if (!found) {
        return false;
      }
    }
    return true;
  }

  class Item implements Comparable<Item> {

    // 初めは移動前の状態も保持していたが、意味なかったのでやめた
    // 実行時間にはほとんど影響ないけど
    int end;
    int time;

    Item(int e, int t) {
      this.end = e;
      this.time = t;
    }

    public int compareTo(Item o) {
      return this.time - o.time;
    }

    public String toString() {
      return "[" + end + "," + time + "]";
    }
  }

}