スポンサーサイト

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

CodeChef March 2011 Challenge

CodeChef の月一ロングコンテスト。
期間は 3/1 18:30 ~ 3/13 21:30 (JST) (サーバの不調で 1 日延びた)
今回で 3 回目だけど、今月のは特に難しかった気がする。

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

結果

問題を、問題ページの上から順に A, B, .., F と呼ぶことにする。
A. -
B. AC (1[pt])
C. AC (1[pt])
D. -
E. WA
F. AC (0.901[pts])
Standing : 31/384
Rank (Long) : 272 → 204
Rating (Long) : 27.70 → 40.58


問題

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

A. Buying Land
大きさ R × C の土地があり、土地の各位置の高さが与えられる。
また、大きさ H × W の 高さ変化パターン と 高さ変化パターン上の店の位置 が与えられる。

土地の大きさ H × W の部分区画 と 高さ変化パターン の類似度を、各位置での高さの差の 2 乗和と定義する。

類似度が K 番目に高くなるような店の位置を求めよ。
( 類似度の数値が等しい場合は、より北、より東のほうが類似度が高いとする )

・ 1 ≦ R, C ≦ 666
・ 1 ≦ H ≦ (R+1)/2
・ 1 ≦ W ≦ (C+1)/2
・ 1 ≦ K ≦ 1000
・ すべての高さは絶対値 30 以下の整数

※ 簡潔な文章では説明しにくいので、ちゃんとした問題文を知りたい場合は原文を読んでください。

B. K-Unique Sequence
N 個の整数からなる数列 (a1, a2, .., aN) が K-Unique であるとは、
連続する K 個の要素からなる N/K 個の部分列
(a1, a2, .., aK)
(aK+1, aK+2, .., a2K)
:
(aN-K+1, aN-K+2, .., aN)
のそれぞれが K 個の異なる数からなることをいう。

N 個の整数からなる数列と K が与えられたとき、数列を並べ替えてできる K-Unique な数列のなかで辞書式最小のものを答えよ。
解がない場合は -1 と答えよ。

・ 1 ≦ N ≦ 50000
・ 1 ≦ K ≦ N
・ N は K の倍数
・ 0 ≦ ai ≦ 1000000000

C. Omax
m × n の行列が与えられる。
行列の中の O 型領域に含まれる数の和の最大値を求めよ。

O 型領域とは、長方形の中から小さな長方形をくりぬいたような形。
凹 のようになってはいけないし、少なくとも 1 つの要素はくりぬかないといけない。

D. Ski Resort
H × W のゲレンデ、各位置での高さが与えられる。
店の位置と家の位置が与えられる。
あるセルから(4方向の)隣接するセルへは、高さが非増加であれば移動することができる。
店から家への移動経路がなくなるように、適当なセルに適当なだけ雪を積もらせるとき、必要な雪の量を最小化せよ。
( 雪 1 単位で高さが 1 上がる。高さを下げることはできない。)

・ 1 ≦ H, W ≦ 50
・ 0 ≦ 各セルの初期高さ ≦ 200000

E. Squares Game
2 次元平面上に n 個の白い正方形が置かれている。
正方形は入力で与えられる順番に 1, 2, .., n の番号が振られている。
どの 2 つの正方形も、一部だけが重なっているということはない。
( 一方がもう一方を包含しているというのはありうる。)

これらの正方形を使って 2 人でゲームをする。
各プレイヤーは白い正方形を 1 つ選び、黒く塗る。
その際、正方形の中にある正方形も同時に塗られる。
塗ることができなくなったプレイヤーが負け。

両プレイヤーが最適な戦略をとるとき、与えられた盤面が先手必勝かどうかを判定せよ。
先手必勝の場合は、最初に塗るべき正方形 (のうち、番号最小のもの) も求めよ。

F. The Amazing All-In-One Cooking Machine - Challenge
Travelling Repairman Problem でコストがより小さい解を求めよ。

・ 頂点数 ≦ 300
・ 辺数 ≦ 2000
・ 顧客数 ≦ 10000

解答

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

B.
int a[50001],b[50000],org[50000],cnt[50001];
priority_queue< int,vi,greater<int> > pq[50001],pq2;

