JOI 2011代表選抜 Day1, Day2 ソースコード

とりあえずコードだけ投げておこう

Day1 Banner

#include <cstdio>

int H, W, map[400][400], in;

int solve(int p, int q)
{
  int t[8] = {0};
  for(int i=0;i<W;i++){
    int v = map[p][i] | map[q][i];
    t[v]++;
  }

  int ret = 0;
  for(int i=0;i<8;i++){
    for(int j=i+1;j<8;j++) if((i|j)==7){
      ret += t[i] * t[j];
    }
  }
  return ret;
}

int main()
{
  scanf("%d%d", &H, &W);
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      scanf("%d", &in);
      map[i][j] = 1<<in;
    }
  }

  long long ret = 0;

  for(int i=0;i<H;i++){
    for(int j=i+1;j<H;j++){
      ret += solve(i, j);
    }
  }

  printf("%lld\n", ret);

  return 0;
}

Day1 Dragon

このコードには間違いがあって、80点しか取れません

#include <cstdio>
#include <algorithm>

using namespace std;

struct minimum
{
  inline int operator()(int &a, int &b)
  {
    if(a > b) return b;
    return a;
  }
};

struct maximum
{
  inline int operator()(int &a, int &b)
  {
    if(a > b) return a;
    return b;
  }
};

template<class T> class seg_tree
{
  T comp;

  int *data[21], size[21], len, def;
  
public:
  seg_tree(int N, int _def)
  {
    def = _def;
    len = 0;
    size[len++] = N;

    while(size[len-1] > 1){
      size[len] = (size[len-1] + 1) / 2;
      len++;
    }

    for(int i=0;i<len;i++){
      int ln = (size[i] + 1) / 2 * 2;
      data[i] = new int[ln];
      for(int j=0;j<ln;j++) data[i][j] = def;
    }
  }

  int query(int left, int right)
  {
    int ret = def;
    for(int i=0;left!=right;i++){
      if(left&1) ret = comp(ret, data[i][left++]);
      if(right&1) ret = comp(ret, data[i][--right]);
      left >>= 1; right >>= 1;
    }
    return ret;
  }

  void set(int pos, int val)
  {
    data[0][pos] = val;
    pos >>= 1;
    
    for(int i=1;i<len;i++){
      data[i][pos] = comp(data[i-1][pos*2], data[i-1][pos*2+1]);
      pos >>= 1;
    }
  }
};

int H, W, N, x[100000], y[100000];
int xs[100000], xLast, ys[100000], yLast;

pair<int, int> st[100000];

struct action
{
  int X, lp;
};

inline bool operator<(const action& a, const action& b)
{
  return a.X < b.X || (a.X == b.X && a.lp < b.lp);
}

action act[400000]; int aLast;

long long solve()
{
  for(int i=0;i<N;i++){
    ys[i] = y[i];
    xs[i] = x[i];
  }

  sort(xs, xs+N);
  sort(ys, ys+N);

  xLast = unique(xs, xs+N) - xs;
  yLast = unique(ys, ys+N) - ys;

  long long ret = 0; aLast = 0;
  int xc = H, yc = W;

  for(int i=0;i<N;i++){
    st[i] = make_pair(x[i], y[i]);
  }

  sort(st, st+N);
  int p = 0;
  for(;p<N;){
    int p2 = p;
    while(p2 < N && st[p].first == st[p2].first) p2++;

    act[aLast].X = st[p].first;
    act[aLast].lp = st[p].second;
    aLast++;
    p = p2;
    xc--;
  }

  for(int i=0;i<N;i++){
    st[i] = make_pair(y[i], x[i]);
  }
  
  sort(st, st+N);
  p = 0;
  for(;p<N;){
    int p2 = p;
    while(p2 < N && st[p].first == st[p2].first) p2++;

    act[aLast].X = st[p].second;
    act[aLast].lp = st[p].first + 1000000001;
    aLast++;

    yc--;
    p = p2;
  }

  seg_tree<maximum> seg1(N, -1);

  sort(act, act + aLast);

  for(int i=0;i<N;i++){
    seg1.set(i, i);
  }

  for(int i=0;i<aLast;i++){
    if(act[i].lp > 1000000000){
      int ps = lower_bound(ys, ys+yLast, act[i].lp - 1000000001) - ys;
      seg1.set(ps, -1);
    }else{
      //about "left"
      int pl = lower_bound(ys, ys+yLast, act[i].lp) - ys;
      int tmp = seg1.query(0, pl);
      //printf("%d %d %d\n", act[i].X, act[i].lp, tmp);
      //if(act[i].X==1) continue;
      if(tmp==-1){
	//only up
	//ret = max(ret, (long long)act[i].X - (upper_bound(xs, xs+xLast, act[i].X) - xs) - 1);
	if(pl>0 && ys[pl-1] == ys[pl]-1){
	  ret = max(ret, (long long)ys[pl] - pl - 1);
	}else{
	  ret = max(ret, (long long)ys[pl] - pl - 2);
	}
      }else{
	ret = max(ret, (long long)act[i].X - (upper_bound(xs, xs+xLast, act[i].X) - xs)
		  + ys[tmp] - tmp - 1);
      }
    }
  }

  ret += (long long)xc * yc;

  return ret;
}

