スポンサーサイト

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

The Caribbean Training Contest #30

2011/12/09 04:00 ~ 07:00 (JST)
COJ でコンテストがあったので参加した。

日本人は自分を含めて 2 人しか参加していなかった。
まわりはキューバの人ばかりでびびった。

難易度は比較的やさしい。

Tags : プログラミング COJ

結果

7 問。
ICPC ルール。

A. -
B. WA, AC (00:28)
C. 2WA, AC (02:32)
D. 3WA, AC (00:51)
E. AC (01:14)
F. WA
G. AC (02:17)
Standing : 2/36


コンテスト終了時は一位だったのに、今見たら 1 つ落ちていた。
リジャッジされたのかもしれない。残念。

問題

問題セットの原文はここを参照。

A. Interest Targeting

二つの表が与えられるのでそれらを結合してできる表を出力せよ。

表 1 は
70000 行以下、4 列からなり、各列は
user_id, category_id, create_time, heuristic_ctr
と名前がついている。

表 2 は
70000 行以下、5 列からなり、各列は
user_id, category_id, adv_id, show_time, click_flag
と名前がついている。

表 2 の各行に対して、マッチする表 1 の行があればそれら 2 つの行を結合して、出力する。
ここで、「マッチする」 とは user_id, category_id が一致し、かつ create_time < show_time であることを指す。
条件をみたす表 1 の行が複数ある場合は show_time - create_time が最小になるものが選ばれる。

出力する順番は
heuristic_ctr, user_id, category_id, create_time, adv_id, show_id
の辞書式順序。

B. Triple Fat Ladies

3 乗したときに下 3 桁が 888 となるような自然数のうち、k 番目に小さいものを求めよ。

1 ≦ k ≦ 2 trillion

C. Prison Break

n 個の部屋と、それらをつなぐ m 本の廊下がある。
廊下は双方向に移動できる。
部屋には 1, 2, ..., n と番号がついている。
k 個の相異なる部屋にそれぞれ人がいる。
部屋 n は出口であって、そこには人はいない。

廊下を爆破して、すべての人が出口にたどり着けないようにしたい。
最小でいくつの廊下を爆破すればいいか?

1 ≦ n ≦ 1000
1 ≦ m ≦ 100000
1 ≦ k ≦ 10

D. Fire

R × C のフィールドがある。
各マスは、何もない、火、壁のいずれか。
自分は 4 方向に隣接する何もないマスにだけ移動できる。
自分が 1 歩移動するごとに、フィールドにあるすべての火が 4 方向すべてについて 1 マス拡散する。
ただし、火は壁を越えられない。
フィールドの端に着くための最小歩数を求めよ。できない場合はそれを報告せよ。

1 ≦ R, C ≦ 1000

E. Sea Travel

R × C のフィールド ( 海 ) がある。
各マスには、海流の方向 ( 8 方向 ) が割り当てられている。
海流と同じ方向にはコスト 0 で、それ以外の方向にはコスト 1 で移動できる。

N 個のクエリ
・ マス (rs, cs) からマス (rd, cd) に移動するときの最小コストを求める
を処理せよ。

1 ≦ R, C ≦ 1000
1 ≦ N ≦ 50

F. Lucas

X = { 1, 2, ..., N } とおく。
X から X への写像が 2 つ与えられる。
これを f, g と書く。

X の部分集合 S で S = f (S) = g (S) となるもののうち、要素数最大のもの ( の要素数 ) を求めよ。

1 ≦ N ≦ 105

G. Cos(NA)

自然数 N について
cos (NA) を cos (A) の多項式で書け。

1 ≦ N ≦ 50

解答

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

A. ( あとで解いた )
struct Row{
int user_id,category_id,create_time,heuristic_ctr,adv_id,show_time,click_flag;
};

bool cmp1(const Row &a,const Row &b){
if(a.user_id!=b.user_id) return a.user_id<b.user_id;
if(a.category_id!=b.category_id) return a.category_id<b.category_id;
return a.create_time<b.create_time;
}

bool cmp2(const Row &a,const Row &b){
if(a.heuristic_ctr!=b.heuristic_ctr) return a.heuristic_ctr<b.heuristic_ctr;
if(a.user_id!=b.user_id) return a.user_id<b.user_id;
if(a.category_id!=b.category_id) return a.category_id<b.category_id;
if(a.create_time!=b.create_time) return a.create_time<b.create_time;
if(a.adv_id!=b.adv_id) return a.adv_id<b.adv_id;
return a.show_time<b.show_time;
}

