C. Valhalla Siege

1400 
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,Q;
    cin>>N>>Q;

    VI A(N);
    rep(i, N) cin >> A[i];

    rep(i,N-1){
      A[i+1] += A[i];
    }    

    ll attack=0;
    while(Q--){
      ll k;cin>>k;
      attack+=k;
      auto it = upper_bound(ALL(A), attack);
      if(it==A.end()){
        // revive
        attack=0;
        p(N);
      }
      else{
        ll i = it-A.begin();
        ll live = N-i;
        p(live);
      }
    }

    return 0;
}

B. String Typing

1400 
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin>>N;
    
    ll mi = N;
    string s;cin>>s;
    string now="";
    ll sz=0;
    for(char c : s){
      now += c;
      sz++;
      if(sz*2<=N){
        // try copy
        string t = now+now;
        if(t==s.substr(0,2*sz)){
          // copy success
          ll rest = N-2*sz;
          ll cost = sz + 1 + rest;
          chmin(mi,cost);
        }
      }
    }
    p(mi);
    
    return 0;
}

B. Our Tanya is Crying Out Loud

1400 
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll n,k,a,b;cin>>n>>k>>a>>b;
    ll cost=0;

    if(k==1){
      cost += (n-1)*a;
      p(cost);
      return 0;
    }

    while(n!=1){
      if(n<k){
        cost += (n-1)*a;
        n=1;
      }
      else if(n%k!=0){
        ll r = n%k;
        cost += r*a;
        n -= r;
      }
      else{
        // n%k==0
        // 安い方を選ぶ
        // kで割る場合のコスト
        ll cost0 = b;
        // 1歩ずつ進む場合のコスト
        ll len = n-n/k;
        ll cost1 = a*len;
        cost += min(cost0, cost1);
        n /= k;
      }
    }
    p(cost);
    
    return 0;
}

連結判定 bfs

ライブラリ
  • やるだけbfsはコピペで済ませよう
  • 今回の設定では、地図が
##.
#..
...
  • のようにドットが空地、＃が壁として、空地が連結かを判定する
ll H,W;

int dx[4] = {-1, 0, 1,  0};
int dy[4] = { 0, 1, 0, -1};

bool in_range(ll i, ll j){
  if(0<=i && i<H && 0<=j && j<W){
    return true;
  }else{
    return false;
  }
}

bool bfs(VS S, PII start){
  ll spaces = 0;
  for(string s : S){
    for(char c : s){
      if(c=='.')spaces++;
    }
  }
  ll paint=0;
  // startからbfsして全部埋められるか
  queue<PII> que;
  que.push(start);
  S[start.first][start.second]='#'; paint++;
  while(!que.empty()){
    auto pa = que.front(); que.pop();
    rep(i,4){
      ll ny = pa.first + dy[i];
      ll nx = pa.second + dx[i];
      if(!in_range(ny,nx))continue;
      if(S[ny][nx]=='.'){
        que.push({ny,nx});
        S[ny][nx]='#'; paint++;
      }
    }
  }
  return spaces==paint;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    cin>>H>>W;
    VS S(H);
    rep(i,H)cin>>S[i];

    ll cnt=0;
    rep(i,H){
      rep(j,W){
        if(S[i][j]=='.')continue;
        S[i][j]='.';
        bool connected = bfs(S, {i,j});
        S[i][j]='#';
        if(connected)cnt++;
      }
    }
    p(cnt);
    
    return 0;
}

verified

C. Uncle Bogdan and Country Happiness

1800

code

editorialと同じ変数名にしています

void solve(){
  ll N,M;
  cin>>N>>M;
  
  VI P(N);
  rep(i,N)cin>>P[i];

  VI H(N);
  rep(i,N)cin>>H[i];
  
  VV G(N);
  rep(i,N-1){
    ll a,b;cin>>a>>b;
    a--;b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }

  VI A(N, -1);
  // i以下の部分木の帰宅者の和（何人が通過する？）
  function<ll(ll,ll)> dfs = [&](ll i, ll prev){
    if(A[i]!=-1)return A[i];
    ll sum = P[i];
    for(ll to : G[i]){
      if(to==prev)continue;
      sum += dfs(to, i);
    }
    return A[i]=sum;
  };
  dfs(0, -1);

  rep(i,N){
    // 通過者とハピの偶奇は一致する
    // if(A[i]%2 != H[i]%2){ // これだとH[i]が負のときダメ
    if((A[i]+H[i])%2==0){
      // ok
    }else{
      debug("parity error",i);
      p_no();return;
    }
  }

  // 各点をhappyで通過した「人数」
  VI g(N);
  rep(i,N){
    g[i] = (H[i]+A[i])/2;
  }

  rep(i,N){
    if(0<=g[i] && g[i]<=A[i]){
      // ok
    }else{
      debug("g is contradicted");
      p_no();return;
    }
  }

  // 子供チェック用dfs
  bool ok=true;
  function<void(ll,ll)> DFS = [&](ll i, ll prev){
    ll g_sum=0;
    for(ll to : G[i]){
      if(to==prev)continue;
      g_sum += g[to];
      DFS(to,i);
    }
    if(g_sum>g[i]){
      ok=false;
    }
  };
  DFS(0, -1);
  if(!ok){
    p_no();return;
  }
  p_yes();
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin>>N;
    
    while(N--)solve();
    
    return 0;
}