Hatena::Grouptopcoder

tsubosakaの日記

2010-09-03

SRM 480

22:27

参加できなかったけど250,450解いたので貼っておく

250

  boolean isDanger(Set<String> dangerWords , String keyword , int threshold){
    int cnt = 0;
    for(String s : keyword.split("\\s+"))
      if(dangerWords.contains(s))
        ++cnt;
    return cnt >= threshold;
  }
  void addDangerWord(Set<String> dangerWords , String keyword){
    for(String s : keyword.split("\\s+"))
      dangerWords.add(s);
  }  
  public String[] determineWebsite(String[] address, String[] keyword,
      String[] dangerous, int threshold) {
    int N = address.length;
    Set<String> dangerWords = new HashSet<String>();
    for(String d : dangerous)
      dangerWords.add(d);
    boolean isDanger[] = new boolean[N];
    boolean f = true;
    while(f){
      f = false;
      for(int i = 0 ; i < N ; ++i){
        if(isDanger[i])continue;
        if(isDanger(dangerWords , keyword[i] , threshold)){
          isDanger[i] = true;
          addDangerWord(dangerWords, keyword[i]);
          f = true;
        }
      }
    }
    List<String> ret = new ArrayList<String>();
    for(int i = 0 ; i < N ; ++i)
      if(isDanger[i])
        ret.add(address[i]);
    return ret.toArray(new String[0]);
  }

450

  public int secureNetwork(String[] clientCable, String[] serverCable) {
    int C = clientCable.length;
    boolean adj[][] = new boolean[C][C];
    // 推移的閉包を計算
    for(int i = 0 ; i < C ; ++i)
      for(int j = 0 ; j < C ; ++j)
        adj[i][j] = i == j || clientCable[i].charAt(j) == 'Y';
    for(int k = 0 ; k < C ; ++k)
      for(int i = 0 ; i < C ; ++i)
        for(int j = 0 ; j < C ; ++j)
          adj[i][j] = adj[i][j] | (adj[i][k] & adj[k][j]);
    int needDataGate = 0;
    int S = serverCable[0].length();
    for(int i = 0 ; i < S ; ++i){
      List<Integer> connectedClients = new ArrayList<Integer>();
      for(int j = 0 ; j < C ; ++j)
        if(serverCable[j].charAt(i) == 'Y')
          connectedClients.add(j);
      for(int c : connectedClients){
        boolean f = false;
        for(int c2 : connectedClients)
          f |= adj[c][c2];
        if(!f)++needDataGate;
      }
    }
    return needDataGate;
  }

ConyersConyers2011/07/09 20:32I had no idea how to approach this before—now I’m lokecd and loaded.

jegcglnjegcgln2011/07/10 00:57V90Y1i <a href="http://jlirhdlmzkgb.com/">jlirhdlmzkgb</a>

ibilabrybibilabryb2011/07/10 20:47Hpp9oU , [url=http://nxsaikczsipi.com/]nxsaikczsipi[/url], [link=http://hahjfdfjqpkd.com/]hahjfdfjqpkd[/link], http://mxdbrnjprhgo.com/

wxgknewxgkne2011/07/11 20:47S4uq5O <a href="http://kahybgqwmlil.com/">kahybgqwmlil</a>