スポンサーサイト

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

CodeChef June Long Contest 2011

CodeChef June Long Contest 2011 の参加記
2011/06/01 18:30 ~ 06/12 18:30 (JST)

好みの問題セットだったのにぜんぜん解けなかった。

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

結果

問題を、問題ページの上から順に A, B, .. と呼ぶことにする。
A. AC [0.075 pts]
B. -
C. AC [1 pts]
D. -
E. -
F. AC [1 pts]
Standing : 77/653
Rank (Long) : 145 → 138
Rating (Long) : 64.297 → 71.739


問題

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

A. Mushroom Cave
洞窟の地図が M × N の 2 次元配列として与えられる。
洞窟の各マスは、何もないか、松明が落ちているか、壁があるかのいずれか。

調査員は洞窟の左上隅から右下隅まで移動したい。

調査員は松明を持っているときだけ移動できる。
調査員が松明のあるマスに入ると、今もっている松明を捨てて、落ちている松明を拾い、火をつける。
捨てた松明をもう一度使うことはできない。
松明は、火をつけてから K マス移動する間だけ使える。

通ったマスの総数が多くなるようなパスを求めよ。
ただし、同じマスを 2 回以上通ったとしても、1 回しかカウントされない。

上記の条件を満たすパスが少なくとも 1 つ存在することが保証されている。

1 ≦ M, N ≦ 100
2 ≦ K ≦ 15

B. Attack of the Clones
B = {0, 1}
boolean function f : Bn → B を考える。
( Bn は B の n 個の直積集合 )

clone と呼ばれる、特別な f の集合 (関数族) を考える。
Z = { f | f(0, 0, .., 0) = 0 }
P = { f | f(1, 1, .., 1) = 1 }
D = { f | !f(x1, x2, .., xn) = f(!x1, !x2, .., !xn) }
A = { f | for every i, a1, .., an, b1, .., bn, c and d;
         f(a1, .., c, .., an) = f(a1, .., d, .., an)
      ⇒ f(b1, .., c, .., bn) = f(b1, .., d, .., bn),
      where c and d are at some position i }


( ! は not 演算を表す )

Z, P, D, A にいくつかの演算をほどこして得られる集合の元の数を mod 1000003 で答えよ。
演算は、共通部分,合併,補集合の 3 種類。

1 ≦ n ≦ 100

C. Chef Teams
N 人のシェフが順番にキッチンに入ってくる。
各シェフは、年齢と能力という 2 つのパラメータで特徴付けられている。
各シェフの年齢はすべて異なる。

キッチンにいるシェフは、2 つのチーム (young team, old team) に分けられる。
キッチンに k 人のシェフがいるとき、
・ シェフの年齢が若い人から順に k/2 人は young team に属する。
・ 残りのシェフは old team に属する。
ただし、k が奇数のときは young team の人数を 1 人多くする。

シェフがキッチンに入る各段階において、young team と old team の能力の差を求めよ。

1 ≦ N ≦ 105

D. Minesweeper Reversed
すべてのマスがあけられているマインスイーパの盤面が与えられる。
いくつかのマスを閉じることで、盤面すべてを閉じたい。
最小で何マスを閉じればよいか?

普通のマインスイーパで、マス A を開けると同時に開くようなマスの集合を SA とする。
マス A を閉じると、
あるマス B があって A ∈ SB となるような、SB のすべての元が同時に閉じられる

盤面のサイズ R × C は 1 ≦ R, C ≦ 50 をみたす。

E. Restock
N × M のグリッドで、格子点に重み w[i][j] が与えられている。
点 (R, C) から点 (0, 0) まで移動したい。
点 (Y1, X1) からは、以下の 2 条件をみたす点 (Y2, X2) に移動できる。
・ (Y1, X1) と (Y2, X2) のマンハッタン距離が D 以下
・ (Y1, X1) と(0, 0) のユークリッド距離 > (Y2, X2) と(0, 0) のユークリッド距離

移動時に使う点の重みの和を最小化せよ。

1 ≦ N, M ≦ 500
1 ≦ D ≦ 500
0 ≦ w[i][j] ≦ 10000

F. Maximal Score Path
重みつき無向グラフ G = (V, E) が与えられる。
辺の score を、その辺の重みと定義する。
道の score を、道を作る辺の score の最小値と定義する。
点対 (u, v) の best path を、u と v をつなぐ道で score が最大のものと定義する。

G の全点対に対して、best path の score を求めよ。

2 ≦ |V| ≦ 1000
0 ≦ 辺の重み ≦ 108

解答

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

A.
struct P{
int x,y,hp;
P(){}
P(int X,int Y,int H):x(X),y(Y),hp(H){}
};

