スポンサーサイト

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

UAPC 2011 summer

2011/09/24 13:00~18:00 (JST) に開催された UAPC 2011 summer の参加記録。

Tags : プログラミング UAPC

結果

A. AC (00:15)
B. AC (01:08)
C. AC (01:40)
D. WA, AC (02:25)
E. AC (02:43)
F. AC (04:04)
G. -
H. -
I. AC (04:48)
J. -

Standing : 14/78


コンテスト中

コンテスト中に考えたことなど。

A. Popularity Estimation

ゆるゆりを意識して問題文を書いたのかなぁ、とか妄想しながら問題文を読んでいると、最初のサンプルにいきなり
akzakr があって笑った。

指示どおりに実装すればいい。

B. High and Low Cube

問題タイトルなどがアレ。けっこう好きだけど。
かなりめんどうな実装だけど、がんばって書いた。

C. Time Manipulation

元ネタを知らなかったのでそれっぽいキーワードで検索してみたら、作問者さんの twitter アイコンがヒットして笑った。

constraints が inclusion-exclusion しろと言っていたのでそれにしたがうことにした。
典型問題だと思う。類題が蟻本にもある。

D. The Great Summer Contest

Math と DP
Greedy と Graph
Geometry と Other
をそれぞれまとめて考えればいいことはすぐにわかる。

・ 3 ジャンルのうち、飛びぬけて多くのストックを持っているものがあれば、適当な回数、それらだけでコンテストを開くのがいい。
・ 3 ジャンルすべてが十分に多くのストックを持っていれば、それらを 1 つずつ使ってコンテストを開くのがいい。
という直感にしたがって書いた。
問題サイズがある程度小さくなったあとは全探索した。

想定解はもっとシンプルだった。

E. SAT-EN-3

加法標準形なので、矛盾式でない clause が 1 つ以上あるかどうかを判定するだけでいい。

F. Cosmic Market

難しい。
同じ行 (or 列) に対するクエリが複数回あった場合、最後のもののみが有効。
このことから、次のようにして解いた。

1.
前処理として、
・ 第 i 行に対する最後の着席クエリの番号
・ 第 i 行に対する最後の起立クエリの番号
を各行ごとに覚えておく。列についても同様。

2.
各行について、最後に立っている人の数を数えたい。
第 i 行に対する最後のクエリを Q とする。
・ Q が着席クエリだったとき
  ( Q より後に起立クエリが来た列の数 ) が答えになる
・ Q が起立クエリだったとき
  列数 - ( Q より後に着席クエリが来た列の数 ) が答えになる
これらは、前処理の結果を使って二分探索することで高速に求められる。

G. Everything Starts With Your Vote

もともと順位が高かった人から優先的に上位にするのが最適。
でも、必要な票数の計算がうまくできなかったので、コンテスト中には解けなかった。

H. World domination

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

I. 11224111122411

同じ文字が何文字連続するかを見て、それらの答えを掛け合わせればいい。
たとえば 11224111122411 なら、
( 11 の答え) × ( 22 の答え) × ( 4 の答え) × ( 1111 の答え) × ( 22 の答え) × ( 4 の答え) × ( 11 の答え)
が最終的な答えになる。

この部分問題をどうやって解くかだけど、うまい数え上げかたが思いつかなかったので、サンプルに載っていた数を元に OEIS で検索して、漸化式を見つけて解いた。ごめんなさい。

J. The Incubator

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



自分が解けるか解けないかというちょうどいいレベルの問題が多かった。
やっぱり Accepted が多いと楽しい。

ソースコード

A.
int main(){
for(int n;scanf("%d",&n),n;){
int pt[30]={};
rep(i,30) pt[i]=n+1;

char name[20][11];
int m[20],d[20][30];
rep(i,n){
scanf("%s%d",name[i],m+i);
rep(j,m[i]){
scanf("%d",d[i]+j);
pt[d[i][j]]--;
}
}

int ans,ians;
rep(i,n){
int sum=0;
rep(j,m[i]) sum+=pt[d[i][j]];
if(i==0 || ans>sum || ans==sum && strcmp(name[ians],name[i])>0){
ans=sum;
ians=i;
}
}
printf("%d %s\n",ans,name[ians]);
}

return 0;
}


