kichi2004's BLOG

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

競プロ

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

投稿日:

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

結果

4完 [A(100), B(200), C(300), D(400)] 72:50 ペナルティ: 4 (-> 92:00)
・順位: 896位 (Rated)
・パフォーマンス: 1403
・Rating変化: 1293 -> 1305 (+12) [Rating最高値]

各問題の解法

A問題 (100点)

提出詳細
計算量 O(1)

int A, P;
cin >> A >> P;
cout << (A * 3 + P) / 2 << endl;

B問題 (200点)

提出詳細
市名(昇順)→点数(降順)にソートする。
pairや構造体、tupleを使うと楽に実装できます。
計算量 O(N log N)

struct restaurant
{
  restaurant(const int no, const string city, const int point)
  {
    this->no = no;
    this->city = city;
    this->point = point;
  }

  int no;
  string city;
  int point;
};

bool comp(const restaurant &left, const restaurant &right)
{
  if (left.city == right.city) 
    return left.point > right.point;
  return left.city < right.city;
}

int main()
{
  int N, P; string S;
  cin >> N;
  vector<restaurant> SP;
  SP.reserve(N);
  for (int i = 0; i < N; i++) {
    cin >> S >> P;
    SP.emplace_back(i + 1, S, P);
  }
  std::sort(SP.begin(), SP.end(), comp);

  for (const restaurant &res : SP) {
    cout << res.no << endl;
  }
}

C問題 (300点)

提出詳細
典型的なbit全探索の問題。
それぞれのスイッチのON/OFF状態をビットで管理し全探索する。
計算量 O(2^N × MN)

int N, M, k, si;
cin >> N >> M;

vector<vector<int>> s(M, vector<int>());
vector<int> p(M);

for (int i = 0; i < M; i++) {
  cin >> k;
  s[i].reserve(k);
  for (int j = 0; j < k; j++) {
    cin >> si;
    s[i].push_back(si - 1);
  }
}

for (int i = 0; i < M; i++) {
  cin >> p[i];
}

int ans = 0;
for (int bit = 0; bit < 1 << N; bit++) {
  //この状態において、すべてのライトが点灯しているかのフラグ
  //点灯していないライトがあったらfalseにする
  bool ok = true;
  for (int i = 0; i < M; i++) {
    //指定されたスイッチのうち、ONになっている数
    int switch_count = 0;
    for (int sw : s[i]) {
      if (bit & 1 << sw)
        switch_count++;
    }
    //p[i]と偶奇が一致しなかった場合は
    //ライトが点灯しないため、フラグをfalseにする
    if ((switch_count & 1) != p[i]) {
      ok = false;
      break;
    }
  }
  //この状態においてすべてのライトが点灯していれば
  //(=点灯していないライトがなければ)
  //答えをインクリメントする
  if (ok) ans++;
}
cout << ans << endl;

D問題 (400点)

提出詳細
宝石を筒に戻すのは「宝石を捨てる」と考えることができる。
A + B ≦ min(N, K)回の範囲内で操作AをA回、操作BをB回、
負数のうち、捨てる操作を絶対値が大きい順に最大 K – (A + B) 回行う。
このAとBを全探索すると答えが求められる。
計算量 O(min(N, K)^3 log min(N, K))

//操作しないことで0を達成できるため、答えの最小値の初期値は0にしておく
int N, K, ans = 0;
cin >> N >> K;
vector<int> V(N);
for (int i = 0; i < N; i++)
  cin >> V[i];

int R = std::min(N, K);

for (int A = 0; A <= R; A++) {
  for (int B = 0; A + B <= R; B++) {
    //左からA個取る
    int sum = 0;
    vector<int> minus_gems;
    minus_gems.reserve(R);

    for (int i = 0; i < A; i++) {
      sum += V[i];
      //負数だったらminus_gemsに追加
      if (V[i] < 0) 
        minus_gems.push_back(V[i]);
    }

    for (int i = 0; i < B; i++) {
      int idx = N - 1 - i;
      sum += V[idx];
      if (V[idx] < 0) 
        minus_gems.push_back(V[idx]);
    }

    std::sort(minus_gems.begin(), minus_gems.end());
    //捨てられる数は、K - (A + B) と負数の個数の小さい方
    int cnt = std::min(K - (A + B), int(minus_gems.size()));
    //負数を捨てられるだけ捨てる
    for (int i = 0; i < cnt; i++) {
      //minus_gems[i]は負数(小さい順(=絶対値大きい順))なので、
      //合計値から minus_gems[i] を "引く"
      sum -= minus_gems[i];
    }

    ans = std::max(ans, sum);
  }
}
cout << ans << endl;

感想

+12というなんとも微妙な上がり方ですが、上がってよかったです。
Dは嘘解法で投げてしまったかもしれない…。

-競プロ

執筆者:


comment

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

CAPTCHA


関連記事

no image

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

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

no image

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

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

no image

競技プログラミングから身を引くことにしました

お詫び 競プロについては、既に復帰しています。記事を書いたからには心情の変化等をお伝えするべきかと思いますが、余裕ができてからにさせていただければと考えています。今後ともよろしくお願いします。 また、 …

no image

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

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

no image

「M-SOLUTIONS プロコンオープン」に参加しました

コンテストページはこちら 結果 3完 [A(100), B(200), D(500)] 68:17 ペナルティ: 0 ・順位: 725位 (Rated) ・パフォーマンス: 1498 ・Rating変 …