2019-10-23

AtCoder Beginner Contest 143

今回は参加が遅れて，1時間以上経っていたので参加見送りました． 22:40 なった瞬間に解き始めました．

D までサクサク解けたので参加したかったです(:3」∠) 参加してたら多分 4完でした．

A - Curtain

長さ $A$ のカーテンが2枚あって $B$ の窓をどれくらい隠せるかという問題．
基本的には引くだけで，負数になる場合は0にする必要があります．
max 取れば終わりです．

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
  int a,b;
  cin >> a >> b;
  cout << max(0, a - 2*b);
}

B - TAKOYAKI FESTIVAL 2019

問題文

$N$ が 50以下なので， $\mathcal{O}(N ^ 2)$ （2重for文）で愚直に書いても通りそうですが，
どうしても $\mathcal{O}(N)$ にしたかったです．（しました）

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

int main() {
  int n;
  int ans = 0;
  cin >> n;
  vector<int> d(n);
  for (int i=0; i<n; i++) cin >> d[i];

  int sum = accumulate(d.begin(), d.end(), 0);
  for (int i=0; i<n; i++) {
    ans += (sum-=d[i])*d[i];
  }

  cout << ans << endl;
}

C - Slimes

問題文

B より簡単なのでは…？
文字が切り替わる所を数えれば良いです．

最近，c=s[i], ans++ みたいな記法を知ったので使ってみました．

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

using namespace std;

int main() {
  int n;
  string s;
  cin >> n >> s;
  int ans = 0;
  char c = ' ';
  for (int i=0; i<n; i++) {
    if (c != s[i]) c=s[i],ans++;
  }

  cout << ans << endl;
}

D - Disjoint Set of Common Divisors

問題文

ソートしておいて，大きい方から処理します．
2つのペアの差よりも小さいものは三角形になり得ないので，そこまでに含まれる個数を数えればOKです．

a < b + c  
b < c + a  
c < a + b

式からもテキトーに求められますね…

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

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> l(n);
  for (int i=0; i<n; i++) cin>>l[i];
  sort(l.begin(),l.end());
  // for (auto i:l)cout<<i<<" ";cout<<endl;

  int ans = 0;
  for (int i=n-1; i>=0; i--) {
    for (int j=i-1; j>=0; j--) {
      auto it = upper_bound(l.begin(),l.end(), l[i]-l[j]);
      ans += max(0, (int)((l.begin()+j) - it));
    }
  }
  cout << ans << endl;
}

まとめ

出てたらパフォーマンス悪くなかったんじゃないかなぁ…
次の ABC144 頑張ります！

2019-10-23

AtCoder Beginner Contest 142

AtCoder 競プロ

はい． AtCoder Beginner Contest 142 です

A,B,C の3完でした．今回もパフォーマンスもダメダメでレートも下がってしまいました…

DもEも見てたけど，両方解けずにダメでした．

f:id:zeronosu77108:20191023120101p:plain

A - Odds of Oddness

問題文

偶数が $\frac{N}{2}$ 個あるので，それを $N$ から引いて，全体の $N$ で割れば奇数である確率が分かりますね．

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

using namespace std;

int main() {
  int n;
  cin >> n;
  cout << (n-(n/2))/(double)n << endl;
}

B - Roller Coaster

問題文

$K$ 以上なら数え上げればいいので，入力を取りながら数えました．

#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;
  for (int i=0; i<n; i++) {
    int h;
    cin >> h;
    if (h >= k) ans++;
  }

  cout << ans << endl;
}

C - Go to School

問題文

とりあえず入力とって， $[0..N$ ] のデータを $A$ のデータを使ってソートして答え作りました．

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

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i=0; i<n; i++) cin>>a[i];
  vector<int> ans(n);
  iota(ans.begin(), ans.end(), 0);

  sort(ans.begin(), ans.end(), 
    [&](int x, int y) { return a[x] < a[y]; });

  for (int i=0; i<n; i++) cout << ans[i]+1 << endl;
}

D - Disjoint Set of Common Divisors

問題文

なんか GCD を求めて，それを素因数分解をしたりしてました(:3」∠)
GCD だと漏れるのでダメでしたね．
うーむ．思考ロックしていたのでダメでしたね．

