スポンサーサイト

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

CodeChef June Cook-Off

2011/06/20 01:00 ~ 03:30 (JST)
CodeChef June Cook-Off の参加記録

Anton 回。

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

結果

問題を、問題ページの上から順に A, B, .. と呼ぶことにする。
A. -
B. -
C. -
D. 2WA, AC (00:33:44)
E. AC (01:03:17)
Standing : 57/413
Rank (Short) : 68 → 52
Rating (Short) : 1266.239 → 1313.323


問題

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

A.

B. D-Power Permutations
N を正整数, S = { 1, 2, ..., N } とする。
正整数 d に対して、全単射 f : S → S が d-power permutation であるとは、ある全単射 g : S → S が存在して、 gd = f となることをいう。
ここで、gd は g を d 回合成した写像を表す。

与えられた D, f に対して、f が d-power permutation になるような d (≦ D) の個数を求めよ。

1 ≦ N ≦ 700
1 ≦ D ≦ 1018

C. Correctness of Knight Move
入力される文字列がチェスのナイトの移動パターンとして正しいものかどうかを判定せよ。

文字列は、
・ ちょうど 5 文字からなり
・ 1, 2 文字目が移動前の場所を表し
・ 3 文字目がハイフン '-' であり
・ 4, 5 文字目が移動後の場所を表す
とき、correct な文字列であるとする。

correct な文字列が与えられたときは、ナイトの移動パターンとして正しいかどうかによって "Yes" or "No" と答えよ。
correct でない文字列が与えられたときは、"Error" と答えよ。

D. Sines Sum Queries
長さ N の整数列 A0, A1, ..., AN-1 があり、最初 Ai = i と初期化されている。

Q 個のクエリを処理せよ。
各クエリ "L R D" は、
・ D=0 のとき、sin (AL) + sin (AL+1) + ... + sin (AR) を計算する
・ D≠0 のとき、Ai = Ai + D (i = L, L+1, ..., R) と更新する
ことを意味する。

E. Super-plane
10000 個以下の空港があり、時間を逆行しうる飛行機が飛んでいる。
N 個のフライト予定 (どの空港からいつ出発して、どの空港にいつ着くか) が与えられる。

Dunno は、ある時間にある空港を出発して、別のある時間までにある空港に着くようにしたい。
Dunno は、考えなしに最初に空港に来た飛行機に乗ることを繰り返す。
Dunno が目的の時間までに目的の空港に着けるかどうかを答えよ。
着ける場合は、経由した飛行機の数も答えよ。

0 ≦ N ≦ 10000
0 ≦ フライト予定に登場する時間 ≦ 100000
同時刻、同じ空港から出発する飛行機は 1 機までと仮定していい。

解答

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

A.


B.

後半 1.5 時間くらいはずっとこの問題に取り組んでいた。
巡回群 ? とか位数 ? とかぐちゃぐちゃ考えていた。
Union-Find などを使って巡回する部分に分けて、それぞれをどうにかするんだろうなぁ、とは思った。

C.
int main(){
int T; scanf("%d",&T);
getchar();
while(T--){
char s[16]; fgets(s,16,stdin);
int len=strlen(s);
s[--len]='\0';
if(len!=5){ puts("Error"); continue; }

if('a'<=s[0] && s[0]<='h'
&& '1'<=s[1] && s[1]<='8'
&& s[2]=='-'
&& 'a'<=s[3] && s[3]<='h'
&& '1'<=s[4] && s[4]<='8'){
int dx=abs(s[3]-s[0]);
int dy=abs(s[4]-s[1]);
if(dx==2 && dy==1
|| dx==1 && dy==2) puts("Yes");
else puts("No");
}
else puts("Error");
}

return 0;
}

やるだけ問題だけど、テストケース数を読むときに scanf("%d ",&T); としたせいで、次の行の先頭にある空白も一緒に読み飛ばしてしまっていた。
原因を特定するのにかなり時間をとられた。

D.

N がもっと小さければ Fenwick Tree でできる気がした。
何も思いつかなかった。

E.
struct Flight{
int t1,t2,dst;
bool used;
Flight(){}
Flight(int T1,int T2,int D):t1(T1),t2(T2),dst(D),used(false){}
bool operator<(const Flight &f)const{ return t1<f.t1; }
};

int main(){
int T; scanf("%d",&T);
vector<Flight> fl[10001];
while(T--){
int n; scanf("%d",&n);
rep(i,10001) fl[i].clear();
rep(i,n){
int c1,t1,c2,t2; scanf("%d%d%d%d",&c1,&t1,&c2,&t2);
fl[c1].push_back(Flight(t1,t2,c2));
}
rep(i,10001) sort(all(fl[i]));
int pos,t,g,tg; scanf("%d%d%d%d",&pos,&t,&g,&tg);

int cnt;
bool ok=false;
for(cnt=0;;cnt++){
if(pos==g && t<=tg){ ok=true; break; }

vector<Flight>::iterator it=lower_bound(all(fl[pos]),Flight(t,-1,-1));
if(it==fl[pos].end() || it->used) break;
pos=it->dst;
t=it->t2;
it->used=true;
}

if(ok) printf("Yes %d\n",cnt);
else puts("No");
}

return 0;
}

分岐はないので、シミュレーションするだけ。
次に乗る便を求めるのには出発時間で二分探索すればいい。

何が一番難しいかというと、問題文を正しく読むのが一番難しい。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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