B.
const char PTTN[9][5][6]={
{
".....",
"...|.",
".....",
"...|.",
"..-.."
},{
"..-..",
"...|.",
"..-..",
".|...",
"..-.."
},{
"..-..",
"...|.",
"..-..",
"...|.",
"..-.."
},{
".....",
".|.|.",
"..-..",
"...|.",
"....."
},{
"..-..",
".|...",
"..-..",
"...|.",
"..-.."
},{
"..-..",
".|...",
"..-..",
".|.|.",
"..-.."
},{
"..-..",
"...|.",
".....",
"...|.",
"....."
},{
"..-..",
".|.|.",
"..-..",
".|.|.",
"..-.."
},{
"..-..",
".|.|.",
"..-..",
"...|.",
"..-.."
}};

void flipLR(char face[5][5]){
rep(i,5) rep(j,2) swap(face[i][j],face[i][4-j]);
}

void flipUD(char face[5][5]){
rep(i,2) rep(j,5) swap(face[i][j],face[4-i][j]);
}

void rot90(char face[5][5]){
static int g[128];
g['|']='-'; g['-']='|'; g['.']='.';

char tmp[5][5];
rep(i,5) rep(j,5) tmp[4-j][i]=g[face[i][j]];

rep(i,5) rep(j,5) face[i][j]=tmp[i][j];
}

void f(char face[5][5],int k){
switch(k){
case 0:
case 2:
case 4:
flipLR(face);
break;
case 1:
flipLR(face);
rot90(face);
break;
case 3:
flipLR(face);
rot90(face); rot90(face); rot90(face);
break;
case 5:
flipUD(face);
flipLR(face);
break;
}
}

void parse(const char die[21][28],int num[6]){
// upper left coordinate
const int ul[6][2]={{0,7},{7,0},{7,7},{7,14},{7,21},{14,7}};

rep(k,6){
int t=ul[k][0]+1,l=ul[k][1]+1;
rep(d,9){
char face[2][5][5];
rep(i,5) rep(j,5) {
face[0][i][j]=die[i+t][j+l];
face[1][i][j]=PTTN[d][i][j];
}
f(face[1],k);

bool eq=true;
rep(i,5) rep(j,5) if(face[0][i][j]!=face[1][i][j]) eq=false;
if(eq){ num[k]=d+1; break; }
}
}
}

int main(){
while(1){
char die[2][21][28];
rep(i,21){
char s[58]; scanf("%s",s);
rep(j,28){
die[0][i][j]=s[j];
die[1][i][j]=s[j+29];
}
}
if(die[0][0][0]=='0') break;

int num[2][6];
rep(k,2) parse(die[k],num[k]);

int win=0,tot=0;
rep(i,6) rep(j,6) {
if(num[0][i]> num[1][j]) win++;
if(num[0][i]!=num[1][j]) tot++;
}
puts(2*win>=tot?"HIGH":"LOW");
}

return 0;
}


C.
ll gcd(ll a,ll b){ return b?gcd(b,a%b):a; }
ll lcm(ll a,ll b){ return a/gcd(a,b)*b; }

int main(){
for(int n,m;scanf("%d%d",&n,&m),n;){
int p[20];
rep(i,m) scanf("%d",p+i);

ll sum=0,tot=0;
rep(S,1<<m){
ll L=1,pc=0;
rep(i,m) if(S&(1<<i)) L=lcm(L,p[i]), pc++;

if(L<=n){
if(pc%2==1) sum-=(L+n)*(n/L)/2, tot-=n/L;
else sum+=(L+n)*(n/L)/2, tot+=n/L;
}
}
printf("%.9f\n",tot==0?0:(double)sum/tot);
}

return 0;
}


D. (自分の解法)
int dfs(int a,int b,int c){
int res=0;
if(a>=3) res=max(res,dfs(a-3,b,c)+1);
if(b>=3) res=max(res,dfs(a,b-3,c)+1);
if(c>=3) res=max(res,dfs(a,b,c-3)+1);
if(a>0 && b>0 && c>0) res=max(res,dfs(a-1,b-1,c-1)+1);
return res;
}

