スポンサーサイト

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

CodeChef January 2011 Challenge

1/1 18:30 ~ 1/11 18:30 (日本時間) の 10 日間で行われた CodeChef January 2011 Challenge の参加記録です。

正月は何かと用事があったので、私が参加したのは 1/6~ でした。

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

概要

CodeChef のコンテストは初参加だったので今回だけ概要を書いておく。

・ コンテストの参加登録というのはなく、1 回でも submit すれば自動的に参加したことになるらしい。
・ 基本的に英語。
・ 参加者は 8 割くらいがインド人で日本人は 4 人しかいなかった。
・ 問題はタイトルの辞書順に並んでいる。難易度順ではない。

問題は全 6 問。
うち 5 問が正解/不正解が判定できるタイプの問題 (TopCoder SRM ライク) で、0 or 1 点。
あとの 1 問ができるだけ良い解を求めるタイプの問題 (TopCoder MM ライク) で、0~1 点。
6 点満点。

結果

問題の上から順に
Unopened
Opened
Accepted (1[pt])
Opened
Accepted (1[pt])
Accepted (0.715[pts])

Standing : 94/273
Rank : NaN → 514
Rating : 0 → 10.9839863694

問題

Chef attic window
問題読んでない。正解者数からみるに今回の最難問。

Chess Pushing Game
サイズ 3×n (n は十分大) のチェス盤を考える。
チェス盤の座標を、左下が (0,0)、右上が (2,n-1) となるようにとる。

チェス盤上には 3 つのポーンがあり、それぞれの座標を (0,y1), (1, y2), (2,y3) とする。
初期状態では y1 = y2 = y3 = 0 である。

ポーンは以下の条件をみたすように動かすことができる。
・ 1 回の移動で、ポーンの y 座標は 1 増える。
・ y1≦y2≦y3.
・ | y1 - y2| ≦ D, | y2 - y3| ≦ D.

ポーンの移動を計 K 回おこなうとき、最終的な座標が y1 = y2 = y3 となる動かし方の総数を mod 1000000007 で求めよ。

( 0 ≦ D ≦ 7, 0 ≦ K ≦ 109 )

Count Relations
集合 A, B を次で定義する。
A = { 1, 2, ..., N }
B = 2A ( A のべき集合 )

関係 R1, R2 を次で定義する。
R1 = { (x,y) | x∈B, y∈B, x is not in y, y is not in x, x∩y = φ }
R2 = { (x,y) | x∈B, y∈B, x is not in y, y is not in x, x∩y ≠ φ }
ただし、(x,y) と (y,x) は区別しない。(同じものとみなす)

#R1, #R2 を mod 100000007 で求めよ。

( 1 <= N <= 1018 )

Flu Shot Lineup
N 人が 1 列に並んでいる。
各人の座標を x1, x2, ..., xN とする。
何人かを適当に移動させて、どの 2 人の間隔も T 以上になるようにしたい。
移動させる最大距離 D の最小値を小数点 3 桁の精度で求めよ。

すなわち、
移動後の座標を x'1, x'2, ..., x'N とすれば、
・ | xi - xj | ≦ T (i = 1, 2, ..., N; j = 1, 2, ..., N; i≠j)
・ | xi - x'i | ≦ D (i = 1, 2, ..., N)
が成り立つような最小の D を求めよ。

( 1 ≦ N ≦ 104, 1 ≦ T ≦ 106, 1 ≦ xi ≦ 106 )

Restaurant Expansion
1 から N まで番号付けされた N コの町がある。
これらの町の間には合計 N-1 本の道があり、任意の 2 つの町を移動する経路がちょうど 1 つだけ存在することが保証されている。

今、町 1 には C 人のシェフがいる。
D 日間で、町にレストランを建て、そこから得られる利益を最大化したい。

各日にできる行動は次の 3 つのうち 1 つである。
1. 何もしない
2. 町 a から町 b に c 人のシェフを移動させる
3. 町 a にレストランを建てる

ただし、
・ 2. を行う際には、町 a と b が 1 本の道でつながっていないといけない。
・ 3. を行う際には、町 a に少なくとも 1 人のシェフがいないといけない。この行動をしたあとは町 a のシェフは移動できない。1 つの町にレストランは 1 件まで。