もう少し丁寧に考えるべきでした．

E - Second Sum

問題文

$N$ が 12以下なので，全探索できる！と思って bitset で書いてたんだけど，ダメでした．
TLE が直せず…

解説をちらっと読んで DP と書いていたので書いてみました．
そうしたら通せました〜
DP という発想が欲しかった(:3」∠)

bitDP と言われているやつっぽいです．
bitでこういうことするのはよく考えるので DP という発想が欲しかった…

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


using namespace std;

int main() {
  long n,m;
  cin >> n >> m;
  vector<long> costs;
  vector<long> open;
  vector<long> dp(1<<n, -1);

  for (int i=0; i<m; i++) {
    long a,b;
    cin >> a >> b;

    long cnt = 0;
    for (long j=0; j<b; j++) {
      long c;
      cin >> c;
      cnt += 1<<(c-1);
    }
    costs.push_back(a);
    open.push_back(cnt);
  }

  dp[0] = 0; 
  for (long i=0; i<m; i++) {
    dp[open[i]] = costs[i];
  }

  for (long i=0; i<(1<<n); i++) {
    if(dp[i]<0) continue;

    for (long j=0; j<m; j++) {
      long index = (i | open[j]);
      if (dp[index]<0) dp[index] = dp[i] + costs[j];
      else 
        dp[index] = min(dp[index], dp[i] + costs[j]);
    }
  }

  cout << dp[(1<<n)-1] << endl;
}

まとめ

レートが30も下がりました．
辛い…

2019-10-16

AtCoder Beginner Contest 141

はい． AtCoder Beginner Contest 141 です

既にもう覚えていません．過去の僕の気持ちになって書きます．

ABCDの4完でした．

f:id:zeronosu77108:20191016143641p:plain

A - Weather Prediction

問題文

書きやすさ重視で実装しました．

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

using namespace std;

int main() {
  string s;
  string ans;
  cin >> s;
  if (s == "Sunny") ans = "Cloudy";
  if (s == "Cloudy") ans = "Rainy";
  if (s == "Rainy") ans = "Sunny";

  cout << ans << endl;
}

B - Tap Dance

問題文

奇数のときに 'L'，偶数のときに 'R'が来るとダメという感じ．
0-indexdなので偶奇が入れ替わりますが，そのまま実装しました．

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

using namespace std;

int main() {
  string s;
  cin >> s;
  int n = s.size();
  bool ans = true;

  for (int i=0; i<n; i++) {
    if (i%2 && s[i]=='R') ans = false;
    if (!(i%2) && s[i]=='L') ans = false;
  }

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

C - Attack Survival

問題文

基本的に $Q$ 回問題が出されるので， $Q$ 点の失点です．
ただし，答えた回数分は点数がもらえるのでその分を引いて， $K$ を超えれば勝ち抜けです．

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

using namespace std;

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

  for (int i=0; i<q; i++) {
    int ai;
    cin >> ai;
    a[ai]++;
  }

  for (int i=1; i<=n; i++) {
    bool ans = (q-a[i] < k);
    cout << (ans? "Yes" : "No") << endl;
  }
}

D - Powerful Discount Tickets

問題文

できるだけ高いものに割引券を使いたいので， priority_queue に突っ込んで大きい奴に割引券を使って priority_queue に戻します．
これを $M$ 回繰り返して，総和を取ると最小の合計金額が求まります．

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

using namespace std;

int main() {
  int n,m;
  cin >> n >> m;
  priority_queue<long> q;
  for (int i=0; i<n; i++) {
    int a;
    cin >> a;
    q.push(a);
  }

  for (int i=0; i<m; i++) {
    int a = q.top();
    q.pop();
    // cerr << a << " " << (int)((double)a/2.0) << endl;
    q.push((int)((double)a/2.0));
  }

  long ans = 0;
  while(! q.empty()) {
    ans += q.top();
    q.pop();
  }

  cout << ans << endl;
}

E - Who Says a Pun?

問題文

コンテスト中に「文字列アルゴリズムだ！」と Suffix-Array を検索して使ってみたんですが，ダメでした．コンテスト後に Z-algorithm をコピペでやってみたら解けました．

