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問目
問題見てない