Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-08-27

SRM480

12:36 | SRM480 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM480 - naoya_t@topcoder SRM480 - naoya_t@topcoder のブックマークコメント

x x - 0pt

ケアレスすぎて死にたい(特にMedium!)ので、通すためのdiffをまず晒す。黄色にとどまるための課題はハッキリ見えている。

経験則:再提出がちらほら見られる問題は自分も再提出しないと多分死ぬ。

  • 問題よく読め
  • あちこちでassertしたほうがよさげ
  • if文には必ずブロックを使うオレオレコーディング規約とか

Easy(250): InternetSecurity

  • 問題がなかなか頭に入ってこないけど
  • 多分やるだけぽ
  • 170.05 → challenged.
    • 辞書逆順で書いてたけどそんな問題と違った。これは早とちり
@@ -94,8 +94,8 @@
       if (sz(ss)==sn) break;
     }
     
-    vector<string> ans_(all(ans));
-    sort(all(ans_)); reverse(all(ans_));
+    vector<string> ans_;
+    rep(i,N) if(found(ans,address[i])) ans_.pb(address[i]);
     return ans_;
   }
 };

Medium(450): NetworkSecurity

  • サーバ1台ずつ別々に考えてよさそう
  • クライアントをトポロジカルソートして逆に見ていけばいいよね
  • 211.26 → failed system test...おや?
    • トポロジカルソートした結果の長さがN以上とか何それバグってる、と思ったら…orz
@@ -30,7 +30,7 @@
      set<int> s;
      rep(o,N){
        bool hi=false;
-       rep(i,N){if(clientCable[i][o]=='Y')hi=true;break;}
+       rep(i,N) if(clientCable[i][o]=='Y'){hi=true;break;}
        if(!hi) s.insert(o);
      }
      while(!s.empty()){

提出全コード

Easy
#include <string>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <algorithm>
#include <sstream>
#include <cmath>
using namespace std;

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0,lim=(n);var<lim;var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(__typeof__((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())

vector<string> split(string str, int delim=' ')
{
  // 昔どこかに貼ってるので略
}

class InternetSecurity {
 public:
  vector <string> determineWebsite(vector <string> address, vector <string> keyword, vector <string> dangerous, int threshold) {
    set<string> ans;
    
    int N=sz(address);
    int D=sz(dangerous); set<string> ds;
    rep(d,D){
      ds.insert(dangerous[d]);
    }
    vector<set<string> > kwds(N,set<string>());
    rep(i,N){
      vector<string> k = split(keyword[i]);
      tr(k,it) kwds[i].insert(*it);
    }

    set<int> ss; rep(i,N) ss.insert(i);
    vector<set<string> > dc(N,set<string>());

    while(!ss.empty()){
      vector<int> ss_(all(ss));
      int sn=sz(ss);
      tr(ss_,it){
        int n=*it;
        tr(kwds[n],it){
          if (found(ds,*it)) dc[n].insert(*it);
        }
        if (sz(dc[n]) >= threshold) {
          ans.insert(address[n]);
          tr(kwds[n],jt) ds.insert(*jt);
          ss.erase(n);
        }
      }
      if (sz(ss)==sn) break;
    }
    
    vector<string> ans_(all(ans)); // OOPS
    sort(all(ans_)); reverse(all(ans_)); // OOPS
    return ans_;
  }
};
Medium
#include <string>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <algorithm>
#include <sstream>
#include <cmath>
using namespace std;

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0,lim=(n);var<lim;var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(__typeof__((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())

class NetworkSecurity {
 public:
   int secureNetwork(vector <string> clientCable, vector <string> serverCable) {
     int N=sz(clientCable), M=sz(serverCable[0]);
     vector<int> l;
     set<int> s;
     rep(o,N){
       bool hi=false;
       rep(i,N){if(clientCable[i][o]=='Y')hi=true;break;} // OOPS
       if(!hi) s.insert(o);
     }
     while(!s.empty()){
       int n=-1; set<int> s2;
       tr(s,it){
         if(n<0) n=*it;
         else s2.insert(*it);
       }
       l.pb(n);
       rep(m,N){
         if (clientCable[n][m]=='Y'){
           clientCable[n][m]='*';
           int hd=0;
           rep(i,N){if(i==n)continue;
             if (clientCable[i][m]=='Y'){hd=1;break;}
           }
           if(!hd) s2.insert(m);
         }
       }
       s = s2;
     }
     reverse(all(l));

     int cnt = 0;
     rep(m,M){
       vector<bool> w(N,false),p(N,false);
       rep(n,N) if(serverCable[n][m]=='Y') w[n]=true;
       rep(i,N){
         int el=l[i];
         if(p[el]) continue;
         if(w[el]) { p[el]=true; cnt++;
           for(int j=i+1; j<N; ++j){
             int jl=l[j];
             if(clientCable[jl][el]!='N') p[jl]=true;
           }
         }
       }
     }
     return cnt;
   }
};

Result

1557 → 1436 blue blue blue

http://gyazo.com/ed62f1ec48c0764456174a7e2f8a7caf.png

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100827