「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は嘘解法で投げてしまったかもしれない…。