int main(){
int T; scanf("%d",&T);
while(T--){
int n,K; scanf("%d%d",&n,&K);
rep(i,K+1){
cnt[i]=0;
pq[i]=priority_queue< int,vi,greater<int> >();
}
pq2=priority_queue< int,vi,greater<int> >();

rep(i,n) scanf("%d",a+i);
sort(a,a+n);

// coordinate compression
for(int i=0,j=0;i<n;i++){
if(i>0 && org[a[i-1]]!=a[i]) j++;
org[j]=a[i];
a[i]=j;
}

a[n]=-1; // sentinel
bool ok=true;
for(int i=0,bef=a[0],c=0;i<n+1;bef=a[i++]){
if(a[i]==bef) c++;
else{
if(c>n/K){ ok=false; break; }
cnt[bef]=c;
pq[c].push(bef);
pq2.push(bef);
c=1;
}
}

if(!ok){ puts("-1"); continue; }

for(int i=n/K;i>=1;i--){
int j=0;
set<int> used;
// required choice
while(!pq[i].empty()){
int t=pq[i].top(); pq[i].pop();
used.insert(t);
b[j++]=t;
}

// greedy choice
while(j<K){
int t=pq2.top(); pq2.pop();
if(used.count(t)) continue;
pq[cnt[t]].pop();
used.insert(t);
b[j++]=t;
}

// repush
for(set<int>::iterator it=used.begin();it!=used.end();++it){
int t=*it;
cnt[t]--;
if(cnt[t]>=1){
pq[cnt[t]].push(t);
pq2.push(t);
}
}

sort(b,b+K);
rep(j,K){
if(i<n/K || j>0) putchar(' ');
printf("%d",org[b[j]]);
}
}
putchar('\n');
}

return 0;
}

O(nlogn) のアルゴリズムが必要。

コンテストが始まってすぐに解いたので、何をやったか忘れた。
基本的には Greedy に (小さい順に) 選んでいけばいい。
ただし、選ばないといけない (それを選ばないと K-Unique でなくなる) 要素は先に選んでおく。
実装がちょっと複雑になる。
2 種類の priority_queue を使って、うまく管理してるみたい。

C.
int a[77][77],dp1[77][77],dp2[77][77][77][77];

inline int rectval(int i1,int i2,int j1,int j2){
int res=dp1[i2][j2];
if(i1>0) res-=dp1[i1-1][j2];
if(j1>0) res-=dp1[i2][j1-1];
if(i1>0 && j1>0) res+=dp1[i1-1][j1-1];
return res;
}

int main(){
for(int m,n;scanf("%d%d",&m,&n),m;){
rep(i,m)rep(j,n){
scanf("%d",a[i]+j);
dp1[i][j]=a[i][j];
if(i>0) dp1[i][j]+=dp1[i-1][j];
if(j>0) dp1[i][j]+=dp1[i][j-1];
if(i>0 && j>0) dp1[i][j]-=dp1[i-1][j-1];
}

rep(i2,m)rep(j2,n){
for(int i1=i2;i1>=0;i1--)for(int j1=j2;j1>=0;j1--){
int tmp;
if(i1==i2 || j1==j2){
dp2[i1][i2][j1][j2]=a[i2][j2];
if(i1<i2){
tmp=dp2[i1][i2-1][j1][j2];
if(tmp<0) dp2[i1][i2][j1][j2]+=tmp;
}
else if(j1<j2){
tmp=dp2[i1][i2][j1][j2-1];
if(tmp<0) dp2[i1][i2][j1][j2]+=tmp;
}
}
else{
dp2[i1][i2][j1][j2]=rectval(i1,i2,j1,j2);
tmp=dp2[i1][i2][j1+1][j2];
if(tmp<dp2[i1][i2][j1][j2]) dp2[i1][i2][j1][j2]=tmp;
tmp=dp2[i1+1][i2][j1][j2];
if(tmp<dp2[i1][i2][j1][j2]) dp2[i1][i2][j1][j2]=tmp;
}
}
}

rep(i1,m)for(int i2=i1;i2<m;i2++){
rep(j1,n)for(int j2=j1;j2<n;j2++){
if(i1<i2){
int tmp=dp2[i1][i2-1][j1][j2];
if(tmp<dp2[i1][i2][j1][j2]) dp2[i1][i2][j1][j2]=tmp;
}
if(j1<j2){
int tmp=dp2[i1][i2][j1][j2-1];
if(tmp<dp2[i1][i2][j1][j2]) dp2[i1][i2][j1][j2]=tmp;
}
}
}

int ans=-(1<<30);
rep(i1,m)for(int i2=i1+2;i2<m;i2++){
rep(j1,n)for(int j2=j1+2;j2<n;j2++){
int tmp=rectval(i1,i2,j1,j2)-dp2[i1+1][i2-1][j1+1][j2-1];
if(ans<tmp) ans=tmp;
}
}
printf("%d\n",ans);
}

return 0;
}

