AtCoder Beginner Contest 141

はい． AtCoder Beginner Contest 141 です

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

ABCDの4完でした．

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

問題文

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

#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 に戻します．
これを 回繰り返して，総和を取ると最小の合計金額が求まります．

#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代だったのでまぁまぁ良いですね．
この調子で頑張ります。