int main(){
while(1){
int n[3]={};
rep(i,6){
int a; scanf("%d",&a);
n[i%3]+=a;
}
if(n[0]==0 && n[1]==0 && n[2]==0) break;

int ans=0;
int n0=min(min(n[0],n[1]),n[2]);
// ストック数が飛びぬけて多いものはそれらだけでコンテストを開く
rep(i,3){
ans+=(n[i]-n0)/3;
n[i]-=(n[i]-n0)/3*3;
}
// 1 つずつ使ってコンテストを開く
ans+=max(n0-3,0);
rep(i,3) n[i]-=max(n0-3,0);

// 残った数回分は全探索する
printf("%d\n",ans+dfs(n[0],n[1],n[2]));
}

return 0;
}


D. (想定解)
int main(){
while(1){
int n[3]={};
rep(i,6){
int a; scanf("%d",&a);
n[i%3]+=a;
}
if(n[0]==0 && n[1]==0 && n[2]==0) break;

int ans=0;
rep(i,3){
int sum=0,ok=1;
rep(j,3) if(n[j]>=i) sum+=(n[j]-i)/3; else ok=0;
if(ok) ans=max(ans,i+sum);
}
printf("%d\n",ans);
}

return 0;
}

解けただけで満足しないで、よい解法はできるだけフォローするようにしたい。

E.
int idx;
char s[501];

int variable(){
int res=s[idx];
idx++;
return res;
}

int literal(){
int sgn=1;
if(s[idx]=='~') sgn*=-1, idx++;
return sgn*variable();
}

bool clause(){
int a,b,c;
a=literal(); idx++;
b=literal(); idx++;
c=literal();
return !(a+b==0 || b+c==0 || c+a==0);
}

bool expr(){
bool res;
idx++;
res=clause();
idx++;
while(s[idx]=='|'){
idx+=2;
res|=clause();
idx++;
}
return res;
}

bool parse(){
idx=0;
return expr();
}

int main(){
for(;scanf("%s",s),s[0]!='#';) puts(parse()?"yes":"no");
return 0;
}

典型的な構文解析解法

E. (手抜き解法)
int main(){
for(char s[501];scanf("%s",s),s[0]!='#';){
bool ok=false;
// アルファベットが 3 つ現れるたびに、その節が矛盾式かどうかをチェックする
for(int i=0,c=0,a[3];s[i];i++){
if(isalpha(s[i])) a[c++]=(s[i-1]=='~'?-1:1)*s[i];
if(c==3){
if(a[0]+a[1] && a[1]+a[2] && a[2]+a[0]) ok=true;
c=0;
}
}
puts(ok?"yes":"no");
}
return 0;
}


F.
int main(){
for(int r,c,q;scanf("%d%d%d",&r,&c,&q),r;){
static int row[50000][2],col[50000][2];
rep(i,r){
row[i][0]=-1;
row[i][1]=-2;
}
rep(j,c){
col[j][0]=-3;
col[j][1]=-4;
}

rep(t,q){
int a,b,ord; scanf("%d%d%d",&a,&b,&ord);
if(a==0) row[b][ord]=t;
else col[b][ord]=t;
}

static int v0[50000],v1[50000];
rep(j,c){
if(col[j][0]<col[j][1]){
v0[j]=col[j][1];
v1[j]=-5;
}
else{
v0[j]=-5;
v1[j]=col[j][0];
}
}
sort(v0,v0+c);
sort(v1,v1+c);

ll ans=0;
rep(i,r){
if(row[i][1]<row[i][0]){ // i 行目が最後に座った
ans+=(v0+c)-lower_bound(v0,v0+c,row[i][0]);
}
else{ // i 行目が最後に立った
ans+=lower_bound(v1,v1+c,row[i][1])-v1;
}
}
printf("%lld\n",ans);
}

return 0;
}


