naoya_t@topcoder

Google Code Jam: Round 1A (2.5hrs)

22:37 |

• A. Multi-base happiness
• B. Crossing the Road
• C. Collecting Cards

Aを解いて、Cにはまって時間を潰す。

結局 A-small だけ通して992位。

A: Multi-base happiness

• A-largeは先に511パターン全部解いてO(1)スクリプトを書こうと思ってたけど数百万でギブアップする軟弱コードだったので無理ぽ

#include <iostream>
#include <vector>
#include <string>
#include <list>

#include "cout.h"
using namespace std;

#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++)
#define found(s,e)  ((s).find(e)!=(s).end())

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;
}

vector<set<long long> > ng, ok, vi;

//
// 二進数
//
vector<int> rebase(long long x, int base)
{
  // printf("rebase(%d,%d) = ", x, base);
  vector<int> ar;
  while (x > 0) {
	ar.push_back(x % base); x /= base;
  }
  // cout << ar << endl;
  return ar;
}

bool check(long long x, int base) {
  // printf("check(x=%d, base=%d)¥n", x,base);
  //cout << ok[base] << " , " << ng[base] << " , " << vi[base] << endl;
  if (found(ok[base],x)) {
    // printf("ok[%d][%d] exists.¥n", base,x);
    return true;
  }
  if (found(ng[base],x)) {
    // printf("ng[%d][%d] exists.¥n", base,x);
    return false;
  }
  if (found(vi[base],x)) {
    // printf("vi[%d][%d] exists. loop.¥n", base,x);
    return false;
  }

  vi[base].insert(x);
  
  vector<int> ar = rebase(x,base);
  long long sum=0;
  tr(ar,it){
    long long y = *it;
    sum += y*y;
  }
  // cout << "sum of " << ar << " = " << sum << endl;
  if (sum==1LL || found(ok[base],sum)) {
    ok[base].insert(x);
    return true;
  }
  if (found(ng[base],sum)) {
    ng[base].insert(x);
    return false;
  }

  int rv = check(sum,base);
  if (rv) {
    ok[base].insert(x);
    return true;
  } else {
    ng[base].insert(x);
    return false;
  }
}

main()
{
  int T;
  string nums;
  
  ng.resize(11);
  ok.resize(11);
  vi.resize(11);
  
  rep(i,11){
    ng[i].clear();
    ok[i].clear();
    vi[i].clear();
  }

  cin >> T;
  getline(cin,nums);

  rep(t,T){
    rep(i,11){
      // ng[i].clear();
      // ok[i].clear();
      // vi[i].clear();
    }

    getline(cin,nums);
    vector<int> bases = map_atoi(split(nums));
    int bn = sz(bases);
    // cout << bases << endl << endl;

    for(long long x=2;;x++){
      int ok=0;
      rep(i,bn){
        int base=bases[i];
        if (check(x,base)) {
          // printf("check(%d,%d) = true¥n", x,base);
          ok++;
        }
        else {
          // printf("check(%d,%d) = false¥n", x,base);
        }
      }
      if (ok==bn) {
        printf("Case #%d: %lld¥n", 1+t, x);
        break;
      }
    }
  }
}

デバッグ用の

#include "cout.h"

入れたままsubmitしちゃったので落とされるかも。その件で運営に問い合わせメールを頑張って書いて送ったけど、返事が来ないしとりあえずRound 1Bに備える。→（Round 1Bが始まった後で）お返事来ました。

Dear naoya.t,

I checked your solution: removing the include and adding "#include <set>" fixes it. Thanks for letting us know, and don't worry about it in this case.

Cheers,

Bartholomew

よかったよかった

C: Collecting Cards

• DP的に書いた
• 何回やっても計算あわない
• どこか間違ってるに違いない
• 時間を無駄にしました

B: Crossing the Road

• 残り10分ぐらいでBを見たけどまあ10分じゃ解けない → ちゃんと解いたら、Cにはまってなければなんとかなる位の時間で解けた。しかもLargeも高速解決。
• あとで（1Bに参加するかどうか決まってから）まとめる →以下にソース貼ります

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <algorithm>
#include <cmath>

//#include "cout.h"
using namespace std;

#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++)
#define found(s,e)  ((s).find(e)!=(s).end())

vector<vector<int> > S,W,Ofs,Cyc;

int passv(int t, int j, int i){
  int t_ = t % Cyc[i][j]; // [0, cyc)
  int o1 = Ofs[i][j], o2 = o1 + S[i][j], o3 = o2 + W[i][j];
  if (t_ < o1) t_ += Cyc[i][j];

  if (t_ < o2) { // go
    return t+1;
  } else { // wait o3
    return o3+1+(t-t_);
  }
}
int passh(int t, int j, int i){
  int t_ = t % Cyc[i][j]; // [0, cyc)
  int o1 = Ofs[i][j], o2 = o1 + S[i][j], o3 = o2 + W[i][j];
  if (t_ < o1) t_ += Cyc[i][j];

  if (t_ < o2) { // wait o2
    return o2+1+(t-t_);
  } else { // go
    return t+1;
  }
}

