Hatena::Grouptopcoder

gnarl,TopCoder

 | 

2010-04-22

Topcoder SRM の注意事項

05:23

250開いたところで寝オチしたらスコアが100くらい下がった(1025→903)ので問題解くか寝るかどっちかにしましょう

Topcoder Member SRM 468 Div2

05:52

メンバーSRMってなんなんですかね


250 RoadOrFlightEasy

都市0からNまで順に移動したい、都市間の移動は陸路か空路を選べるが空路は合計K回までしか利用できない。それぞれの経路の所要時間が与えられるので最短時間を求めよ。

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Set;
 
public class RoadOrFlightEasy {
 
  static class Pair {
    public Pair(int a, int b) {
      this.a = a;
      this.b = b;
    }
 
    public final int a;
    public final int b;
  }
 
  public int minTime(int N, int[] roadTime, int[] flightTime, int K) {
    Pair[] benefits = new Pair[N];
    for (int i = 0; i < benefits.length; i++) {
      benefits[i] = new Pair(i, roadTime[i] - flightTime[i]);
    }
    Arrays.sort(benefits, new Comparator<Pair>() {
      public int compare(Pair o1, Pair o2) {
        return -Double.compare(o1.b, o2.b);
      }
    });
    Set<Integer> flights = new HashSet<Integer>();
    for (int i = 0; i < K; i++)
      if (benefits[i].b > 0)
        flights.add(benefits[i].a);
    int time = 0;
    for (int i = 0; i < N; i++) {
      if (flights.contains(i)) {
        time += flightTime[i];
      } else {
        time += roadTime[i];
      }
    }
    return time;
  }

}

空路を選ぶとどの程度得か計算しといて上位K個の経路は空路を使う。

必要なのは距離のみなので道の位置まで覚えとく必要はなかったですね。

passed system test

500 T9

1-9の数字に対応するアルファベットの組、可能な単語の辞書、押されたキーのパターンが与えられる。入力された文書をデコードせよ。

import java.util.Arrays;
import java.util.regex.Pattern;
 
public class T9 {
 
  public String message(String[] part, String[] dict, String[] keystr) {
    Arrays.sort(dict);
    final String[] subpats = new String[part.length];
    for (int i = 0; i < subpats.length; i++) {
      subpats[i] = "[" + part[i] + "]";
    }
    final StringBuilder result = new StringBuilder();
    StringBuilder cur = new StringBuilder();
    String keys = "";
    for (String k : keystr)
      keys += k;
 
    for (int i = 0; i < keys.length(); i++) {
      if (keys.charAt(i) == '0') {
        result.append(dictAt(dict, cur.toString(), 0));
        cur = new StringBuilder();
        result.append(' ');
      } else if (keys.charAt(i) == '#' || keys.charAt(i) == '*') {
        int n = 0;
        while (i < keys.length()
            && (keys.charAt(i) == '#' || keys.charAt(i) == '*')) {
          if (keys.charAt(i) == '#')
            n++;
          else
            n += 5;
          i++;
        }
        i--; // :(
        result.append(dictAt(dict, cur.toString(), n));
        cur = new StringBuilder();
      } else {
        cur.append(subpats[keys.charAt(i) - '1']);
      }
    }
    if (cur.length() > 0)
      result.append(dictAt(dict, cur.toString(), 0));
 
    return result.toString();
  }
 
  private String dictAt(String[] dict, String pat, int n) {
    if (pat.length() == 0)
      return "";
    final Pattern regex = Pattern.compile(pat);
    for (int i = 0; i < dict.length; i++) {
      if (regex.matcher(dict[i]).matches()) {
        if (n == 0)
          return dict[i];
        n--;
      }
    }
    throw new AssertionError();
  }
 
}

数字の列から正規表現を構築して辞書を線形サーチ。

passed system test.

250,500はコンスタントに解けるようになってきたけど時間がなくて1000は開けずというパターン。精進が必要。

 |