seri::diary::competitive_programming

AtCoderで茶から赤を目指す競プロ精進日記

ABC143

atcoder.jp

所要時間

  • 30分4問完答
  • 通常のABCと比べると異常なほど簡単だった

解答メモ

A - Curtain

問題文通りに実装すればよし.

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int A, B;
  cin >> A >> B;

  cout << max(A - 2 * B, 0) << endl;

  return 0;
}

B - TAKOYAKI FESTIVAL 2019

ワークロードが小さいので何も考えずに時間計算量O(N^2)のbrute forceで解を求めれば良い.

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N;
  int d[100];

  cin >> N;
  REP(i, N) { cin >> d[i]; }

  int result = 0;
  for (int i = 0; i < N; ++i) {
    for (int j = i + 1; j < N; ++j) {
      result += (d[i] * d[j]);
    }
  }

  cout << result << endl;

  return 0;
}

C - Slimes

S[i] ≠ S[i+1] となる箇所のカウント+1が解答.

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N;
  string S;

  cin >> N >> S;

  if (N == 1) {
    cout << 1 << endl;
    return 0;
  }

  int result = 1;
  char prev = '\0';

  REP(i, N) {
    if (prev == '\0') {
      prev = S[i];
    }

    if (S[i] != prev) {
      ++result;
      prev = S[i];
    }
  }

  cout << result << endl;

  return 0;
}

D - Triangles

brute forceで解くと時間計算量がO(N^3)のためTLEする(実際にやってみたらした). しかし,O(N^3)の実装で解いても最初に昇順ソートしてから枝刈りを入れるとACした(1744 ms). 多分これは嘘解答レベルの悪い解答.

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N;
  int L[2000];

  cin >> N;
  REP(i, N) { cin >> L[i]; }

  ll result = 0;
  sort(L, L + N);

  for (int i = 0; i < N - 2; ++i) {
    for (int j = i + 1; j < N - 1; ++j) {
      for (int k = j + 1; k < N; ++k) {
        if ((L[i] < L[j] + L[k]) && (L[j] < L[k] + L[i])) {
          if (L[k] < L[i] + L[j]) {
            ++result;
          } else {
            break;
          }
        }
      }
    }
  }

  cout << result;

  return 0;
}

解説を読んで二分探索で条件を満たす3個目の辺のindexを探す方法を実装(54 ms).

Lを昇順ソートしてa<b<cが保証されている時,aとbが決まるとa<bが常に成り立つため最後の条件はc < a+bなので,最後のcとなり得る要素の数の総和が解となる.
cとなり得る要素の個数は,a+b以上の要素を境界として, 境界のindex+1(lower_bound - Lすると境界のindex+1の値になる)- bのindex+1 で求められる.

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N;
  int L[2000];

  cin >> N;
  REP(i, N) { cin >> L[i]; }

  sort(L, L + N);

  int result = 0;
  int boundary;
  for (int i = 0; i < N; ++i) {
    for (int j = i + 1; j < N; ++j) {
      boundary = lower_bound(L, L + N, L[i] + L[j]) - L;
      result += max(boundary - (j + 1), 0);
    }
  }

  cout << result << endl;

  return 0;
}