void turnX()
{
  for(int i=0;i<N;i++){
    x[i] = H - x[i] + 1;
  }
}

void turnY()
{
  for(int i=0;i<N;i++){
    y[i] = W - y[i] + 1;
  }
}

void turnXY()
{
  for(int i=0;i<N;i++){
    swap(x[i], y[i]);
  }
  swap(W, H);
}

int main()
{
  scanf("%d%d%d", &H, &W, &N);

  xLast = yLast = N;
  for(int i=0;i<N;i++){
    scanf("%d%d", x+i, y+i);
  }

  long long ret = 0;

  ret = max(ret, solve());
  turnX(); ret = max(ret, solve());
  turnY(); ret = max(ret, solve());
  turnX(); ret = max(ret, solve());
  turnY(); turnXY(); ret = max(ret, solve());
  turnX(); ret = max(ret, solve());
  turnY(); ret = max(ret, solve());
  turnX(); ret = max(ret, solve());
  printf("%lld\n", ret);
  return 0;
}

Day1 Joitter

#include <cstdio>
#include <algorithm>

using namespace std;

int N, type[1000], cost[1000][1000];

void solve1()
{
  int cnt = 0, ret = 0;
  for(int i=0;i<N;i++){
    for(int j=i+1;j<N;j++){
      if(type[i]==1 || type[j]==1){
	ret += cost[i][j];
	cnt++;
      }
    }
  }

  printf("%d %d\n", cnt, ret);
}

void solve2(int T)
{
  if(T==2){
    int v1=-1, v2=-1;
    for(int i=0;i<N;i++){
      if(type[i]==2){
	if(v1==-1) v1 = i;
	else v2 = i;
      }
    }

    int ret = cost[v1][v2];
    for(int i=0;i<N;i++){
      if(i != v1 && i != v2){
	ret += min(cost[i][v1], cost[i][v2]);
      }
    }

    for(int i=0;i<N;i++){
      int tmp = 0;
      for(int j=0;j<N;j++) if(i != j) tmp += cost[i][j];
      ret = min(ret, tmp);
    }

    printf("%d %d\n", N-1, ret);
  }else{
    int ret = 2100000000;
    for(int i=0;i<N;i++){
      int tmp = 0;
      for(int j=0;j<N;j++) if(i != j) tmp += cost[i][j];
      ret = min(ret, tmp);
    }

    printf("%d %d\n", N-1, ret);
  }
}

void solve3()
{
  int ret = 0;
  int minc[1000];
  bool visited[1000];

  for(int i=0;i<N;i++){
    minc[i] = 1000000;
    visited[i] = false;
  }

  minc[0] = 0;

  for(int i=0;i<N;i++){
    int mp = -1;
    for(int j=0;j<N;j++)
      if(!visited[j] && (mp==-1 || minc[mp] > minc[j])){
	mp = j;
      }
    
    visited[mp] = true;
    ret += minc[mp];

    for(int j=0;j<N;j++){
      minc[j] = min(minc[j], cost[mp][j]);
    }
  }

  printf("%d %d\n", N-1, ret);
}

int uf[1000];
pair<int, pair<int, int> > edge[5100000]; int end;

int root(int p)
{
  return (uf[p]<0)?p:(uf[p]=root(uf[p]));
}

bool join(int p, int q)
{
  p = root(p);
  q = root(q);
  if(p==q) return false;

  uf[p] += uf[q];
  uf[q] = p;
  return true;
}

void kruskal()
{
  for(int i=0;i<N;i++) uf[i] = -1;
  end = 0;

  for(int i=0;i<N;i++){
    for(int j=i+1;j<N;j++){
      edge[end++] = make_pair(cost[i][j], make_pair(i, j));
    }
  }

  sort(edge, edge+end);

  int ret = 0;
  for(int i=0;i<end;i++){
    if(-uf[root(0)] == N) break;
    if(join(edge[i].second.first, edge[i].second.second)){
      ret += edge[i].first;
    }
  }

  printf("%d %d\n", N-1, ret);
}

