Qualifier for Nationwide Preliminary 2009, SAITAMA (Code)

本番中に書いたプログラム晒し上げ。

Problem A:

"if(find(ALL(a),c[i])==a.end())" のところは最初 "p==a.size()" と書いてたんだけど、答えが出なかった。
今思い出してみると、"p==c.size()" とか書いてたような気がする。

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

#define REP(i,e) for(int i=0;i<(int)(e);++i)
#define FOR(i,b,e) for(int i=(b);i<(int)(e);++i)
#define ALL(c) (c).begin(), (c).end()

using namespace std;

main(){
  string a,b,c;
  while(getline(cin,a) && getline(cin,b) && getline(cin,c)){
    REP(i,c.size()){
      int p=distance(a.begin(),find(ALL(a),c[i]));
      if(find(ALL(a),c[i])==a.end()) cout << c[i];
      else cout << b[p];
    }
    cout << endl;
  }
}

Problem B:

最近、エラトステネスの篩を一行で書くようになりました。

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

#define REP(i,e) for(int i=0;i<(int)(e);++i)
#define FOR(i,b,e) for(int i=(b);i<(int)(e);++i)
#define ALL(c) (c).begin(), (c).end()

using namespace std;

const int N=1600000;

bool table[N];
int list[N];
int cnt=0;
bool ans[N];

main(){
  REP(i,N) table[i]=true;
  for(int i=2;i*i<N;++i) if(table[i]) for(int j=2;i*j<N;++j) table[i*j]=false;
  FOR(i,2,N) if(table[i]) list[cnt++]=i;

  REP(i,N) ans[i]=false;
  REP(i,cnt-2) if(list[i]+list[i+1]+list[i+2]<N) 
    ans[list[i]+list[i+1]+list[i+2]]=true;

  int C;
  cin >> C;
  while(C--){
    int t; cin >> t;
    cout << (ans[t] ? "Yes" : "No") << endl;
  }
}

Problem C:

REPを使いすぎると、Emacsが混乱して正しくインデントしてくれないことがあるから困る。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

#define REP(i,e) for(int i=0;i<(int)(e);++i)
#define FOR(i,b,e) for(int i=(b);i<(int)(e);++i)
#define ALL(c) (c).begin(), (c).end()

using namespace std;

const int N=13;
const int inf=1<<20;

int adj[N][N];

int compute(int n){
  static int cost[1<<N][N];
  REP(i,1<<n) REP(j,n) cost[i][j]=-inf;
  cost[1][0]=0;

  REP(i,1<<n) REP(j,n) if(i&(1<<j)) REP(k,n) if(!(i&(1<<k))){
      cost[i|(1<<k)][k]=max(cost[i|(1<<k)][k],cost[i][j]+adj[j][k]);
    }
		
  int result=0;
  REP(i,1<<n) result=max(result,cost[i][n-1]);
  return result;
}

main(){
  int a,b;
  while(cin >> a >> b && a|b){
    REP(i,a) REP(j,a) adj[i][j]=-inf; 
    REP(i,b){
      int c,d,e; cin >> c >> d >> e; c--,d--;
      adj[c][d]=max(adj[c][d],e);
      adj[d][c]=max(adj[d][c],e);
    }

    cout << compute(a) << endl;
  }
}

Problem E:

見所は論理演算子。C++に論理XOR演算子は存在しない・・・と見せかけて、実はこんな演算子があったりします。*1
ICPCでenumを使ったのはこれが初めてなのですが、意外と便利ですね。

#include <iostream>
#include <vector>
#include <string>
#include <cassert>
#include <map>

#define REP(i,e) for(int i=0;i<(int)(e);++i)
#define FOR(i,b,e) for(int i=(b);i<(int)(e);++i)
#define ALL(c) (c).begin(), (c).end()

using namespace std;

map<string,int> kmap;
enum{ AND, OR, XOR, NAND, NOR, NOT, IN};
const int T=10100;

class gate{
public:
  int kind;
  int sa,sb;
  int v[T];
  bool done[T];  
  int value(int t); 
};

gate G[512];

int gate::value(int t){
  if(kind==IN) return v[t];
  if(!done[t]){
    done[t]=true;
    
    switch(kind){
    case  AND: v[t]= (G[sa].value(t-1) and G[sb].value(t-1)); break;
    case   OR: v[t]= (G[sa].value(t-1) or  G[sb].value(t-1)); break;
    case  XOR: v[t]= (G[sa].value(t-1) xor G[sb].value(t-1)); break;
    case NAND: v[t]=!(G[sa].value(t-1) and G[sb].value(t-1)); break;
    case  NOR: v[t]=!(G[sa].value(t-1) or  G[sb].value(t-1)); break;
    case  NOT: v[t]=! G[sa].value(t-1);                       break;
    default: assert(false);
    }
  }
  return v[t];
}

int name(int n,string s){
  int i=atoi(s.c_str()+1)-1;
  //cout << "name " << s << " -> " << (s[0]=='i' ? n+i : i) << endl;;
  return s[0]=='i' ? n+i : i;
}

main(){
  kmap["AND"]=AND;
  kmap["OR"]=OR;
  kmap["XOR"]=XOR;
  kmap["NAND"]=NAND;
  kmap["NOR"]=NOR;
  kmap["NOT"]=NOT;

  int n,m,t;
  while(cin >> n >> m >> t && n|m|t){
    int ncnt=0;

    REP(i,n){
      string a,b,c; cin >> a >> b;

      G[i].kind=kmap[a];
      G[i].sa=name(n,b);

      if(G[i].kind!=NOT){
	cin >> b;
	G[i].sb=name(n,b);
      }

    }

    string o; cin >> o;
    int out=name(n,o);

    REP(i,n) REP(j,t) G[i].done[j]=false;
    REP(i,n) G[i].done[0]=true, G[i].v[0]=0;

    FOR(i,n,n+m) G[i].kind=IN;
    REP(j,t) FOR(i,n,n+m) {
      char c; cin >> c;
      G[i].v[j]=c-'0', G[i].done[j]=true;
    }

//     REP(i,n+m){
//       REP(j,t+1) cout << G[i].value(j); cout << endl;
//     } cout << endl;

    REP(i,t+1) cout << G[out].value(i) ;
    cout << endl;

  }
}

*1:もしかしたらGNU拡張かもしれません