PCK2012予選・校内予選

今回はISZK君と参加しました。
結果は
ooooo-----
の５完、校内予選敗退です。
ISZK君が奇数番目、僕が偶数番目の問題をやることになっていましたが、３番５番が競技慣れてる人じゃないと難しい問題だったので僕が代わりに解いたりして、ISZK君には強実装の６番とかまかせたりしてたら結局僕４完、ISZK君１完でまたなんか謝られてしまいました（去年も僕が簡単な問題いっぱい解いて、きたゆたさんが難しいやつ担当してたら結局ボクばっかりで謝られてた…）

1問目

書いてもらうだけ

2問目

書くだけ

#include <cstdio>
int main() {
  int a, b, c;
  scanf("%d%d%d",&a,&b,&c);
  if ((a&&!b&&!c)||(!a&&b&&!c)||(!a&&!b&&!c)) puts("Close");
  else puts("Open");
}

3問目

全列挙

#include <cstdio>
#include <vector>
using namespace std;
int n;
int h[100];
int main() {
  while (scanf("%d",&n)) {
	if (!n) break;
	for (int i=0; i<n+1; i++) scanf("%d",&h[i]);
	for (int i=0; i<n+1; i++) {
	  vector<int> tmp;
	  for (int j=0; j<n+1; j++) if (j!=i) tmp.push_back(h[j]);
	  bool flag = true;
	  int diff = tmp[1]-tmp[0];
	  for (int j=1; j<tmp.size()-1; j++) if (diff!=tmp[j+1]-tmp[j]) {
		  //printf("%d %d\n",tmp[j+1],tmp[j]);
		  flag=false;
		}
	  if (flag) {
		printf("%d\n",h[i]);
		break;
	  }
	}
  }
}

4問目

文字列計算するだけ

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
string calc(string l, string s) {
  reverse(s.begin(), s.end());
  int temp = 0;
  string ret = "";
  for (int i=0; i<4; i++) {
	int a = l[i]-'0', b = s[i]-'0';
	int res = a-b-temp;
	if (res<0) {
	  res+=10;
	  temp=1;
	} else {
	  temp=0;
	}
	ret+=(res+'0');
  }
  reverse(ret.begin(), ret.end());
  return ret;
}
int main() {
  string n;
  while (cin>>n) {
	if (n=="0000") break;
	int cnt[10];
	memset(cnt, 0, sizeof(cnt));
	bool flag=true;
	for (int i=0; i<4; i++) {
	  cnt[n[i]-'0']++;
	  if (cnt[n[i]-'0']==4) flag=false;
	}
	if (!flag) {
	  puts("NA");
	  continue;
	}
	//cout<<calc("2210","2210")<<endl;
	int res = 0;
	while (n!="6174"&&res<10) {
	  res++;
	  string l = n;
	  string s = n;
	  sort(l.begin(), l.end());
	  sort(s.begin(), s.end());
	  n = calc(l, s);
	  //cout<<l<<s<<endl;
	  //cout<<n << " " << calc(l,s)<<endl;
	}
	printf("%d\n",res);
  }
}

5問目

DP（O(n^2)になるけど）だと思ったら普通にO(n)の貪欲だった

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int n;
ll p[65000], j[65000];
int main() {
  while (scanf("%d",&n)) {
	if (!n) break;
	ll sum=0;
	for (int i=0; i<n; i++) {
	  scanf("%lld",&p[i]);
	  sum+=p[i];
	}
	for (int i=0; i<n-1; i++) scanf("%lld",&j[i]);
	sort(j, j+n-1);
	ll res=sum*n;
	for (int i=n-2; i>=0; i--) {
	  sum+=j[i];
	  res=max(res, sum*(i+1));
	}
	printf("%lld\n",res);
  }
}

6問目

まぁやばすぎ

7問目

ただのワーシャルフロイドってTwitterで見てなるへそってなったけどまだ解いてない

8問目

bitDPっぽいのはわかってて結局そうらしいんだけどO(2^16 * n^2)って通るのかな？
(21:30追記)
書いた。bit演算みゅずい

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n, c;
int a[30], b[30];
int dp[2][1<<16];
int main() {
  while (scanf("%d%d",&n,&c)) {
	if (!n&&!c) break;
	memset(a, 0, sizeof(a));
	memset(b, 0, sizeof(b));
	memset(dp, -1, sizeof(dp));
	for (int i=0; i<n; i++) {
	  for (int j=0; j<16; j++) {
		int in; scanf("%d",&in);
		if (in) a[i] |= (1<<j);
	  }
	}
	for (int i=0; i<c; i++) {
	  for (int j=0; j<16; j++) {
		int in; scanf("%d",&in);
		if (in) b[i] |= (1<<j);
	  }
	}
	dp[0][0]=0;
	for (int i=0; i<n; i++) {
	  memset(dp[(i+1)&1], -1, sizeof(dp[i&1]));
	  for (int S=0; S<(1<<16); S++) {
		if (dp[i&1][S]==-1) continue;
		dp[(i+1)&1][S|a[i]]=max(dp[(i+1)&1][S|a[i]], dp[i&1][S]);
		for (int j=0; j<c; j++) {
		  dp[(i+1)&1][(S|a[i])&(~b[j])]=max(dp[(i+1)&1][(S|a[i])&(~b[j])], dp[i&1][S]+__builtin_popcount((S|a[i])&b[j]));
		  printf("%d\n",__builtin_popcount((S|a[i])&b[j]));
		}
	  }
	}
	int res=0;
	for (int S=0; S<(1<<16); S++) {
	  res=max(res, dp[n&1][S]);
	}
	printf("%d\n",res);
  }
}