「diverta 2019 Programming Contest」参加記録

「diverta 2019 Programming Contest」に参加しました

投稿日：2019年5月23日

結果

4完 [A(100), B(200), C(400), D(500)] 47:04 ペナルティ: 1 (47:04 -> 52:04)
・順位: 446位 (Unrated)

各問題の解法

A問題 (100点)

int N, K;
cin >> N >> K;
cout << N + K - 1 << endl;

B問題 (200点)

提出詳細
計算量 O(1)
R, G それぞれ最大3000個を試し、全探索をする。
よくあるループを1つ減らすテクニックを使う。

long long R, G, B, N;
cin >> R >> G >> B >> N;
int ans = 0;
for (int r = 0; r <= 3000; r++) {
  for (int g = 0; g <= 3000; g++) {
    int r_cnt = R * r, g_cnt = G * g;
    if (rr + gg <= N && (N - (rr + gg)) % B == 0)
      ans++;
  }
}
cout << ans << endl;

C問題 (400点)

提出詳細
すべての文字列内の”AB”の出現数 + 組み合わせたときの A][B ( [] は文字列の境界 ) の最大値が答えとなる。
このとき、組み合わせたときの最大値は、
x := min( Aで終わる文字列の数, Bで終わる文字列の数)
とおいたときのxである。
ただし、x > 0 の場合において、”Aで始まりBで終わらない文字列”か、”Aで始まらずBで終わる文字列”がない場合は、x-1となる。

計算量 O(N･|Si|)

int N;
cin >> N;
int ans = 0, cnta = 0, cntb = 0, cntab = 0;
for (int i = 1; i < N; i++) {
  string s;
  cin >> s;
  for (int i = 0; i < s.size() - 1; i++) {
      if(a[i] == 'A' && a[i+1] == 'B') ans++;
  }
  bool start_b = s[0] == 'B';
  bool end_a = s[s.size() - 1] == 'A';
  if (start_b) cntb++;
  if (end_a) cnta++;
  if (end_a && start_b) cntab++;
}
int res = min(cnta, cntb);
if (res && cnta == cntb && res == cntab) res--;
cout << ans + res << endl;

D問題 (500点)

提出詳細
N / m = X あまり X
→ Xm + X = N
としたとき、m は √N 以下である。
そのため、A = { 1, 2, …, √N } として、
p := N / A[i] としたとき、
N % p = [N / p] であるもののpの合計値が答えとなる。
※ここで、 x % y は x ÷ y のあまり、 [x / y] は x ÷ y の小数以下を切り捨てたものである。

(別の解法としては、Nの約数を全て列挙し、それから1を引いたものが答えとなるというものがあるそうです。
多分やってることは同じですが。)

計算量 O(√N)

long long N;
cin >> N;
long long ans = 0;
int end = int(sqrt(N));
for (int i = 1; i <= end; i++) {
  long long a = N / i - 1;
  //除数が0の場合は計算しない
  if (a && N % a == N / a) ans += a;
}
cout << ans << endl;

感想

500まで解いて、過去最高のperf 1847…!! と思っていたのですが、システムの不具合でUnratedとなり、Rating +74 が失われてしまいました。
めちゃめちゃ悔しいです。半月後くらいに第２弾があるみたいなので、そこではもっと高いパフォーマンスを出せるようにしたいです。