スポンサーサイト

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

XXV Colombian Programming Contest

2011/10/09 04:00~07:00 (JST)
UVa にて。

英語が読みにくいけど、意味がわかれば取り組みやすい問題が多かった。

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

結果

A. -
B. 4WA
C. 2WA
D. AC (01:59:38)
E. -
F. -
G. WA, AC (01:06:00)
H. -
I. AC (02:28:10)
J. AC (01:49:52)
Standing : 25/78


問題

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

C. Document Compression

m 個の元文書がある。
これらの中からいくつかを合成して新文書を作る。
各文書は 16 個以下の整数 ( 整数の値は 1 以上 16 以下 ) からなる。

文書を合成するとは、文書に含まれる整数の和集合をとるということ。

n 個の各新文書に対して、それを作るために必要な元文書の最小数を求めよ。

D. Digital Roulette

0 から N までの N+1 個の数字が書かれたルーレットがある。

整数係数の k 次多項式 P が与えられる。
トリガーをひく強さが x のとき、玉はルーレットの P(x) mod N+1 のマスに止まる。

強さを x = 0, 1, ..., M と変えたとき、玉の止まりうる位置は全部でいくつあるか?

1 ≦ N ≦ 107
0 ≦ M ≦ 105
0 ≦ k ≦ 10

E. Edgetown's Traffic Jams

頂点数 n の無向グラフと、その各辺に向きをつけた有向グラフが与えられる。
グラフのすべての点対に対して
( 無向グラフでの最短距離 ) ≦ A × ( 有向グラフでの最短距離 ) + B
が成立しているかどうか判定せよ。

3 ≦ n ≦ 100

G. Gas Stations

長さ L の直線状の道路に G 個のガソリンスタンドが点在している。
ガソリンスタンド i は閉区間 [xi - ri, xi + ri] にいる車にガソリンを与える。
道路のすべての位置においてガソリンが得られるようにした上で、最大でいくつのガソリンスタンドを潰すことができるか求めよ。
そもそもガソリンが供給されない位置がある場合はそのことを報告せよ。

1 ≦ L ≦ 108
1 ≦ G ≦ 104

H. Handgun Shooting Sport

問題文の図参照。
すべての線分を貫くには最小でいくつの半直線が必要か求めよ。

線分の個数は 103 以下。

I. Inspecting Radars

問題文の図参照。
天球の半径 R と N 個の星の位置が与えられる。

E 個のクエリに答えよ。
クエリ : 観測できる領域のパラメータ A, H が与えられる。α, H を任意に動かすとき、同時に見ることができる星の最大個数を求める

θ 方向は両端を含むが、R 方向は上端を含まないことに注意せよ。

1 ≦ N ≦ 104
2 ≦ R ≦ 102
1 ≦ E ≦ 102
入力値はすべて整数。
位置は極座標で指定される。

J. Philip J. Fry Problem

n 個の宇宙旅行の予定がある。旅行の順番は決まっている。
旅行 i には ti 時間がかかり、この旅行の後、宇宙空間には bi 個の暗黒物質が放出される。
各旅行において、宇宙空間にある暗黒物質を高々 1 つ取り込むことができて、そうした場合、旅行にかかる時間が半分になる。

最初、宇宙空間に暗黒物質はない。

すべての旅行を終えるのに最短でどれだけの時間がかかるか?

1 ≦ n ≦ 100
2 ≦ ti ≦ 1000 ( 偶数 )
0 ≦ bi ≦ n

解答

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

C. ( 時間外 )
const int INF=1<<29;