main(){
  int C; // 1-100
  cin >> C;
  for(int t=1;t<=C;t++){
    int N, M;
    cin >> N >> M;
    
    S.resize(N);
    W.resize(N);
    Ofs.resize(N);
    Cyc.resize(N);
    rep(i,N) {
      S[i].resize(M);
      W[i].resize(M);
      Ofs[i].resize(M);
      Cyc[i].resize(M);
    }
    rep(i,N) {
      rep(j,M) {
        int s, w, t, cyc, ofs;
        cin >> s >> w >> t;
        cyc = s + w;
        ofs = t % cyc;
        S[i][j] = s;
        W[i][j] = w;
        Ofs[i][j] = ofs;
        Cyc[i][j] = cyc;
      }
    }

    ///
    int mini = 0;

    pair<int,int> goal = make_pair((M-1)*2+1,-1);
    
    priority_queue<pair<int,pair<int,int> > > pq;
    pq.push(make_pair(0,make_pair(0,(N-1)*2)));

    map<pair<int,int>,int> reserved;
    int fastest = INT_MAX;
    
    while(!pq.empty()){
      pair<int,pair<int,int> > tp = pq.top(); pq.pop();
      int time = -tp.first;
      pair<int,int> loc = tp.second;
      if (loc == goal) { fastest = reserved[goal]; continue; }
      else if (time >= fastest) continue;
  
      int x = loc.first, y = loc.second;
      if (x < 0 || y < -1) continue;
      
      int cx = x/2, cy = (y + 1)/2;
      if (cx < 0 || M-1 < cx) continue;
      if (cy < 0 || N-1 < cy) continue;

      //printf("at t=%d on (%d,%d), block (%d,%d), ", time, x,y, cx,cy);
      int t; pair<int,int> l;
      if (x & 1) {
        if (y & 1) {
          // 交差点右上
          t = time+2;
          l = make_pair(x,y-1); // ^
          if (t <= fastest && !(found(reserved,l) && reserved[l]<=t)) {
            pq.push(make_pair(-t,l));
            reserved[l]=t;
          }
          t = passv(time,cx,cy);
          l = make_pair(x,y+1); // v
          if (t <= fastest && !(found(reserved,l) && reserved[l]<=t)) {
            pq.push(make_pair(-t,l));
            reserved[l]=t;
          }
          t = passh(time,cx,cy);
          l = make_pair(x-1,y); // <
          if (t <= fastest && !(found(reserved,l) && reserved[l]<=t)) {
            pq.push(make_pair(-t,l));
            reserved[l]=t;
          }
          t = time+2;
          l = make_pair(x+1,y); // >
          if (t <= fastest && !(found(reserved,l) && reserved[l]<=t)) {
            pq.push(make_pair(-t,l));
            reserved[l]=t;
          }
        } else {
          // 交差点右下
          t = passv(time,cx,cy);
          l = make_pair(x,y-1); // ^
          if (t <= fastest && !(found(reserved,l) && reserved[l]<=t)) {
            pq.push(make_pair(-t,l));
            reserved[l]=t;
          }
          t = time+2;
          l = make_pair(x,y+1); // v
          if (t <= fastest && !(found(reserved,l) && reserved[l]<=t)) {
            pq.push(make_pair(-t,l));
            reserved[l]=t;
          }
          t = passh(time,cx,cy);
          l = make_pair(x-1,y); // <
          if (t <= fastest && !(found(reserved,l) && reserved[l]<=t)) {
            pq.push(make_pair(-t,l));
            reserved[l]=t;
          }
          t = time+2;
          l = make_pair(x+1,y); // >
          if (t <= fastest && !(found(reserved,l) && reserved[l]<=t)) {
            pq.push(make_pair(-t,l));
            reserved[l]=t;
          }
        }
      } else {
        if (y & 1) {
          // 交差点左上
          t = time+2;
          l = make_pair(x,y-1); // ^
          if (t <= fastest && !(found(reserved,l) && reserved[l]<=t)) {
            pq.push(make_pair(-t,l));
            reserved[l]=t;
          }
          t = passv(time,cx,cy);
          l = make_pair(x,y+1); // v
          if (t <= fastest && !(found(reserved,l) && reserved[l]<=t)) {
            pq.push(make_pair(-t,l));
            reserved[l]=t;
          }
          t = time+2;
          l = make_pair(x-1,y); // <
          if (t <= fastest && !(found(reserved,l) && reserved[l]<=t)) {
            pq.push(make_pair(-t,l));
            reserved[l]=t;
          }
          t = passh(time,cx,cy);
          l = make_pair(x+1,y); // >
          if (t <= fastest && !(found(reserved,l) && reserved[l]<=t)) {
            pq.push(make_pair(-t,l));
            reserved[l]=t;
          }
        } else {
          // 交差点左下
          t = passv(time,cx,cy);
          l = make_pair(x,y-1); // ^
          if (t <= fastest && !(found(reserved,l) && reserved[l]<=t)) {
            pq.push(make_pair(-t,l));
            reserved[l]=t;
          }
          t = time+2;
          l = make_pair(x,y+1); // v
          if (t <= fastest && !(found(reserved,l) && reserved[l]<=t)) {
            pq.push(make_pair(-t,l));
            reserved[l]=t;
          }
          t = time+2;
          l = make_pair(x-1,y); // <
          if (t <= fastest && !(found(reserved,l) && reserved[l]<=t)) {
            pq.push(make_pair(-t,l));
            reserved[l]=t;
          }
          t = passh(time,cx,cy);
          l = make_pair(x+1,y); // >
          if (t <= fastest && !(found(reserved,l) && reserved[l]<=t)) {
            pq.push(make_pair(-t,l));
            reserved[l]=t;
          }
        }
      }
    }

    printf("Case #%d: %d¥n", t, fastest);
  }
}