kichi2004's BLOG

競技プログラミングの参加記とか日常とか。(※Google Analyticsを使用しています)

競プロ

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

投稿日:

コンテストページはこちら

結果

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

各問題の解法

A問題 (100点)

提出詳細
計算量 O(1)

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 が失われてしまいました。
めちゃめちゃ悔しいです。半月後くらいに第2弾があるみたいなので、そこではもっと高いパフォーマンスを出せるようにしたいです。

-競プロ

執筆者:


comment

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA


関連記事

no image

「AtCoder Beginner Contest 128」に参加しました

コンテストページはこちら 結果 4完 [A(100), B(200), C(300), D(400)] 72:50 ペナルティ: 4 (-> 92:00) ・順位: 896位 (Rated) ・パフォ …

no image

「AtCoder Beginner Contest 124」に参加しました

コンテストページはこちら 結果 全完 [A(100), B(200), C(300), D(400)] 39:46 ペナルティ: 1 (+5:00 -> 44:46) ・順位: 313位 ・パフォーマ …

no image

「第3回 RCO日本橋ハーフマラソン 予選」に参加しました

コンテストページはこちら 結果:133位(A: 147位、B: 108位) A: 286,823点、B: 493,349点 予選突破はできませんでした。(ほぼ確実) 各問題の考察 A問題 (画像:in …

no image

「AtCoder Beginner Contest 141」に参加しました

コンテストページはこちら 結果 5完 [A(100), B(200), C(300), D(400), E(500)] 46:53 ペナルティ: 1 (-> 51:53) ・順位: 329位 (Rat …

no image

JOI 2020 / 2021 二次予選 参加記

はじめに おひさしぶりです.kichi2004 です.競プロ関係の記事は今年の 3 月以来 9 か月ぶりなので,まずはそれについて簡単にお話します.今年の 2 月に,JOI に二次予選落ちしたことや …