int main(){
const char *DIR="ENWS";

int T; scanf("%d",&T);
while(T--){
int m,n,k; scanf("%d%d%d",&m,&n,&k);
static char cave[100][101];
rep(i,m) scanf("%s",cave[i]);

static P path[100][100][16];
static char dir[100][100][16];
static bool visited[100][100][16];
rep(i,m) rep(j,n) rep(l,k+1) visited[i][j][l]=false;
visited[0][0][0]=true;

P end;
queue<P> qu; qu.push(P(0,0,0));
while(1){
P p=qu.front(); qu.pop();

int nexthp=(cave[p.y][p.x]=='t'?k:p.hp)-1;
if(nexthp<0) continue;

if(p.y==m-1 && p.x==n-1){ end=p; break; }

rep(i,4){
int yy=p.y+dy[i],xx=p.x+dx[i];
if(0<=yy && yy<m && 0<=xx && xx<n && cave[yy][xx]!='#'){
if(!visited[yy][xx][nexthp]){
visited[yy][xx][nexthp]=true;
dir[yy][xx][nexthp]=DIR[i];
path[yy][xx][nexthp]=p;
qu.push(P(xx,yy,nexthp));
}
}
}
}

string ans;
for(P p=end;;p=path[p.y][p.x][p.hp]){
if(p.y==0 && p.x==0 && p.hp==0) break;
ans+=dir[p.y][p.x][p.hp];
}
reverse(all(ans));
puts(ans.c_str());
}

return 0;
}

許容解を出力するだけのプログラム。
最短経路を計算しているので、スコアはかなり低い。

[y座標][x座標][持っている松明の残り時間] を状態にして BFS した。
どの松明を拾ったかという情報を持っていないので、一度拾った松明を再度拾ってしまうように思うかもしれないけど、最短経路を探すのであればそんな状況は起きない。
というのも、松明のあるマスを複数回通るような経路は最短経路でないことが証明できるから。

B.

がっつり数学チックな問題。この手の言い回しに慣れていないと題意を読み取るのも難しいかもしれない。
結局解けなかったので、あとで Editorials を見ながら解く。

C.
int main(){
int n; scanf("%d",&n);

set<pii> young,old;
int young_rate=0,old_rate=0;
// dummy elements
young.insert(mp(-1,0));
old.insert(mp((1<<31)-1,0));

rep(t,n){
int age,rate; scanf("%d%d",&age,&rate);
// insert to young
if(young.size()==old.size()){
pii old_min=*old.begin();
if(age<old_min.first){
young.insert(mp(age,rate));
young_rate+=rate;
}
else{
young.insert(old_min);
young_rate+=old_min.second;
old.erase(old.begin());
old.insert(mp(age,rate));
old_rate+=rate-old_min.second;
}
}
// insert to old
else{ // young.size()==old.size()+1
pii young_max=*young.rbegin();
if(young_max.first<age){
old.insert(mp(age,rate));
old_rate+=rate;
}
else{
old.insert(young_max);
old_rate+=young_max.second;
young.erase(--young.end());
young.insert(mp(age,rate));
young_rate+=rate-young_max.second;
}
}

printf("%d\n",abs(old_rate-young_rate));
}

return 0;
}

チームを管理するデータ構造には std::set を使った。
問題文どおりに操作すればいい。
チームが空のときがわずらわしいので、能力 0 のめちゃくちゃ若い人とめちゃくちゃ老いた人が最初からいることにした。

D.

winmine.exe でしばらく遊んでみると、同時に消えるマスはいくつかのブロックに分解できることに気付く。
これらのブロックが交わることはある。
この交わるマスを閉じることで、一気に多くのマスを閉じることができる。

ブロックを頂点、交わるという関係を辺にしたグラフを考える。
3 つ以上のブロックが 1 マスで交わることはない (多分) ということが重要。
この性質があるので、閉じるマスの最小個数は、グラフの最小辺被覆の大きさに等しくなる。

最小辺被覆は、最大マッチングが解ければ解ける。 ( 蟻本参照 )
なので、この問題は一般グラフの最大マッチング問題に帰着される。

と、ここまで考えたのだけど、最大マッチングを実装するための時間と知識がなかったので結局解けなかった。

E.

DP とか RMQ とか考えた。

F.
struct Edge{
int u,v,w;
Edge(){}
Edge(int U,int V,int W):u(U),v(V),w(W){}
bool operator>(const Edge &e)const{ return w>e.w; }
};

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 n,m,deg[1000];
Edge E[1000*999/2],MST[1000][1000];

void Kruskal(){
sort(E,E+m,greater<Edge>());

UnionFind uf(n);
rep(i,m){
int u=E[i].u,v=E[i].v,w=E[i].w;
if(uf.find(u)!=uf.find(v)){
uf.unite(u,v);
MST[u][deg[u]++]=Edge(u,v,w);
MST[v][deg[v]++]=Edge(v,u,w);
if(uf.size(u)==n) break;
}
}
}

int score[1000];

void dfs(int u,int prev){
rep(i,deg[u]){
int v=MST[u][i].v,w=MST[u][i].w;
if(v!=prev){
score[v]=(score[u]<w?score[u]:w); // min(score[u],w)
dfs(v,u);
}
}
}

int main(){
scanf("%d%d",&n,&m);
rep(i,m){
int u,v,w; scanf("%d%d%d",&u,&v,&w);
E[i]=Edge(u,v,w);
}

Kruskal();

rep(u,n){
score[u]=INF;
dfs(u,-1);
score[u]=0;
rep(v,n) printf("%d%c",score[v],v<n-1?' ':'\n');
}

return 0;
}

証明はできてないけど、いくつかの例で試したかぎりでは、best path はグラフの maximum spanning tree の上にあるようだ。
気付くまでに結構時間がかかった。

木であれば、2 点間をつなぐ道は 1 つしかないので、全点対間最短距離も DFS なり何なりして高速に求められる。
隣接リストに O(V+V2) のメモリを使う富豪的プログラミングをしている。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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