ICPC 2017 国内予選 (ソースコード)

大会中に自分が実装したソースコードのまとめ

A (ソースコード紛失したけど、こんな感じ)

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;(i)<(n);++(i))

using namespace std;

int main() {
	int n,m;
	while(cin >> n >> m,n){
		vector<int> a(n);
		for(auto &elem:a) cin >> elem;

		int ans = -1;
		for(int i = 0; i < n;++i){
			for(int j = 0; j < i; ++j){
				if(a[i]+a[j]<=m){
					ans = max(ans,a[i]+a[j]);
				}
			}
		}
		if(ans == -1)
			puts("NONE");
		else
			cout << ans << endl;
	}
	return 0;
}

C

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;(i)<(n);++(i))
#define range(i,a,b) for(int i=a;(i)<(b);++(i))

using namespace std;

int main() {
	int h,w;
	while(cin >> h >> w,h){
		int a[15][15];
		rep(i,h)rep(j,w) cin >> a[i][j];

		int ans = 0;
		rep(u,h)rep(l,w){
			range(d,u+3,h+1)range(r,l+3,w+1){
				//cerr << u << " " << d << " " << l << " " << r << endl;
				bool ok = true;
				int cmin = a[u][l];
				range(i,u,d){
					cmin = min(cmin,a[i][l]);
					cmin = min(cmin,a[i][r-1]);
				}

				range(j,l,r){
					cmin = min(cmin,a[u][j]);
					cmin = min(cmin,a[d-1][j]);
				}

				int cur = 0;
				range(i,u+1,d-1)range(j,l+1,r-1){
					if(cmin <= a[i][j]) ok = false;
					cur += cmin - a[i][j];
				}

				//cerr << ok << " " << cmin << endl;
				if(ok) ans = max(ans,cur);
			}
		}

		cout << ans << endl;

	}
	return 0;
}

D

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;(i)<(n);++(i))
using namespace std;

template<class T> bool chmax(T &a,const T &b){
	return (a<b)?(a=b,1):0;
}

int n,m;
string b[510];

int dp[2][1<<20];

void solve_dp(){
	rep(i,2)rep(j,1<<m) dp[i][j]=-1;

	dp[0][0]=0;
	rep(i,n){
		int cur = 0;
		rep(j,m) cur = 2 * cur + (b[i][j]-'0');

		rep(j,1<<m){
			if(dp[0][j]==-1) continue;
			chmax(dp[1][j],dp[0][j]);
			chmax(dp[1][j^cur],dp[0][j] +1);
		}

		rep(j,1<<m) dp[0][j] = dp[1][j];
		rep(j,1<<m) dp[1][j] = -1;
	}

	cout << max(dp[0][0],0) << endl;
}

void solve_bulte(){
	int ans = 0;
	const char tmp = '0'^'1';
	rep(i,1<<n){
		string cur = string(m,'0');
		rep(j,n){
			if(i&(1<<j)){
				rep(k,m) if(b[j][k]=='1') cur[k]^=tmp;
			}
		}

		bool ok = true;
		rep(k,m) if(cur[k]=='1') ok = false;
		if(ok) chmax(ans,__builtin_popcount(i));
	}

	cout << ans << endl;
}


int main() {
	while(cin >> n >> m,n){
		rep(i,n) cin >> b[i];
		if(m<=20)
			solve_dp();
		else
			solve_bulte();
	}
	return 0;
}

E

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;(i)<(n);++(i))

using namespace std;

const int limit = 16;

set<string> cand;

void dfs(string cur){
	const int n = cur.size();
	if(n > limit) return;
	rep(i,n-1) if(cur.substr(i,2)=="--") return; 

	cand.insert(cur);
	rep(i,n){
		if(cur[i]=='E'){
			for(auto &elem:{"-E","(E^E)","(E*E)"}){
				string nxt = cur.substr(0,i) + elem + cur.substr(i+1,n-i-1);
				dfs(nxt);
			}
		}
	}

	return;
}

const int XOR[2][2]={{0,1},{1,0}};
const int AND[2][2]={{0,0},{0,1}};

int val;

bool E(const string &s,int &cur){
	const int n = s.size();	
	
	if(s[cur]=='-'){
		cur++;
		return !E(s,cur);
	}

	if(s[cur]=='('){
		cur++;
		bool l = E(s,cur);
		char op = s[cur++];
		bool r = E(s,cur);
		cur++;

		if(op=='*')
			return AND[l][r];
		else
			return XOR[l][r];
	} 

	char mark = s[cur++];

	if(isdigit(mark))
		return mark-'0';
	else
		return (val >> (mark-'a'))&1;
}

bool original[16];


bool search(string s){
	const int n = s.size();
	int idx = -1;
	
	rep(i,n){
		if(s[i]=='E'){
			idx = i;
			break;
		}
	}

	if(idx == -1){
		bool ok = true;

		rep(mask,16){
			val = mask;
			int cur = 0;
			if(original[mask] != E(s,cur)) ok = false;
		}

		return ok;
	}else{
		for(auto &c:{'0','1','a','b','c','d'}){
			string ns = s;
			ns[idx] = c;
			if(search(ns)==true) return true; 
		}
	}
	return false;
}

int main() {
	dfs("E");
	
	string s;
	while(cin >> s){
		if(s==".") break;
		
		rep(mask,16){
			val = mask;
			int cur = 0;
			original[mask] = E(s,cur);
		}

		int ans = s.size();

		for(auto &t:cand){
			const int m = t.size();
			if(search(t)) ans = min(ans,m);
		}

		cout << ans << endl;
	}
	
	return 0;
}

F

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;(i)<(n);++(i))

using namespace std;
using ll = long long;

int main() {
	ll n,_i,j;
	while(cin >> n >> _i >> j,n){
		const ll i = (1LL<<n) - _i;
		j--;
		string ans= "";
		//cerr << i << endl;
		
		rep(b,n){
			const ll total = 1LL << (n -b);
			ll ib  = i & 1;
			//cerr << i/total << endl;
			if((i/total)&1) ib^=1;
			const ll cur = j >> b &1;
			ans += ((ib^cur)==1?'L':'R');
		}

		reverse(begin(ans),end(ans));
		cout << ans << endl;
	}
	return 0;
}