スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

UTPC 2011

2011/05/04 12:00 ~ 17:00 (JST)
東京大学競技プログラミング同好会主催 (?) の UTPC 2011 に参加してきました。

Tags : プログラミング UTPC 未解決

概要

5 時間で 12 問。
ICPC 形式に近いが、部分点がある。
過去問の傾向では、前半 4, 5 問は簡単で、後半の問題はかなり難しい。

結果

A. 100 (5 min)
B. 100 (13 min)
C. 100 (30 min)
D. 100 (63 min)
E. 20 (269 min)
F. 20 (130 min)
G. 0
H. -
I. -
J. -
K. -
L. -

Standing : 65/160 くらい

問題

日本語なので省略。
ここを参照。

解答 & 思考過程

言語は C++。テンプレはここを参照。

A.
int main(){
int m,n; scanf("%d%d",&m,&n);
int cnt[20]={};
rep(i,m) rep(j,n) {
int a; scanf("%d",&a);
cnt[i]+=a;
}

printf("%d\n",*max_element(cnt,cnt+m));

return 0;
}

さすがに A は書くだけだった。

B.
bool match(char a,char b){
if(a=='i' && b=='i') return true;
if(a=='w' && b=='w') return true;
if(a=='(' && b==')') return true;
if(a==')' && b=='(') return true;
return false;
}

int main(){
string s; cin>>s;
int len=s.length();
int cnt=0;
rep(i,len/2) if(!match(s[i],s[len-i-1])) cnt++;
if(len%2==1 && !isalpha(s[len/2])) cnt++;
cout<<cnt<<endl;
return 0;
}

挿入、削除がないので、回文の左右でどの文字とどの文字が対応するかが一意に決まっている。
それをカウントしてやればいい。

C.
bool match(char a,char b){
if(a=='i' && b=='i') return true;
if(a=='w' && b=='w') return true;
if(a=='(' && b==')') return true;
if(a==')' && b=='(') return true;
if(a=='{' && b=='}') return true;
if(a=='}' && b=='{') return true;
if(a=='[' && b==']') return true;
if(a==']' && b=='[') return true;
return false;
}

bool isSymmetry(const string &s){
int len=s.length();
if(len%2==0) return false;
rep(i,(len+1)/2) if(!match(s[i],s[len-i-1])) return false;
return s.find("iwi")!=string::npos;
}

int main(){
string s; cin>>s;
int n=s.length();

int ans=0;
rep(S,1<<n){
string t;
rep(i,n) if(S&(1<<i)) t+=s[i];
if(isSymmetry(t)) ans=max(ans,(int)t.length());
}
printf("%d\n",ans);

return 0;
}

文字列長が短いので、全部の部分列を調べても間に合う。
文字列中に "iwi" が入っているという条件を読み飛ばしていて、何回か WA を出してしまった。
実装しなかったけど、"iwi" の左右の部分文字列の LCS をとるという発想はあった。

D.
struct Stat{
int x,y,dir,mem;
Stat(){}
Stat(int X,int Y,int D,int M):x(X),y(Y),dir(D),mem(M){}
};

void update(int &x,int &y,int dir,int r,int c){
x=(x+dx[dir]+c)%c;
y=(y+dy[dir]+r)%r;
}

int main(){
int r,c; scanf("%d%d",&r,&c);
char prog[20][21];
rep(i,r) scanf("%s",prog[i]);

bool end=false;
bool visited[20][20][4][16]={};
queue<Stat> qu; qu.push(Stat(0,0,0,0));
while(!qu.empty()){
Stat s=qu.front(); qu.pop();
int x=s.x,y=s.y,dir=s.dir,mem=s.mem;

if(visited[x][y][dir][mem]) continue;
visited[x][y][dir][mem]=true;

if(prog[y][x]=='@'){ end=true; break; }

switch(prog[y][x]){
case '<':
dir=2;
update(x,y,dir,r,c);
qu.push(Stat(x,y,dir,mem));
break;

case '>':
dir=0;
update(x,y,dir,r,c);
qu.push(Stat(x,y,dir,mem));
break;

case '^':
dir=1;
update(x,y,dir,r,c);
qu.push(Stat(x,y,dir,mem));
break;

case 'v':
dir=3;
update(x,y,dir,r,c);
qu.push(Stat(x,y,dir,mem));
break;

case '_':
if(mem==0) dir=0;
else dir=2;
update(x,y,dir,r,c);
qu.push(Stat(x,y,dir,mem));
break;

case '|':
if(mem==0) dir=3;
else dir=1;
update(x,y,dir,r,c);
qu.push(Stat(x,y,dir,mem));
break;

case '?':
for(dir=0;dir<4;dir++){
int xx=x,yy=y;
update(xx,yy,dir,r,c);
qu.push(Stat(xx,yy,dir,mem));
}
break;

case '.':
update(x,y,dir,r,c);
qu.push(Stat(x,y,dir,mem));
break;

case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
mem=prog[y][x]-'0';
update(x,y,dir,r,c);
qu.push(Stat(x,y,dir,mem));
break;

case '+':
mem=(mem+1)%16;
update(x,y,dir,r,c);
qu.push(Stat(x,y,dir,mem));
break;

case '-':
mem=(mem-1+16)%16;
update(x,y,dir,r,c);
qu.push(Stat(x,y,dir,mem));
break;
}
}

puts(end?"YES":"NO");

return 0;
}

