読者です 読者をやめる 読者になる 読者になる

beet's soil

競プロのことなど

square869120Contest #4

双子コン。35th

Fの部分点が時間内に通ってれば8位だったので悔しい。
(問題文のミスをらてさんに教えてもらって通したので無理だけど)

【A - Atcoder Handles】

N個の文字列が与えられる。読めなくなっている部分がある。
これらにある文字列Tを加えてソートした時Tが取りうる番号を全て求めよ。

必ず大きいものと必ず小さいものの数を数えれば求まるので求める。
O(N(|S|+|T|)).

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n;
  cin>>n;
  string s[n];
  for(int i=0;i<n;i++) cin>>s[i];
  string t;
  cin>>t;
  int a=0,b=0;
  for(int i=0;i<n;i++){
    string u[2],v[2];
    u[0]=u[1]=s[i];
    v[0]=v[1]=t;
    for(int j=0;j<(int)s[i].size();j++)
      if(s[i][j]=='?') u[0][j]='a';
    for(int j=0;j<(int)t.size();j++)
      if(t[j]=='?') v[0][j]='z';
    for(int j=0;j<(int)s[i].size();j++)
      if(s[i][j]=='?') u[1][j]='z';
    for(int j=0;j<(int)t.size();j++)
      if(t[j]=='?') v[1][j]='a';
    if(u[0].compare(v[0])>0) b++;
    if(v[1].compare(u[1])>0) a++;
    
  }
  //cout<<a<<b<<endl;
  for(int i=a+1;i<=n+1-b;i++) cout<<i<<" \n"[i==n+1-b];
  return 0;
}
【B - Buildings are Colorful!】

N個の建物が並んでいる。建物を1m高くするためにはコストが1かかる。
左から見た時にK個以上見えるようにするための最小コストを求める。

制約が小さいので蟻本に載っているK個の要素を列挙するやつでできる。
左から見ていって高くしないといけない場合は高くする貪欲を全通り試す。
O( (N,K) ).

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n,k;
  cin>>n>>k;
  int a[n];
  for(int i=0;i<n;i++) cin>>a[i];
  int comb=(1<<k)-1;
  int ans=1LL<<50LL;
  while(comb<(1<<n)){
    int tmp=0,res=0;
    for(int i=0;i<n;i++){
      if((comb>>i)&1){
	if(tmp<a[i]){
	  tmp=a[i];
	  continue;      
	}
	res+=(tmp+1)-a[i];
	tmp++;
      }else{
	tmp=max(tmp,a[i]);
      }
    }
    //cout<<res<<endl;
    ans=min(ans,res);
    int x=comb&-comb;
    int y=comb+x;
    comb=((comb&~y)/x>>1)|y;
  }
  cout<<ans<<endl;
  return 0;
}
【D - Driving on a Tree】

木が与えられる。E君は等確率で隣接する未訪問の頂点に移動する。
各頂点に対し移動回数の期待値を求める。

†全方位木DP†をする。今まで存在は知っていたけど書いたことはなかった。
頂点1を根として2回dfsをする。1回目のdfsでは自身と子の期待値を求める。
2回目のdfsでは親から子に1回目の情報から求めた期待値を渡す。
式が立てられなくて無限に時間を溶かしてしまった。
O(N).

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAX 214514
vector<int> G[MAX];
vector<double> L[MAX];
double ans[MAX];
double memo[MAX];
int n;
double dfs(int v,int p){
  double res=0;
  L[v].resize(G[v].size());
  for(int i=0;i<(int)G[v].size();i++){
    int u=G[v][i];
    if(u==p) continue;
    L[v][i]=dfs(u,v);
    //cout<<v<<":"<<u<<"/"<<k<<endl;
    res+=L[v][i];
  }
  if(G[v].size()==1) return memo[v]=1.0;
  //cout<<v<<"-"<<res<<endl;
  return memo[v]=(res/(G[v].size()-1))+1.0;
}


void dfs2(int v,int p,double x){
  ans[v]=x;
  //cout<<v<<" "<<x<<endl;
  for(int i=0;i<(int)G[v].size();i++){
    int u=G[v][i];
    if(u==p) continue;
    ans[v]+=memo[u];
    //cout<<v<<" "<<i<<":"<<((memo[v]-1.0)*(G[v].size()-1))<<" "<<L[v][i]<<" "<<x<<endl;
    dfs2(u,v,(G[v].size()>1?
	      (((memo[v]-1.0)*(G[v].size()-1)-L[v][i]+x)
	       /(double)(G[v].size()-1))
	       :x)+1.0);
	 
  }
  ans[v]/=G[v].size();
}

signed main(){
  cin>>n;
  int u[n-1],v[n-1];
  for(int i=0;i<n-1;i++) cin>>u[i]>>v[i];
  for(int i=0;i<n-1;i++){
    u[i]--;v[i]--;
    G[u[i]].push_back(v[i]);
    G[v[i]].push_back(u[i]);
  }
  dfs(0,-1);
  dfs2(0,-1,0);
  //for(int i=0;i<n;i++) printf("%.12f\n",memo[i]);puts("");
  for(int i=0;i<n;i++) printf("%.12f\n",ans[i]);
  return 0;
}
【F - Find the Route!】