Suffix-Array でも解けたようなので， Suffix-Array も勉強したいと思います．

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

using namespace std;


vector<long> z_algorithm(const std::string& s, const long n){
  std::vector<long> z(n, 0);
  long L=0, R=0;
  for (long i=1; i<n; i++){
    if(i>R) {
      L = R = i;
      while(R<n && s[R-L]==s[R]) R++;
      z[i] = R-L;
      R--;
    } else {
      long k = i-L;
      if(z[k] < R-i+1){
        z[i] = z[k];
      } else {
        L = i;
        while(R<n && s[R-L]==s[R]) R++;
        z[i] = R-L; R--;
      }
    }
  }
  return z;
}

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

  vector<long> z;
  for (int i=0; i<n-1; i++) {
    z = z_algorithm( s.substr(i, n-i), n-i);
    for (long j=1; j<n-i; j++) {
      ans = max(ans, min(z[j],j));
    }
  }

  cout << ans << endl;
}

まとめ

パフォーマンスが1200代だったのでまぁまぁ良いですね．
この調子で頑張ります。

2019-09-09

AtCoder Beginner Contest 140

AtCoder 競プロ

はい． AtCoder Beginner Contest 140 です

A,B,C の3完でした．今回はパフォーマンスもダメダメでレートも下がってしまいました…

一列に並んでいて，反転させる系の問題苦手過ぎる…

f:id:zeronosu77108:20190909163229p:plain

C まで20分ほどで解けているんので，やはり解く時間はあったと思います…

A - Password

問題文

$1 \leq N \leq 9$ なので， 1桁に $N$ 種類の記号が使えるので， $N * N * N$ するだけですね．
pow で書いたけど，普通に n*n*n すれば良かったですね．

#include <iostream>
#include <cmath>

using namespace std;

int main() {
  int n;
  cin >> n;
  cout << pow(n,3) << endl; 
}

B - Buffet

問題文

問題文読み解くのに時間かかりました…
今回 C の方が簡単なのでは…？と思いました．

問題文通りに実装するだけですね．
後から気付いたんですけど， B は絶対食べるので総和取るだけで良かったですね．
for (int i=0; i<n; i++) { cin>>b; ans+=b; } という感じですね．

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

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  vector<int> b(n);
  vector<int> c(n);

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

  int ans = 0;

  for (int i=0; i<n; i++) {
    ans += b[a[i]-1];
    if (i!=n-1 && a[i]+1 == a[i+1]) ans+=c[a[i]];
  }

  cout << ans << endl;
}

C - Maximal Value

問題文

$A _ 2 \leq \min(B _ 1, B _ 2)$ という感じですね．
$A _ 1$ と $A _ N$ に関しては， $B _ 1$ と $B _ {N-1}$ しか制約がないのでそのまま足してあげる感じです．

#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;
  int ans = 0;

  int b1,b2;
  cin >> b1;
  ans += b1;
  for (int i=1; i<n-1; i++) {
    cin >> b2;
    ans += min(b1,b2);
    b1 = b2;
  }
  ans += (n==2? b1 : b2);

  cout << ans << endl;
}

D - Face Produces Unhappiness

問題文

しゃくとり法とかいろいろ考えていたんですが，
LR+L もしくは RL+R の場合に幸福な人が+2 されるので，LRのグループに別けて，偶数番目のグループを $K$ 回反転させるだけで良かったですね．

1度反転させて，もう1度数えるのはめんどくさいので，最初から反転させている前提で幸福な人を数えるプログラムを書きました．

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

using namespace std;

int main() {
  int n,k;
  int ans = 0;
  string s;
  cin >> n >> k;
  cin >> s;

  int start,i,cnt;
  start = i = cnt = 0;
  while(i<n) {
    char c = s[i];
    while(i<n && c==s[i]) i++;  
    cnt++;
    if (i<n && cnt < 2*k+1) continue;
    else ans += (i-start)-1;
    start = i;
  }
  cout << ans << endl;
}

E - Second Sum

問題文

解説見ました．
全区間に対して，最大の値を解くプログラムの拡張でできるようです．
まだ実装していませんが，近いうちに実装します．

F - Many Slimes

問題文

（リャマ君と一緒に）雑にグラフを書いてたら，思いつきました．

