beet's soil

競プロのことなど

Codeforces Round #383 (Div. 2)

劇冷え回

【A. Arpa’s hard exam and Mehrdad’s naive cheat】

mod_powがあると思ったのになかった(完
(そもそもこの問題では必要ない)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod_pow(ll x,ll n,ll mod){
  ll res=1;
  while(n>0){
    if(n&1) res=res*x%mod;
    x=x*x%mod;
    n>>=1;
  }
  return res;
}

int main(){
  ll n;
  cin>>n;
  cout<<mod_pow(1378,n,10)<<endl;
  return 0;
}
【B. Arpa’s obvious problem and Mehrdad’s terrible solution】

intでオーバフローしてhackされてつらかった。
これからは基本的にlong longを使うことにする(戒め。

#include<bits/stdc++.h>
using namespace std;
#define int long long 
signed main(){
  int n,x,i,j,k,ans=0;
  cin>>n>>x;
  map<int,int> m;
  int a[n];
  for(i=0;i<n;i++) cin>>a[i],m[a[i]]++;
  if(x) for(i=0;i<n;i++) ans+=((m.find(x^a[i])!=m.end())?m[x^a[i]]:0);
  else for(auto it=m.begin();it!=m.end();++it) ans+=(it->second-1)*(it->second);
  cout << ans/2 << endl;
  return 0;
}
【C. Arpa's loud Owf and Mehrdad's evil plan】

全探解を書いて落ちた(それはそう。

【D. Arpa's weak amphitheater and Mehrdad's valuable Hoses】

変なDPで書いてて面白かった。
bfsして集合を作った後、中から一人選ぶか全員選ぶかをナップザックする。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
int main(){
  ll n,m,W,i,j,k;cin>>n>>m>>W;
  ll w[n],b[n];
  for(i=0;i<n;i++) cin>>w[i];
  for(i=0;i<n;i++) cin>>b[i];
  vector<ll> G[n];
  for(i=0;i<m;i++){
    cin>>j>>k;
    j--;k--;
    G[j].push_back(k);
    G[k].push_back(j);
  }
  bool u[n];
  memset(u,0,sizeof(u));
  vector<P> v;
  vector<vector<ll> > vl;
  for(i=0;i<n;i++){
    if(u[i]) continue;
    queue<ll> q;
    vector<ll> l;
    q.push(i);
    P p=P(0,0);
    while(!q.empty()){
      k=q.front();q.pop();
      if(u[k]) continue;
      u[k]=1;l.push_back(k);
      p.first+=b[k];
      p.second+=w[k];
      for(j=0;j<G[k].size();j++) q.push(G[k][j]);
    }
    v.push_back(p);
    vl.push_back(l);
  }
  ll V=v.size(),ans=0;
  ll dp[V+1][W+1];
  memset(dp,0,sizeof(dp));
  for(i=0;i<V;i++){
    for(j=0;j<W;j++){
      dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
      for(k=0;k<vl[i].size();k++){
	if(j+w[vl[i][k]]>W) continue;
	dp[i+1][j+w[vl[i][k]]]=max(dp[i+1][j+w[vl[i][k]]],dp[i][j]+b[vl[i][k]]);
      }
      if(j+v[i].second>W) continue;
      dp[i+1][j+v[i].second]=max(dp[i+1][j+v[i].second],dp[i][j]+v[i].first);
    }
  }
  for(i=0;i<=V;i++) for(j=0;j<=W;j++) ans=max(ans,dp[i][j]);
  cout << ans << endl;
  return 0;
}
【全体】

610位 1702 -> 1714 (+12)
全体的にひどい。
ジャッジフェーズが後にあるコンテストは慎重にならないとなあと思った。