kichi2004's BLOG

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

競プロ

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

投稿日:

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

結果

全完 [A(100), B(200), C(300), D(400)] 41:40 ペナルティ: 2 (41:40 -> 51:40)
・順位: 421位 (Unrated)

各問題の解法

A問題 (100点)

提出詳細
T / A * B で求まる。

int A, B, T;
cin >> A >> B >> T;
cout << (T / A * B) << endl;

B問題 (200点)

提出詳細
V[i] > C[i] であるものの合計

int N;
vector<int> V(N), C(N);
for (int i = 0; i < N; i++)
  cin >> V[i];
for (int i = 0; i < N; i++)
  cin >> C[i];

int ans = 0;
for (int i = 0; i < N; i++)
  ans += max(0, V[i] - C[i]);
cout << ans << endl;

C問題 (300点)

提出詳細
Aからある1要素を除いたときの最大公約数の最大値を求める問題。
Aから2つの数 x, y を取る。
x, y のすべての約数をそれぞれ X, Y とし、その和集合を S とする。
答えは x or y どちらかの約数であるため、Aの全てに対して、S[i]が約数であるかを判定し、(N-1)個以上が約数であるものの最大値が答えとなる。

int N;
cin >> N;
vector<int> A(N);
for (int i = 0; i < N; i++)
  cin >> A[i];

set<int> set;
for (int i = 0; i < 2; i++) {
  for (int j = 1; j * j <= v; j++) {
    if (A[i] % j == 0) {
      set.insert(j);
      set.insert(A[i] / j);
    }
  }
}

int ans = -1;
for (int val : set) {
  int cnt = 0;
  for (int a : A)
  {
    if (a % val) cnt++;
    if (cnt > 1) break;
  }
  if (cnt < 2 && ans < val)
    ans = val;
}
cout << ans << endl;

D問題 (400点)

提出詳細
負数が偶数個(0個を含む)である場合は、すべての数を正にできるため、答えはAの絶対値の合計値となる。
そうでない場合は、必ず1つ負数が残ってしまう。答えを最大化したいので、負数は絶対値が小さい方がよい。答えは、Aの絶対値の合計値 – Aの絶対値の最小値 * 2 である。
なお、負数が奇数の場合でも、0が1つでも存在する場合はすべての数を正にすることができるが、0は何度符号を反転させても答えは変わらないため、0を1つだけ-0と考えても答えは変わらない。そのため、0が存在するかどうかで特別な処理を書く必要はない。
(絶対値の最小値が0のため、結局答えは絶対値の合計値となると考えても良い。)

int N;
cin >> N;
int minus_count = 0, abs_min = 1000000010;
long long ans = 0;
for (int i = 0; i < N; i++) {
  int tmp;
  cin >> tmp;
  if (tmp < 0) minus_count++;
  if (abs_min > abs(tmp)) abs_min = abs(tmp);
  ans += abs(tmp);
}
//負数の個数が奇数の場合
if (minus_count % 2) ans -= abs_min * 2LL;
cout << ans << endl;

感想

水色になってから初めてのABC (Unrated)。
最近全完少しずつ全完できるようになってきたので嬉しい。
AとBがかなり調子悪くて早解きに失敗したので、このあたりはもうちょっと頑張らなければ…

-競プロ

執筆者:


comment

メールアドレスが公開されることはありません。

CAPTCHA


関連記事

no image

「AtCoder Beginner Contest 145」A~E問題解説 / 参加記

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

no image

AtCoder 解説についての考え

kichi2004 です. 先日,AtCoder の解説についてのツイートを複数行ったところ,かなり広範囲に広まってしまい,いくつかのルートでは,誤解を含んで広まっているようでした. この記事では,A …

no image

JOI 2020 / 2021 本選 参加記

JOI (第20回日本情報オリンピック)の本選に参加しました.146 点(100 – 0 – 12 – 34)で本選落ちでした. ARC や AGC にも OI に …

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 121」に参加しました

コンテストページはこちら 結果 3完 [A(100), B(200), C(300)] 11:16 ペナルティ: 0 ・順位: 1006位 ・パフォーマンス: 1108 ・Rating変化: 1039 …