H*Wのグリッドが与えられる。いくつかのマスには矢印が書かれている。
矢印を書き換えてスタートからゴールに移動したい。書き換えの最小コストを求める。

部分点のみ。コンテスト後に取った。
xyの順番とかの制約がおかしくてエスパーしないといけない。
辺を陽に持たないグラフ上でdijkstraをする。
移動できるのは縦横どちらかなので高々H+W通りになる。
一回使った矢印はもう使うことがないので自由に書き換えていい。
頂点数を矢印がある位置だけにすれば満点取れるはず。
O(HW(H+W)log(HW)).

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct st{
  int d,x,y;
  st(){}
  st(int d,int x,int y):d(d),x(x),y(y){}
  bool operator<(const st &a)const{
    return d>a.d;
  }
};
signed main(){
  int h,w,n,f;
  cin>>h>>w>>n>>f;
  int sx,sy,gx,gy;
  cin>>sy>>sx>>gy>>gx;
  int a[n],b[n],d[n],e[n];
  char c[n];
  for(int i=0;i<n;i++) cin>>a[i]>>b[i]>>c[i]>>d[i]>>e[i];
  int ar[w][h];
  memset(ar,-1,sizeof(ar));
  for(int i=0;i<n;i++){
    a[i]--,b[i]--;
    ar[b[i]][a[i]]=i;
  }
  sx--;sy--;gx--;gy--;
  int dp[w][h];
  memset(dp,-1,sizeof(dp));
  priority_queue<st> q;
  q.push(st(0,sx,sy));
  dp[sx][sy]=0;
  while(!q.empty()){
    st p=q.top();q.pop();
    int x=p.x,y=p.y,dist=p.d;
    if(dp[x][y]<dist) continue;
    if(ar[x][y]<0) continue;
    int k=ar[x][y];
    //cout<<x<<"-"<<y<<endl;
    for(int i=0;i<w;i++){
      int nx=i,ny=y,nc;
      if(x==nx) continue;
      if(c[k]=='N'||c[k]=='S'){
	nc=e[k]+f*abs(d[k]-abs(nx-x));
      }else{
	if(x<nx){
	  if(c[k]=='E'){
	    nc=f*abs(d[k]-abs(nx-x));
	  }else{
	    nc=min(e[k]+f*abs(d[k]-abs(nx-x)),f*abs(d[k]+abs(nx-x)));
	  }
	}else{
	  if(c[k]=='W'){
	    nc=f*abs(d[k]-abs(nx-x));
	  }else{
	    nc=min(e[k]+f*abs(d[k]-abs(nx-x)),f*abs(d[k]+abs(nx-x)));
	  }
	}
      }
      //cout<<nx<<"+"<<ny<<" "<<dist<<":"<<nc<<endl;
      if(dp[nx][ny]<0||dist+nc<dp[nx][ny]){
	dp[nx][ny]=dist+nc;
	q.push(st(dist+nc,nx,ny));
      }
    }
    for(int i=0;i<h;i++){
      int nx=x,ny=i,nc=0;
      if(y==ny) continue;
      if(c[k]=='E'||c[k]=='W'){
	nc=e[k]+f*abs(d[k]-abs(ny-y));
      }else{
	if(y<ny){
	  if(c[k]=='S'){
	    nc=f*abs(d[k]-abs(ny-y));
	  }else{
	    nc=min(e[k]+f*abs(d[k]-abs(ny-y)),f*abs(d[k]+abs(ny-y)));
	  }
	}else{
	  if(c[k]=='N'){
	    nc=f*abs(d[k]-abs(ny-y));
	  }else{
	    nc=min(e[k]+f*abs(d[k]-abs(ny-y)),f*abs(d[k]+abs(ny-y)));
	  }
	}
      }
      //cout<<nx<<"+"<<ny<<" "<<dist<<":"<<nc<<endl;
      if(dp[nx][ny]<0||dist+nc<dp[nx][ny]){
	dp[nx][ny]=dist+nc;
	q.push(st(dist+nc,nx,ny));
      }
    }
  }
  cout<<dp[gx][gy]<<endl;
  return 0;
}
【H - Huge Kingdom: Atcoder

N頂点の木が与えられる。任意の頂点集合に対して森を形成した後の
木の直径の2乗の和を求めるクエリを投げることができる。
なるべく少ない回数のクエリで木を復元する。

O(N^2)の自明解。2頂点の組を全て試すとそこに辺があるかどうかがわかる。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n;
  cin>>n;
  string s(n,'0');
  int a[n-1],b[n-1],c=0;
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      string t=s;
      t[i]=t[j]='1';
      cout<<"? "<<t<<endl;
      int d;
      cin>>d;
      if(d){
	a[c]=i;
	b[c]=j;
	c++;
      }
    }
  }
  cout<<"!";
  for(int i=0;i<n-1;i++) cout<<" ("<<a[i]<<","<<b[i]<<")";
  cout<<endl;
  return 0;
}