スポンサーサイト

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

CodeChef May Cook-Off Challenge

2011/05/30 01:00 ~ 03:30 (JST)
CodeChef May Cook-Off Challenge の参加記録

Tags : プログラミング CodeChef

結果

問題を、問題ページの上から順に A, B, .. と呼ぶことにする。
A. 3WA
B. -
C. TLE, AC (01:20:22)
D. WA, 4TLE
E. AC (00:19:46)
Standing : 91/442
Rank (Short) : 69 → 68
Rating (Short) : 1231.803 → 1266.239


問題

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

A. Socializing Game around Pizza
円周上に等間隔に並べられた N 個の点がある。
これを使って、二人でゲームをする。
プレイヤーは自分のターンに、まだ選ばれていない点を 2 つ選んで、それらを直線で結ぶ。
ただし、直線がすでにある直線と交差してはいけない。
両プレイヤーが最適な戦略をとるとしたとき、与えられた N に対して、先手必勝か後手必勝かを答えよ。

1 ≦ テストケース数 ≦ 1000
2 ≦ N ≦ 10000

B. Preferred Cooking Schools
N 個の学校が与えられる。
学校は 2 つのパラメータ ( 家からの距離 D と授業料 F ) で特徴付けられている。

2 つの学校 s1 = (D1, F1), s2 = (D2, F2) の間の順序 ≧ を
s1 ≧ s2 ⇔ D1 ≦ D2 かつ F1 ≦ F2
と定義する。

学校の集合 A に対して、A の極大元の集合を Max Special A と書く。

Q 個のクエリが与えられる。
クエリは 3 つの整数 maxD, minF, maxF からなる。
各クエリに対して Max Special A の要素数を求めよ。
ここで、
A = { N 個の学校の中で D≦maxD and minF≦F≦maxF をみたすもの }
とする。

1 ≦ N, Q ≦ 105
1 ≦ D, F, maxD, minF, maxF ≦ 109

C. Distribute idlis Equally
N 人の生徒がそれぞれ A[i] 個のお菓子を持っている。
次の操作で、生徒の持っているお菓子の数を等しくしたい。

[ 操作 ]
持っているお菓子の数が最小の生徒 i, 最大の生徒 j とする。
R = ceil( (A[j]-A[i])/2 ) とする。
j のお菓子から R 個を i に渡す。

全員のお菓子の数が等しくなるまでに何回の操作が必要か?
全員のお菓子の数を等しくすることができないときは -1 と答えよ。

1 ≦ テストケース数 ≦ 20
1 ≦ N ≦ 3000
0 ≦ A[i] ≦ N


D. Packing the Golden Triangles
N 個の箱 (1 辺 L の立方体) と M 個のバンド (最小半径 R1, 最大半径 R2) がある。

2K・R1 ≦ 4L ≦ 2K・R2
のとき、箱をバンドでとめることができる。ここで K=22/7 である。

1 つのバンドは高々 1 つの箱をとめることができる。
バンドでとめることのできる箱の最大個数を答えよ。

1 ≦ N, M ≦ 1000
1 ≦ L, R1, R2 ≦ 108

E. Popular Rice Recipe
N 回の投票が行われる。
各投票は +1, -1 のいずれかとしてカウントされる。
同じ人が複数回投票することがありえる。そういった場合、最後の投票のみが有効になる。
全ての投票が終わったときの値 (+1, -1 の累積値) を求めよ。

1 ≦ テストケース数 ≦ 20
1 ≦ N ≦ 100

解答

言語は C++。テンプレはここを参照。
ただし、 A は C 言語で書いた。

A. (時間外)
int main(){
int grundy[10001],used[10001],T,n,i;
for(n=0;n<=10000;n++){
for(i=1;i<n;i++) used[grundy[i-1]^grundy[n-i-1]]=n;
for(i=0;i<n;i++) if(used[i]!=n) break;
grundy[n]=i;
}

for(scanf("%d",&T);T--;){
scanf("%d",&n);
puts(grundy[n]>0?"Arjuna":"Bhima");
}

return 0;
}

Editorials を見ながら。

Grundy 数を知っていればやるだけ問題。知らなければ泥沼。
Grundy 数は以前の Chef のロングコンテストで出題されたときに勉強してたのに、すっかり忘れていた。
以前勉強したときにほかの例題を解かなかったのも、習熟度が低くなっていた原因。

Grundy 数については、忘れる前に、別の記事に簡単にまとめておくつもり。

B. (時間外)
const int INF=(1<<31)-1;

int n,x[100000],y[100000];
pii school[100000];
vi polyline[400000];

void makeSegtree(int u,int l,int r){
int yy=INF;
for(int i=l;i<r;i++){
if(y[i]<yy){ // strictly decreasing
yy=y[i];
polyline[u].pb(y[i]);
}
}

if(l+1<r){
int m=(l+r)/2;
makeSegtree(2*u+0,l,m);
makeSegtree(2*u+1,m,r);
}
}

int query(int u,int l,int r,int x_min,int x_max,int &y_max){
if(x_min<=x[l] && x[r-1]<=x_max){
if(y_max<polyline[u].back()) return 0;

// y_max 以下で最小の要素の番号
int lo=0,hi=polyline[u].size()-1;
while(lo<hi){
int mi=(lo+hi)/2;
if(polyline[u][mi]<=y_max) hi=mi;
else lo=mi+1;
}
y_max=polyline[u].back()-1;
return polyline[u].size()-hi;
}

if(l+1<r){
int ans=0,m=(l+r)/2;
if(x_min<=x[m-1]) ans+=query(2*u+0,l,m,x_min,x_max,y_max);
if(x[ m ]<=x_max) ans+=query(2*u+1,m,r,x_min,x_max,y_max);
return ans;
}
}