基本的に大きい方から考えて行きます．
まず，1番大きい値と2番目に大きい値で pair を作ります（このとき 1番目>2番目）．

それを queue に入れて， pair それぞれの値より小さい中で一番大きい値と pair を作って次の queue に登録します．
これを繰り返していくと，二分木のようなものを作る事になります．

queue に追加されなくなった段階で，日付やいろいろを確認して未誕生のスライムが居たら「作れません！」という感じです．
思いついたらプログラムは難しくなかったので，コンテスト中に思いつきたかった！！
（D,E 見て難しくて F は目を通してなかった）

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

using namespace std;

typedef pair<int, int> P;

bool add_queue(const int s1, queue<P>& q, vector<int>& s) {
    auto it = lower_bound(s.begin(), s.end(), s1);
    if (it == s.begin()) return false;
    it--;
    q.push(P(s1, *it));
    s.erase(it);
    return true;
}

int main() {
    int n;
    cin >> n;

    int ns = pow(2, n);
    vector<int> s(ns);
    for (int i=0; i<ns; i++) cin >> s[i];
    sort(s.begin(), s.end());

    int s1, s2;
    s2 = s.back();
    s.pop_back();
    s1 = s.back();
    s.pop_back();
    
    bool ans = true;
    queue<P> q;
    if (s1 < s2) q.push(P(s1, s2));
    else ans = false;

    int day = 0;
    while (true) {
        if (q.empty()) break;
        queue<P> next_q;
        day++;
        while (!q.empty()) {
            P p = q.front();
            q.pop();
            s1 = p.first;
            s2 = p.second;

            add_queue(s1, next_q, s);
            add_queue(s2, next_q, s);
        }
        q = next_q;
    }

    ans = ans && q.empty() && s.size()<=0 && day <= n;
    cout << (ans?"Yes":"No") << endl;
}

まとめ

今回は真面目に解いて，レート下がりました…
結構ショックでした．

コンテスト後ですが F 問題，割りと自力で解けたので良かったです．
E も近いうち解いて更新します！！

2019-09-02

AtCoder Beginner Contest 139

競プロ AtCoder

はい． AtCoder Beginner Contest 139 です

A,B,C,D の4完でした．無限に E問題 TLE してました．

f:id:zeronosu77108:20190902152501p:plain

D まで結構早かったので，「E まで解ける！」と思ったのに，最大ケースがダメだったようです．

B 問題で引っかかったのでランキングも微妙でした．

A - Tenki

問題文

入力とって for 回しました．

#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 >> s >> t;

  int ans = 0;
  for (int i=0; i<3; i++)
    if (s[i] == t[i]) ans++;

  cout << ans << endl;
}

B - Power Socket

問題文

最初， ceil(b / (double)a) とかやって WA でした．
20以下なの while とか回しても良いかなと．

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

using namespace std;

int main() {
  int a,b;
  cin >> a >> b;

  int ans = 0;
  int tap = 1;

  a--;
  while(tap < b) {
    tap += a;
    ans++;
  }
  cout << ans << endl;
}

C - Lower

問題文

前から数えていくだけで良いですね．

#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;

  int h1,h2;
  cin >> h1;
  int cnt = 0;
  int ans = 0;
  for (int i=1; i<n; i++) {
    cin >> h2;
    if (h1>=h2) {
      cnt++;
      if(cnt>ans) ans = cnt;
    } else cnt=0;
    h1 = h2;
  }
  cout << ans << endl;
}

D - ModSum

問題文

「どうやって計算するんだ？」と思ったけど，
12 をそのまま作り出すには 13 だよなぁと考えていたら，全部ずらせばいいと気付きました．

ずらすと 1 + 2 + ... + (N-1) が答えなので，等差数列の和を取って終わりですね．

#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;

  cout << (long long)n*(n-1)/2 << endl;
}

E - League

問題文

貪欲法で大丈夫そうだな〜と思って組んでたんだけど，O(日数 * 試合数) みたいな計算をしていた．
これだと1日に1試合しか行われないのが最悪で，ダメみたいですね．

試合を queue に入れて，試合をした場合に次の試合が組めるなら queue に登録するみたいな感じで解けました．これだと O(試合数) になりますね．