int main(){
int n,m; scanf("%d%d",&n,&m);
static Row row[70000];
rep(i,n){
int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d);
row[i]=(Row){a,b,c,d};
}
sort(row,row+n,cmp1);

int k=0;
static Row ans[70000];
rep(i,m){
int a,b,c,d,e; scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
int j=lower_bound(row,row+n,(Row){a,b,d},cmp1)-row-1;
if(~j && row[j].user_id==a && row[j].category_id==b){
ans[k++]=(Row){a,b,row[j].create_time,row[j].heuristic_ctr,c,d,e};
}
}
sort(ans,ans+k,cmp2);

printf("%d\n",k);
rep(i,k) printf("%d %d %d %d %d %d %d\n",ans[i].user_id,ans[i].category_id,ans[i].create_time,ans[i].heuristic_ctr,ans[i].adv_id,ans[i].show_time,ans[i].click_flag);

return 0;
}

コンテスト中は誰も手を着けていなかったので問題文すら読まなかったけど、読んでみたらふつうに書くだけだった。
二分探索。

B.
int main(){
const int low[]={192,442,692,942};

int T; scanf("%d",&T);
while(T--){
ll k; scanf("%lld",&k); k--;
if(k>=4) printf("%lld",k/4);
printf("%d\n",low[k%4]);
}

return 0;
}

下 3 桁を見るということは、mod 1000 を考えるということ。
なので、明らかに 1000 以上の桁はどうでもいい。
1000 以下について全探索すれば、192, 442, 692, 942 が題意をみたすことがわかる。

C.
template<class T> struct Edge{
int v,rev;
T capa,flow;
};

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

template<class T>
void add_edge(AdjList<T> &adj,int u,int v,T capa){
adj[u].push_back((Edge<T>){v,adj[v].size() ,capa,0});
adj[v].push_back((Edge<T>){u,adj[u].size()-1,capa,0});
}

template<class T>
T augment(AdjList<T> &adj,int s,int t){
int n=adj.size();
vector<int> pre(n);
vector<bool> vis(n); vis[s]=true;

queue< pair<int,T> > qu;
qu.push(make_pair(s,INF));

T res=0;
while(!qu.empty()){
int u=qu.front().first;
T water=qu.front().second;
qu.pop();

if(u==t){ res=water; break; }

rep(i,adj[u].size()){
Edge<T> &e=adj[u][i];
if(!vis[e.v] && e.capa-e.flow>0){
vis[e.v]=true;
pre[e.v]=e.rev;
qu.push(make_pair(e.v,min(water,e.capa-e.flow)));
}
}
}

if(res>0){
for(int v=t;v!=s;){
Edge<T> &e1=adj[v][pre[v]];
Edge<T> &e2=adj[e1.v][e1.rev];
e1.flow-=res;
e2.flow+=res;
v=e1.v;
}
}

return res;
}

template<class T>
T Edmonds_Karp(AdjList<T> &adj,int s,int t){
T ans=0;
for(T water=1;water>0;ans+=water) water=augment(adj,s,t);
return ans;
}

int main(){
for(int n,m,k;~scanf("%d%d%d",&n,&m,&k);){
int src=n,snk=n-1;
AdjList<int> adj(n+1);
rep(i,k){
int u; scanf("%d",&u); u--;
add_edge(adj,src,u,INF);
}
rep(i,m){
int u,v; scanf("%d%d",&u,&v); u--; v--;
add_edge(adj,u,v,1);
}

printf("%d\n",Edmonds_Karp(adj,src,snk));
}

return 0;
}

グラフの最小カットそのものなので、適当にグラフを作って最大流を流す。
コードはお手製 Edmonds-Karp。
遅い。

D.
const int INF=1<<29;
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

struct P{ int x,y; };

