2019-10-16

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

まとめ

A,B,C の3完でした．
緑色になれたので，モチベーションも上がりました！
さらに頑張ります！！

「やっぱり，E問題はアルゴリズムを知らないと解けないような問題が出てくるのか…」と思ったのでもっと頑張ります！
（毎回言ってる）

2019-08-06

AtCoder Beginner Contest 136

競プロ AtCoder

はい． AtCoder Beginner Contest 136 です

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

f:id:zeronosu77108:20190806113958p:plain f:id:zeronosu77108:20190806114002p:plain

A - Transfer
B - Uneven Numbers
C - Build Stairs
D - Gathering Children
E - Max GCD
- コンテスト中に書いたプログラム
まとめ

A - Transfer

問題文

$C - (A - B)$ して正の数を出力するだけ．負数なら $0$

#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

問題文

$10 ^5$ だから総当たりするだけ．
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

問題文

後ろから $-1$ しても単調非減少（広義単調増加）にできないなら，'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 が入れ替わるところに溜まっていくことが分かって，
$10 ^ {100}$ なので，全ての子どもが 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

問題文

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

勉強します．

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

#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問くらいは解けると思うので早く解けるようになりたいですね．

2019-07-29

AtCoder Beginner Contest 135

AtCoder 競プロ

はい． AtCoder Beginner Contest 135 です

A,B,C の3完でした．今回はペナルティーも多いしとても酷い…

f:id:zeronosu77108:20190729232834p:plain

A - Harmony

問題文

$A$ と $B$ のちょうど間の数字が $\mid A - K \mid = \mid B - K \mid$ になる数字なので，
$A$ と $B$ の和が偶数のときは解があって，そうでないときは IMPOSSIBLE となる．

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

using namespace std;

long long main() {
  long long a,b;
  cin >> a >> b;
  if ( (a+b) %2==0) {
    cout << (a+b)/2 << endl;
  } else {
    cout << "IMPOSSIBLE" << endl;
  }
}

B - 0 or 1 Swap

問題文

「0回か1回の swap で昇順にすることができますか？」っていう問題．
$\{1,2,3,\cdots,N\}$ なので，入力を取りながら，何個 i と異なるかを数えておいて，それが2より大きければ 1回以下の swap では昇順にすることができません．

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

using namespace std;

long long main() {
  long long n;
  cin >> n;
  long long count=0;

  for(long long i=1; i<=n; i++) {
    long long t;
    cin >> t;
    if(t != i) count++;
  }

  cout << (count>2 ? "NO" : "YES") << endl;
}

C - City Savers

問題文

$A _1$ と $A _ {N+1}$ がループしていないので，
前（もしくは後ろ）から全力で倒していけば良いです．

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

using namespace std;

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

  for(long long i=0; i<n; i++) {
    long long b;
    cin >> b;

    if(a[i] <= b) {
      ans += a[i];
      b -= a[i];
    } else {
      ans += b;
      b=0;
    }

    if(a[i+1] <= b) {
      ans += a[i+1];
      a[i+1]=0;
    } else {
      ans += b;
      a[i+1] -= b;
    }

  }
  cout << ans << endl;
}

D - Digits Parade

問題文

時間内に解けずに F 問題に手を出していました(もちろん F 問題は解けていません)．

解説を読もうと思ったら， DP と書いていたので，解けるかも！と考えたら，解けました．
かけ算と足し算はどのタイミングで mod 取っても良いので，位ごとに mod を取って DP できそうだなと思いました．

例えば， $44 \bmod 13$ の場合， $( ( 4 \ast 10 \bmod 13) + (4 \bmod 13)) \bmod 13$ みたいなことをしても言い訳ですね．

ということは，下位（もしくは上位）桁から 13 で割った余りがどこに行くかで DP を取っていけば良いと．

時間内に気がつきたかった…

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


using namespace std;

const int mod = 1000000007;


int main() {
  string s;
  int dp[100005][13];
  cin >> s;
  int n = s.size();
  reverse(s.begin(),s.end());
  cout << s << endl; 

  int digit=1;
  dp[0][0] = 1;
  for(int i=0; i<n; i++) {

    // 未確定のとき
    if(s[i] == '?') {
      for(int d=0; d<10; d++) {
        for(int j=0; j<13; j++) {
          dp[i+1][(d*digit + j)%13] += dp[i][j];
          dp[i+1][(d*digit + j)%13] %= mod;
        }
      }
    } 
    // 確定しているとき
    else {
        int d = (s[i] - '0'); // 数値に変換
        for(int j=0; j<13; j++) {
          dp[i+1][(d*digit + j)%13] += dp[i][j];
          dp[i+1][(d*digit + j)%13] %= mod;
        }
    }

    // DPテーブル出力
    // for (int i=0; i<=n; i++) {
    //   for (int j=0; j<13; j++) {
    //     cout << dp[i][j] << " ";
    //   }
    //   cout << endl;
    // }
    // cout << endl;

    digit *= 10;
    digit %= 13;
  }

  cout << dp[n][5] << endl;
}

F - Permutation Oddness

問題文

なんとなく解けそう！と思ったんだけど，ダメでした．

なんか zアルゴリズムなどで点を列挙して， Union-Find するらしい．
両方知りませんでした．

僕が書いた雑なプログラムでもある程度通ってるの笑いました．
Union-Find は，さらっと勉強したので， zアルゴリズム勉強したいと思います．

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

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

using namespace std;

std::vector<long long> find_all(const std::string str, const std::string subStr) {
    std::vector<long long> result;
 
    long long subStrSize = subStr.size();
    long long pos = str.find(subStr);
 
    while (pos != std::string::npos) {
        result.push_back(pos);
        pos = str.find(subStr, pos + subStrSize);
    }
 
    return result;
}

int main() {
  string s,t;
  cin >> s; 
  cin >> t;

  string st = s;
  string tt = t;


  while(t.size()*2 > s.size()) {
    s += s;
  }

  vector<long long> ans = find_all(s,t);



  if(ans.size()>1 && ans[0]+t.size() == ans[1]) {
    cout << -1 << endl;
    return 0;
  }


  cout << ans.size() << endl;
}