見るからに DP.
明らかに作為的な入力の大きさをみるに、O(m2n2) で間に合う。

とりあえず書いてみるが、Runtime Error (MLE).
メモリ制限が厳しいようだ。
配列をうまく再利用して AC.
実は first accepted. ( ロングコンテストなのですごくない )

プログラムをちょっとだけ解説
  • dp1[i][j] := ∑[y=0→i]∑[x=0→j] a[y][x]

  • rectval(i1,i2,j1,j2) := ∑[y=i1→i2]∑[x=j1→j2] a[y][x]

  • コード中段での dp2[i1][i2][j1][j2] := (i2,j2) を右下端点とする長方形の中で、和が最大のもの

  • コード下段での dp2[i1][i2][j1][j2] := (i1,j1) を左上端点, (i2,j2) を右下端点とする長方形に含まれる長方形の中で、和が最大のもの

O(m n2) で解いている人が 2 人いて、すごいなぁと思った。

E. (時間外)
struct Square{
int x,y,a,parent,grundy;
vi child;
Square(){ parent=grundy=-1; child.clear(); }
} sq[50000];

int calcGrundyNumber(int id){
if(~sq[id].grundy) return sq[id].grundy;
int g=0;
rep(i,sq[id].child.size()){
g^=calcGrundyNumber(sq[id].child[i]);
}
return sq[id].grundy=1+g;
}

int findSuitableSquare(int p,int g){
if(g==0) return p;
int ans=INF;
int gp=calcGrundyNumber(p);
rep(i,sq[p].child.size()){
int c=sq[p].child[i];
ans=min(ans,findSuitableSquare(c,(g-1)^(gp-1)^calcGrundyNumber(c)));
}
return ans;
}

enum SIDE{TOP=0,BOTTOM=1,LEFT=0,RIGHT=1};
struct Event{
int t,id;
SIDE side;
Event(int T,int ID,SIDE S):t(T),id(ID),side(S){}
bool operator<(const Event &e)const{ return t<e.t; }
bool operator>(const Event &e)const{ return e<*this; }
};

int tmp_parent[50000];

int determineParent(int id){
if(~tmp_parent[id]){
int p=determineParent(tmp_parent[id]);
sq[id].parent=p;
sq[p].child.pb(id);
}
return sq[id].parent;
}

int main(){
int T; scanf("%d",&T);
while(T--){
int n; scanf("%d",&n);
rep(i,n){
tmp_parent[i]=-1;
sq[i]=Square();
scanf("%d%d%d",&sq[i].x,&sq[i].y,&sq[i].a);
}

priority_queue< Event,vector<Event>,greater<Event> > pq;
rep(i,n){
pq.push(Event(sq[i].y,i,TOP));
pq.push(Event(sq[i].y+sq[i].a,i,BOTTOM));
}

set<Event> st;
while(!pq.empty()){
Event e=pq.top(); pq.pop();
int y=e.t,id=e.id;
if(e.side==TOP){
set<Event>::iterator it=st.lower_bound(Event(sq[id].x+sq[id].a,-1,LEFT));
if(it!=st.end()){
Event ee=*it;
if(ee.side==RIGHT){
sq[id].parent=ee.id;
sq[ee.id].child.pb(id);
}
else{ // ee.side==LEFT
tmp_parent[id]=ee.id; // find it later
}
}
st.insert(Event(sq[id].x,id,LEFT));
st.insert(Event(sq[id].x+sq[id].a,id,RIGHT));
}
else{ // e.side==BOTTOM
st.erase(Event(sq[id].x,id,LEFT));
st.erase(Event(sq[id].x+sq[id].a,id,RIGHT));
}
}

rep(i,n) if(~tmp_parent[i]) determineParent(i);

int g=0;
rep(i,n)if(sq[i].parent==-1){ // for each root
g^=calcGrundyNumber(i);
}

if(g==0) puts("Fit");
else{
int ans=INF;
rep(i,n)if(sq[i].parent==-1){
ans=min(ans,findSuitableSquare(i,g^calcGrundyNumber(i)));
}
printf("Fat %d\n",ans+1);
}
}

return 0;
}