int main(){
int h,w; scanf("%d%d",&h,&w);
static char B[1000][1001];
int jx,jy;
rep(i,h){
scanf("%s",B[i]);
rep(j,w) if(B[i][j]=='J') jx=j, jy=i;
}

// fire BFS
static int fire[1000][1000];
rep(i,h) rep(j,w) fire[i][j]=INF;

queue<P> qu;
rep(i,h) rep(j,w) if(B[i][j]=='F') qu.push((P){j,i}), fire[i][j]=0;
while(!qu.empty()){
int x=qu.front().x,y=qu.front().y; qu.pop();

rep(k,4){
int xx=x+dx[k],yy=y+dy[k];
if(0<=xx && xx<w && 0<=yy && yy<h
&& B[yy][xx]!='#' && fire[yy][xx]>fire[y][x]+1){
fire[yy][xx]=fire[y][x]+1;
qu.push((P){xx,yy});
}
}
}

// Joe BFS
static int t[1000][1000];
rep(i,h) rep(j,w) t[i][j]=(i==jy&&j==jx?0:INF);

qu=queue<P>(); qu.push((P){jx,jy});
while(!qu.empty()){
int x=qu.front().x,y=qu.front().y; qu.pop();

rep(k,4){
int xx=x+dx[k],yy=y+dy[k];
if(!(0<=xx && xx<w && 0<=yy && yy<h)){
printf("%d\n",t[y][x]+1);
return 0;
}
if(B[yy][xx]!='#' && fire[yy][xx]>t[y][x]+1 && t[yy][xx]>t[y][x]+1){
t[yy][xx]=t[y][x]+1;
qu.push((P){xx,yy});
}
}
}

puts("IMPOSSIBLE");

return 0;
}

火が各マスに到達するまでのターン数をあらかじめ BFS で求めておく。
あとは、自分の動きをふつうに BFS で調べればよい。
O(RC).

気分は AOJ 2008 : Dragon Fantasy に似ている。 ( 解法は違う )

・ 火が 1 つしかない
・ 火が壁を突き抜ける
などの仮定を勝手においたために何回か WA した。

E.
const int INF=1<<29;
const int dx[]={0,1,1,1,0,-1,-1,-1},dy[]={-1,-1,0,1,1,1,0,-1};

struct P{
int x,y,cost;
bool operator<(const P &p)const{ return cost>p.cost; }
};

int main(){
int h,w; scanf("%d%d",&h,&w);
static char B[1000][1001];
rep(i,h) scanf("%s",B[i]);

int T; scanf("%d",&T);
while(T--){
int sy,sx,gy,gx; scanf("%d%d%d%d",&sy,&sx,&gy,&gx); sy--; sx--; gy--; gx--;

static int d[1000][1000];
rep(i,h) rep(j,w) d[i][j]=INF;
d[sy][sx]=0;

priority_queue<P> pq; pq.push((P){sx,sy,0});
while(!pq.empty()){
int x=pq.top().x,y=pq.top().y,cost=pq.top().cost; pq.pop();

if(d[y][x]<cost) continue;
if(y==gy && x==gx) break;

rep(k,8){
int xx=x+dx[k],yy=y+dy[k];
if(0<=yy && yy<h && 0<=xx && xx<w){
int cost2=cost+(B[y][x]-'0'==k?0:1);
if(cost2<d[yy][xx]){
d[yy][xx]=cost2;
pq.push((P){xx,yy,cost2});
}
}
}
}

printf("%d\n",d[gy][gx]);
}

return 0;
}

いい方法が思いつかなかったので、各クエリごとにふつうに Dijkstra した。
計算量を見積もるとぎりぎり間に合うかどうかという感じだけど、最悪ケースはなかったようで余裕をもって通った。

F. ( あとで解いた )
bool vis[100000];
vector<int> order;

void dfs(int u,const vector< vector<int> > &adj){
vis[u]=true;
rep(i,adj[u].size()){
int v=adj[u][i];
if(!vis[v]) dfs(v,adj);
}
order.push_back(u);
}

void rdfs(int u,const vector< vector<int> > &radj,vector<int> &com){
vis[u]=true;
rep(i,radj[u].size()){
int v=radj[u][i];
if(!vis[v]) rdfs(v,radj,com);
}
com.push_back(u);
}

vector< vector<int> > SCC(const vector< vector<int> > &adj){
int n=adj.size();
order.clear();
rep(u,n) vis[u]=false;
rep(u,n) if(!vis[u]) dfs(u,adj);

vector< vector<int> > radj(n);
rep(u,n) rep(i,adj[u].size()) radj[adj[u][i]].push_back(u);

vector< vector<int> > res;
rep(u,n) vis[u]=false;
for(int i=n-1;i>=0;i--){
int u=order[i];
vector<int> com;
if(!vis[u]){
rdfs(u,radj,com);
res.push_back(com);
}
}
return res;
}