int main(){
for(int m,n;scanf("%d%d",&m,&n),m;){
int from[100]={};
rep(i,m){
int k; scanf("%d",&k);
from[i]=0;
rep(j,k){
int a; scanf("%d",&a); a--;
from[i]|=1<<a;
}
}

dp[1<<16];
rep(S,1<<16) dp[S]=(S==0?0:INF);

queue< pair<int,int> > qu; qu.push(make_pair(0,0));
while(!qu.empty()){
int c=qu.front().first,S=qu.front().second; qu.pop();
rep(i,m){
int S2=S|from[i];
if(dp[S2]>c+1){
dp[S2]=c+1;
qu.push(make_pair(c+1,S2));
}
}
}

rep(i,n){
int to=0,k; scanf("%d",&k);
rep(j,k){
int a; scanf("%d",&a); a--;
to|=1<<a;
}
printf("%d%c",dp[to]<INF?dp[to]:0,i<n-1?' ':'\n');
}
}

return 0;
}

m × 216 かかる二重ループの bit DP だとなぜか TLE した。
16 個より多くの元文書を組み合わせる意味はないので、BFS で書けばたくさん枝刈りできて、これだと通った。

メモ化再帰しようとしたら、状態がうまく表現できなくて驚いた。
ボトムアップの DP はできるけど、トップダウンのメモ化再帰はしにくい、珍しい問題だと思った。

D.
int b[10000001];

int main(){
for(int T=1,n,m;scanf("%d%d",&n,&m),n;T++){
int k,a[11]; scanf("%d",&k);
rep(i,k+1) scanf("%d",a+i);

int ans=0;
rep(x,m+1){
int px=0;
rep(i,k+1) px=(a[k-i]+(ll)x*px)%(n+1);
if(b[px]!=T) ans++, b[px]=T;
}
printf("%d\n",ans);
}

return 0;
}

どうみてもただのシミュレーションなのに、なぜか TLE。
色々高速化したあとに、間違えて B 問題に submit していたことに気付いた。ばか。

E. ( 時間外 )
const int INF=1<<29;

int main(){
for(int n;scanf("%d",&n),n;){
int d[2][100][100];
rep(l,2){
rep(i,n){
int j;
for(j=0;j<n;j++) d[l][i][j]=(i==j?0:INF);
for(scanf("%*d");getchar()==' ';) scanf("%d",&j), j--, d[l][i][j]=1;
}
rep(k,n) rep(i,n) rep(j,n) if(d[l][i][j]>d[l][i][k]+d[l][k][j]) d[l][i][j]=d[l][i][k]+d[l][k][j];
}

int a,b; scanf("%d%d",&a,&b);

bool ok=true;
rep(i,n) rep(j,n) if(a*d[0][i][j]+b<d[1][i][j]) { ok=false; break; }
puts(ok?"Yes":"No");
}

return 0;
}

問題文が無駄に長い。しかも前半はいかにも意味がありそうなのに本題にまったく関係ない。

意味がわかれば Warshall-Floyd やるだけ。

G.
struct Interval{
int a,b;
bool operator<(const Interval &I)const{ return a<I.a; }
};

