Hatena::Grouptopcoder

tsubosakaの日記

2010-01-04

SRM 457

23:53

250

"?6:?? GMT??"みたいな"16:00 GMT-7"の一部が伏せられた文字列が与えられる。

このときあり得る時刻の中でGMT+0で最も辞書順に小さいものを答えよという問題。

?の数は高々6つしかなく、先頭は0,1,2の3通り、+/-の部分は2通りしかとらないので全部列挙しても6 * 10^4通りのパターンしかありえない。

はまりどころとして問題文にさらっと書いてあるGMT-0はありえないという記述。これに気づかなかったため落ちていた回答がかなり多かった。自分も最初それを見逃していて再提出した。

public class TheTriangleBothDivs {
  String res; 
  String trance(char carr[]){
    int hour = (carr[0] - '0') * 10 + (carr[1] - '0');
    int min  = (carr[3] - '0') * 10 + (carr[4] - '0');
    if(hour < 0 || hour >= 24)return null;
    if(min  < 0 || min  >= 60)return null;
    int   p  = (carr[10] - '0');
    if(carr[9] == '+'){
      hour = (hour + 24 - p) % 24;
    }else{
      if(p == 0)return null;
      hour = (hour +  p) % 24;      
    }
    String r = String.format("%02d:%02d", hour , min);
    return r;
  }
  void rec(int pos , char carr[]){
    if(pos == carr.length){
      String r = trance(carr);
      if(r == null)return;
      if(res == null || res.compareTo(r) > 0){
        res = r;
      }
      return ;
    }
    if(carr[pos] == '?'){
      if(pos == 0){
        carr[pos] = '0';
        rec(pos + 1 , carr);
        carr[pos] = '1';
        rec(pos + 1 , carr);
        carr[pos] = '2';
        rec(pos + 1 , carr);
        carr[pos] = '?';
      }else if(pos == 9){
        carr[pos] = '+';        
        rec(pos + 1 , carr);
        carr[pos] = '-';
        rec(pos + 1 , carr);
        carr[pos] = '?';
      }else{
        for(char c = '0' ; c <= '9' ; ++c){
          carr[pos] = c;        
          rec(pos + 1 , carr);
          carr[pos] = '?';
        }
      }
    }else{
      rec(pos + 1 , carr);
    }
  }
  public String fix(String time) {
    res = null;
    char carr[] = time.toCharArray();
    rec(0, carr);
    return res;
  }
}

500

一般性を失うことなく中心を固定してもよく、場合の数に2*nを掛ければよい。

中心を固定すると円上の6点に数字をどう配置すればよいかという問題に落ちる。あとはDPで解くことができる。回転は同一とみなすので最後に6で割る必要がある。

別解としてさらに円の隣り合う2点は固定して、場合の数に(2 * (n-1) * 2 *(n-2))を掛ける。残りの4点に関しては3点に関しては取り得る数字を列挙するこれは高々300^3=2700万にしかならない。最後の一点は他のすべての点が決定していれば何通り選べるかはただちに求まる。

public class TheHexagonsDivOne {
  boolean adj(int a , int b , int n){
    return a % n != b % n;
  }
  public long count(int n) {
    if (n <= 3)
      return 0;
    long res = 0;
    boolean used[] = new boolean[2 * n + 1];
    // fix center = n
    used[n] = used[2 * n] = true;
    // fix head = 1 , tail = 2
    int head = 1;
    int tail = 2;
    used[head] = used[tail] = true;
    for(int t1 = 3 ; t1 < 2 * n ; ++t1){
      if(used[t1] || !adj(head , t1 , n))continue;      
      used[t1] = true;
      for(int t2 = 3 ; t2 < 2 * n ; ++t2){
        if(used[t2] || !adj(t1 , t2 , n))continue;      
        used[t2] = true;
        for(int t3 = 3 ; t3 < 2 * n ; ++t3){
          if(used[t3] || !adj(t2 , t3 , n))continue;      
          used[t3] = true;
          int rest = 2 * n - 7;
          if(!used[n + 2])rest--;
          if(!used[(t3 + n) % (2 * n)])rest--;          
          res += rest;
          used[t3] = false;
        }
        used[t2] = false;
      }
      used[t1] = false;
    }
    return res * 8l * (n * (n- 1) * (n - 2))/ 6;
  }
}