class UnionFind{
vector<int> a;
public:
UnionFind(int n):a(n,-1){}
int find(int x){
if(a[x]<0) return x;
return a[x]=find(a[x]);
}
void unite(int x,int y){
x=find(x),y=find(y);
if(x!=y){ a[x]+=a[y]; a[y]=x; }
}
int size(int x){ return -a[find(x)]; }
};

int main(){
int n,a[100000]; scanf("%d",&n);
rep(i,n) scanf("%d",a+i), a[i]--;

UnionFind uf(n);
static bool bad[100000];
vector< vector<int> > adj(n,vector<int>(1));
rep(_,2){
rep(i,n) scanf("%d",&adj[a[i]][0]), adj[a[i]][0]--;

vector< vector<int> > scc=SCC(adj);

rep(i,scc.size()){
int u=scc[i][0];
if(scc[i].size()==1 && adj[u][0]!=u) bad[u]=true;
rep(j,scc[i].size()) uf.unite(u,scc[i][j]);
}
}

static bool bad_root[100000];
rep(u,n) if(bad[u]) bad_root[uf.find(u)]=true;

int ans=n;
static bool checked[100000];
rep(u,n){
int r=uf.find(u);
if(!checked[r]){
if(!bad_root[r]) ans-=uf.size(r);
checked[r]=true;
}
}
printf("%d\n",ans);

return 0;
}

電車の中なんかで考えてたら一応解けた。
他の人はより速い、より短いコードで正解しているので、もっとうまい方法があるはずで、自分のはたぶん別解。

まず 1 つの写像だけに注目する。
写像を n 頂点の有向グラフと思う。
すなわち、対応 i → f (i) があるとき、i から f (i) への有向辺を張る。
( functional graph と呼ばれる )

このグラフにおける強連結成分は 1 つのループか 1 つの頂点かのどちらか。
このループ内における頂点を 1 つでも残そうとすると、ループ内のすべての頂点を残さないといけない。
1 つの頂点からなる成分は選んでもいいものと選んではいけないものの 2 種類がある。 ( 自己ループがあるものは選んでもいい )

この強連結成分分解を 2 つの写像それぞれについて行う。
たとえば、写像 f に 3 -> 4 -> 5 -> 3 というループがあり、写像 g に 5 -> 1 -> 2 -> 5 というループがあったとする。
このとき、1, 2, 3, 4, 5 のひとつでも残そうとすれば、他の 4 つもすべて残さないといけない。

なので、この情報を Union-Find で管理して、一緒に選ばなければいけない頂点の集合を 1 つにまとめる。

最後に選べるだけ選ぶ。

計算量は Union-Find が支配的で、自分の実装では O(n log n) になる。

G.
typedef long long  ll;
typedef vector<ll> poly;

poly operator*(ll c,poly p){
rep(i,51) p[i]*=c;
return p;
}

poly operator*(poly p,poly q){
poly r(51);
rep(i,51) rep(j,51) if(p[i]*q[j]!=0) r[i+j]+=p[i]*q[j];
return r;
}

poly f(int n){
poly res(51);
if (n==0) res[0]=1;
else if(n==1) res[1]=1;
else if(n%2==0){
res=2*f(n/2)*f(n/2);
res[0]--;
}
else{
res=2*f(n/2+1)*f(n/2);
res[1]--;
}
return res;
}

int main(){
for(int n;scanf("%d",&n),n;){
poly ans=f(n);
bool first=true;
for(int i=50;i>=0;i--) if(ans[i]!=0) {
if(!first || ans[i]<0){
if(ans[i]>0) putchar('+');
else putchar('-'), ans[i]*=-1;
}
if(i==0 || ans[i]>=2) printf("%lld",ans[i]);
if(i>=1){
printf("Cos");
if(i>=2) printf("^%d",i);
printf("(A)");
}
first=false;
}
putchar('\n');
}

return 0;
}

加法定理とか積和公式を使って適当に式をこねると
Cos (2NA) = 2 Cos^2 (NA) - 1
Cos ((2N+1)A) = 2 Cos ((N+1)A) Cos (NA) - Cos (A)
がわかる。
これを元に再帰的にやればいい。

多項式クラスを持っていなかったので vector で簡易実装した。
一度ちゃんとしたものを作っておかないと。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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