コンテスト中に解きたかった…！

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

using namespace std;

typedef pair<int,int> P;

void addGame(int a1, const vector<queue<int>>& a, const int day, queue<tuple<int,int,int>>& q) {
  if (a[a1].empty()) return;
  int a2 = a[a1].front();
  if (a1 == a[a2].front()) q.push( make_tuple(a1,a2,day));
}

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

  vector<queue<int>> a(n+1);

  for (int i=1; i<n+1; i++) {
    for (int j=0; j<n-1; j++) {
      int ai;
      cin >> ai;
      a[i].push(ai);
    }
  }

  queue<tuple<int,int,int>> games;

  vector<bool> used(n+1,false);
  for (int i=1; i<n+1; i++) {
    if (used[i]) continue;
    int j = a[i].front();
    if (i == a[j].front()) {
      used[i]=true; used[j]=true;
      games.push(make_tuple(i,j,1));
    }
  }

  while(!games.empty()) {
    int a1,a2,day;
    tie(a1,a2,day) = games.front();
    ans = max(ans, day);
    games.pop();

    a[a1].pop();
    a[a2].pop();

    addGame(a1,a,day+1,games);
    addGame(a2,a,day+1,games);
  }


  for (auto ai : a) {
    if (ai.size() > 0 ) {
      ans = -1;
      break;
    }
  }
  cout << ans << endl;

}

まとめ

D 問題まで 25分で解いていたので， E は解きたかったです…
もっといろいろ解いて練習しなくては…！

2019-08-19

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
B - Resistors in Parallel
C - Alchemist
D - Ki
- after_contest 2019-08-21追記
E - Strings of Impurity
まとめ

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 のケースも通るように修正しました〜

▶クリックで展開

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

using namespace std;

