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

問題文

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 競プロ

はい． 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 競プロ

はい． 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桁になれたので良かった．
蟻本も買ったので，今からアルゴリズムも勉強するし，もっと解けるようになるかな〜と思いました．
もっと頑張るぞ〜

AtCoder Beginner Contest 133

AtCoder 競プロ

はい． AtCoder Beginner Contest 133 です

C問題沼りましたが，4完でした．

f:id:zeronosu77108:20190709101430p:plain f:id:zeronosu77108:20190709101433p:plain


A - T or T

問題文

電車かタクシーかどちらが安いかという問題．
単純に N*A と B のどちらか小さい方を出力するだけ．

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

using namespace std;

int main() {
    int n,a,b;
    cin >> n >> a >> b;
    cout << min(n*a, b) << endl;
}



B - Bite Eating

問題文

問題文の通りに計算しました．
整数の判定ぱっと思いついたものが，ceil() と floor() して，同じなら〜と思ったんだけど，
他の人のソース見てみたら， sum == (int)sum みたいなことしていて，そっちの方が良いな〜と思いました．

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

using namespace std;

int main() {
    int n,d;
    int count=0;
    cin >> n >> d;
    vector< vector<int> > x (n+10, vector<int>(d+10));

    for(int i=0; i<n; i++) {
        for(int j=0; j<d; j++) {
            cin >> x[i][j];
        }
    }

    for(int i=0; i<n; i++) {
        for(int j=i+1; j<n; j++) {
            double sum = 0.0;
            for(int k=0; k<d; k++) {
                sum += pow((abs(x[i][k] - x[j][k])), 2);
            }
            sum = sqrt(sum);
            if ( ceil(sum) == floor(sum) ) {
                count++;
            }
        }
    }

    cout << count << endl;
}



C - Remainder Minimization 2019

問題文

割った余りなので，単純に l %= 2019; r %= 2019 して，［l,r］ で探索したら良いかな〜と思ったんだけど， それだと，１周（以上）している場合に判定できないな といろいろやっていたら沼りました．

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

using namespace std;

const long mod = 2019;

int main() {
    long l,r;
    cin >> l >> r;

    long ldiv = (l-1) / mod;
    long rdiv = r / mod;
 
    if ( rdiv - ldiv > 0 ) {
        puts("0");
        return 0;
    }

    l%=mod; r%=mod;

    long ans = 3000;
    for (long i=l; i<=r; i++) {
        for(long j=i+1; j<=r; j++) {
            ans = min(ans, (i*j)%mod);
        }
    }
    cout << ans << endl;

}


最初に

if ( r-l >= 2019 ) {
  puts("0");
  return 0;
}

とかやってたんだけど，そっちの方が良かった．



D - Rain Flows into Dams

問題文

「なんだこの問題…」と思っていました（Cが解けなくてD来てよく分からん…と何度か往復しました）．

最初に考えたのは，連立方程式をたてて，行列で解く方法なんだけど，
なんとなくダメそうな気がして辞めました．

その連立方程式を足したり引いたりしたら，解けるのでは？と考えていたら解けました．
こんな感じの式がたてられるんだけど x_1 / 2 + x_2 / 2 = A_1 分母の2が邪魔なので，全体に2をかけて．
N=3 のとき，全体としては以下の感じ．

x_1 + x_2 = 2A_1 \\ x_2 + x_3 = 2A_2 \\ x_3 + x_1 = 2A_3 \\

１行目の式から，２行目の式を引いて，

x_1 - x_3 = 2A_1 - 2A_2

さらにその式に３行目の式を足して，

2x_1 = 2A_1 - 2A_2 + 2A_3

という感じで， x _ 1 が求められる． x _ 1 が決まったら後は，
x _ {i+1} = 2A _ {i} - x _ i \quad(i = 1,2,\cdots,n-1) という感じ．


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

using namespace std;

const long mod = 2019;

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

    x[0] = 0;

    for(long i=0; i<n; i++) {
        cin >> a[i];
        if (i%2==0){
            x[0] += a[i];
        } else {
            x[0] -= a[i];
        }
    }

    cout << x[0] << " ";
    for(long i=1; i<n; i++) {
        x[i] = a[i-1]*2 - x[i-1];
        cout << x[i] << " ";
    }
    cout << endl;
}



E - Friendships

問題文

残り15分くらいで読んだけどよく分かりませんでした．
解説を聞きながら寝たんだけどなんか nPr を使うらしい．
解けたら追記します．



まとめ

4完で，緑パフォーマンスだったので，最近の成績から言えば悪くなかったですね． C問題沼らなければ，もう少しパフォーマンス出たのかなぁ〜と思うので，もっと勉強しなくては！

AtCoder Beginner Contest 131

AtCoder 競プロ

はい． AtCoder Beginner Contest 131 です

久しぶりに参加したので，ちゃんと解けるか不安だったけど， A,B,C,D は解けました．
E も解けそうだったけど，時間が足りませんでした（ C に時間をかけ過ぎた）．

