naoya_t@hatenablog

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

SRM562 DIV1 Medium<500> : CheckerFreeness

DIV1 Medium Random Challenge第4回。

全テストケースが通るところまで(休憩挟んでるとはいえ)4時間かかってる… ・角度の計算。cyclic なものをうまく扱えてない ・線分から直線の方程式を出すのは良い。線分のこちらか向こうかの区別は ax+by+c に (x,y) を代入した正負で出来る TLE…そりゃ2224じゃあTLE出るわな。222 x (111x221) x log(222) あたりまで行かないと無理。そのlogNが出来てない。 TLEじゃないとこでエラーが出てる。これは何だ

analysis読むよ 単純な解法は、白2つ黒2つを取って、成ってるか調べるというもの。convexityが示唆するもの・必要条件の理解が必要。 (黒線で白2つが割れて、白線で黒2つが割れればOKか)

3つの点が与えられたとき、時計回りなのか反時計回りなのかを判別する関数を使う例。cross product を用いて面積を求めるやつ? 黒1黒2白1 と 黒1黒2白2 が逆回転になればOK

あ、そうか 黒を2つ選んで(nC2)、全白についてどっち回りか調べて、1つでも違う方にあればその時点でOKなんだ それだとO(n3) だよね… すげー いやダメじゃね?必ずしもconvexにはならない。 …

3つのbitsetを作って xor , and で演算、で出来た これってO(n4)、というか O(w2b2) な気がするけど 0.5secぐらい? あちら側で謎のコンパイルエラーが出て all マクロが展開できないみたいだったのは何故?

expected unqualified-id before ')' token

ってやつ

今回得た知見

  • ccw() で平面を分割していく方法
  • bitset<222>. 確かに別にbitsetでなくたっていいんだろうけど、vector<> に放り込んで1つのオブジェクトみたいに使えること、論理演算とか、popcountとか、小規模の集合を扱うのに便利だし、割と高速。

実装

#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>
#define NDEBUG
// BEGIN CUT HERE
#include "cout.h"
#undef NDEBUG
// END CUT HERE
#include <cassert>
using namespace std;

#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(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)

typedef long long ll;


string concat(vector<string>& strs) {
  stringstream ss;
  tr(it, strs) ss << *it;
  return ss.str();
}

vector<string> split(string str, int delim=' ')
{
  vector<string> result;

  const char *s = str.c_str();
  if (delim == ' ') {
    for (const char *p=s; *p; p++) {
      if (*p == delim) s++;
      else break;
    }
    if (!*s) return result;

    for (const char *p=s; *p; p++) {
      if (*p == delim) {
        if (s < p) {
          string a(s,p-s);
          result.push_back(a);
        }
        s = p + 1;
      }
    }
    if (*s) result.push_back(s);
  } else {
    for (const char *p=s; *p; p++) {
      if (*p == delim) {
        string a(s,p-s);
        result.push_back(a);
        s = p + 1;
        if (*s == '\0') result.push_back("");
      }
    }
    if (*s) result.push_back(s);
  }

  return result;
}

vector<int> map_atoi(vector<string> nums)
{
  vector<int> vals(nums.size());
  for (int i=nums.size()-1; i>=0; i--) vals[i] = atoi(nums[i].c_str());
  return vals;
}

inline int ccw(int p0x,int p0y, int p1x,int p1y, int p2x,int p2y) {
    p1x -= p0x; p1y -= p0y;
    p2x -= p0x; p2y -= p0y;
    long long x = (long long)p1x*p2y - (long long)p1y*p2x;
    if (x > 0) return 1;
    if (x < 0) return -1;
    return 0;
}

#include <bitset>
typedef bitset<222> BitSet;

class CheckerFreeness {
    vector<int> parse(vector<string>& broken) {
        string sc = concat(broken);
        vector<string> ss = split(sc);
        return map_atoi(ss);
    }
public:
    string isFree(vector<string> whiteX, vector<string> whiteY, vector<string> blackX, vector<string> blackY) {
        vector<int> wx = parse(whiteX);
        vector<int> wy = parse(whiteY);
        vector<int> bx = parse(blackX);
        vector<int> by = parse(blackY);
        int nWhite = wx.size(); assert(wy.size() == nWhite);
        int nBlack = bx.size(); assert(by.size() == nBlack);
        assert(1 <= nWhite && nWhite <= 222);
        assert(1 <= nBlack && nBlack <= 222);
        int N = nWhite + nBlack;

        if (nWhite < 2 || nBlack < 2) return "YES"; // checker_free;

        bx.insert(bx.end(), wx.begin(), wx.end());
        by.insert(by.end(), wy.begin(), wy.end());

        vector<vector<BitSet>> bs(N, vector<BitSet>(N, BitSet(0)));

        repC2(i,j,N) {
            rep(b,nBlack) {
                if (b == i || b == j) continue;
                int yn = ccw(bx[i],by[i], bx[j],by[j], bx[b],by[b]);
                if (yn > 0) bs[i][j].set(b);
                if (yn < 0) bs[j][i].set(b);
            }
        }

        repC2(w1,w2,nWhite) {
            BitSet bww = bs[nBlack+w1][nBlack+w2];

            int plus = bww.count(), minus = nBlack - plus;
            if (!plus || !minus) continue;

            rep(b1,nBlack) {
                bool b1on = bww.test(b1);
                if (b1on) continue;
                // b1には、bwwで0なやつを選ぶ → b2は1なやつ (andが使える)
                BitSet b12 = (bs[nBlack+w1][b1] ^ bs[nBlack+w2][b1]) & bww;
                if (b12.count() > 0) return "NO";
            }
        }

        return "YES";
    }
};