AtCoder Beginner Contest 140 - zeronosu77108’s blog

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