f:id:zeronosu77108:20190623155652p:plain f:id:zeronosu77108:20190623155657p:plain


A - Security

問題文

char で取って1つ前を保存しておきました．

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>


using namespace std;

int main(void) {
    char c1,c2;
    c2 = '-';
    bool f = false;
    for(int i=0; i<4; i++) {
        cin >> c1;

        if ( f || c1 == c2 ) {
            f = true;
        }
        c2 = c1;
    }

    cout << (f? "Bad" : "Good") << endl;
}



B - Bite Eating

問題文

愚直に計算しつつ，絶対値の小さいものを保存しておきました．

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>


using namespace std;

int main(void) {
    int n,l;
    int eat = 999;
    int sum = 0;
    cin >> n >> l;

    for(int i=1; i<=n; i++) {
        sum += l + i - 1;
        if( abs(eat) > abs(l+i-1) ) {
            eat = l+i-1;
        }
    }

    cout << sum - eat << endl;
}



C - Anti-Division

問題文

a未満の c,dで割りきれる数と b以下の割り切れる数を求めて引き算したら解けました．
最初 (b-a) で range を取ってごにょごにょしていたんですが，それではダメでした
（本当にこの方法で良いのか疑問を持ちながら書いていたので，まぁ当たり前と言えば当たり前でした）

この手の問題は，問題集とかにも載っているらしく，時間かかってしまったのは，ちょっと残念ですね．

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


using namespace std;

long long gcd(long long a,long long b){
    if (a%b==0){
        return(b);
    }
    else{
        return(gcd(b,a%b));
    }
}

int main(void) {
    long long a,b,c,d;
    cin >> a >> b >>  c >> d;
    long long ans1,ans2;
    long long GCD = gcd(c,d);
    a--;
    ans1 = a/c + a/d - a/((c*d)/GCD);
    ans2 = b/c + b/d - b/((c*d)/GCD);

    cout << (b-a) - (ans2 - ans1) << endl;
}



D - Megalomania

問題文

期限の短い順に並べて，処理していけば 時間内に仕事が終わるかどうか分かります．
C より簡単なのでは…？

なんか compare の関数内側に書く方が良さそうなんだけど，書き方を覚えていなかったので外側に書くことになってしまった．
pair をほとんど調べずに進められたので，成長を感じました．

最初，期限の長いものから引き算していったので，変数名とかがそこに引きずられて残念な感じになっています…

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
#include <cmath>
#include <utility>


using namespace std;


bool compare(pair<long long, long long> i1, pair<long long, long long> i2) 
{ 
    if ( i1.second == i2.second) return i1.first > i2.first;
    return (i1.second < i2.second); 
} 

int main(void) {
    long long n;
    cin >> n;
    vector< pair<long long, long long> > ab;
    for (long long i=0; i<n; i++) {
        long long tmp1,tmp2;
        cin >> tmp1 >> tmp2;
        ab.push_back( make_pair(tmp1,tmp2));
    }

    sort(ab.begin(), ab.end(), compare);
    long long max = 0;

    for (long long i=0; i<n; i++) {
        if ( max+ab[i].first > ab[i].second ) {
            cout << "No" << endl;
            return 0;
        }
        max += ab[i].first;
    }

    cout << "Yes" << endl;



}



E - Friendships

問題文

これもそんなに難しく無さそう…（希望的観測）
もう少し時間があったら解けた気もしますが，とりあえず解けませんでした．

勉強して書けたら追記します．



まとめ

今回は A,B,C,D 解けて，E もある程度解けそうだったので悪くないかもと思ったのですが，順位的には微妙でした．
次回はもっとレートを上げられるように頑張ります！

AtCoder Beginner Contest 128

競プロ プログラム AtCoder

はい． AtCoder Beginner Contest 128 です

f:id:zeronosu77108:20190527000245p:plain f:id:zeronosu77108:20190527000304p:plain

今回は酷い． AC になったのは， A と B だけでした(:3」∠)
とりあえず，この2つをまとめておきます．

C以降は勉強して解けたら追記していきます．


A - Apple Pie

問題文
リンゴが 3 つの欠片になるのだから，足して割るだけ．

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main(void) {
    int a,p;
    cin >> a >> p;
    cout << (a*3+p)/2 << endl;
}



B - Guidebook

問題文
index 置いてソートするだけ．

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

using namespace std;


int main(void) {
    long n;
    vector< pair<string, int> > ass;
    cin >> n;

    for (long i=0; i<n; i++) {
        pair<string, int> tmp;
        cin >> tmp.first >> tmp.second;
        ass.push_back(tmp);
    }

    vector<int> index(ass.size());
    iota(index.begin(), index.end(), 0);


    sort(index.begin(),
         index.end(),
             [&](long x, long y){if( ass[x].first != ass[y].first) return ass[x].first<ass[y].first; return ass[x].second>ass[y].second;}
    );

    sort(ass.begin(), ass.end());

    for(auto i: index){
        cout << i+1 << endl;
    }
}




C問題以上は，明日以降にちゃんと考えて解いたら追記します．

AtCoder Beginner Contest 127