G. (あとで解いた)
struct Idol{
int vote;
bool love;
string name;
bool operator<(const Idol &I)const{
if(vote!=I.vote) return vote>I.vote;
return name<I.name;
}
};

int main(){
for(int n,m,k,l;scanf("%d%d%d%d",&n,&m,&k,&l),n;){
map<string,int> f;
static Idol I[100000];
rep(i,n){
char s[11]; scanf("%s%d",s,&I[i].vote);
I[i].name=s;
f[s]=i;
I[i].love=false;
}
rep(i,m){
char s[11]; scanf("%s",s);
I[f[s]].love=true;
}
sort(I,I+n);

int lo=0,hi=k;
while(lo<hi){
int mi=(lo+hi+1)/2;

// x 人が上位 k 位に入るには、x 人全員が、元々 k-x 位だった人より上位にいることが必要十分
int thr=n-1,cnt=0;
rep(i,n) if(!I[i].love) {
if(cnt==k-mi){ thr=i; break; }
cnt++;
}

cnt=0;
int v=l;
rep(i,n) if(I[i].love) {
int tmp;
if(i>thr) tmp=I[thr].vote-I[i].vote+(I[thr].name<I[i].name?1:0);
else tmp=0;

if(v>=tmp) v-=tmp, cnt++;
else break;
}

if(cnt>=mi) lo=mi; else hi=mi-1;
}

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

return 0;
}

解説スライドと simezi_tan さんのブログ を見て解いた。
「 x 人が上位 k 位に入るには、x 人全員が、元々 k-x 位だった人より上位にいればいい 」
というのが一番のポイントで、これに気付けるのはスマートだなぁと思った。

H. (あとで解いた)
ll xgcd(ll a,ll b,ll &x,ll &y){
if(b==0){ x=1; y=0; return a; }
ll g=xgcd(b,a%b,y,x); y-=a/b*x;
return g;
}

ll modinv(ll a,ll m){
ll x,y;
if(xgcd(a,m,x,y)==1) return (x+m)%m;
return -1;
}

int n,id[100];
double p[100],w[100];

bool vis[100];

void dfs1(int u,vector<int> &cyc){
if(vis[u]) return;
vis[u]=true;
cyc.push_back(u);
dfs1(id[u],cyc);
}

double dfs2(int u,bool first){
if(vis[u]) return 0;
vis[u]=true;
return 1/(first?p[u]:w[u])+dfs2(id[u],false);
}

int main(){
ll fact[101]={1},factinv[101]={1};
rep(i,100){
fact[i+1]=(i+1)*fact[i]%M;
factinv[i+1]=modinv(i+1,M)*factinv[i]%M;
}

for(;scanf("%d",&n),n;){
rep(u,n) scanf("%lf%d%lf",p+u,id+u,w+u);

int m=0;
vector<int> cyc[100];
fill(vis,vis+n,false);
rep(u,n) if(!vis[u]) dfs1(u,cyc[m++]);

double ans=0;
ll ans2=fact[n];
rep(i,m){
double ex=1e70;
ll cnt=0;
rep(j,cyc[i].size()){
fill(vis,vis+n,false);
double tmp=dfs2(cyc[i][j],true);
if(tmp<ex-EPS){
ex=tmp;
cnt=1;
}
else if(abs(ex-tmp)<EPS){
cnt++;
}
}
ans+=ex;
ans2=ans2*cnt%M;
ans2=ans2*factinv[cyc[i].size()]%M;
}
printf("%.11f %ld\n",ans,ans2);
}

return 0;
}

解説スライドを見ながら解いた。
問題が理解できればそれほど難しくなかった。 ( 言い訳

確率 p で成功するとき、1 回成功するのに必要な試行回数の期待値は 1/p である
というのはよく出てくるし、直感にもあっているから理解しやすい。

場合の数についても、
サイズ a, b, c の 3 つの箱があって、n = a+b+c 個のボールを 3 つの箱に分けて入れるときの入れ方の総数は n!/(a! b! c!) になる
ということを使えば楽に数えられる。 (3 つ以上にも一般化できる)

I. (自分の解法)
const ll M=100000007;

int main(){
int T[128]; // period
T['1']=T['2']=T['3']=T['4']=T['5']=T['6']=T['7']=T['9']=5;
T['8']=T['0']=3;

// 周期 T の文字が i 個連続している状態から dp[T][i] 通りの文字列ができる
static ll dp[6][100001];
rep(k,2){
int T=(k==0?5:3);
rep(i,T+1) dp[T][i+1]=1<<i;
for(int i=T+1;i<100000;i++) dp[T][i+1]=((2*dp[T][i]-dp[T][i-T])%M+M)%M;
}

for(char s[100001];scanf("%s",s),s[0]!='#';){
ll ans=1;
for(int i=1,p=0;s[i-1];i++) if(s[i-1]!=s[i]) {
ans=(ans*dp[T[s[i-1]]][i-p])%M;
p=i;
}
printf("%lld\n",ans);
}

return 0;
}


I. (想定解)
const ll M=100000007;

ll dp[2][100001];

ll f(char c,int n){ return (c=='0'||c=='8')?dp[0][n]:dp[1][n]; }

int main(){
rep(t,2){
int T=(t==0?3:5);
rep(i,T) dp[t][i+1]=1<<i;
// 周期 T のループがないような変換結果のみを数える
for(int i=T;i<100000;i++) rep(j,T) dp[t][i+1]=(dp[t][i+1]+dp[t][i-j])%M;
// T, 2T, ... 個前の値を足す (余分な kT 個は最後の文字につけると思えば重複カウントしない)
for(int i=T;i<100000;i++) dp[t][i+1]=(dp[t][i+1]+dp[t][i+1-T])%M;
}

for(char s[100001];scanf("%s",s),s[0]!='#';){
ll ans=1;
for(int i=1,p=0;s[i-1];i++) if(s[p]!=s[i]) ans=ans*f(s[p],i-p)%M, p=i;
printf("%lld\n",ans);
}
return 0;
}

解説スライドを見て理解した。賢い。

J. (あとで解いた)
template<class T>
class FenwickTree{
vector<T> a;
public:
FenwickTree(int n):a(n){}
T sum(int i,int j)const{
if(i==0){
T s=0;
for(;j>=0;j=(j&(j+1))-1) s+=a[j];
return s;
}
return sum(0,j)-sum(0,i-1);
}
void add(int i,T v){
for(;i<a.size();i|=i+1) a[i]+=v;
}
};

// 左から数えて x 番目にある 1 の位置を求める
int calc(int n,const FenwickTree<int> &ft,int x){
int lo=0,hi=n-1;
while(lo<hi){
int mi=(lo+hi)/2;
if(ft.sum(0,mi)<x) lo=mi+1; else hi=mi;
}
return lo;
}

int main(){
for(int nq,lim;scanf("%d%d",&nq,&lim),nq;){
int n=0,m=0; // n : 生きている個体の総数, m : 次に個体を追加する位置

map<int,int> f;
static int id[400000];

FenwickTree<int> ft(nq);
rep(_,nq){
int q,x; scanf("%d%d",&q,&x);
if(q==0){
ft.add(m,1);
f[x]=m;
id[m]=x;
m++;
n++;
if(n>lim){
ft.add(calc(nq,ft,1),-1);
n--;
}
}
else if(q==1){
ft.add(calc(nq,ft,x),-1);
n--;
}
else if(q==2){
printf("%d\n",id[calc(nq,ft,x)]);
}
else{
ft.add(f[x],-1);
n--;
}
}
puts("end");
}

return 0;
}

BIT を使って解いた。
個体が消されても配列を詰めるということをせずに、あとにあとに追加していくのがポイント。
a. 配列の末尾に追加するクエリは O(1) でできる。
b. id が x の個体を削除するクエリは、id と配列上の位置の対応を map で覚えておけば O(log Q) でできる
c. 生きている個体の中で x 番目のものを削除するクエリは、BIT で二分探索すれば O(log2 Q) でできる
d. 生きている個体の中で x 番目のものを出力するクエリは c. と同じ
e. lim を超えると前から消していく仕様は、1 番目の個体を削除すると思えば c. と同じ
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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