レストランから得られる利益は、各町によって予め決まっている。
得られる利益の最大値と最適な行動計画(の1つ)を示せ。

( 1 ≦ N ≦ 30, 1 ≦ C ≦ 30, 1 ≦ D ≦ 30 )

Splitting Giant Subs
細長いサンドイッチがある。サンドイッチは N コの部分に分かれており、各部分にはちょうど 1 種類の具がつまっている。

サンドイッチを c 回 切ることで、切り分けられた c+1 コのサンドイッチが次の条件をみたすようにする。

・ 切り分けられたサンドイッチに左から順に 0 1 0 1 とラベル付けするとき、ラベル 0 のサンドイッチの具とラベル 1 のサンドイッチの具(の種類と個数)が全て等しい。

なるだけ小さい c を求めよ。また、その c に対応する切り方を 1 通り示せ。

すべての具は偶数回現れることが保証されている。

( 2 ≦ N ≦ 1000 )

解答

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

Chess Pushing Game (時間外)
const int M=1000000007;

int main(){
int D,K; scanf("%d%d",&D,&K);

int Apow[30][64][64]={}; // Apow[n] := A^(2^n)
rep(i,D+1)rep(j,D+1){
if(i-1>=0) Apow[0][i*(D+1)+j][(i-1)*(D+1)+(j+0)]=1; // L pawn moves
if(i+1<=D&&j-1>=0) Apow[0][i*(D+1)+j][(i+1)*(D+1)+(j-1)]=1; // M pawn moves
if(j+1<=D) Apow[0][i*(D+1)+j][(i+0)*(D+1)+(j+1)]=1; // R pawn moves
}
for(int n=1;n<30;n++){
rep(i,(D+1)*(D+1))rep(j,(D+1)*(D+1)){
rep(l,(D+1)*(D+1)){
Apow[n][i][j]=(Apow[n][i][j]+1LL*Apow[n-1][i][l]*Apow[n-1][l][j])%M;
}
}
}

int v[64]={}; v[0]=1;
for(int t=0;K;t++){
if(K&1){
int tmp[64]={};
rep(i,(D+1)*(D+1))rep(j,(D+1)*(D+1)){
tmp[i]=(tmp[i]+1LL*Apow[t][i][j]*v[j])%M;
}
rep(i,(D+1)*(D+1)) v[i]=tmp[i];
}
K>>=1;
}

printf("%d\n",v[0]);

return 0;
}

正解には至らなかったが、考えたことを書いておく。

まず、K は 3 の倍数でないといけない。そうでないと K 回の移動後に 3 つのポーンが一直線に並ぶことはありえない。

・ D = 0 のとき
ポーンが動けない。K = 0 かどうかで場合分け。

・ D = 1 のとき
紙に書いているうちにパターンがみえた。答えは 2K/3-1 くらい。

・ D = 2 のとき
試行錯誤していると、線形の 4 項間漸化式が出てきた。
一般項は求められなくもないが、√ が出てくるしあまり参考にならない。
同じ方針で D = 3 以上の表式を求めるのはかなり大変そう。
そもそもそれがわかったとしても、K = 109 なので DP 的に漸化式をなぞっていく O(K) 解法では TLE になる。

ポーンの動かし方の条件で、D に関する制約を取り除いた場合には、
(つまり、条件が y1≦y2≦y3 だけ)
1
5
42
462
6006
87516
1385670
という数列が得られた。
この数列の一般項を自力で見つけることはできなかったが、調べてみるとこれは Catalan 数 を 3 次元へ拡張したもので、
\frac{2\cdot(3n)!}{n!(n+1)!(n+2)!}
という表式があることがわかった。(A005789)

[ 2011/01/15 追記 ]
Editorials が出たので、それを見ながら解いてみた。

DP を行列乗算で高速化するというのが想定解だった。
109 という数字を見た瞬間に DP じゃないと思ってしまったのが敗因。

Count Relations
const ll L=100000007,inv2=50000004;

