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 Grand Contest 031」に参加しました

コンテストページはこちら 結果 0完 ・順位: 1565位 ・パフォーマンス: 358 ・Rating変化: 1046 -> 992 (-54) 各問題の考察 感想 全くわからなかった。出なかったら良 …

no image

「AtCoder Grand Contest 034」に参加しました

コンテストページはこちら 結果 2完 [A(400), B(600)] 49:18 ペナルティ: 3 (-> 64:18) ・順位: 736位 (Rated) ・パフォーマンス: 1552 ・Rati …

no image

JOI 2020 / 2021 本選 参加記

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

no image

「エクサウィザーズ 2019」に参加しました

コンテストページはこちら 結果 2完 [A(100), B(200)] 2:00 ペナルティ: 0 ・順位: 550位 (Rated内533位) ・パフォーマンス: 1721 [パフォーマンス最高値] …

no image

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

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