読者です 読者をやめる 読者になる 読者になる

naoya_t@hatenablog

いわゆるチラシノウラであります

TCO12 Algorithm Online Round 2A

TopCoder Programming Contest

4/22(日) 1:10am〜
上位50人が通過、という事でやる前から通過あきらめムード
Challenge Phaseの最後の3分がChallengeできなかったらしくてRoundの有効性について審議中
ChallengeそっちのけでMedium問題考えてたわけですが
x-- 0点 462/1362位

Easy(300) SwitchesAndLamps

  • 可能性を潰していく / 辻褄があわなければ-1を返す
  • 128.98点(49'40'') → 0点。撃墜されなかったがFailed System Test
    • 早めに全組み合わせが分かってもその後で辻褄合わないのが来るかもしれないからreturn 0は早計
    • 残りの組み合わせに解けないものがあるかもしれないのにチェックせずlog2返してる
    • というかlog2の計算間違ってる
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);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 SwitchesAndLamps {
 public:
  int theMin(vector<string> switches, vector<string> lamps) {
    int ne=sz(switches), ns=sz(switches[0]);
    vector<ll> ans(ns, (1LL<<ns)-1);
    map<string,string> hs;
    rep(i,ne){
      if (found(hs,switches[i])) {
        if (hs[switches[i]] != lamps[i]) return -1;
      } else {
        hs[switches[i]] = lamps[i];
      }
    }
    rep(i,ne){
      ll on=0LL, off=0LL;
      int onc=0, offc=0;  /// これは使ってない
      rep(j,ns){
        if (lamps[i][j]=='Y') {
          on |= (1LL << j); onc++;
        } else {
          off |= (1LL << j); offc++;
        }
      }
      rep(j,ns){
        if (switches[i][j]=='Y') {
          ans[j] &= on;
        } else {
          ans[j] &= off;
        }
        if (ans[j] == 0) return -1;
      }

      int ld = 0;
      while(true) {
        set<ll>decided;
        rep(j,ns){
          if(__builtin_popcountll(ans[j])==1){
            if(found(decided,ans[j])) return -1;
            decided.insert(ans[j]);
          }
        }
        tr(decided,it){
          rep(j,ns) if (ans[j] > *it && ans[j] & *it) {
            ans[j] -= *it;
            if (ans[j] == 0) return -1;
          }
        }
        int d = sz(decided);
        if (d == ld) break;
        ld = d;
      }
      int res=ns-ld;
      if (res==0) return 0; /// 残りの実験にinconsistentなものがあった場合に-1を返すべきなのでこれはダメ
    }
    map<ll,int> notyet;
    rep(j,ns){
      if(__builtin_popcountll(ans[j])>1){
        if(found(notyet,ans[j])) notyet[ans[j]]++;
        else notyet[ans[j]] = 1;
      }
    }
    /// 未解決なものをグループ分けしているが解決不能なものがあれば-1を返さなければならない。というチェックが抜けていたので例えば以下の1行を追加
    /// tr(notyet,it) if (__builtin_popcountll(it->first) != it->second) return -1;
    int mx=0; tr(notyet,it) mx=max(mx,it->second);
    if (mx==0) return 0;
    for (int i=2,a=1; i<=ns; i*=2,a++) { /// これでは例えばmx=50,ns=50の場合にreturnせずループを抜けてしまう。終了条件(i<=ns)を削除すればOK
      if (mx<=i) return a;
    }
  }
};

Medium(450) CucumberWatering

  • 残り25分
  • ワープどこに入れるのが良いのか
  • 解けなかった