vb toBinary(ll a){
vb res;
do{
res.pb(a&1);
a>>=1;
}while(a);
return res;
}

int main(){
ll pow2[128],pow3[128]; // pow2[i]=2^(2^i), pow3[i]=3^(2^i)
pow2[0]=2,pow3[0]=3;
rep(i,126){
pow2[i+1]=(pow2[i]*pow2[i])%L;
pow3[i+1]=(pow3[i]*pow3[i])%L;
}

int t; scanf("%d",&t);
while(t--){
ll n; scanf("%lld",&n);
vb bits=toBinary(n-1);

ll t1=1,t2=3; // t1=2^(n-1), t2=3^n
rep(i,bits.size()){
if(bits[i]){
t1=(t1*pow2[i])%L;
t2=(t2*pow3[i])%L;
}
}

ll r1,r2;
r1=( ((t2+1)*inv2)%L - (2*t1)%L + L )%L;
r2=( (t1*(2*t1+3))%L - ((3*t2+1)*inv2)%L + L )%L;
printf("%lld %lld\n",r1,r2);
}

return 0;
}

#R1, #R2 の式をがんばって求めて、あとはそれをコーディングする。
多分 Editorials にも出るだろうけど、公式導出のスケッチを書いておく。

・ #R1 の導出

(x,y) ∈ R1 とおいて #x + #y に注目する。
R1 の元のうち #x + #y = M となるものは
NCM・(2M-1-1) 通り
これを M = 1, 2, ..., N について足し合わせて、二項定理の逆とかを使ってまとめると
#R1 = (3N-1)/2 - 2N
となる。

・ #R2 の導出

R3 = { (x,y) | x∈B, y∈B, x is not in y, y is not in x } とおけば、
#R2 = #R3 - #R1 である。

包除原理により
#R3
= #{ (x,y) | x∈B, y∈B }
- #{ (x,y) | x∈B, y∈B, x is in y }
- #{ (x,y) | x∈B, y∈B, y is in x }
+ #{ (x,y) | x∈B, y∈B, x is in y, y is in x }

となる。
これをごにょごにょすると
#R3 = 2N-1 (2N+1) - 3N
となって、結局
#R2 = 2N-1 (2N+3) - (3N+1-1)/2.

あとは、この値を mod 100000007 で求めればいいが、N がかなり大きいので愚直にかけ算できない。
ここでは、べき剰余を高速に求める方法として、バイナリ法を使った。
バイナリ法についてはわかりやすい解説サイトがたくさんあるので説明略。

上式を計算するためには、もう一点、÷2 の部分を解決しないといけない。
一般に、合同式では加減乗算はできるが、除算はできない。
この問題の解決法については、cafelierさんの記事が参考になる。
幸いなことに 100000007 は素数。
ちなみに、mod 100000007 の世界での 2-1 を計算してみると、50000004 になった。

Flu Shot Lineup (時間外)
int N;
double T,x[10000];

bool isMovable(double D){
double xx[10000];
xx[0]=max(x[0]-D,0.0);
for(int i=1;i<N;i++){
if(xx[i-1]+T>x[i]+D+EPS) return false;
xx[i]=max(xx[i-1]+T,x[i]-D);
}
return true;
}

int main(){
int K; scanf("%d",&K);
while(K--){
scanf("%d%lf",&N,&T);
rep(i,N) scanf("%lf",x+i);

double Dl=0,Dr=1e11,Dm;
while(Dr-Dl>EPS){
Dm=(Dl+Dr)/2;
if(isMovable(Dm)) Dr=Dm;
else Dl=Dm;
}

printf("%.4f\n",Dm);
}

return 0;
}

方針も立たなかった。
結構解かれてるからそんなに難しくはないはず。
入力のサイズから推測するに、想定解法は O(N) か O(N log N) だと思う。

[ 2011/01/15 追記 ]
Editorials を見ながら。
二分探索らしい。D を 1 つ決めれば、その D 内で移動できるかどうかは O(N) で判定できる。
具体的には、できるだけ左に詰めて配置したときにすべての間隔が T 以上になっているかどうかを調べればいい。
Codeforces 48 C といい、二分探索の問題が苦手すぎる。なんとかしないと。

