スポンサーサイト

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

Xmas Contest 2011

2011/12/24 14:15 ~ 19:15 (JST)
Xmas Contest 2011 の参加記録

書こう書こうと思いつつずっと放置していた。

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

結果

各問題には 25 点の部分点がある。

A.  25 (02:56)
B. 100 (00:35)
C.  25 (02:19)
D.  25 (02:24)
E. 100 (00:17)
F. 100 (04:46)
G.  25 (03:13)
H.   -

Standing : 14/105


昨年はひどい結果だったので、成長した感があってよい。

問題

ここ

解答と感想

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

A. ( 部分点 )
map<ll,int> factorize(ll a){
map<ll,int> res;
for(ll p=2;p*p<=a;p++) if(a%p==0) {
int cnt=0;
do{ a/=p; cnt++; }while(a%p==0);
res[p]=cnt;
}
if(a>1) res[a]=1;
return res;
}

int main(){
srand(777);
string color[150];
rep(i,150){
int l=rand()%10+1;
rep(j,l) color[i]+='a'+rand()%26;
}

ll x; cin>>x;
if(x==1){
cout<<1<<endl<<"fnyrbtctst"<<endl;
return 0;
}

map<ll,int> pf=factorize(x);
map<ll,int>::iterator it;
int sum=0,c=0;
for(it=pf.begin();it!=pf.end();++it) sum+=it->first*it->second;
cout<<sum<<endl;
for(it=pf.begin();it!=pf.end();++it) rep(i,it->second) {
rep(j,it->first) cout<<color[c]<<endl;
c++;
}

return 0;
}

いつもと違った感じの出題でおもしろい。
でも解けない。
数論むずい。

部分点だけなら、素因数分解して適当に何かやるだけで取れる。
ブログを書くのが遅すぎてあんまり覚えてない...
乱数を使ってるんだけど、当時の自分は何を考えていたんだろう?

N=1 がコーナーケース。
funny rabbit contest

B. ( 満点 )
const int INF=(int)(1e9+1);

template<class T> struct Edge{
int v;
T w;
Edge(int V,T W):v(V),w(W){}
};

template<class T>
struct AdjList:public vector< vector< Edge<T> > >{
AdjList(int n):vector< vector< Edge<T> > >(n){}
};

template<class T>
T ijk(const AdjList<T> &adj,int s,int t){
int n=adj.size();
vector<T> d(n,INF); d[s]=0;

priority_queue< pair<T,int> > pq; pq.push(make_pair(0,s));
while(!pq.empty()){
pair<T,int> a=pq.top(); pq.pop();
int u=a.second;
if(d[u]<-a.first) continue;
if(u==t) break;

rep(i,adj[u].size()){
int v=adj[u][i].v;
T w=adj[u][i].w;
if(d[u]+w<d[v]){
d[v]=d[u]+w;
pq.push(make_pair(-d[v],v));
}
}
}

return d[t];
}

int main(){
int n,m,d,s,t; scanf("%d%d%d%d%d",&n,&m,&d,&s,&t);
AdjList<int> adj(n);
rep(u,n-1){
adj[u].push_back(Edge<int>(u+1,d));
adj[u+1].push_back(Edge<int>(u,d));
}
rep(i,m){
int u,v,w; scanf("%d%d%d",&u,&v,&w);
adj[u].push_back(Edge<int>(v,w));
adj[v].push_back(Edge<int>(u,w));
}

printf("%d\n",ijk(adj,s,t));

return 0;
}

部分点なら、Warshall-Floyd するだけでいい。

満点を取るためには、グラフの形の特殊性を利用する。
2 点間の距離が線形に増えているので、隣接する 2 点のみ辺を張れば、グラフのすべての情報を表現できる。
なので、辺数は M+N 程度に抑えられて、Dijkstra 法が間に合う。

C. ( 部分点 )
// a == p^m (p:prime)
bool check(int a,int *pp,int *mm){
int c=0;
for(int p=2;p<=a;p++) if(a%p==0) {
*mm=0;
do{ a/=p; (*mm)++; }while(a%p==0);
*pp=p;
c++;
}
return c==1;
}