void dfs(int qi, int p, int x, vector<vector<int>>& g, vector<long>& ans) {

  int a = ans[qi]+x;
  ans[qi] = a;
  x = a;
  for(auto v : g[qi] ) {
    if(v == p) continue;
    dfs(v,qi,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);
    g[b].push_back(a);
  }

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

  dfs(1,-1,0,g,ans);

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

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できているので良い感じだと思っています．
青パフォーマンスも狙えるところに来ている気がするので，もっと頑張りたいです！

2019-08-13

AtCoder Beginner Contest 137

AtCoder 競プロ

はい． AtCoder Beginner Contest 137 です

A,B,C の3完でした．
D難しかった…

f:id:zeronosu77108:20190813165414p:plain

C までが割りと早かったということもあり，パフォーマンスは水色手前でした
（難しくてみんな D 解けなかったのかな？）

今回で，緑色になれました！

f:id:zeronosu77108:20190813165411p:plain

A - +-x
B - One Clue
C - Green Bin
D - Summer Vacation
E - Coins Respawn
まとめ

A - +-x

問題文

そのまま最大値取るだけですね．

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

using namespace std;

int main() {
  int a,b;
  int ans = INT_MIN;
  cin >> a >> b;

  ans = max(ans,a+b);
  ans = max(ans,a-b);
  ans = max(ans,a*b);

  cout << ans << endl;
}

B - One Clue

問題文

-1000000 〜 1000000 のうち，連続して $K$ 個の石が黒く塗られているので，
その塗られている可能性がある座標を出力して下さいという問題．ヒントとして座標 $X$ が黒だと教えられます．

$X$ が左端のパターンと右端のパターンがあるので， $X-K$ から $X+K$ まで出力したら良いですね． -1000000 とか 1000000 付近は値を考慮する必要がありますが，今回は， $1 \leq K \leq 100$ と $0 \leq X \leq 100$ なので考慮する必要はないです．

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

using namespace std;

int main() {
  int k,x;
  cin >> k >> x;
  k--;

  for(int i=x-k; i<=x+k; i++) {
    cout << i << (i==x+k ? "\n" : " ");
  }
}

C - Green Bin

問題文

アナグラムになるような組み合わせがいくつあるかという問題．
アナグラムになるかどうかは，出現するアルファベットによって一意に決まる形に変換してやれば良いですね．

まぁ，一番簡単なのはソートで，ソートした後にそれを数え上げれば良いです．

数え上げて $_ 3 C _2$ みたいなことしても良いんですが， $i$ 番目が見つかったときに，他のやつとの組み合わせが増えるので， $i-1$ を足してあげれば良いです．

$_ 1 C _ 2 = 0$ ， $_ 2 C _ 2 = 1$ ， $_ 3 C _ 2 = 3$ ， $_ 4 C _ 2 = 6$ を逐次で加算していく感じですね．

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

using namespace std;

int main() {
  int n;
  long ans=0;
  cin >> n;
  map<string, int> ex;

  for (int i=0; i<n; i++) {
    string s;
    cin >> s;
    sort(s.begin(), s.end());
    if (ex[s]) ans+=ex[s];
    ex[s]++;
  }

  cout << ans << endl;
}

D - Summer Vacation

問題文

これ，考え方はあっていたのですが， TLE を大量に出してしまい時間ないに解けませんでした．
priority queue を使うんですね．

考え方はあっていただけに悔しい…
もっとデータ構造勉強しなくては！！！

考え方としては， $m-1$ 日目に仕事をして $m$ 日目までに給料をもらえるものは $A=1$ の物しかないので，その中から最大の物を選ぶ．
$m-2$ 日目に仕事をして $m$ 日目までに給料をもらうには， $A=1$ のものと $A=2$ のものから最大の物（ $m-1$ 日目の仕事とは別の物）という風に決めいく感じです．

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

using namespace std;

typedef pair<long,long> P;

int main() {
  long n,m;
  long ans=0;
  cin >> n >> m;
  vector< vector<long> > jobs(m+1);

  for (int i=0; i<n; i++) {
    int a,b;
    cin >> a >> b;
    if(a>m) continue;
    jobs[a].push_back(b);
  }

  priority_queue<int> pq;
  for (int i=1; i<=m; i++) {
    for (auto j : jobs[i]) pq.push(j);

    if(pq.empty()) continue;

    ans += pq.top();
    pq.pop();
  }

  cout << ans << endl;
}

E - Coins Respawn

問題文

解説聞いたあとに自分で書いてみました．

この問題は，負の辺を持つグラフの最短経路問題に落とし込むことができるようです．負辺を持つグラフの最短経路問題は Bellman-Ford アルゴリズムで解くことができるらしく．

聞いたとおりに実装してみました．
（プログラムは解説とは少し違うかもしれない）

書いてみるとそんなに難しくなかったので，コンテスト中に E まで解けるようになりたいですね．

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

using namespace std;

void dfs(int v, vector<vector<int>>& to, vector<bool>& f) {
  if(f[v]) return;
  f[v] = true;
  for (auto u : to[v]) {
    dfs(u,to,f);
  }
}

int main() {
  int n,m,p;
  int ans = -1;
  cin >> n >> m >> p;
  vector<vector<int>> to(n+1);
  vector<vector<int>> ot(n+1);
  vector< tuple<int,int,int> > edges;

  for (int i=0; i<m; i++) {
    int a,b,c;
    cin >> a >> b >> c;
    c = -1 * (c-p);
    to[a].push_back(b);
    ot[b].push_back(a);
    edges.emplace_back(a,b,c);
  }

  // 1 からたどり着けないやつと Nにたどり着けないやつは考慮する必要が無い
  vector<bool> from1Flag(n+1,false);
  vector<bool> toNFlag(n+1,false);
  dfs(1,to,from1Flag);
  dfs(n,ot,toNFlag);
  vector<bool> ok(n+1,false);
  for (int i=1; i<=n; i++)
    ok[i] = from1Flag[i] && toNFlag[i];

  // Bellman-Ford アルゴリズム
  vector<long> d(n+1,INT_MAX);
  d[1] = 0;
  bool updated = true;
  int step = 0;

  while(updated) {
    updated = false;
    step++;
    if(step >= n+1) break;

    for(int i=0; i<m; i++) {
      int a,b,c;
      tie(a,b,c) = edges[i];
      if (!ok[a]) continue;
      if (!ok[b]) continue;

      if (d[a]+c < d[b]) {
        updated = true;
        d[b] = d[a]+c;
      }
    }
  }

  if(step <= n) ans = max(0, (int)(-1*d[n]));
  cout << ans << endl;
}