naoya_t@topcoder

SRM beta (Member Pilot 2)

15:33 |

09.29+.2009

300点問題: TwistedMatrix

• 変更のあり得る場所を検出して場合分けとか書いてて
• 全部試しても大丈夫なことに途中で気づいたので書き直し
• １つずつやって、前回までの辞書順最小と比較しつつ、小さければ答えを更新していくのは良いが最初を{"11111..."...}にしていたので{"11","11"}的なものでも死ぬような糞コード。比較を<=にするか,初期値を変えるか
• AもBも当該箇所が?だった場合は0でいいが、Bが?でない場合にまで0にしてた。そりゃ駄目だろう
• というわけでFailed System Test
• なぜか誰にも撃墜されなかった

450点問題: TransportationNetwork

• 道路建設。空港建設。
• minimum spanning treeっぽいけど
• 具体的にどうするよ
• 間に合わず

900点問題: 開いてない

Challenge Time

• 落としも落とされもせず

System Test

• failed... 0点
• レーティングには変更なし

SRM beta 2 Div1 Easy: TwistedMatrix

過去問, 練習 | 11:13 |

提出コード（もちろん通らない）

#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 all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)

ll ubin(const string& s){
  ll n=0LL;
  for (int i=0,c=sz(s); i<c; i++){
    n = (n<<1LL) | (s[i]=='1'?1:0);
  }
  return n;
}
vector<ll> lex(const vector<string>& A){
  int n=sz(A);
  vector<ll> v(n,0LL);
  rep(i,n){
    v[i] = ubin(A[i]);
  }
  return v;
}
vector<string> turn(const vector<string>& A,int xmin,int ymin,int dir){
  vector<string> At(all(A));
  switch(dir){
    case 1: // cw
      At[ymin][xmin]     = A[ymin+1][xmin];
      At[ymin][xmin+1]   = A[ymin][xmin];
      At[ymin+1][xmin]   = A[ymin+1][xmin+1];
      At[ymin+1][xmin+1] = A[ymin][xmin+1];
      break;
    case -1: // ccw
      At[ymin][xmin]     = A[ymin][xmin+1];
      At[ymin][xmin+1]   = A[ymin+1][xmin+1];
      At[ymin+1][xmin]   = A[ymin][xmin];
      At[ymin+1][xmin+1] = A[ymin+1][xmin];
      break;
  }
  return At;
}

class TwistedMatrix {

 public:
  int d(int c1, int c2){ /// これは使ってないよ
    if (c1==c2) return 0;
    if (c2=='?') return 9;
    return c2-c1;
  }

  int N, M;
  
  int diff(const vector<string>& A, const vector<string>& B){
    int cnt = 0;
    rep(n,N){
      rep(m,M){
        if (A[n][m]=='?' || B[n][m]=='?') continue;
        if (B[n][m]!=A[n][m]) cnt++;
      }
    }
    return cnt;
  }
  vector<string> zero(const vector<string>& A){
    vector<string> z(all(A));
    rep(n,N){
      rep(m,M){
        if (A[n][m]=='?') z[n][m] = '0';
      }
    }
    return z;
  }
  
  vector <string> solve(vector <string> A, vector <string> B) {
    N=sz(A);
    M=sz(A[0]);

    vector<ll> minlex(N, (1LL << M) - 1LL);
    vector<string> ans(0);
    
    rep(n,N-1){
      rep(m,M-1){
        vector<string> At1 = turn(A,m,n,1);
        if(diff(At1,B)==0) {
          if (lex(At1) < minlex){
            ans = zero(At1);
            minlex = lex(At1);
          }
        }
        vector<string> At2 = turn(A,m,n,-1);
        if(diff(At2,B)==0) {
          if (lex(At2) < minlex){
            ans = zero(At2);
            minlex = lex(At2);
          }
        }
      }
    }
    return ans;
  }
};

修正コード（これは通る）

int ubin(const string& s){
  int n=0;
  for (int i=0,c=sz(s); i<c; i++){
    n = (n<<1) | (s[i]=='1'?1:0);
  }
  return n;
}
vector<int> lex(const vector<string>& A){
  int n=sz(A);
  vector<int> v(n,0);
  rep(i,n){
    v[i] = ubin(A[i]);
  }
  return v;
}
vector<string> turn(const vector<string>& A,int xmin,int ymin,int dir){
  vector<string> At(all(A));
  switch(dir){
    case 1: // cw
      At[ymin][xmin]     = A[ymin+1][xmin];
      At[ymin][xmin+1]   = A[ymin][xmin];
      At[ymin+1][xmin]   = A[ymin+1][xmin+1];
      At[ymin+1][xmin+1] = A[ymin][xmin+1];
      break;
    case -1: // ccw
      At[ymin][xmin]     = A[ymin][xmin+1];
      At[ymin][xmin+1]   = A[ymin+1][xmin+1];
      At[ymin+1][xmin]   = A[ymin][xmin];
      At[ymin+1][xmin+1] = A[ymin+1][xmin];
      break;
  }
  return At;
}

class TwistedMatrix {
  int N, M;

 public:
  int diff(const vector<string>& A, const vector<string>& B){
    int cnt = 0;
    rep(n,N){
      rep(m,M){
        if (A[n][m]=='?' || B[n][m]=='?') continue;
        if (B[n][m]!=A[n][m]) cnt++;
      }
    }
    return cnt;
  }

  vector<string> zero(const vector<string>& A, const vector<string>& B){
    vector<string> z(all(A));
    rep(n,N){
      rep(m,M){
        if (A[n][m]=='?') {
          z[n][m] = (B[n][m]=='?') ? '0' : B[n][m];
        }
      }
    }
    return z;
  }
  
  vector <string> solve(vector <string> A, vector <string> B) {
    N=sz(A);
    M=sz(A[0]);

    // vector<ll> minlex(N, (1LL << M) - 1LL);
    vector<int> minlex(N, (1 << M));
    vector<string> ans(0);
    
    rep(n,N-1){
      rep(m,M-1){
        for(int dir=-1;dir<=1;dir+=2) {
          vector<string> At = turn(A,m,n,dir);
          if(diff(At,B)==0) {
            vector<string> tmp = zero(At,B);
            vector<int> la = lex(tmp);
            if (la < minlex){
              ans = tmp;
              minlex = la;
            }
          }
        }
      }
    }
    return ans;
  }
};