int main(){
scanf("%d",&n);
rep(i,n) scanf("%d%d",&school[i].second,&school[i].first);
sort(school,school+n);
rep(i,n){
x[i]=school[i].first;
y[i]=school[i].second;
}

makeSegtree(1,0,n);

int nq; scanf("%d",&nq);
while(nq--){
int d_max,f_min,f_max; scanf("%d%d%d",&d_max,&f_min,&f_max);
printf("%d\n",query(1,0,n,f_min,f_max,d_max));
}

return 0;
}

Editorials を見ながら。
Problem Setter の模範解答が自分好みだったので、自分で書いたコードもそれと似た感じになってしまった。

解法は Editorials そのままなので簡単に書くだけにする。

学校 (F, D) を二次元の格子点と考える。
クエリは、長方形領域 (底辺が x 軸に接している) 内にある極大元の個数を訊いていることになる。
点を x 座標でソートする。
点を葉とした Segment Tree を考える。
Segment Tree の各ノードには、「その点とそれより右だけを見たときの極大元の列」 を格納する。
極大元の定義から、この点列 (を直線で結んだもの) は、左上から右下にかけての折れ線になる。
Editorials の図がわかりやすい。

この前処理にかかる計算量がうまく見積もれないのだけど、O(N2) よりは小さくなっているようだ。

Segment Tree を使うことで、クエリを高速に処理できる。
次に述べるように、1 クエリあたり O(log2 N) で済む。

区間 [minF, maxF] をちょうど覆うために必要なノードは O(log N) 個ある。 (Segment Tree の性質)
このノード達の 「極大元の列」 をうまく merge して、区間 [minF, maxF] における 「極大元の列」 にしたい。
これは、二分探索を使えば O(log N) でできる。
Editorials の図 (2 枚目) を見ると様子がよく分かる。
maxD に関する制約は、この部分にうまく繰り込むことができる。

以上で必要なパーツは全部そろったので、あとはがんばって実装すればいい。

C.
#define ceil(x,y) (((x)+(y)-1)/(y))

int main(){
int T; scanf("%d",&T);
int a[3000],a2[3000];
while(T--){
int n; scanf("%d",&n);
int sum=0;
rep(i,n) scanf("%d",a+i), sum+=a[i];

if(sum%n!=0){
puts("-1");
continue;
}

int ave=sum/n,n2=0;
rep(i,n) if(a[i]!=ave) a2[n2++]=a[i];

int ans=0;
multiset<int> A(a2,a2+n2);
while(!A.empty()){
int a_min=*A.begin(),a_max=*A.rbegin();
int d=ceil(a_max-a_min,2);
A.erase(A.begin());
A.erase(--A.end());
if(a_min+d!=ave) A.insert(a_min+d);
if(a_max-d!=ave) A.insert(a_max-d);
ans++;
}

printf("%d\n",ans);
}

return 0;
}

お菓子の総数が N の倍数でなければ、もちろん等分割できない。
逆に、N の倍数であればいつでも等分割できる。

TCO11 Qual2 Medium (だったはず) の簡易版。
反復回数はそう多くないと踏んで、シミュレーションすることにした。
1 人の生徒が操作にかかわる回数は、高々 2 回程度になると思う。

具体的には multiset を使って実装した。multiset を使ったのは今回が初めてかもしれない。
個数が平均に一致したら再挿入はしないなどの、小手先の最適化はした。

D. (時間外)
template<class T> struct Interval{
T a,b;
Interval(){}
Interval(T A,T B):a(A),b(B){}
bool operator<(const Interval &I)const{ return b<I.b; }
};

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

int n,m,L[1000];
Interval<int> R[1000];
while(T--){
scanf("%d",&n);
rep(i,n){
scanf("%d",L+i);
L[i]*=7;
}
scanf("%d",&m);
rep(i,m){
int R1,R2; scanf("%d%d",&R1,&R2);
R[i]=Interval<int>(11*R1,11*R2);
}
sort(L,L+n);
sort(R,R+m);

int ans=0;
bool used[1000]={};
rep(i,n){
rep(j,m) if(!used[j]) {
if(R[j].a<=L[i] && L[i]<=R[j].b){
used[j]=true;
ans++;
break;
}
}
}
printf("%d\n",ans);
}

return 0;
}

見るからに二部グラフの最大マッチングを求める問題だけど、それはひっかけ。
二部グラフの最大マッチングは、
・ 交互路を Greedy に見つける方法では O( V・(V+E) )
・ Hopcroft-Karp でも O( (√V)・(V+E) )
かかるので、グラフが密になると間に合わなくなる。

以下、Editorials を参考にした。
問題の構造の特殊性を使う。二部グラフという発想からは離れないといけない。
箱を座標 4L の点、バンドを区間 [2K・R1, 2K・R2] とみると、M 個の区間, N 個の点に関する問題に言い換えられる。
この問題に関しては、区間スケジューリング問題とほぼ同様の Greedy 解法が適用できる。
すなわち、区間たちを右端の昇順でソートして、各箱について、一番左の区間を割り当てていく。

この問題は、点と区間への言い換えにさえ気づけば解けていたので、惜しかった。

E.
int main(){
int T; cin>>T;
while(T--){
int n; cin>>n;
map<string,int> f;
rep(i,n){
string name;
char vote; cin>>name>>vote;
if(vote=='+') f[name]=+1;
else f[name]=-1;
}

int ans=0;
map<string,int>::iterator it;
for(it=f.begin();it!=f.end();++it){
ans+=it->second;
}
printf("%d\n",ans);
}

return 0;
}

特に書くことがない。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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