int main(){
int n; scanf("%d",&n);
int p,m;
if(!check(n,&p,&m)) puts("NO");
else{
if(m==1){
rep(a,n) rep(b,n) printf("%d%c",(a+b)%n,b<n-1?' ':'\n');
rep(a,n) rep(b,n) printf("%d%c",(a*b)%n,b<n-1?' ':'\n');
}
else if(n==4){
puts("0 1 2 3");
puts("1 0 3 2");
puts("2 3 0 1");
puts("3 2 1 0");
puts("0 0 0 0");
puts("0 1 2 3");
puts("0 2 3 1");
puts("0 3 1 2");
}
else if(n==8){
puts("0 1 2 3 4 5 6 7");
puts("1 0 3 2 5 4 7 6");
puts("2 3 0 1 6 7 4 5");
puts("3 2 1 0 7 6 5 4");
puts("4 5 6 7 0 1 2 3");
puts("5 4 7 6 1 0 3 2");
puts("6 7 4 5 2 3 0 1");
puts("7 6 5 4 3 2 1 0");
puts("0 0 0 0 0 0 0 0");
puts("0 1 2 3 4 5 6 7");
puts("0 2 4 6 5 7 1 3");
puts("0 3 6 5 1 2 7 4");
puts("0 4 5 1 7 3 2 6");
puts("0 5 7 2 3 6 4 1");
puts("0 6 1 7 2 4 3 5");
puts("0 7 3 4 6 1 5 2");
}
else if(n==9){
puts("0 1 2 3 4 5 6 7 8");
puts("1 2 0 4 5 3 7 8 6");
puts("2 0 1 5 3 4 8 6 7");
puts("3 4 5 6 7 8 0 1 2");
puts("4 5 3 7 8 6 1 2 0");
puts("5 3 4 8 6 7 2 0 1");
puts("6 7 8 0 1 2 3 4 5");
puts("7 8 6 1 2 0 4 5 3");
puts("8 6 7 2 0 1 5 3 4");
puts("0 0 0 0 0 0 0 0 0");
puts("0 1 2 3 4 5 6 7 8");
puts("0 2 1 6 8 7 3 5 4");
puts("0 3 6 2 5 8 1 4 7");
puts("0 4 8 5 6 1 7 2 3");
puts("0 5 7 8 1 3 4 6 2");
puts("0 6 3 1 7 4 2 8 5");
puts("0 7 5 4 2 6 8 3 1");
puts("0 8 4 7 3 2 5 1 6");
}
}
return 0;
}

おもしろそうと思って飛びついた。
まず、問題の条件は f を和, g を積と思ったとき、集合が整域の構造をもつということ。
といっても今の自分の知識ではここらが限界。代数に関してはほとんど無知。

大学の講義ノートを引っ張り出してきて、ネットの情報とあわせていろいろ調べる。
すると、
・ 有限整域は体
・ 有限体は次数 p^n ( p は素数, n は正整数 ) のものに限られる
ということがわかった。

次数が素数のときは、普通の和と積で mod N したものを考えればいい。
一般の場合はそうはいかなくて、変なパターンがある。
一般の次数の有限体の演算表を求める方法を調べたけど、既約多項式とか出てきてよくわからない。

ここであきらめて、N ≦ 9 だけ埋め込んで部分点をもらう戦略に切り替えた。
N が小さいときの演算表は、本当はよくないけど Wolfram Alpha に頼った。
GF(8) とかで検索すると出る。

ちなみに、問題タイトルの integral domain は日本語で整域。

D. ( 部分点 )
bool isPalindrome(const string &s){
int n=s.length();
for(int i=0,j=n-1;i<j;i++,j--) if(s[i]!=s[j]) return false;
return true;
}

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

if(n>15){
cout<<"difficult"<<endl;
return -1;
}

string ans=s;
rep(S,1<<n){
string s1,s2;
rep(i,n) if(S&(1<<i)) s1+=s[i]; else s2+=s[i];
if(isPalindrome(s1)) ans=min(ans,s2);
}
cout<<ans<<endl;

