AtCoder Beginner Contest 136

はい． AtCoder Beginner Contest 136 です

A,B,C,D の4完でした．

A - Transfer

問題文

して 正の数を出力するだけ．負数なら

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
  int a,b,c;
  cin >> a >> b >> c;
  int ans = c - (a-b);
  cout << (ans>=0? ans : 0) << endl;
}

B - Uneven Numbers

問題文

だから総当たりするだけ．
to_string 使ってるけど，普通に桁数求めても良かった．

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
  int n;
  cin >> n;
  int ans=0;

  for(int i=1; i<=n; i++) {
    if(to_string(i).length() %2) {
      ans++;
    }
  }
  cout << ans << endl;
}

C - Build Stairs

問題文

後ろから しても単調非減少（広義単調増加）にできないなら，'No' となる．

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
  int n;
  bool ans = true;
  cin >> n;
  vector<int> h(n);

  for(int i=0; i<n; i++) {
    cin >> h[i];
  }

  for(int i=n-1; i>0; i--) {
    if(h[i-1] > h[i]) {
      if(h[i-1]-1 <= h[i]) h[i-1]--;
      else ans = false;
    }
  }

  cout << (ans? "Yes" : "No") << endl;
}

D - Gathering Children

問題文

R と L が入れ替わるところに溜まっていくことが分かって，
なので， 全ての子どもが RL の入れ替わるところに溜まりますね．

そこで，スタートのRから数えて偶数桁は同じ所に行くので，集めながら L を探していきます．
そんな感じです．

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
  string s;
  cin >> s;
  int n = s.size();
  vector<int> ans(n,0);
  vector<bool> f(n,false);

  for (int i=0; i<n; i++) {
    if (f[i]) continue;
    if(s[i] == 'R') {
      int cnt = 0;
      int ad = 0;

      while(i+cnt < n && s[i+cnt] != 'L') {
        if (cnt%2==0) {
          f[i+cnt] = true;
          ad++;
        }
        cnt++;
      }
      if (cnt%2 == 0) ans[i+cnt]+=ad;
      else ans[i+cnt-1]+=ad;

    }
  }

  for (int i=n-1; i>0; i--) {
    if (f[i]) continue;

    if (s[i] == 'L') {
      int cnt = 0;
      int ad = 0;
      while( i-cnt>0 && s[i-cnt] != 'R') {
        if (cnt%2 == 0) {
          f[i-cnt] = true;
          ad++;
        }
        cnt++;
      }
      if (cnt%2 == 0) ans[i-cnt]+=ad;
      else ans[i-cnt+1]+=ad;
    }
  }

  for (int i=0; i<n; i++) {
    printf("%d%c",ans[i],(i<n-1? ' ' : '\n'));
  }
}

E - Max GCD

問題文

の総和の約数しか出てこないことは分かっていたので，それを確かることをしたかった…
確かめるところが難しかったです．

勉強します．

コンテスト中に書いたプログラム

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
  int n,k;
  int ans=0;
  cin >> n >> k;
  vector<int> a(n);
  long long s = 0;
  for (int i=0; i<n; i++) {
    cin >> a[i];
    s += a[i];
  }

  // 約数を求める
  vector<int> t;
  for (int i=s; i>=2; i--) {
    if (s%i == 0) {
      // cout << "pb " << i << endl;
      t.push_back(i);
    }
  }


  
  for (auto i : t) {
    vector<int> tmp(n);
    copy(a.begin(),a.end(), tmp.begin());
    for (int j=0; j<n; j++) {
      tmp[j]%=i;
      s += tmp[j];
    }

    sort(tmp.begin(), tmp.end());
    int l,r;
    l = 0;
    r = s;
    int j=0;
    bool f=true;
    while(l != r) {
      l += tmp[j];
      r -= tmp[j];
      j++;
      if (j>=n) { 
        f = false;
        break;
      }
    }
    if(f) {
      if( max(l,r) <= k ) {
        ans = max(l,r);
        break;
      }
    }
  }

  cout << ans << endl;
}

まとめ

A,B,C,D の4完でした．
やっぱり E 以降はもう少しアルゴリズムを勉強しないと安定して解けないな．と思いました．
蟻本を読み始めたので，早く読んで勉強します．

タイム的には後1問くらいは解けると思うので早く解けるようになりたいですね．