AtCoder Beginner Contest 139

はい． AtCoder Beginner Contest 139 です

A,B,C,D の4完でした． 無限に E問題 TLE してました．

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