GCJ 2013 Qual

http://snuke.hatenablog.com/entry/2013/04/14/164938
ここにsnuke神さんが解説書いてくれています。

C

制約をうまく使って解を全列挙して、クエリが来るたび二分探索をすることを考えます
(制約とは、すべての桁の(数字)^2の総和<=9を意味します)

以下はPracticeで通したコードです。

//(include略)

typedef long long LL;
typedef pair<int,int> PII;
#define MP make_pair
#define REP(i,n) for(int i=0;i<(int)n;i++) 
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++) 
#define ALL(c) (c).begin(),(c).end() 


vector<string> data;

void trans(string s) {
  int n = s.size();
  string k = "";
  for(int i=0; i<106-n; i++) k+="0";
  data.push_back(k+s);
  
}


string two(string s) {
  string ret;
  int n = s.size();
  for(int i=0; i<2*n-1; i++) {
    ret += "0";
  }
  for(int i=0; i<n; i++) if(s[i]!='0') {
      for(int j=0; j<n; j++) {
	ret[i+j] += (s[i]-'0') * (s[j]-'0');
	if(ret[i+j]-'0'>=10)
	  cout<<"hogehoge"<<endl;
      }
  }
  
  return ret;
  
}


void saiki(string t, string s, int sum, int length) {
  if(s.size()+t.size()>=52) return;
  if(sum>=10) return;
  if(t[0]!='0')
    trans(two(t+s));
  
  saiki("0"+t, s+"0", sum, length+1 );
  
  saiki("1"+t, s+"1", sum+2, length+1);
  
}


void init() {
  {
    string t="";
    string s ="2";
    trans("9");
    //    trans("484");
    saiki(t,s,4,1);
    s = "1";
    saiki(t,s,1,1);
    saiki(s,s,2,1);
    s="0";
    saiki(t,s,0,1);
    saiki(s,s,0,1);
    
  }
  
  {
    string s = "2";
    string t = "";
    for(int i=0; i<26; i++) {
      trans(two("2"+t+"0"+t+"2"));
      trans(two("2"+t+"1"+t+"2"));
      trans(two("2"+t+t+"2"));
      t+="0";
    }
    
  }
  sort(ALL(data)); 
}
int solve() {
  string s,t;
  cin>>s>>t;
  
  while(s.size()<=105) s = "0"+s;
  while(t.size()<=105) t = "0"+t;
  
  int ans =upper_bound(ALL(data),t) - upper_bound(ALL(data),s);
  if(binary_search(ALL(data), s)) ans++;
  return ans;
}


int main() {
  init();
  /*
  for(int i=0; i<80; i++) {
    cout<<data[i]<<endl;
    }
  */
  int t;
  cin>>t;
  REP(i,t) {
    int ans = solve();
    cout<<"Case #"<<i+1<<": "<<ans<<endl;
  }
  return 0;
}

D

snukeさんみたいに何の操作をするのが最善かは特に考えませんでした。
ですが方針は同じです。操作を一つ行なってその手の先に解がなければその操作を行わず、解があれば一歩進んでその中で考えます。

解の有無判定は以下のような考えをしました。
とりあえず、「解なし」<=>「ある開けていない箱の鍵をどうやっても手に入れられない」と考えます。
自分が鍵を持っていたらその番号には到達可能です。
次に、ある箱を開ける鍵がKEYAiでその箱にKEYBijが入っているとすればKEYAi->KEYBijに辺を張ってります。
これで到達不可能な鍵があれば解なしだ、というかんじでやりました。

（証明してないのであんま詳しいことは言えない…）

あと、明らかにダメなケース（鍵が足りない）は事前に除きました

REPとforが混じってます

//(include略)

typedef long long LL;
typedef pair<int,int> PII;
#define MP make_pair
#define REP(i,n) for(int i=0;i<(int)n;i++) 
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++) 
#define ALL(c) (c).begin(),(c).end() 