AtCoder プログラム 競プロ

はい． AtCoder Beginner Contest 127 です

今回は縛りプレイじゃないです（だからといって順位は高くないです）．

f:id:zeronosu77108:20190525231129p:plain


f:id:zeronosu77108:20190525231148p:plain

A - Ferris Wheel

問題文
はい．問題文の通りに実装しました．

#include <iostream>

using namespace std;

int main() {
    int a,b;
    cin >> a >> b;
    if ( a <= 5 ) {
        b = 0;
    } else if ( a <= 12 ) {
        b /= 2;
    }

    cout << b << endl;
}



B - Algae

問題文
for文ぶん回すだけ…？

#include <iostream>

using namespace std;

int main() {
    long long r,d,x;
    cin >> r >> d >> x;
    
    for(long long i=0; i<10; i++) {
        cout << (x=r*x-d) << endl;
    }
}



C - Prison

問題文
Lの最大値と Rの最小値を求めれば良いだろ〜って感じで書いた．
これ，LとRすれ違うこともあるよなぁとか思いつつもそのまま出してしまって WA
即 if文を書き足して AC

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    long long n,m;
    cin >> n >> m;
    long long nmax=-1;
    long long nmin=9999999999;
    for(long long i=0; i<m; i++) {
        long long l,r;
        cin >> l >> r;
        nmax = max(nmax, l);
        nmin = min(nmin, r);
    }

    long long ans = abs(nmin - nmax) + 1;
    if ( nmin < nmax ) {
        ans = 0;
    }
    cout << ans << endl;
}



D - Integer Cards

問題文
ソートして小さい方から書き換えて行けば良いのでは？という感じ．
入れ子な vector のソート慣れてなくて時間がかかった．

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

using namespace std;

bool compare(vector<long long> i1, vector<long long> i2) 
{ 
    return (i1[1] > i2[1]); 
} 

int main() {
    long long n,m;
    vector<long long> a;
    vector<vector<long long> > bc;
    cin >> n >> m;

    for(long long i=0; i<n; i++) {
        long long tmp;
        cin >> tmp;
        a.push_back(tmp);
    }

    for(long long i=0; i<m; i++) {
        long long tmp;
        vector<long long> vtmp;
        cin >> tmp;
        vtmp.push_back(tmp);
        cin >> tmp;
        vtmp.push_back(tmp);
        bc.push_back(vtmp);
    }
    
    sort(a.begin(), a.end());
    sort(bc.begin(), bc.end(), compare);

    long long i,j;
    i = j = 0;

    while( a[i] < bc[j][1] ) {
        if( bc[j][0] > 0 ) {
            a[i] = bc[j][1];
            i++;
            if( i > n-1 ) {
                break;
            }
            bc[j][0]--;
        } else {
            j++;
            if( j > m-1 ) {
                break;
            }
        }
    }
    long long ans = 0;
    for(long long i=0; i<n; i++) ans += a[i];
    cout << ans << endl;
}



E - Cell Distance

問題文
最初 4C2 とか組み合わせ使うのかな〜って考えてたけど，思いつかなくて一旦 F問題へ．
戻ってきて雑に総当たり書いてみたけど，よく分からず…

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

using namespace std;

long long mod = 1000000007;

long long calc(long, long, long, long, long, long );

int main() {
    long n,m,k;
    cin >> n >> m >> k;
    long sum = 0;

    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++ ) {
            sum += calc(n,m,i,j,k,1);
        }
    }
    cout << sum << endl;
}

long long calc(long n, long m, long i, long j, long k, long l) {
    if ( l == k ) {
        return 0;
    }

    long sum = 0;
    for (int ii=i; ii<i; ii++) {
        for (int jj=j+1; jj<j; jj++) {
            sum = (sum + calc(n,m,ii,jj,k,l+1) + abs(ii-jj)) % mod;
            //cout << "sum " << sum << " ";
        }
    }
    //cout << endl;
    //cout << "(" << i << "," << j << ") " << "l : " << l << endl;
    //cout << "sum " << sum << endl;
    //cout << endl;
    return sum;
}



F - Absolute Minima

問題文
何だこの問題は…
a の最小値と a を vector に溜めておいて， 2 が来たら全部絶対値取って足せば良いかな〜とか思ってた．
ダメみたいです．

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

using namespace std;


int main() {
    vector<long long> a;
    long amin = 9999999999;
    long n;
    long b = 0;
    cin >> n;
    for (int i=0; i<n; i++) {
        long q;
        cin >> q;
        // cout << "q : " << q << endl;
        if( q == 2 ) {
            long sum = 0;
            for (auto it : a ) {
                sum += abs(amin - it);
            }
            cout << amin << " " << sum + b << endl;
        } else {
            long ta,tb;
            cin >> ta >> tb;
            // cout << "a b : " << ta << " " << tb << endl;
            a.push_back(ta);
            amin = min(amin, ta);
            b += tb;
        }
    }
}




E問題と F問題は解けなかったので，次回までに（と言っても明日なんだけど…）勉強したい(:3」∠)