beet's soil

競プロのことなど

AtCoder Regular Contest 074

60th 2014 -> 2076 (+62) highest
ARCの最高順位更新した。

【C - Chocolate Bar】

縦横それぞれ1回目で分ける位置を決めうちする。
O(H+W).

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int h,w;
  cin>>h>>w;
  int ans=h*w;
  for(int k=0;k<2;k++){
    for(int i=1;i<h;i++){
      int s1=i*w;
      int s2=(h-i)*(w/2);
      int s3=h*w-s1-s2;
      int tmp=max(max(s1,s2),s3)-min(min(s1,s2),s3);
      ans=min(ans,tmp);
    }
    swap(h,w);
  }
  ans=min(ans,h);
  ans=min(ans,w);
  if(h%3==0||w%3==0) ans=0;
  cout<<ans<<endl;
  return 0;
}
【D - 3N Numbers】

上からn個と下からn個とるデータ構造が欲しくなる。両方priority_queueでできる。
O(NlogN).

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[3*114514];
int b[3*114514];
int c[3*114514];
signed main(){
  int n;
  cin>>n;
  for(int i=0;i<n*3;i++) cin>>a[i];
  priority_queue<int,vector<int>,greater<int> > q1;
  priority_queue<int> q2;
  memset(b,0,sizeof(b));
  memset(c,0,sizeof(c));
  int tmp1=0,tmp2=0;
  for(int i=0;i<n;i++){
    q1.push(a[i]);
    tmp1+=a[i];
    b[i]=tmp1;
    q2.push(a[3*n-1-i]);
    tmp2+=a[3*n-1-i];
    c[3*n-1-i]=tmp2;
  }
  for(int i=n;i<n*3;i++){
    q1.push(a[i]);
    tmp1+=a[i];
    int k=q1.top();q1.pop();
    tmp1-=k;
    b[i]=tmp1;
    q2.push(a[3*n-1-i]);
    tmp2+=a[3*n-1-i];
    k=q2.top();q2.pop();
    tmp2-=k;
    c[3*n-1-i]=tmp2;
  }
  int ans=-(1LL<<55LL);
  for(int i=n-1;i<2*n;i++){
    ans=max(ans,b[i]-c[i+1]);
  }
  cout<<ans<<endl;
  return 0;
}
【E - RGB Sequence】

区間DPにこだわってしまって解けなかった。
dp[Rの最後][Gの最後][Bの最後]とすると条件を確認できるようになる。

#include<bits/stdc++.h>
using namespace std;
int dp[333][333][333];
bool used[333][333][333];
typedef pair<int,int> P;
typedef pair<P,int> PP;
int MOD=1000000007LL;
signed main(){
  int n,m;
  cin>>n>>m;
  int l[m],r[m],x[m];
  for(int i=0;i<m;i++) cin>>l[i]>>r[i]>>x[i];
  vector<P> T[n+1];
  for(int i=0;i<m;i++) T[r[i]].push_back(P(l[i],x[i]));
  dp[0][0][0]=1;
  queue<PP> q;
  q.push(PP(P(0,0),0));
  used[0][0][0]=1;
  int ans=0;
  while(!q.empty()){
    PP pp=q.front();q.pop();
    int R=pp.first.first,G=pp.first.second,B=pp.second;
    //cout<<R<<" "<<G<<" "<<B<<":"<<dp[R][G][B]<<endl;
    int t=max(max(R,G),B);
    if(t==n){
      (ans+=dp[R][G][B])%=MOD;
      continue;
    }
    bool f1=0,f2=0,f3=0;
    for(int i=0;i<(int)T[t+1].size();i++){
      int c1=(T[t+1][i].first<=G)+(T[t+1][i].first<=B)+1;
      int c2=(T[t+1][i].first<=R)+(T[t+1][i].first<=B)+1;
      int c3=(T[t+1][i].first<=R)+(T[t+1][i].first<=G)+1;
      f1|=(T[t+1][i].second!=c1);
      f2|=(T[t+1][i].second!=c2);
      f3|=(T[t+1][i].second!=c3);
    }
    if(!f1){
      (dp[t+1][G][B]+=dp[R][G][B])%=MOD;
      if(!used[t+1][G][B]) q.push(PP(P(t+1,G),B)),used[t+1][G][B]=1;
    }
    if(!f2){
      (dp[R][t+1][B]+=dp[R][G][B])%=MOD;
      if(!used[R][t+1][B]) q.push(PP(P(R,t+1),B)),used[R][t+1][B]=1;
    }
    if(!f3){
      (dp[R][G][t+1]+=dp[R][G][B])%=MOD;
      if(!used[R][G][t+1]) q.push(PP(P(R,G),t+1)),used[R][G][t+1]=1;
    }
  }
  cout<<ans<<endl;
  return 0;
}
【F - Lotus Leaves】