問題は大きく 3 つのパートに分けられる。
1. 正方形の重なりの情報を処理する。(森を作る)
2. 先手必勝かどうかを判定する。
3. 最初に塗るべき正方形を見つける。

すべて、O(n2) より小さいオーダーで実現しないといけない。

2. と 3. は分かった。
キーワードは Nim, Grundy Number. ここにかなり詳しく載っている。

木の Grundy number の規則は、小さな例をたくさん作ってみると推測できた。
すなわち、
あるノードを根とする木の Grundy number は、子ノードを根とする部分木の Grundy number すべての xor をとったもの +1.
葉の Grundy number は 1.
すべての根付き木の Grundy number の xor をとったものが 0 なら後手必勝。そうでなければ先手必勝。

3. のチェックも、DFS しながらうまくやれば O(n) でできる。

1. を実現するのに苦労した。( 結局完成しなかった )
正方形たちを上から順に走査していって、Interval Tree に区間情報を逐一 追加 / 削除 していく。
ある正方形の親がどの正方形かは、点クエリのアルゴリズムをちょっと変形すればできると思って書いてみたが、実装が間違っているらしく WA.
というか、日本語の Interval Tree の情報が Web 上にほとんどない。
この時点でコード量が大変なことになっているので、多分もっと簡単な方法があるんだと思う。

[ 2011/03/16 追記 ]
Editorials を見ながら解いた。

思ったとおり、Interval Tree なんて持ち出さなくても O(nlogn) で森を作ることはできた。
正方形の辺を区間として処理するんじゃなくて、頂点を別々に管理するとうまくいく。

正方形の頂点を管理するデータ構造 A を用意しておく。追加 / 削除を log オーダーでしないといけないので set or map がいい。
平面を上から下に向けて走査していって、正方形の上辺がきたらその両端を A に追加する。さらに、その正方形の親になる正方形を求める。これは、A 内を二分探索することでできる。
( 上辺の右端の 1 つ右にある頂点に注目して、それが辺の左端か右端かで場合分け。左端のときは親がすぐには決まらないので、情報をメモしておいてあとで DFS する。)
正方形の下辺がきたら、先に A に追加していた両端点を削除する。

F.
int client[10000],dis[300][300];

double eval(int from,int to,const vi *a){
const static double PRM=1e7;
return PRM/(dis[from][to]+EPS)+a[to].size();
}

int main(){
int T; scanf("%d",&T);
while(T--){
int n,m,K; scanf("%d%d%d",&n,&m,&K);
rep(i,K) scanf("%d",client+i);
rep(u,n)rep(v,n) dis[u][v]=(u==v?0:INF);
rep(i,m){
int u,v,d; scanf("%d%d%d",&u,&v,&d);
dis[u][v]=dis[v][u]=d;
}

// Warshall-Floyd Algorithm
rep(k,n)rep(i,n)rep(j,n) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

vi a[300];
rep(i,K) a[client[i]].pb(i);

vi ord(1,0);
bool visited[300]={}; visited[0]=true;
for(int now=0;;){
int iopt=-1;
double val=-1;
rep(i,n)if(!visited[i] && a[i].size()>0){
if(val<eval(now,i,a)){
val=eval(now,i,a);
iopt=i;
}
}
if(iopt==-1) break;
visited[iopt]=true;
ord.pb(iopt);
now=iopt;
}

rep(i,ord.size())rep(j,a[ord[i]].size()) printf("%d ",a[ord[i]][j]+1);
putchar('\n');
}

return 0;
}

近くにいる顧客から順に処理していく。(Nearest Neighbor)
また、同じ頂点にいる顧客はまとめて処理する。
という、単純な戦略しか実装していない。

同じ頂点にいる顧客の数が多いほどウェイトを大きくするとか、隣接する 2 頂点をスワップしてみるとか、色々やってみるべきことは思いつくけど E. が解けなくてこっちを解く気が起きなかった。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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