return 0;
}

これもまったくわからないので、とりあえず全探索して部分点だけもらった。

E. ( 満点 )
int main(){ int n,k; scanf("%d%d ",&n,&k); printf("%d\n",k-(n-2*k)); return 0; }

ややこしく見えるけど、accepted 以外は出力の文字列が一つ増えるので、N と L だけから逆算できる。
( コンテスト中はもう少し変なことを考えていた気がする )

F. ( 満点 )
const ll INF=1LL<<61;

int main(){
int n,m;
ll D; scanf("%d%d%lld",&n,&m,&D);

if(n>15){
static vector<ll> cost[100000];
rep(i,m){
int u,v,c; scanf("%d%d%d",&u,&v,&c);
cost[u].push_back(c);
cost[v].push_back(c);
}

ll ans=n*D;
rep(u,n){
sort(cost[u].begin(),cost[u].end());
// 頂点 u を通るのに、コストが D より大きいの辺を 2 つ使う
if(cost[u].size()==n-1){
ans=max(ans,min((n-1)*D+2*cost[u][0],(n-2)*D+cost[u][0]+cost[u][1]));
}
// 頂点 u を通るのに、コストが D より大きいの辺を 1 つ使う
else if(cost[u].size()==n-2){
ans=max(ans,min((n+1)*D,(n-1)*D+cost[u][0]));
}
}
printf("%lld\n",ans);

return 0;
}

ll d[15][15];
rep(u,n) rep(v,n) d[u][v]=(u==v?0:D);
rep(i,m){
int u,v,c; scanf("%d%d%d",&u,&v,&c);
d[u][v]=d[v][u]=c;
}

rep(k,n) rep(i,n) rep(j,n) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

static ll dp[1<<15][15];
rep(S,1<<n) rep(u,n) dp[S][u]=INF;
rep(u,n) dp[1<<u][u]=d[0][u];
rep(S,1<<n) rep(u,n) {
rep(v,n) if((S&(1<<v))==0) {
dp[S|(1<<v)][v]=min(dp[S|(1<<v)][v],dp[S][u]+d[u][v]);
}
}
printf("%lld\n",dp[(1<<n)-1][0]);

return 0;
}

もちろん、制約 M ≦ N が重要。
これがないと、頂点数 10^5 の完全グラフの TSP になって本当に無理ゲーになる。

まず、部分点 ( N ≦ 15 ) は bit DP でできる。これは有名。

N が大きい場合はどうするか?
M ≦ N なので、直感的にはほとんどの辺がコスト D であることになる。
ということは、ほとんどの頂点にはコスト 2D で行って帰ってくることができるだろう、と思う。
危ない頂点はせいぜい 1 個くらい。
なので、危なそうな頂点だけを全部調べればいい。

嘘解法だと思って投げていたので、AC したときには声が出そうになった。

O(N+M) くらいでできる。
自分の実装はソートしているのでもう少し悪いオーダーになっている。

G. ( 部分点 )
int m,n,a,b,x[1024],y[64];
int from[6];

int rec(int i){
if(i==n){
bool ok=true;
rep(j,a){
int num=0;
rep(k,n) if(x[j]&(1<<from[k])) num|=1<<k;
if(find(y,y+b,num)==y+b) ok=false;
}
return ok?1:0;
}

int sum=0;
rep(j,m){
from[i]=j;
sum+=rec(i+1);
}
return sum;
}

int main(){
int T; scanf("%d",&T);
while(T--){
scanf("%d%d%d%d",&m,&n,&a,&b);
rep(i,a) scanf("%d",x+i);
rep(i,b) scanf("%d",y+i);
printf("%d\n",rec(0));
}
return 0;
}

数字が小さいので、DFS で全探索して部分点だけもらった。
枝刈りすれば通りそうな雰囲気だったけど、満点出してる人が少なかったので見送った。

H.

取り組んでいない。
H 自身の出力が絡んでいるあたり、かなり複雑そう。



復習はきっちりやりましょう。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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