naoya_t@topcoder

SRM480

12:36 |

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

• サーバ１台ずつ別々に考えてよさそう
• クライアントをトポロジカルソートして逆に見ていけばいいよね
• 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