"等確率で" とか書かれていて一瞬怯んだけど、よく考えてみれば、全部の可能性を調べればいいだけだった。
今いる位置、方向、メモリの値の組を状態として BFS.

E.
int main(){
int n; scanf("%d",&n);
int a[1000],b[1000];
rep(i,n) scanf("%d%d",a+i,b+i);

int sum[1<<16]={};
rep(S,1<<n){
rep(i,n) if(S&(1<<i)) sum[S]+=a[i];
}

int dp[1<<16]={};
rep(S,1<<n){
rep(i,n) if((S&(1<<i))==0) {
if(sum[S]+a[i]<=b[i]){
dp[S|(1<<i)]=max(dp[S|(1<<i)],dp[S]+1);
}
}
}
printf("%d\n",*max_element(dp,dp+(1<<n)));

return 0;
}

ちょっと前の SRM Div.1 500 に似てるなーと思いながら。
解法は SRM の問題とほぼ同じだったのに、どの順でソートすればいいか最後までわからなかった。

上のコードは 20 点の解法。
指数時間の DP.
今 見直してみれば、dp[S] の意味づけがちょっと変だけど、一応正しく動く。

F.
int main(){
int n,k; scanf("%d%d",&n,&k);
if(n>8){ puts("-1"); return 0; }

int deg[8];
fill(deg,deg+n,n-1);
bool adj[8][8];
rep(u,n) rep(v,n) adj[u][v]=(u!=v);

int perm[8];
rep(i,n) perm[i]=i;
vector< vector<pii> > stree;
do{
int degmin=*min_element(deg,deg+n);
if(deg[perm[0]]!=degmin || deg[perm[n-1]]!=degmin) continue;

int i;
for(i=0;i<n-1;i++){
int u=perm[i],v=perm[i+1];
if(!adj[u][v]) break;
}
if(i<n-1) continue;

for(i=0;i<n;i++){
int u=perm[i];
if(i==0 || i==n-1){
if(deg[u]==0) break;
}
else{
if(deg[u]<=1) break;
}
}
if(i<n) continue;

vector<pii> path(n-1);
for(i=0;i<n-1;i++){
int u=perm[i],v=perm[(i+1)%n];
path[i]=mp(u,v);
adj[u][v]=adj[v][u]=false;
deg[u]--, deg[v]--;
}
stree.pb(path);
}while(next_permutation(perm,perm+n));

if(stree.size()<k) puts("-1");
else{
rep(t,k){
if(t>0) putchar('\n');
rep(i,stree[t].size()){
int u=stree[t][i].first,v=stree[t][i].second;
printf("%d %d\n",u+1,v+1);
}
}
}

return 0;
}

20 点の解法。
紙に色々書いていると、どうやら 1 本のパスになっている全域木を使うのがよさそうだと見当がついた。
なぜなら、パスであれば、全部の頂点の次数をほぼ均等に減らせるから。
(パスの端点に相当する 2 つの頂点だけは少し様子が違うけど)

そこで、次数が一番小さい頂点を 2 つ選んで、その点を端点としたパスになっている全域木を探すことにした。
それを求める個数の全域木が得られるまで繰り返した。
Greedy に選んでいいという確証はなかったけど、何となく大丈夫な気はした。

パスを探すのは、全部の順列を調べるという愚直な方法で。

G.
とりあえず、長さでソートした。
3 つ連続する棒を使えばいいんじゃないか? と思ったけど、それだと反例が見つかってダメだった。
2 10 20 25 99 100
とかだと、 2 99 100 で三角形を作ることができるから。

色々ぐだぐだと考えるも、結局、最後まで何も閃かず。


あとの問題はあまり考えてない。

解説を聞いた感じだと、I の 20 点分は解ける難易度だったという印象。
他は今の実力では苦しい。
特に、最後の 3 問はとても時間内に書ける気がしなかった。

感想

どの問題も凝っていて、考えがいがあった。
後半の問題はやっぱりかなり難しかったけど、赤い人たちにとってはこれくらいのほうがいいんだろうなーとか思ったり。
もっと精進しないと。

楽しいコンテストでした。ありがとうございました。 @ 実行委員会の皆様
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。