AtCoder Beginner Contest 138

競プロ AtCoder

はい． AtCoder Beginner Contest 138 です

A,B,C,D,E の5完でした．
5完！！！

f:id:zeronosu77108:20190819194214p:plain

パフォーマンスが青手前くらいの水色でした！

f:id:zeronosu77108:20190819194432j:plain:w300



A - Red or Not

問題文

問題文の通り書くだけですね

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

using namespace std;

int main() {
  int a;
  string s;
  cin >> a >> s;

  cout << (a>=3200? s : "red") << endl;
}



B - Resistors in Parallel

問題文

なにか良い計算方法があるのかな？と思ったんだけど，
そのまま計算しても大丈夫そうだったので，愚直に書きました．

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

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<long double> a(n);

  for (int i=0; i<n; i++) cin >> a[i];

  long double sum = 0;

  for (int i=0; i<n; i++) sum += 1/a[i];

  printf("%.14Lf\n",(1/sum));
}



C - Alchemist

問題文

蟻本にある板切る問題と似てますね．
priority_queue で実装しました．

価値の高い具材はできるだけ 1/2 したくないので，価値の低い物から計算します．

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


using namespace std;

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

  priority_queue<long double, vector<long double>, greater<long double>> v;

  for (int i=0; i<n; i++) {
    long double v_t;
    cin >> v_t;
    v.push(v_t);
  }

  while(v.size() > 1 ) {
    long double v1 = v.top(); v.pop();
    long double v2 = v.top(); v.pop();

    v.push((v1+v2)/2.0);
  }

  cout << v.top() << endl;
}



D - Ki

問題文

答えの配列にQ の操作を保存しておいて，上から DFS するだけですね．

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


using namespace std;

void dfs(int qi, int x, vector<vector<int>>& g, vector<long>& ans) {
  int a = ans[qi]+x;
  ans[qi] = a;
  x = a;
  for(auto v : g[qi] ) {
    dfs(v,x,g,ans);
  }
}

int main() {
  int n,q;
  cin >> n >> q;
  vector<vector<int>> g(n+1);
  vector<long> ans(n+1,0);

  for (int i=0; i<n-1; i++) {
    int a,b;
    cin >> a >> b;
    g[a].push_back(b);
  }

  for (int i=0; i<q; i++) {
    int qi,x;
    cin >> qi >> x;
    ans[qi] += x;
  }

  dfs(1,0,g,ans);

  for (int i=1; i<=n; i++) {
    cout << ans[i] << (i==n? '\n' : ' ');
  }
}


after_contest 2019-08-21追記

僕のプログラムは嘘解法だったらしく， after_contest のテストケースに引っかかったので after_contest のケースも通るように修正しました〜



E - Strings of Impurity

問題文

ダメ元で書いたら通りました．
s を圧縮して t を探索して，何周で表すことができるかと計算しました．

最初 upper_bound していなくて， TLE したけど upper_bound にしたら通りました．

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

using namespace std;

int main() {
  string s,t;
  cin >> t >> s;
  vector<vector<long>> tc(26);

  long n = t.size();
  for (long i=0; i<n; i++) {
    tc[t[i]-'a'].push_back(i);
  }

  n = s.size();
  long cnt = 0;
  long m = -1;
  vector<vector<long>> ntc = tc;
  for (long i=0; i<n; i++) {

    if( tc[s[i]-'a'].size() <= 0 ) {
      cout << -1 << endl;
      return 0;
    }
    bool flag = false;
    int ind = s[i]-'a';
    auto it = upper_bound(tc[ind].begin(), tc[ind].end(), m);
    if (it != tc[ind].end() ){
      flag = true;
      m = *it;
    }

    if (!flag) {
      cnt++;
      m = tc[s[i]-'a'][0];
    }
  }
    
  cout << (long long)t.size()*cnt + m + 1 << endl;

}



まとめ

5完でした！！！
E 問題解けたのとても嬉しかったです．

最近は， E 問題を解説・自力ACできているので良い感じだと思っています．
青パフォーマンスも狙えるところに来ている気がするので，もっと頑張りたいです！