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

beet's soil

競プロのことなど

AtCoder Grand Contest 009

意識朦朧としながら出た。

【A - Multiple Array】

後ろから条件を満たすように貪欲。O(N)
AとBを逆に見ていてサンプルの理解に時間がかかってしまった。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n;
  cin>>n;
  ll a[n],b[n];
  for(ll i=0;i<n;i++) cin>>a[i]>>b[i];
  reverse(a,a+n);
  reverse(b,b+n);
  ll ans=0;
  for(ll i=0;i<n;i++){
    if((a[i]+ans)%b[i]){
      ans+=b[i]-(a[i]+ans)%b[i];
    }
  }
  cout<<ans<<endl;
  return 0;
}
【B - Tournament】

それぞれの必要な数は子の数+何試合目かで再帰的に求まるのでdfsする。
最初は子の数だけでいいと思ってしまって時間を溶かした。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> G[111111];
int ans=0;
int dfs(int v){
  if(!G[v].size()) return 0;
  int res=0;
  vector<int> vv;
  for(int i=0;i<(int)G[v].size();i++){
    int k=dfs(G[v][i]);
    res=max(res,k);
    vv.push_back(k);
  }
  sort(vv.begin(),vv.end());
  for(int i=0;i<(int)vv.size();i++){
    res=max(res,vv[i]+(int)vv.size()-i);
  }
  return res;
}
int main(){
  int n;
  cin>>n;
  int a[n];
  a[0]=-1;
  for(int i=1;i<n;i++){
    cin>>a[i];
    G[a[i]-1].push_back(i);
  }
  cout<<dfs(0)<<endl;
  return 0;
}
【全体】

1908 -> 1911 (+3) highest
上がってびっくりした。
典型中難易度を出してという気持ちになった。
1000点越えを解けるようになりたいなあ、、