SHIINBLOG

AtCoder Beginner Contest 140

はい. 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 も近いうち解いて更新します!!

AtCoder Beginner Contest 139

はい. 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 は解きたかったです…
もっといろいろ解いて練習しなくては…!

AtCoder Beginner Contest 138

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

AtCoder Beginner Contest 137

はい. AtCoder Beginner Contest 137 です

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

f:id:zeronosu77108:20190813165414p:plain

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

今回で,緑色になれました!

f:id:zeronosu77108:20190813165411p:plain


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問題はアルゴリズムを知らないと解けないような問題が出てくるのか…」と思ったのでもっと頑張ります!
(毎回言ってる)

AtCoder Beginner Contest 136

はい. AtCoder Beginner Contest 136 です

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

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



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

AtCoder Beginner Contest 135

はい. 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;
}



まとめ

今回は,C問題までしか解けなかった上に, D 問題が全然分からなくて焦って C の再提出などして,
たくさんペナルティーもらってしまったので,ダメダメでした.

緑になれるかな〜と思っていたのにむしろレート下がりました_(:3」∠)_

AtCoder Beginner Contest 134

はい. AtCoder Beginner Contest 134 です

A,B,C,D,E の5完でした.
E で 5ペナルティー.つらい…

f:id:zeronosu77108:20190722134013p:plain
f:id:zeronosu77108:20190722134016p:plain


A - Dodecagon

問題文

入力の  r  3*r^ 2 して出力するだけですね.

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

using namespace std;

int main() {
  int r;
  cin >> r;
  cout << 3*r*r << endl;
}



B - Golden Apple

問題文

監視員は前後  D マス見えるんだから,1人の監視員でカバーできる範囲は  2*D+1
だから,それで  N を割って,切り上げをしたら答えが出る.

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

using namespace std;

int main() {
  int n,d;
  cin >> n >> d;
  cout << ceil(n/(2*d+1.0)) << endl;
}



C - Exception Handling

問題文

最初,最大値と次に小さい値を持っておけば解けるじゃん〜と思っていたんだけど,
次に小さい値っていうのがちょっとめんどくさかったので sort() しちゃえ!と実装しました.

なんか sort(b.rbegin(), b.rend()) という書き方もあるっぽい?次からそれで書こう!

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

using namespace std;

typedef pair<int,int> P;

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

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

  sort(b.begin(),b.end(), greater<int>());

  for(int i=0; i<n; i++) {
    if (a[i] == b[0]) {
      cout << b[1] << endl;
    } else {
      cout << b[0] << endl;
    }
  }
}



D - Preparing Boxes

問題文

 i の倍数の箱に入っているボールが奇数か偶数か,みたいな問題.
 N から決めていけば大丈夫な感じ.

(これよく見たら存在しない場合'-1'を出力とか書いてるけど,そんな機能つけてないよ…?)
たまたま通してしまった()

解が存在しないということがないってことかな…? こういうのは証明して「ないから必要無い」とするのは良いけど,たまたま通すのはちょっと減らしていきたいね.

iの倍数を通って行って,もしボールが入っていたら,フラグを反転させて,
未確定(-1)なら,フラグを代入する形で決定していった.

よく考えたら for(j=i+i; j<=n; j+=i) とかしたらかけ算とかしなくて良かったかな.

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

using namespace std;

typedef pair<int,int> P;

int main() {
  int n,m;
  m=0;
  cin >> n;
  vector<int> a(n);
  vector<int> b(n,-1);

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

  for(int i=n; i>0; --i) {
    bool f = a[i-1];
    int l = n/i;
    for(int j=l; j>0; --j) {
      if(b[i*j-1] == -1) {
        b[i*j-1] = f;
        if(f) m++;
        break;
      } else {
        if(b[i*j-1] == 1)
          f = !f;
      }
    }
  }

  cout << m << endl;
  for(int i=0; i<n; i++) {
    if(b[i] >= 1)
      cout << i+1 << endl;
  }
}



E - Sequence Decomposing

問題文

なぜか時間内に解けてしまいました()
グラフではないけど,1つのレーンみたいなものを作って,その後ろに積み重ねていくイメージで書いた.
ニムトっていうボードゲームっぽいな〜と思いながら書いてました.

最初は, roots っていう変数に頭の数保存して,その列の最大値にアクセスして〜みたいなこと書いてたけど,TLE になったので,考え直しました(最初のコード).
roots を探すループを書いていたので,それが悪いと思って vector で列の最大値だけ管理するようにしたら通りました(REとかたくさん出したけど).

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

using namespace std;

template< typename T >
typename std::vector<T>::iterator 
   insert_sorted( std::vector<T> & vec, T const& item )
{
    return vec.insert
        ( 
            std::upper_bound( vec.begin(), vec.end(), item ),
            item 
        );
}

int main() {
  int n;
  cin >> n;
  vector<int> roots;

  for(int i=0; i<n; i++) {
    int v;
    cin >> v;
    v = -1*v;
    if(roots.size() <= 0) {
      roots.push_back(v);
      continue;
    }

    auto index = upper_bound(roots.begin(), roots.end(), v);
    if(index != roots.end()) {
      roots.erase(index);
    }
    insert_sorted(roots,v);

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



まとめ

初めて E問題まで解けました.
ABCで初めて900位と3桁になれたので良かった.
蟻本も買ったので,今からアルゴリズムも勉強するし,もっと解けるようになるかな〜と思いました.
もっと頑張るぞ〜