beet's soil

競プロのことなど

Codeforces Round #384 (Div.2)

初めてextraregisterした。

【A. Vladik and flights】

やるだけ。
空港が2種類しかないという制約を見落としていて時間が溶けた。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n,a,b;
  string s;
  cin>>n>>a>>b>>s;
  cout << (s[a-1]!=s[b-1]) << endl;
  return 0;
}
【B. Chloe and the sequence】

二進数で下位ビットから見ていって初めて1になるところを出力すればいい。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n,k,j=0;
  cin>>n>>k;
  while(!(k&1LL)) k>>=1LL,j++;
  cout << j+1 << endl;
  return 0;
}
【C. Vladik and fractions】

作れる最大が1/1+1/2+1/3=11/6なのでn=1のとき-1、それ以外ならn,n+1,n(n+1)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n;cin>>n;
  if(n==1) cout << -1 << endl;
  else cout << n << " " << n+1 << " " << n*(n+1) << endl;
  return 0;
}
【D. Chloe and pleasant prizes】

解法はあってたのにグラフ作成パートで有向辺にしていて終了。
kzyさんに指摘してもらった細かいミスなどを修正して終了後にAC。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX_V 200050
ll INF = -(1LL<<50LL);
vector<ll> G[MAX_V];
ll a[MAX_V],memo[MAX_V],memo2[MAX_V];
ll dfs(ll x,ll p){
  ll res=a[x];
  for(ll i=0;i<(ll)G[x].size();i++){
    if(G[x][i]==p) continue;
    res+=dfs(G[x][i],x);
    memo2[x]=max(memo2[x],memo2[G[x][i]]);
  }
  memo2[x]=max(memo2[x],res);
  return memo[x]=res;
}
ll dfs2(ll x, ll p){
  ll res=INF;
  priority_queue<ll> q;
  for(ll i=0;i<(ll)G[x].size();i++) {
    if(G[x][i]==p) continue;
    res=max(res,dfs2(G[x][i],x));
    q.push(memo2[G[x][i]]);
  }
  if(q.size()>1){
    ll m1,m2;
    m1=q.top();q.pop();
    m2=q.top();q.pop();
    res=max(res,m1+m2);
  }
  return res;
}
int main(){
  ll n;
  cin>>n;
  for(ll i=0;i<n;i++) cin>>a[i],memo[i]=INF,memo2[i]=INF;
  for(ll i=0;i<n-1;i++){
    ll u,v;
    cin>>u>>v;
    G[u-1].push_back(v-1);
    G[v-1].push_back(u-1);
  }
  dfs(0,-1);
  ll ans=dfs2(0,-1);
  //for(ll i=0;i<n;i++) cout << i << ":" << memo[i] <<"/"<< memo2[i]<<endl;
  if(ans==INF) cout << "Impossible" << endl;
  else cout << ans << endl;
  return 0;
}
【全体】

758位 1714 -> 1726 (+12)
一週間ぐらい問題解いてなかったのでアホなミスが多かった。
もっとたくさんとかなきゃなあという気持ち。