const int MAXKEY = 210;
const int MAXCHEST = 210;
bool usedMain[MAXCHEST];
vector<int> solve() {
  int K,N;
  cin>>K>>N;
  int calcKeys[MAXKEY];
  int keys[MAXKEY];
  REP(i,MAXKEY) {
    keys[i] = 0;
    calcKeys[i]= 0;
  }
  REP(i,K) {
    int p;
    cin>>p;
    p--;
    keys[p]++;
    calcKeys[p]++;
  }
  
  vector<vector<int> > chest;
  vector<int> openKey;
  for(int i=0; i<N; i++) {
    int p,q;
    cin>>p>>q;
    vector<int>tmp;

    p--;
    calcKeys[p]--;
    openKey.push_back(p);
    for(int j=0; j<q; j++) {
      int r; cin>>r; r--;
      tmp.push_back(r);
      calcKeys[r]++;
    }
    chest.push_back(tmp);
  }
  vector<int> noSolution;
  for(int i=0; i<MAXKEY; i++) 
    if(calcKeys[i]<0) 
      return noSolution;
  
  vector<int> ans;
  
  REP(i,MAXCHEST) usedMain[i] = false;
  
  REP(turn,N) {
    bool update = false;;
    REP(chestNum, N) if(!usedMain[chestNum]) if(keys[openKey[chestNum]]>0){
      usedMain[chestNum] = true;
      keys[openKey[chestNum]]--;
      for(int i=0; i<chest[chestNum].size(); i++) {
	keys[chest[chestNum][i]]++;
      }
      bool ok = true; 
      {
	bool usedQueue[MAXCHEST];
	bool usedKeys[MAXKEY];
	queue<int> qu;
	vector<int> graph[MAXKEY];
	REP(i,MAXKEY) {
	  usedKeys[i] = false;
	  usedQueue[i] = false;
	}
	REP(i,N) if(!usedMain[i]) {
	  //	  cout<<"node"<<i<<endl;
	  int s = openKey[i];
	  usedKeys[s] = true;
	  REP(j,chest[i].size()) {
	    int t = chest[i][j];
	    graph[s].push_back(t);
	    //	    cout<<"edge"<<s<<" "<<t<<endl;
	  }
	}
	REP(i,MAXKEY) if(keys[i]>0) {
	  qu.push(i);
	  usedQueue[i] = true;
	}
	while(!qu.empty()) {
	  int cur = qu.front(); qu.pop();
	  //	  cout<<"cur"<<cur<<endl;
	  //	  usedQueue[cur] = true;
	  for(int i=0; i<graph[cur].size(); i++) {
	    int next = graph[cur][i];
	    if(!usedQueue[next]) {
	      qu.push(next);
	      usedQueue[next] = true;
	    }
	  }
	}
	/*
	REP(i,N) cout<<turn<<" "<<i<<" "<<usedQueue[i]<<endl;
	REP(i,3) cout<<keys[i]<<endl;
	REP(i,3) cout<<usedQueue[i]<<" "<<usedKeys[i]<<endl;
	*/
	REP(i,MAXKEY) if(!usedQueue[i] && usedKeys[i] ) ok = false;
	
      }
      if(!ok) {
	usedMain[chestNum] = false;
	keys[openKey[chestNum]]++;
	for(int i=0; i<chest[chestNum].size(); i++) {
	  keys[chest[chestNum][i]]--;
	}
      }
      else {
	update = true;
	ans.push_back(chestNum+1);
	break;
      }
    }
    if(!update) return noSolution;
  }
  return ans;
  
}



int main() {
  int t;
  cin>>t;
  REP(i,t) {
    vector<int> ans = solve();
    if(ans.empty())
      cout<<"Case #"<<i+1<<": IMPOSSIBLE"<<endl;
    else {
      cout<<"Case #"<<i+1<<":";
      REP(x, ans.size()) 
	cout<<" "<<ans[x];
      cout<<endl;
    }  
  }
  
  return 0;
}