int main(){
for(int l,n;scanf("%d%d",&l,&n),l;){
Interval I[10001];
rep(i,n){
int x,r; scanf("%d%d",&x,&r);
I[i].a=max(x-r,0);
I[i].b=min(x+r,l);
}
sort(I,I+n);
I[n].a=I[n].b=l+1;

int ans=n,p=0,next=0;
rep(i,n+1){
if(p<I[i].a){
if(p==next) break;
p=next;
ans--;
i--;
}
else next=max(next,I[i].b);
}
if(p<l) ans=-1;

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

return 0;
}

コンテスト中はこの問題のデバッグでかなり時間をとられた。
あまりにもひどいコードになったので、終わってから一から書き直してみたら、10 行以上短くなってうれしかった。

区間の左端でソートして、左の区間から見ていく。
位置 p = 0 はどれかの区間で覆わないといけないので、p を含んだ右端が最大の区間 A で覆うことにして、p を含むそれ以外の区間は捨てる。
次に、p = A の右端として同じことを繰り返す。
道路の終端まで行けば終了。

うまく実装すれば本処理は O(G) でできる。
全体の計算量はソートが支配的で O(G log G) になる。

実装量は少ないけど、書くのはけっこう難しいと思った。

H. ( 時間外 )
const double EPS=1e-9;

struct Interval{
double a,b;
bool operator<(const Interval &I)const{ return b<I.b; }
};

int main(){
for(int n;scanf("%d",&n),n;){
Interval I[1000];
rep(i,n){
double theta[2];
rep(j,2){
int x,y; scanf("%d%d",&x,&y);
theta[j]=atan2(y,x);
}
I[i].a=min(theta[0],theta[1]);
I[i].b=max(theta[0],theta[1]);
}

sort(I,I+n);

int ans=0;
double p=-1e77;
rep(i,n) if(p+EPS<I[i].a) p=I[i].b, ans++;

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

return 0;
}

コンテスト中は、誤って集合被覆問題に還元してしまって解けなくなっていた。

よく考えれば、「与えられた区間の集合に対して、すべての区間に少なくとも 1 つの点が乗っているような点集合の最小サイズはいくつか」 という問題に落ちる。
半円領域なので、区間が循環する心配もない。
これは Codeforces #22 D と同じ問題。
リンク先の記事にも書いたように、この問題には線形時間の Greedy 解法がある。

I.
int main(){
for(int n,r;scanf("%d%d",&n,&r),n;){
static int dp[101][1081];
rep(i,r+1) rep(j,1081) dp[i][j]=0;
rep(i,n){
int a,b; scanf("%d%d",&a,&b);
dp[a+1][b+1]=1;
dp[a+1][b+361]=1;
dp[a+1][b+721]=1;
}
rep(i,r) rep(j,1080) {
dp[i+1][j+1]+=dp[i+1][j]+dp[i][j+1]-dp[i][j];
}

int q; scanf("%d",&q);
while(q--){
int h,a; scanf("%d%d",&h,&a);
int ans=0;
for(int i=h;i<=r;i++) for(int j=a+1;j<=1080;j++) {
ans=max(ans,dp[i][j]-dp[i-h][j]-dp[i][j-a-1]+dp[i-h][j-a-1]);
}
printf("%d\n",ans);
}
}

return 0;
}

R-θ を直交座標だと思って長方形の領域を考える。
左端と右端がつながっていることに注意。( 円柱の側面みたいな感じ )

入力値がすべて整数なので、単純な DP で解ける。
dp[r][θ] := (0, 0)-(r, θ) で指定される長方形領域にある星の数
とする。
これを前計算しておけば、任意の長方形内にある星の数は O(1) で求められる。

左端と右端がつながっているので、θ 方向には 3 × 360 サイズの領域をとった。
ここまで広げれば、循環を気にせずに長方形内の星の数を数える問題だと思える。

境界のケースがサンプルに入っていて親切だと思った。

J.
const int INF=1<<29;

int main(){
for(int n;scanf("%d",&n),n;){
int t[100],b[100];
rep(i,n) scanf("%d%d",t+i,b+i);

static int dp[101][101];
rep(i,n+1) rep(j,n+1) dp[i][j]=(i==0&&j==0?0:INF);
rep(i,n){
for(int j=0;j<=n;j++){
int j2=min(j+b[i],n);
dp[i+1][j2]=min(dp[i+1][j2],dp[i][j]+t[i]);
if(j>0){
dp[i+1][j2-1]=min(dp[i+1][j2-1],dp[i][j]+t[i]/2);
}
}
}
printf("%d\n",*min_element(dp[n],dp[n]+n+1));
}

return 0;
}

典型的な DP。
dp[i][j] := その旅行 i が終わって、j 個の暗黒物質が残っているときの最短時間
とする。

感想

冷静に考えれば 7 問は解ける問題だった。
D で submit 先を間違え続けたのがあほすぎた。

B も、多倍長でなくて mod hoge で求めろという問題なら解けたはず。
まあ、これは言い訳だけど。

幾何は難しいけど、幾何のふりをした問題なら解ける。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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