int main()
{
  int ones=0, twos=0;

  scanf("%d", &N);

  for(int i=0;i<N;i++){
    scanf("%d", type+i);
    if(type[i]==1) ones++;
    if(type[i]==2) twos++;
  }

  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++) scanf("%d", &(cost[i][j]));
  }
  
  if(ones>0){
    solve1();
  }else if(twos>0){
    solve2(twos);
  }else{
    solve3();
    //kruskal();
  }

  return 0;
}

Day2 Guess Them All

#include <cstdio>
#include <vector>

using namespace std;

int N, ret[100];
int output[100], one_pos;

int query()
{
  int rt;

  for(int i=0;i<N;i++) printf("%d\n", output[i]);
  fflush(stdout);
  scanf("%d", &rt);

  return rt;
}

bool determineX(int X)
{
  vector<int> cand;
  for(int i=0;i<N;i++) if(ret[i]==-1) cand.push_back(i);

  int left=0, right=cand.size();
  while(right-left > 1){
    int mid = (left + right) / 2;
    int m2 = cand[mid];
    for(int i=0;i<m2;i++) output[i] = X;
    for(int i=m2;i<N;i++) output[i] = 1;

    int q = query();
    if(q==N) return true;
    if(m2 <= one_pos) q--;
    if(q==1){
      right = mid;
    }else{
      left = mid;
    }
  }

  ret[cand[left]] = X;
  return false;
}

int main()
{
  scanf("%d", &N);

  if(N==1){
    output[0] = 1;
    query();
    return 0;
  }

  for(int i=0;i<N;i++) ret[i] = -1;

  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++) output[j] = 1;
    output[i] = 2;

    int q = query();
    if(q==N) return 0;

    if(q==0){
      one_pos = i;
      ret[one_pos] = 1;
      break;
    }
  }

  for(int i=2;i<=N;i++) if(determineX(i)) return 0;
  for(int i=0;i<N;i++) output[i] = ret[i];
  query();

  return 0;
}

Day2 Keycards

#include <cstdio>

#define MOD 1000000007
#define MAX 1000000

int N, K;
long long invs[MAX+1];
long long kaijo[MAX+1], kaijo_inv[MAX+1];

long long inv(int X, long long M)
{
  long long a=X, b=1;
  while(a>1){
    long long t = M / a;
    b = (b * t) % M;
    a = M % a;
    b = (M - b) % MOD;
  }

  return b;
}

inline long long C(int a, int b)
{
  return ((kaijo[a] * kaijo_inv[b])%MOD * kaijo_inv[a-b]) % MOD;
}

long long modpow(int X, long long Y, int M)
{
  if(Y == 0) return 1;
  if(Y == 1) return X;

  long long tmp = modpow(X, Y/2, M);
  tmp = (tmp * tmp) % M;
  if(Y%2==1) tmp = (tmp * X) % M;
  return tmp;
}

int main()
{
  scanf("%d%d", &N, &K);
  if(N == K){
    printf("1\n"); return 0;
  }

  for(int i=1;i<=N;i++) invs[i] = inv(i, MOD);

  kaijo[0] = kaijo_inv[0] = 1;
  for(int i=1;i<=N;i++){
    kaijo[i] = (kaijo[i-1] * i) % MOD;
    kaijo_inv[i] = (kaijo_inv[i-1] * invs[i]) % MOD;
  }
  long long ret = 0;

  long long mpw = 2;
  for(int i=0;i<=N-K;i++){
    int sign = ((N-K-i)%2==0)?1:(-1);
    long long tmp = C(N-K, i);
    //tmp *= modpow(2, modpow(2, i, MOD-1), MOD);
    tmp *= mpw;
    mpw = (mpw * mpw) % MOD;
    tmp %= MOD;

    if(sign==1) ret = (ret + tmp) % MOD;
    else ret = (ret + MOD - tmp) % MOD;
  }

  ret *= C(N, K);
  ret %= MOD;

  printf("%lld\n", ret);

  return 0;
}

Day2 Shiritori

下のコード中において、「strongness」なんていう英語は存在しません。正しくは「strength」です。

#include <cstdio>

struct word
{
  int v[5];
};

struct node
{
  node* next;
  int val;
};

int N, kind;
char in[11];
word wd[500000];

int bg[100], ed[100], edge[100][100];

bool visited[100];

node* con[100][100];
node pool[500000]; int pl;

bool strongness[100][100];
int uf[100];
int id[100], iLast;

inline int root(int p)
{
  return (uf[p]<0)?p:(uf[p]=root(uf[p]));
}

