スポンサーサイト

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

UAPC 2011

2011/06/05 13:00~18:00 (JST) に開催された UAPC 2011。

この日は都合が合わなくて参加できなかったので、09/01 の夜に AOJ の Virtual Arena を借りて一人コンテストしてみました。

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

結果

A. AC (00:11)
B. WA, AC (01:20)
C. PE, AC (04:07)
D. -
E. -
F. -
G. WA, 2TLE
H. 3WA, 3TLE, AC (03:15)
I. -
J. -
K. AC (03:31)
L. -

Standing : 1/1 (


コンテスト中

A. 伝票整理

A 問題にしてはややこしい。
適当に書いて提出。 AC.

B. アニメスケジューリング

え、難しい。
区間スケジューリング問題の応用みたいな感じかな。

23:59 と 0:00 みたいなケースで時間がかぶるときの処理が厄介だなぁ。 ( そんなケースはない

蟻本の Log ステップ DP の項目にあった例題に似てる。
まぁ、これはサイズが小さいので、使う区間を 1 つ決め打ちする方法で間に合う。
書く。
ややこしい。
書く。
サンプル合った。
submit.
:
WA

なんでだろう。
問題を読み直す。
ここで、アニメの開始時刻が 6:00~29:29 だということに気付く。

日をまたいでかぶらないじゃん!!

なら普通の区間スケジューリングだ。
もちろん、絶対使わないといけない区間はあらかじめ抽出しておいて、それらとかぶる区間は最初から候補にいれない。

区間スケジューリングは終端ソートして、Greedy に選べばいい。

C. マンガ読み読み

実装するだけっぽいけど複雑そう。
あとでやろう。

D. グラフを 2 つに分割する何か

問題文がいまいち読み取れない。
グラフの全域最小カットっぽいなぁと思った。
とりあえずパス。

あと、サンプル超弱い。

E. 円の中で多角形ころころ

幾何 + シミュレーション。
丁寧にやればできなくはないけど...パス。

F. チョコレート分割 (やや知的)

また幾何か...
E よりは書きやすそう。
アーモンドがどのピースにあるかは二分探索でできる。
面積 S 以上というのも、尺取法でなめれば O(n) でできる。 ( ここも二分探索でもできた

時間があれば書けそう。
保留。

G. 2D RMQ

典型的な 2 次元の Range Minimum Query.
しかしそんなライブラリは持っていない。

よく考えずに平方分割解法を書いてみる。
わりとすぐに書きあがった。
submit...TLE
微高速化...TLE

だめだ。
まともな 2D RMQ を書ける自信はまるでないのであきらめ。

H. 乗算しなイカ

これも取り組みやすそうな気がした。
偶数が 1 つだけあるので、それを使って hogehoge するんだろうと思う。

反射的に bi のうち偶数のものすべての GCD を計算してみた。
これの約数が a0 の候補になる。
a0 を決めうちすれば、偶数の bi を a0 で割ることで、すべての ai を復元できる。
復元した ai から bi を再構成して、入力された bi と完全に一致するかを調べればいい。

書いた。
submit...TLE.

mm..
復元した ai が正しいものかのチェックがボトルネックな気がしたので、この部分を乱択アルゴリズムに変えてみる。
TLE.
TLE.

mmm...
あ、よく考えたら GCD が 264 くらい大きくなりうるので、約数列挙の時点で絶望する。
方針を大きく変えないといけない。

thinking...

奇数の bi を 1 つ選んで固定する。 (bo とする)
偶数の bi を 2 つ選ぶ。 (be1, be2 とする)
うまく be1, be2 を選んだとき be1×be2/bo = a02 となる。
なので、be1, be2 の任意の選び方に対して √(be1×be2/bo) を計算すると、これが a0 の候補になる。

a0 が決まれば、上に書いた方法で ai がすべて復元できる。

書いた。
submit...AC!!

この時点で 3 時間以上経っている。ようやく 3AC.

I. 数列に何かする

問題文が長すぎて読めなかった。

J. 何か

文字列系のアルゴリズム + ほげ だと思う。

K. 席替え

簡単そう。
まず、縦か横の少なくとも一方が偶数なら自明に席替え可能。 (隣同士入れ替えればいい)

奇数×奇数の場合はどうだろう。
無理そう。どうやっても 1 人余る。

こんな簡単でいいのかな。
まぁ、ためしに送ってみよう。

submit..AC.
通ってしまった。

L. 超大作

どうみても超シミュレーション。

一通り見たので C. に戻る。

C.

後ろの難しい問題たちを考えたあとだから C が易しくみえる。

書いた。
サンプル合わない。
何でだ。
問題文読み直し。
あ、座標軸の取り方が直感と違う。きもい

修正。
サンプル合った。
submit...AC.

あと 1 時間弱。
比較的解けそうな F をやってみよう。

F.

方針は上に書いたとおり。

なかなかサンプル合わない。
尺取法の実装難しすぎる。

修正。
サンプル合わない。
修正。
サンプル合わない。
修正。
サンプル合わない。

時間切れ。ひどい。



F. が通らなかったのは残念だけど、かなり楽しかった。
問題は全体的に難しめのものが多かった印象。
実装量はちょっと多めだった気もする。

一人でやるのもたまにはいいかもしれない。

ソースコード

A.
#include<cstdio>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

int main(){
for(int n;scanf("%d",&n),n;){
int ans[3]={},tot[3]={};
rep(_,n){
int h,m,m2; scanf("%d:%d%d",&h,&m,&m2);
if(m2<m) m2+=60;

int t=60*h+m;
if (11<=h && h<15){ tot[0]++; if(m2-m<=8) ans[0]++; }
else if(18<=h && h<21){ tot[1]++; if(m2-m<=8) ans[1]++; }
else if(21<=h || h< 2){ tot[2]++; if(m2-m<=8) ans[2]++; }
}

char *s[]={"lunch","dinner","midnight"};
rep(i,3){
if(tot[i]==0) printf("%s no guest\n",s[i]);
else printf("%s %d\n",s[i],100*ans[i]/tot[i]);
}
}

return 0;
}


B.
#include<map>
#include<cstdio>
#include<string>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

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

bool intersect(const Interval &I,const Interval &J){
return I.a<J.b && J.a<I.b;
}

int solve(int n,Interval *I){
sort(I,I+n);

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

return ans;
}

int main(){
for(int n;scanf("%d",&n),n;){
map<string,int> f;
Interval I[500];
rep(i,n){
char name[33];
int week,start; scanf("%s%d%d",name,&week,&start);
f[name]=i;

int h=start/100,m=start%100;
start=week*24*60+h*60+m;
I[i]=Interval(start,start+30);
}

int nf; scanf("%d",&nf);
Interval fav[500];
rep(i,nf){
char name[33]; scanf("%s",name);
fav[i]=I[f[name]];
}

bool ok=true;
rep(j,nf) rep(i,j) if(intersect(fav[i],fav[j])) ok=false;
if(!ok){ puts("-1"); continue; }

int n2=0;
Interval J[500];
rep(i,n){
bool ok=true;
rep(j,nf) if(intersect(I[i],fav[j])) ok=false;
if(ok) J[n2++]=I[i];
}

printf("%d\n",nf+solve(n2,J));
}

return 0;
}


C.
#include<cstdio>
#include<vector>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const int INF=1<<29;

struct Rect{ int t,l,b,r,id; };

int n,ans[10];

void simulate(vector<Rect> rc,int &order){
while(!rc.empty()){
int i0=0;
rep(i,rc.size()){
if(rc[i0].l>rc[i].l || (rc[i0].l==rc[i].l && rc[i0].t>rc[i].t)) i0=i;
}
ans[rc[i0].id]=order++;

int r=INF,x1=rc[i0].l,x2=rc[i0].r,y=rc[i0].b;
rc.erase(rc.begin()+i0);
rep(i,rc.size()){
if(rc[i].t<y && y<rc[i].b && rc[i].l<=x2) r=min(r,rc[i].l);
}

vector<Rect> next;
rep(i,rc.size()){
if(rc[i].b<=y && x1<=rc[i].l && rc[i].r<=r){
next.push_back(rc[i]);
rc.erase(rc.begin()+i);
i--;
}
}
if(!next.empty()) simulate(next,order);
}
}

int main(){
for(int T=0,n;scanf("%d",&n),n;T++){
if(T) putchar('\n');

vector<Rect> rc(n);
rep(i,n){
scanf("%d%d%d%d",&rc[i].l,&rc[i].t,&rc[i].r,&rc[i].b);
if(rc[i].t>rc[i].b) swap(rc[i].t,rc[i].b);
if(rc[i].l>rc[i].r) swap(rc[i].l,rc[i].r);
rc[i].id=i;
}

int order=1;
simulate(rc,order);

rep(i,n) printf("%d\n",ans[i]);
}

return 0;
}


D. (あとで解いた)
#include<queue>
#include<cstdio>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const int INF=1<<29;

template<class T>
struct AdjMatrix:public vector< vector<T> >{
AdjMatrix(int n,const vector<T> &v=vector<T>()):vector< vector<T> >(n,v){}
};

template<class T>
T augment(const AdjMatrix<T> &capa,int src,int snk,AdjMatrix<T> &flow){
int n=capa.size();
vector<int> parent(n,-1); parent[src]=-2;

T water=0;
queue< pair<T,int> > qu; qu.push(make_pair(INF,src));
while(!qu.empty()){
pair<T,int> a=qu.front(); qu.pop();
int u=a.second;
T w=a.first;
if(u==snk){ water=w; break; }
rep(v,n) if(parent[v]==-1 && capa[u][v]-flow[u][v]>0) {
qu.push(make_pair(min(w,capa[u][v]-flow[u][v]),v));
parent[v]=u;
}
}

if(water==0) return 0;

for(int v=snk,u=parent[snk];v!=src;v=u,u=parent[u]){
flow[u][v]+=water;
flow[v][u]-=water;
}

return water;
}

template<class T>
T FordFulkerson(const AdjMatrix<T> &capa,int src,int snk){
int n=capa.size();
AdjMatrix<T> flow(n,vector<T>(n));

T ans=0;
while(1){
T water=augment(capa,src,snk,flow);
if(water==0) break;
ans+=water;
}
return ans;
}

int main(){
for(int n,m;scanf("%d%d",&n,&m),n;){
int ans=0;
AdjMatrix<int> adj(n,vector<int>(n));
rep(i,m){
int u,v,w; scanf("%d%d%d",&u,&v,&w);
if(w<0) ans+=w;
adj[u][v]=adj[v][u]=max(w,0);
}

int ans2=INF;
rep(v,n) if(v!=0) ans2=min(ans2,FordFulkerson(adj,0,v));
printf("%d\n",ans+ans2);
}

return 0;
}

[ 2011/09/22 追記 ]

無向グラフの全域最小カットそのものだった。
全域最小カットを求めるのは最大隣接順序を利用する高速なアルゴリズムがあるけど、この問題のサイズなら |V|-1 回最大流を流すだけでも間に合う。
最大流はライブラリから貼り付け。グラフを隣接行列でもっているので遅い。
ちなみに、想定解は別にあって、グラフの特殊性を利用するらしい。

F. (あとで解いた)
#include<cstdio>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const int INF=1<<29;
const double EPS=1e-9;

struct Choco{
int nut;
double S;
};

int n,m,w,h,thre;
Choco ch[30000];

int solve(){
static Choco acc[30001];
acc[0]=(Choco){0,0};
rep(i,m) acc[i+1]=(Choco){acc[i].nut+ch[i].nut,acc[i].S+ch[i].S};

int ans=INF;
rep(i,m){
int lo=i,hi=m;
while(lo<hi){
int mi=(lo+hi+1)/2;
if(acc[mi].S-acc[i].S<w*h-thre+EPS) lo=mi; else hi=mi-1;
}
ans=min(ans,n-(acc[lo].nut-acc[i].nut));
}
return ans;
}

int main(){
for(;scanf("%d%d%d%d%d",&n,&m,&w,&h,&thre),n;){
static int l[30001],r[30001];
l[0]=r[0]=0;
rep(i,m) scanf("%d%d",l+i+1,r+i+1);

rep(i,m){
ch[i].S=((l[i+1]-l[i])+(r[i+1]-r[i]))/2.0*w;
ch[i].nut=0;
}
rep(i,n){
double cx,cy; scanf("%lf%lf",&cx,&cy);

int lo=0,hi=m+1;
while(lo<hi){
int mi=(lo+hi+1)/2;
if((w-cx)*l[mi]+cx*r[mi]<w*cy) lo=mi; else hi=mi-1;
}
ch[lo].nut++;
}

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

return 0;
}

結局、全部二分探索で書いた。

G. (あとで解いた)
#include<cstdio>
#include<vector>
#include<cstdlib>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;

const int INF=(1<<31)-1;

template<class T> struct Interval{
T a,b;
Interval(T A,T B):a(A),b(B){}
};

template<class T>
class RMQ{
int n;
T *a;

T query(const Interval<int> &I,const Interval<int> &J,int u){
if(J.b<=I.a || I.b<=J.a) return INF;
if(I.a<=J.a && J.b<=I.b) return a[u];

int m=(J.a+J.b)/2;
T tl=query(I,Interval<int>(J.a,m),2*u+1);
T tr=query(I,Interval<int>(m,J.b),2*u+2);
return tl<tr?tl:tr;
}

public:
RMQ(){}

RMQ(const vector< vector<T> > &v,int k,int b):n(1){
int N;
if(!b) N=v[0].size();
else N=v.size();

while(n<N) n<<=1;
a=(T *)malloc((2*n-1)*sizeof(T));
rep(i,2*n-1) a[i]=0;

if(!b) rep(i,N) a[n+i-1]=v[k][i];
else rep(i,N) a[n+i-1]=v[i][k];

for(int i=n-2;i>=0;i--) a[i]=min(a[2*i+1],a[2*i+2]);
}

T query(int a,int b){
return query(Interval<int>(a,b),Interval<int>(0,n),0);
}
};

int main(){
for(int h,w,q;scanf("%d%d%d",&h,&w,&q),h||w||q;){
vvi a(h,vi(w));
rep(i,h) rep(j,w) scanf("%d",&a[i][j]);

RMQ<int> *rmq1=(RMQ<int> *)malloc(h*sizeof(RMQ<int>));
RMQ<int> *rmq2=(RMQ<int> *)malloc(w*sizeof(RMQ<int>));
rep(i,h) rmq1[i]=RMQ<int>(a,i,0);
rep(j,w) rmq2[j]=RMQ<int>(a,j,1);

rep(_,q){
int t,l,b,r; scanf("%d%d%d%d",&t,&l,&b,&r); b++; r++;

int ans=INF;
if(b-t<r-l) for(int i=t;i<b;i++) ans=min(ans,rmq1[i].query(l,r));
else for(int j=l;j<r;j++) ans=min(ans,rmq2[j].query(t,b));
printf("%d\n",ans);
}
}

return 0;
}

一次元 RMQ を工夫して使えば通った。
メモリ制限が厳しいので vector の代わりに malloc を使った。

H.
#include<cmath>
#include<cstdio>
#include<vector>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef long long ll;

ll gcd(ll a,ll b){ return b?gcd(b,a%b):a; }

int main(){
for(int n;scanf("%d",&n),n;){
static ll b[32000];
int m=n*(n+1)/2;
rep(i,m) scanf("%lld",b+i);

int n_ev=0,n_od=0;
static ll b_ev[250],b_od[32000];
rep(i,m){
if(b[i]%2==0) b_ev[n_ev++]=b[i];
else b_od[n_od++]=b[i];
}

sort(b_ev,b_ev+n_ev);
sort(b_od,b_od+n_od);

vector<ll> a0_cand;
rep(j,n_ev) rep(i,j) {
ll x=b_ev[i],y=b_ev[j],z=b_od[0],g;
g=gcd(x,z); x/=g; z/=g;
g=gcd(y,z); y/=g; z/=g;
if(z==1){
ll a0=(ll)(sqrt(x)*sqrt(y)+0.5);
for(ll t=max(a0-1,2LL);t<=a0+1;t++){
if(t%2==0 && t*t==x*y) a0_cand.push_back(t);
}
}
}

ll a0;
static ll a_od[250];
rep(i,a0_cand.size()){
a0=a0_cand[i];

rep(j,n) a_od[j]=b_ev[j]/a0;

int n_od2=0;
static ll b_od2[32000];
rep(k,n_ev) rep(j,k) b_od2[n_od2++]=a_od[j]*a_od[k];
sort(b_od2,b_od2+n_od2);

bool ok=true;
rep(j,n_od) if(b_od[j]!=b_od2[j]) { ok=false; break; }
if(ok) break;
}

printf("%lld\n",a0);
rep(i,n_ev) printf("%lld%c",a_od[i],i<n_ev-1?' ':'\n');
}

return 0;
}


K.
#include<cstdio>

using namespace std;

int main(){
for(int r,c;scanf("%d%d",&r,&c),r;) puts((r*c)%2==0?"yes":"no");
return 0;
}

スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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