Restaurant Expansion
int n,n_chef,profit[30];
pii f[30][30]; // f : original tree -> reassembled tree
pii finv[30][30]; // f^(-1) : inverse map of f

pii calcMaxProfit(int stat,int remday){
vector<pii> a;
rep(i,n) if(stat&(1<<i)) a.pb(mp(profit[i],i));
sort(a.begin(),a.end(),greater<pii>());

int n_bld=min(min(n_chef,remday),(int)a.size());
int pres=0,sres=0;
rep(i,n_bld)if(a[i].first>0){
pres+=a[i].first;
sres|=(1<<a[i].second);
}

return mp(pres,sres);
}

void reasm(int u,vvi &connect){
int csz=connect[u].size();
rep(i,csz){
int v=connect[u][i];
reasm(v,connect);
}

vector<pii> sub;
rep(i,csz){
int v=connect[u][i];
if(connect[v].size()==0) sub.pb(mp(-profit[v],v));
else return;
}
sort(sub.begin(),sub.end());
int o=u;
rep(i,sub.size()){
int v=sub[i].second;
connect[u].clear();
connect[u].pb(v);
f[o][v]=mp(u,v);
u=v;
}
}

int main(){
int n_day;
scanf("%d%d%d",&n,&n_chef,&n_day);
rep(i,n) scanf("%d",profit+i);

vi toporder;
vvi connect(n);
{
bool adj[30][30]={};
rep(i,n-1){
int u,v; scanf("%d%d",&u,&v);
u--,v--;
adj[u][v]=adj[v][u]=true;
}

toporder.pb(0);
bool visited[30]={}; visited[0]=true;
queue<int> qu; qu.push(0);
while(!qu.empty()){ // BFS
int u=qu.front(); qu.pop();
rep(v,n)if(adj[u][v] && !visited[v]){
toporder.pb(v);
connect[u].pb(v);
visited[v]=true;
qu.push(v);
}
}
}

vvi xconnect=connect;
reasm(0,xconnect);

rep(u,n)rep(v,n){
pii a=f[u][v];
finv[a.first][a.second]=mp(u,v);
}

set<int> movable[30]; // movable[d]: set of movable vertices in d day (bit representation)
movable[0].insert(1); // only include node 0
for(int d=1;d<n_day;d++){
set<int>::iterator it;
for(it=movable[d-1].begin();it!=movable[d-1].end();++it){
int stat=*it;
rep(u,n)if(stat&(1<<u)){
rep(i,xconnect[u].size())if((stat&(1<<xconnect[u][i]))==0){
movable[d].insert(stat|(1<<xconnect[u][i]));
}
}
}
}

int pmax=0,smax=0,dmax=0;
rep(d,n_day){
set<int>::iterator it;
for(it=movable[d].begin();it!=movable[d].end();++it){
int stat=*it;
pii a=calcMaxProfit(stat,n_day-d);
if(pmax<a.first){
pmax=a.first;
smax=a.second;
dmax=d;
}
}
}

printf("%d\n",pmax);

int chef[30]={};
for(int i=toporder.size()-1;i>=0;i--){
int u=toporder[i];
if(smax&(1<<u)) chef[u]++;
rep(i,connect[u].size()){
int v=connect[u][i];
chef[u]+=chef[v];
}
}
rep(i,toporder.size()){
int u=toporder[i];
rep(i,connect[u].size()){
int v=connect[u][i];
if(chef[v]>0) printf("transfer %d %d %d\n",u+1,v+1,chef[v]);
}
}

vi bld;
rep(u,n) if(smax&(1<<u)) bld.pb(u);
for(int d=dmax,i=0;d<n_day;d++){
if(i<bld.size()) printf("build %d\n",bld[i++]+1);
else puts("nothing");
}

return 0;
}

D 日経ったタイミングでレストランが建っているかどうかに興味があるので、レストランを早めに建てることにメリットはない。むしろ、シェフが動けなくなるというデメリットがある。
なので、最適な計画は、
1. 最初の D1 日間でシェフの移動を済ませる
2. 次の D2 日間でレストランを建てる
3. 余った日数は何もしない。
という順番になる。

