決して暇ではないし、なんか節目の時期であるわけでもなく、Advent Calendarシーズンですらないのに、唐突に変な記事を書きます。
Wolf Sotheとは？
昔のITMO Universityのアイスホッケーチームのユニフォーム。Edmonton Oilersと同じカラーリング。
このブログをわざわざ見ている人にはご存知かもしれませんが、Wolf Sotheというのは(特に僕がwriterをしているときによく登場する)プログラミングコンテストのキャラクターです。
例えば、以下のようなところに出没しています。
CODE FESTIVAL 2015 OKINAWA OPEN - CODE FESTIVAL 2015 OKINAWA OPEN | AtCoder
TopCoder Statistics - Match Overview SRM637 (non-tozangezanなWolf Sothe)
TopCoder Statistics - Problem Statement SRM690
本名は Tozan Southerpacks です。(pack: 狼の群れ) *1 現にプログラミングコンテスト上以外の彼(自分？)は、ほとんどTozanと呼ばれています。
いろいろあって彼はアイスホッケーが好きなんだそうです。
ちなみに、よくコンテストに持っていく狼のスモールマスコットはco-Sotheと言います。参考
おまけ
DCJが近いので本番で通せなかった問題を解いて振り返ったのでメモをば。
rps
これはまあ。使うノードの数を2のべきにする。ノードを使いすぎない。
#include<stdio.h> #include<algorithm> #include<message.h> #include"rps.h" using namespace std; /* USER'S GUIDE Num of data / node: 1000 Amount of data / node: 8MB HOW TO USE TOO COMPLICATED AND TOO DIFFICULT LIBRARIES python dcj/dcj.py test --source QUESTIONNAME.cpp --nodes NUMBER_OF_NODES FUNCTION LIBRARIES : int NumberOfNodes(); int MyNodeId(); void PutChar(int target, char value); void PutInt(int target, int value); void PutLL(int target, long long value); void Send(int target); : call this after using Put*** int Receive(int source); call this before using Get*** (return value: number of sended values) char GetChar(int source); int GetInt(int source); long long GetLL(int source); */ char ch[4200000]; long long ind[4200000]; int main(){ int T=NumberOfNodes(); int I=MyNodeId(); int N=GetN(); long long a=1LL<<N; int use=1; while(use*2<T&&use<a){ use*=2; } if(I==T-1){ for(int i=0;i<use;i++){ Receive(i); ch[i]=GetChar(i); ind[i]=GetLL(i); } int n=use; while(n>1){ int at=0; for(int i=0;i<n;i+=2){ if((ch[i]=='R'&&ch[i+1]=='P')||(ch[i]=='S'&&ch[i+1]=='R')||(ch[i]=='P'&&ch[i+1]=='S')){ ch[at]=ch[i+1]; ind[at]=ind[i+1]; }else{ ch[at]=ch[i]; ind[at]=ind[i]; } at++; } n/=2; } printf("%lld\n",ind[0]); }else if(I<use){ long long L=a/use*I; long long R=a/use*(I+1); for(long long i=L;i<R;i++){ ch[i-L]=GetFavoriteMove(i); ind[i-L]=i; } int n=R-L; while(n>1){ int at=0; for(int i=0;i<n;i+=2){ if((ch[i]=='R'&&ch[i+1]=='P')||(ch[i]=='S'&&ch[i+1]=='R')||(ch[i]=='P'&&ch[i+1]=='S')){ ch[at]=ch[i+1]; ind[at]=ind[i+1]; }else{ ch[at]=ch[i]; ind[at]=ind[i]; } at++; } n/=2; } PutChar(T-1,ch[0]); PutLL(T-1,ind[0]); Send(T-1); } }
necklace
2015finalの簡単枠。
substringのほうの文字列は短いことが大事。あとはここ1年で嫌という程見た「区間の左をiでスタートしたらどこまでいけるのか」をちまちま求めていく。
#include<stdio.h> #include<algorithm> #include<message.h> #include"necklace.h" using namespace std; /* USER'S GUIDE Num of data / node: 1000 Amount of data / node: 8MB HOW TO USE TOO COMPLICATED AND TOO DIFFICULT LIBRARIES python dcj/dcj.py test --source QUESTIONNAME.cpp --nodes NUMBER_OF_NODES FUNCTION LIBRARIES : int NumberOfNodes(); int MyNodeId(); void PutChar(int target, char value); void PutInt(int target, int value); void PutLL(int target, long long value); void Send(int target); : call this after using Put*** int Receive(int source); call this before using Get*** (return value: number of sended values) char GetChar(int source); int GetInt(int source); long long GetLL(int source); */ int str[10100000]; int in[3100]; int g[110][3100]; int sz[10100]; int q[10100][3010]; int to[3100]; int main(){ int T=NumberOfNodes(); int I=MyNodeId(); int N=GetNecklaceLength(); int M=GetMessageLength(); int L=(long long)N*I/T; int R=(long long)N*(I+1)/T; for(int i=L;i<R;i++)str[i-L]=GetNecklaceElement(i); for(int i=0;i<M;i++)in[i]=GetMessageElement(i); for(int i=0;i<=M;i++){ to[i]=i; if(i<M)q[in[i]][sz[in[i]]++]=i; } int n=R-L; for(int i=0;i<n;i++){ int t=str[i]; int ke=sz[t]; for(int j=0;j<ke;j++){ to[q[t][j]]++; } sz[t]=0; for(int j=0;j<ke;j++){ if(to[q[t][j]]>=M)continue; q[in[to[q[t][j]]]][sz[in[to[q[t][j]]]]++]=q[t][j]; } } if(I==0){ for(int i=0;i<=M;i++)g[0][i]=to[i]; for(int i=1;i<T;i++){ Receive(i); for(int j=0;j<=M;j++)g[i][j]=GetInt(i); } int ret=0; for(int i=0;i<M;i++){ int now=i; for(int j=0;j<T;j++){ now=g[j][now]; } ret=max(ret,now-i); } printf("%d\n",ret); }else{ for(int i=0;i<=M;i++)PutInt(0,to[i]); Send(0); } }
johnny
考察のほうが大事で、distribution要素はほぼない。
出次数が小さい順にソートして、左端から到達できる範囲の右端がどこかを探す。到達できない頂点がjohnnyの手札。
実は、転送するデータ量が結構厳しめ。一つ前のノードから受け取って一つ後のノードに転送すると、ノードあたりの通信量は抑えられるが、これは時間がかかるのでTLEする。
結局押し込むのが正解。charはsignedなので気をつける。
#include<stdio.h> #include<algorithm> #include<message.h> #include"johnny.h" using namespace std; /* USER'S GUIDE Num of data / node: 1000 Amount of data / node: 8MB HOW TO USE TOO COMPLICATED AND TOO DIFFICULT LIBRARIES python dcj/dcj.py test --source QUESTIONNAME.cpp --nodes NUMBER_OF_NODES FUNCTION LIBRARIES : int NumberOfNodes(); int MyNodeId(); void PutChar(int target, char value); void PutInt(int target, int value); void PutLL(int target, long long value); void Send(int target); : call this after using Put*** int Receive(int source); call this before using Get*** (return value: number of sended values) char GetChar(int source); int GetInt(int source); long long GetLL(int source); */ int out[21000]; pair<int,int> p[21000]; int at[21000]; int rev[21000]; int lm[21000]; bool is[210][21000]; int main(){ int T=NumberOfNodes(); int I=MyNodeId(); int N=NumberOfCards(); int L=N*I/T; int R=N*(I+1)/T; for(int i=L;i<R;i++){ for(int j=0;j<N;j++){ if(IsBetter(i,j)){ out[i]++; is[i-L][j]=true; } } } if(I==0){ for(int i=1;i<T;i++){ int left=N*i/T; int right=N*(i+1)/T; Receive(i); for(int j=left;j<right;j++)out[j]=GetInt(i); } for(int i=0;i<N;i++)p[i]=make_pair(out[i],i); std::sort(p,p+N); for(int j=1;j<T;j++){ for(int i=0;i<N;i++){ PutChar(j,p[i].second/256); PutChar(j,p[i].second%256); at[i]=p[i].second; } Send(j); } }else{ for(int i=L;i<R;i++)PutInt(0,out[i]); Send(0); Receive(0); for(int i=0;i<N;i++){ at[i]=GetChar(0); if(at[i]<0)at[i]+=256; at[i]*=256; int tt=GetChar(0); if(tt<0)tt+=256; at[i]+=tt; } } for(int i=0;i<N;i++)lm[i]=rev[i]; for(int i=0;i<N;i++)rev[at[i]]=i; for(int i=L;i<R;i++){ for(int j=0;j<N;j++){ if(is[i-L][j]){ lm[i]=max(lm[i],rev[j]); } } } if(I==0){ for(int i=1;i<T;i++){ int left=N*i/T; int right=N*(i+1)/T; Receive(i); for(int j=left;j<right;j++)lm[j]=GetInt(i); } int tmp=0; for(int i=0;i<N;i++){ if(tmp<i)break; tmp=max(tmp,lm[p[i].second]); } if(tmp==N-1)printf("IMPOSSIBLE\n"); else printf("%d\n",N-tmp-1); }else{ for(int i=L;i<R;i++)PutInt(0,lm[i]); Send(0); } }
gold
2016final、2番目に簡単とはいえ、これが解ければ入賞できる。
基本アイデアは「範囲[L,R]が与えられた時、その中に金が埋まってるかを判定し、埋まってるならどこか一つの場所を返す」のをlogで求める方針。
両端の文字で場合分けすると2段階の処理で済むことになる。
特定の場所に偏りすぎだとあるノードで探す金の個数が多すぎるが、これはある程度多い時は諦め、再度親ノードに戻ってきて多かった場所をさらに分割してやり直せばよい。
打ち切りは何回くらいがいいのか多分真面目にやったら解析できるが、practiceにはlargeにフィードバックがあるのでサボった。
#include<stdio.h> #include<algorithm> #include<queue> #include<message.h> #include"gold.h" using namespace std; /* USER'S GUIDE Num of data / node: 1000 Amount of data / node: 8MB Send, Receive / 5 ~ 10ms? Linear Message passing: slow (500ms through every nodes) HOW TO USE TOO COMPLICATED AND TOO DIFFICULT LIBRARIES python dcj/dcj.py test --source QUESTIONNAME.cpp --nodes NUMBER_OF_NODES FUNCTION LIBRARIES : int NumberOfNodes(); int MyNodeId(); void PutChar(int target, char value); void PutInt(int target, int value); void PutLL(int target, long long value); void Send(int target); : call this after using Put*** int Receive(int source); call this before using Get*** (return value: number of sended values) char GetChar(int source); int GetInt(int source); long long GetLL(int source); */ long long bs(long long L,long long R){ while(1){ long long M=(L+R)/2; char tmp=Search(M); if(tmp=='X')return M; if(L+1>=R)return -1; if(tmp!='>')R=M; else L=M+1; } } long long chk(long long L,long long R){ if(L>=R)return -1; char Lc=Search(L); if(Lc=='X')return L; char Rc=Search(R-1); if(Rc=='X')return R-1; if(L+1==R)return -1; if(Lc!='<'&&Rc!='>'){ return bs(L,R); } long long bl=L; long long br=R; if(Lc=='<'){ long long ks=1; while(1){ bl+=ks; ks*=2; if(bl>=R)break; char cc=Search(bl); if(cc=='X')return bl; if(cc!='<')break; } } if(Rc=='>'){ long long ks=1; while(1){ br-=ks; ks*=2; if(bl>=br)break; char cc=Search(br-1); if(cc=='X')return br-1; if(cc!='>')break; } } if(bl>=br)return -1; return bs(bl,br); } long long solve(long long L,long long R){ long long ret=0; int cnt=0; queue<pair<long long,long long> > Q; Q.push(make_pair(L,R)); while(Q.size()){ pair<long long,long long> at=Q.front();Q.pop(); if(at.first>=at.second)continue; long long tmp=chk(at.first,at.second); if(tmp>=0){ cnt++; ret^=tmp; Q.push(make_pair(at.first,tmp)); Q.push(make_pair(tmp+1,at.second)); } if(cnt==10000)break; } if(cnt==10000){ return -1; } return ret; } int main(){ int T=NumberOfNodes(); int I=MyNodeId(); int N=NumberOfNuggets(); long long L=RoadLength(); //printf("%d\n",I); if(I==T-1){ vector<pair<long long,long long > >Q[10]; long long ret=0; Q[0].push_back(make_pair(0,L)); for(int i=0;i<9;i++){ for(int j=0;j<Q[i].size();j++){ long long n=Q[i][j].second-Q[i][j].first; for(int k=0;k<T-1;k++){ long long left=Q[i][j].first+n*k/(T-1); long long right=Q[i][j].first+n*(k+1)/(T-1); PutLL(k,left); PutLL(k,right); } } for(int j=0;j<T-1;j++){ PutLL(j,-1); PutLL(j,-1); Send(j); } for(int j=0;j<T-1;j++){ Receive(j); for(int k=0;k<Q[i].size();k++){ long long tmp=GetLL(j); if(tmp<0){ long long n=Q[i][k].second-Q[i][k].first; long long left=Q[i][k].first+n*j/(T-1); long long right=Q[i][k].first+n*(j+1)/(T-1); if(left<right){ Q[i+1].push_back(make_pair(left,right)); } }else ret^=tmp; } GetLL(j); } } printf("%lld\n",ret); }else{ for(int i=0;i<9;i++){ Receive(T-1); while(1){ long long left=GetLL(T-1); long long right=GetLL(T-1); if(left<0)break; long long ret=solve(left,right); // printf("%lld %lld: %lld\n",left,right,ret); PutLL(T-1,ret); } PutLL(T-1,-1); Send(T-1); } } }