うーん最小カット -> 超頂点作るんやろなあ まあdinic速いし一応投げてみるか -> AC(えぇ…

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1LL<<55LL
#define MAX_V 21111
struct edge {
  int to,cap,rev;
  edge(){}
  edge(int to,int cap,int rev):to(to),cap(cap),rev(rev){}
};

vector<edge> G[MAX_V];
int level[MAX_V];
int iter[MAX_V];


void add_edge(int from,int to,int cap){
  //cout<<from<<" "<<to<<" "<<cap<<endl;
  G[from].push_back(edge(to,cap,G[to].size()));
  // directed
  G[to].push_back(edge(from,0,G[from].size()-1));
}

void bfs(int s){
  memset(level,-1,sizeof(level));
  queue<int> que;
  level[s]=0;
  que.push(s);
  while(!que.empty()){
    int v=que.front();que.pop();
    for(int i=0;i<(int)G[v].size();i++){
      edge &e = G[v][i];
      if(e.cap>0&&level[e.to]<0){
	level[e.to]=level[v]+1;
	que.push(e.to);
      }
    }
  }
}

int dfs(int v,int t,int f){
  if(v==t) return f;
  for(int &i=iter[v];i<(int)G[v].size();i++){
    edge &e=G[v][i];
    if(e.cap>0&&level[v]<level[e.to]){
      int d = dfs(e.to,t,min(f,e.cap));
      if(d>0){
	e.cap-=d;
	G[e.to][e.rev].cap+=d;
	return d;
      }
    }
  }
  return 0;
}

int max_flow(int s,int t,int lim){
  int flow=0;
  for(;;){
    bfs(s);
    //cout<<level[t]<<" "<<lim<<endl;
    if(level[t]<0||lim==0) return flow;
    memset(iter,0,sizeof(iter));
    int f;
    while((f=dfs(s,t,lim))>0){
      flow+=f;
      lim-=f;
    }
  }
}
int max_flow(int s,int t){
  return max_flow(s,t,INF);
}
typedef pair<int,int> P;
signed main(){
  int h,w;
  cin>>h>>w;
  string a[h];
  for(int i=0;i<h;i++) cin>>a[i];
  int s,t;
  int cnt=0;
  map<P,int> m;
  int sx,sy,tx,ty;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(a[i][j]=='o') m[P(i,j)]=cnt++;
      if(a[i][j]=='S') s=m[P(i,j)]=cnt++,sy=i,sx=j;
      if(a[i][j]=='T') t=m[P(i,j)]=cnt++,ty=i,tx=j;
    }
  }
  
  //for(auto p:m) cout<<p.first.first<<" "<<p.first.second<<endl;
  
  if(sx==tx||sy==ty){
    cout<<-1<<endl;
    return 0;
  }
  for(int i=0;i<h;i++){
    int j=0;
    while(j<w&&a[i][j]=='.') j++;
    vector<int> v(1,j++);
    while(1){
      while(j<w&&a[i][j]=='.') j++;
      if(j>=w) break;
      v.push_back(j++);
    }
    for(int x=0;x<(int)v.size();x++)
      for(int y=0;y<(int)v.size();y++)
	if(x!=y) add_edge(m[P(i,v[x])]+cnt,m[P(i,v[y])],1LL);
  }
  for(int j=0;j<w;j++){
    int i=0;
    while(i<h&&a[i][j]=='.') i++;
    vector<int> v(1,i++);
    while(1){
      while(i<h&&a[i][j]=='.') i++;
      if(i>=h) break;
      v.push_back(i++);
    }
    for(int x=0;x<(int)v.size();x++)
      for(int y=0;y<(int)v.size();y++)
	if(x!=y) add_edge(m[P(v[x],j)]+cnt,m[P(v[y],j)],1LL);
  }
  for(int i=0;i<cnt;i++){
    if(i==s||i==t) add_edge(i,i+cnt,INF);
    else add_edge(i,i+cnt,1LL);
  }
  //cout<<s<<" "<<t+cnt<<endl;
  cout<<max_flow(s,t+cnt)<<endl;
  return 0;
}


こういうセットは順位がよくなるので嫌いではない(E解けてれば大好きだったと思う