問題はグラフ理論の言葉で次のように言い換えることができる。

N コのノードからなる木が与えられる。各頂点には重み(レストランの利益)がついている。
ノード 1 を含むノード数 D1+1 の部分木から、D2 コのノードを選ぶとき、選んだノードの重みの和を最大にせよ。


シェフの移動が部分木を作る操作に、レストランの建設がノードを選ぶ操作に対応している。

D1 が決まれば、D2 は自動的に決まる。
( D2 = min(シェフの人数 C, 残り日数 D-D1, シェフがいる町の数) )
なので、D1 の値でループして、その中から最適なものを選べばいい。

このアルゴリズムでは、各 D1 について、ありうる部分木を全通り生成しないといけない。
これは、木の形によっては非常に時間がかかる。
最悪ケースは、ノード 2, 3, ..., N がすべて ノード 1 につながっている場合で、この場合は、N = 20 程度でも計算するのに数十秒かかった。
( こういうグラフを星グラフ (star graph) というらしい。)
ためしに submit してみたが当然 TLE になった。

この問題を解決するために、グラフを(部分木が少ない)等価なグラフに変形することを考えた。
文章で説明するのが難しいので、図に書いてみた。
○の中に書いたのがノード番号で、青い数字がノードの重み。左が元のグラフで右が変形したグラフ。
木の変形
要するに、あるノードから先の分岐が辺 1 本だけのものなら、重みの大きいものから Greedy に選んで一列につなげなおしたものと等価だということ。

これでも意地悪なデータが来れば TLE しそうな気がするけど、とりあえずはこれで Accepted をもらえた。

[ 2011/02/18 追記 ]

想定解法は木の上での DP (メモ化再帰) らしい。
その方針でも書いてみた。
複数の子をもつノードをどのように処理するかがポイントで、それは、今何番目の子を見ているかを状態に含めればうまくいく。

Splitting Giant Subs
int main(){
int t; scanf("%d",&t);
while(t--){
int n; scanf("%d",&n);
int a[1000],hist[501]={};
rep(i,n){ scanf("%d",a+i); hist[a[i]]++; }

vi optcut(2000);
rep(s,n){ // start from any points
vi cut;
int jack[501]={},jill[501]={};
bool turn=true; // true: Jack's turn, false: Jill's turn
for(int i=s;i<n;i++){
if(turn){
if(jack[a[i]]<hist[a[i]]/2) jack[a[i]]++;
else{ cut.pb(i); jill[a[i]]++; turn=false; }
}
else{
if(jill[a[i]]<hist[a[i]]/2) jill[a[i]]++;
else{ cut.pb(i); jack[a[i]]++; turn=true; }
}
}
turn=true;
for(int i=s-1;i>=0;i--){
if(turn){
if(jack[a[i]]<hist[a[i]]/2) jack[a[i]]++;
else{ cut.pb(i+1); jill[a[i]]++; turn=false; }
}
else{
if(jill[a[i]]<hist[a[i]]/2) jill[a[i]]++;
else{ cut.pb(i+1); jack[a[i]]++; turn=true; }
}
}
sort(cut.begin(),cut.end());
if(cut.size()<optcut.size()) optcut=cut;
}

printf("%d\n",optcut.size());
rep(i,optcut.size()){
if(i) putchar(' ');
printf("%d",optcut[i]);
}
putchar('\n');
}

return 0;
}

Greedy に選ぶだけのプログラム。
3 回 submit した。
1 回目: 左から右へ 1 回だけ走査しただけ。O(N). 0.472 pts
2 回目: 左から右、右から左の 1 回ずつ走査して良い方をとっただけ。O(N). 0.639 pts
3 回目: 任意の位置からはじめて、左と右の両方向に走査しただけ。O(N2). 0.715 pts

上のコードは 3 回目に submit したもの。

この方法で得られた解を改良しようとしたけど、うまいヒューリスティクスが思いつかず時間切れ。
そもそも、この方法で最適解が得られない例ですら、ちょっと考えた程度では出てこなかった。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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