夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

PCK2012予選・校内予選

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

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);
  }
}

9問目

構文解析好きらしいISZK君にとっては逆元の求め方さえわかれば簡単だったらしい。
手元に蟻本あったから見せれば良かった(後の祭り)

10問目

問題見てない

小並感

  • 環境アドをしている方のメンバーで速度を稼ぐという作戦が必須だなと実感
  • ターミナルからgvim開こうとしたら(ISZK君がvim派なので)ターミナルがバグりはじめて悲しみ…Ubuntuなんとかしなくては
  • やっぱり校内予選は予想通りの結果だった、しょうがない
  • 実力不足
  • とざんさんが狼の人形持っていた
  • 後輩の「もう5時か」の連呼がやばかった(実際は4時10分ぐらいだった)
  • 藤原さんのPCが相変わらず危機的だった
  • ライブラリとか、やばし
  • 終わった後のハラスメントが異様
  • 準急さんがFacebookをふぁいすぶっくと読んでてやばかった
広告を非表示にする