void join(int p, int q)
{
  p = root(p);
  q = root(q);
  if(p==q) return;
  uf[p] += uf[q];
  uf[q] = p;
}

void str_visit1(int p)
{
  if(visited[p]) return;
  visited[p] = true;

  for(int i=0;i<kind;i++) if(edge[p][i]) str_visit1(i);
  
  id[iLast++] = p;
}

void str_visit2(int p, int id)
{
  if(visited[p]) return;
  visited[p] = true;
  join(p, id);

  for(int i=0;i<kind;i++) if(edge[i][p]) str_visit2(i, id);
}

void determine_strongness()
{
  iLast = 0;
  for(int i=0;i<kind;i++) visited[i] = false;
  for(int i=0;i<kind;i++) if(bg[i] || ed[i]){
      str_visit1(i);
    }

  for(int i=0;i<kind;i++){
    visited[i] = false;
    uf[i] = -1;
  }

  for(int i=iLast-1;i>=0;i--){
    str_visit2(id[i], id[i]);
  }

  int bgs[100], eds[100];
  for(int i=0;i<kind;i++) bgs[i] = eds[i] = 0;
  for(int i=0;i<kind;i++){
    for(int j=0;j<kind;j++) if(edge[i][j]){
	bgs[i]++;
	eds[j]++;
      }
  }

  int mg = -1;
  for(int i=0;i<kind;i++) if(bgs[i]==1 && eds[i]==0) mg = i;

  if(mg>=0 && uf[mg]<-1) mg = -1;

  for(int i=0;i<kind;i++){
    for(int j=0;j<kind;j++){
      strongness[i][j] = false;
      if(edge[i][j]){
	if(root(i) == root(j)) strongness[i][j] = true;
	else if(mg>=0 && i==mg) strongness[i][j] = true;
      }
    }
  }
}

void _visit(int p)
{
  if(visited[p]) return;
  visited[p] = true;
  for(int i=0;i<kind;i++) if(edge[p][i]) _visit(i);
}

bool test(int v)
{
  for(int i=0;i<kind;i++) visited[i] = false;
  _visit(v);
  for(int i=0;i<kind;i++) if(!visited[i] && !(bg[i]==0&&ed[i]==0)) return false;
  return true;
}

void output(int k)
{
  for(int i=0;i<5;i++){
    printf("%02d", wd[k].v[i]);
  }
  puts("");
}

int main()
{
  scanf("%d", &N);
  for(int i=0;i<100;i++){
    bg[i] = ed[i] = 0;
    for(int j=0;j<100;j++){
      edge[i][j] = 0;
      con[i][j] = NULL;
    }
  }

  for(int i=0;i<N;i++){
    scanf("%s", in);
    for(int j=0;j<5;j++){
      wd[i].v[j] = (in[j*2]-'0')*10 + (in[j*2+1]-'0');
    }
    bg[wd[i].v[0]]++;
    ed[wd[i].v[4]]++;
    edge[wd[i].v[0]][wd[i].v[4]]++;
  }

  for(int i=0;i<100;i++){
    if(bg[i]>0 || ed[i]>0) kind = i+1;
  }

  pl = 0;
  for(int i=N-1;i>=0;i--){
    pool[pl].next = con[wd[i].v[0]][wd[i].v[4]];
    pool[pl].val = i;
    con[wd[i].v[0]][wd[i].v[4]] = &(pool[pl]);
    pl++;
  }

  int over_p = -1;
  for(int i=0;i<kind;i++){
    if(bg[i]-ed[i]==0) continue;
    if(bg[i]-ed[i]==1){
      if(over_p == -1) over_p = i;
      else goto bad;
    }
    if(bg[i]-ed[i]>1) goto bad;
  }

  if(over_p==-1){
    over_p = wd[0].v[0];
  }

  if(!test(over_p)) goto bad;

  determine_strongness();

  for(int i=0;i<N;i++){
    int nex = -1;
    for(int j=0;j<kind;j++){
      if(edge[over_p][j]==0) continue;
      if(edge[over_p][j]>=2){
	goto valid;
      }else if(strongness[over_p][j]){
	goto valid;
      }
      continue;
    valid:
      if(nex==-1) nex = j;
      else if(con[over_p][nex]->val > con[over_p][j]->val) nex = j;
      continue;
    }

    output(con[over_p][nex]->val);
    con[over_p][nex] = con[over_p][nex]->next;
    edge[over_p][nex]--;
    bg[over_p]--;
    ed[nex]--;

    if(edge[over_p][nex]==0) determine_strongness();

    over_p = nex;
  }

  return 0;

 bad:
  puts("impossible");
  return 0;
}