SRM588 solutions

SRM588.cpp

#include <vector>
#include <string>
using namespace std;

// repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define FORR(x,arr) for(auto& x:arr)
#define SZ(a) int((a).size())

// 9:24-9:28 1WA
// 11:25-11:26 system test passed

class InsertZ {
public:
  string yes="Yes",no="No";
  string canTransform(string const &A,
                      string const &B) {
    
    int zA=count(A.begin(),A.end(),'z'),zB=count(B.begin(),B.end(),'z');
    if(zA>zB) return no;
    
    string AA="",BB="";
    FORR(c,A) if(c!='z') AA+=c;
    FORR(c,B) if(c!='z') BB+=c;
    
    return AA==BB?yes:no;
  }
};



#include <vector>
#include <string>
using namespace std;

// repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define FORR(x,arr) for(auto& x:arr)
#define SZ(a) int((a).size())

// 9:29-9:45 analysis
// 9:46-9:49 submit and system test passed
class JumpFurther {
public:
  int furthest(int N,
               int NG) {
    bool ok=true;
    int sum=0;
    FOR(i,1,N+1) {
      sum+=i;
      if(sum==NG) ok=false;
    }
//    cout << sum<<endl;
    return ok?sum:sum-1;
  }
};




#include <vector>
#include <string>
#include <cassert>
using namespace std;

// repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define FORR(x,arr) for(auto& x:arr)
#define SZ(a) int((a).size())

// 9:50-10:47 analysis (ok, bipartite mathching, 3-coloring problem is NP-complete...)
// 10:47-11:15 implement and system test passed
int C[52][52];
class ThreeColorabilityEasy {
public:
  int H,W;
  string yes="Yes",no="No";
  string isColorable(vector<string> const &B) {
    this->H=SZ(B),this->W=SZ(B[0]);
    
    memset(C,-1,sizeof(C));
    C[0][0]=0;
    REP(i,H) REP(j,W) {
      int &c0=C[i][j],&c1=C[i][j+1],&c2=C[i+1][j],&c3=C[i+1][j+1];
      assert(c0>=0);
      assert((c1==-1&&c2==-1)||(c1>=0&&c2==-1)||(c1==-1&&c2>=0)||(c1>=0&&c2>=0));
      assert(c3==-1);
      if(B[i][j]=='Z') {
        // Z
        c3=c0;
        if(c1==-1&&c2==-1) {
          c1=(c0+1)%3;
          c2=3-c0-c1;
        } else if(c2==-1) {
          assert(c1>=0);
          c2=3-c0-c1;
        } else if(c1==-1) {
          assert(c2>=0);
          c1=3-c0-c2;
        }
        if(c0!=c3) return no;
        if(c0==c1||c1==c2||c1==c3||c2==c3) return no;
      } else {
        // N
        if(c1==-1&&c2==-1) {
          c1=(c0+1)%3;
          c2=c1;
        } else if(c2==-1) {
          assert(c1>=0);
          c2=c1;
        } else if(c1==-1) {
          assert(c2>=0);
          c1=c2;
        }
        c3=3-c0-c1;
        if(c1!=c2) return no;
        if(c0==c1||c0==c2||c0==c3||c1==c3||c2==c3) return no;
      }
    }
    
    return yes;
  }
};