beet's soil

競プロのことなど

AtCoder Grand Contest 014

274th 2022 -> 2014 (-8)
D時間内に通したかった

【A - Cookie Exchanges】

Aだし愚直でしょ(最悪

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef tuple<int,int,int> T;
signed main(){
  int a,b,c;
  cin>>a>>b>>c;
  if(a%2||b%2||c%2){
    cout<<0<<endl;
    return 0;
  }
  int ans=1;
  int a2,b2,c2;
  a2=b/2+c/2;
  b2=a/2+c/2;
  c2=a/2+b/2;
  set<T> s;
  while(!(a2%2||b2%2||c2%2)){
    ans++;
    if(s.count(make_tuple(a2,b2,c2))){
      cout<<-1<<endl;
      return 0;
    }
    s.insert(make_tuple(a2,b2,c2));
    a=a2;b=b2;c=c2;
    a2=b/2+c/2;
    b2=a/2+c/2;
    c2=a/2+b/2;
  }
  cout<<ans<<endl;
  return 0;
}
【B - Unplanned Queries】

なんか頂点の偶奇になる(なんでだろう…

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n,m;
  cin>>n>>m;
  int a[m],b[m];
  for(int i=0;i<m;i++) cin>>a[i]>>b[i];
  int c[n];
  memset(c,0,sizeof(c));
  for(int i=0;i<m;i++){
    a[i]--,b[i]--;
    c[a[i]]++;
    c[b[i]]++;
  }
  bool f=0;
  for(int i=0;i<n;i++) f|=c[i]%2;
  cout<<(f?"NO":"YES")<<endl;
  return 0;
}
【C - Closed Rooms】

初回で出れない場合は通る経路に魔法を使えばいいのでなんかいい感じになる

#include<bits/stdc++.h>
using namespace std;
int dp[808][808];
struct st{
  int y,x;
  st(){}
  st(int y,int x):y(y),x(x){}
};
signed main(){
  int h,w,k;
  cin>>h>>w>>k;
  string a[h];
  for(int i=0;i<h;i++) cin>>a[i];
  int sy,sx;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(a[i][j]=='S') sy=i,sx=j;
    }
  }
  //cout<<sy<<" "<<sx<<endl;
  int ans=800000;
  int ay[]={0,0,1,-1};
  int ax[]={1,-1,0,0};
  //puts("a");
  memset(dp,-1,sizeof(dp));
  //puts("b");
  queue<st> q;
  q.emplace(sy,sx);
  dp[sy][sx]=0;
  while(!q.empty()){
    st p=q.front();q.pop();
    int y=p.y,x=p.x;
    if(y==0||y==h-1||x==0||x==w-1){
      cout<<1<<endl;
      return 0;
    }
    //cout<<y<<" "<<x<<":"<<dp[y][x]<<endl;
    if(dp[y][x]==k) break;
    for(int i=0;i<4;i++){
      int ny=y+ay[i],nx=x+ax[i];
      if(ny<0||ny>=h||nx<0||nx>=w) continue;
      if(a[ny][nx]=='#') continue;
      if(~dp[ny][nx]) continue;
      dp[ny][nx]=dp[y][x]+1;
      q.emplace(ny,nx);
    }
  }
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(dp[i][j]<0||dp[i][j]>k) continue;
      int tmp=(i-1)/k+1;
      tmp=min(tmp,(j-1)/k+1);
      tmp=min(tmp,((h-i)-2)/k+1);
      tmp=min(tmp,((w-j)-2)/k+1);
      ans=min(ans,tmp+1);
    }
  }
  cout<<ans<<endl;
  return 0;
}
【D - Black and White Tree】

二つ以上の葉と繋がっている頂点があれば勝ちで、葉の一個上を取るのが最適な戦略。

#include<bits/stdc++.h>
using namespace std;
#define int long long
set<int> G[114514];
signed main(){
  int n;
  cin>>n;
  int a[n],b[n];
  for(int i=0;i<n-1;i++){
    cin>>a[i]>>b[i];
    a[i]--;b[i]--;
    G[a[i]].insert(b[i]);
    G[b[i]].insert(a[i]);
  }
  bool f=0;
  queue<int> q;
  for(int i=0;i<n;i++){
    int tmp=0;
    int k;
    for(int u:G[i]){
      if(G[u].size()==1){
	tmp++;
	k=u;
      }
    }
    f|=(tmp>=2);
    if(f){
      cout<<"First"<<endl;
      return 0;
    }
    if(G[i].size()==2&&tmp==1){
      G[i].erase(k);
      G[k].erase(i);
      int u=*G[i].begin();
      G[i].erase(u);
      G[u].erase(i);
      q.push(u);
      for(int v:G[u]) if(G[v].size()>1) q.push(v);
    }
  }
  while(!q.empty()){
    int i=q.front();q.pop();
    int tmp=0;
    int k;
    for(int u:G[i]){
      if(G[u].size()==1){
	tmp++;
	k=u;
      }
    }
    f|=(tmp>=2);
    if(f){
      cout<<"First"<<endl;
      return 0;
    }
    if(G[i].size()==2&&tmp==1){
      G[i].erase(k);
      G[k].erase(i);
      int u=*G[i].begin();
      G[i].erase(u);
      G[u].erase(i);
      q.push(u);
      for(int v:G[u]) if(G[v].size()>1) q.push(v);
    }
  }
  cout<<(f?"First":"Second")<<endl;
  return 0;
}

終わってすぐ書かないと忘れてしまうなあ…