SRM 422 Level2 CavePassage

前回のSRMの500点問題、手が出なかったので復習。1時間強をかけてダイクストラ法で書いてみました。こんなに時間がかかってしまうと本番ではとても無理だな…。どうやったらこんなのが20、30分で書けるようになるのだろう。

それはさておき、僕が書いたコードはアルゴリズム的には正しい答えを返すみたいですが、システムテストにかけると2秒の時間制限をオーバーするケースが一つあります（57番）。
手元の環境では2.4秒程度で実行されて、TopCoderのサーバーではそれより1割速いくらいなので、あと1割ほどコードを高速化しないといけない。

どこが縮められるだろう。うーん。やっぱりPriorityQueueにaddするのが遅いのかな。
とりあえず貼っとく。

→解けたー！

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];
    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() == 0) {
        continue;
      } else 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;
      }
    }

    int[] min = new int[1 << (N + 1)];
    Arrays.fill(min, Integer.MIN_VALUE);
    min[0] = 0;
    PriorityQueue<Item> q = new PriorityQueue<Item>(100000);
    for (int i = 0; i < (1 << N); i++) {
      if (group[i] > 0) {
        q.add(new Item(0, 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 st = item.end & ((1 << N) - 1);
        for (int i = 0; i < st; i++) {
          if ((i | st) != st) {
            continue;
          }
          int move = i ^ st;
          if (group[move] > 0 && min[i] < 0) {
            q
                .add(new Item(item.end, 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) {
            q.add(new Item(item.end, newEnd, min[item.end]
                + group[move]));
          }
        }
      }
    }
    return min[(1 << N + 1) - 1];
  }

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

  class Item implements Comparable<Item> {

    int start;
    int end;
    int time;

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

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

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

}