プログラミングバトル 予選・本戦 - BCU30 2019

本戦B問題解けず20位...めっちゃ悔しい

予選

A Bullet of Flame

atcoder.jp

考察

を小さい方から和を取り、 を超えたところまでの壁の枚数を出力する。

提出コード

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n,p;
  cin >> n >> p;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    if (a[i] <= p) {
      p -= a[i];
      ans += 1;
    } else {
      break;
    }
  }
  cout << ans << endl;
}

本戦

A Wolf Keyboard

atcoder.jp

考察

問題文に少し気圧されるが、多く使う文字ほど押す回数を減らせれば良い。 使う回数の少ない文字 個を2回、それ以外を1回押せばよい。

提出コード

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n,k;
  cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) cin >> a[i];
 
  sort(a.begin(), a.end());
  int ans = 0;
  for (int i = 0; i < n - k; ++i) {
    ans += a[i] * 2;
  }
 
  for (int i = n - k; i < n; ++i) {
    ans += a[i];
  }
 
  cout << ans << endl;
}

B Interval Addition

atcoder.jp

考察

全ての要素が の配列中の連続する区間を自由に選び、その要素を となるように変更し、与えられた配列 と等しくなるまでに最小何回操作を行う必要があるかという問題。

区間の広さは自由に選べるがとする必要がある。 従って目的の配列 の要素が となるまで を更新できる。

配列 が最初から全てが のときに注意。

提出コード

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> a(n+1);
  bool isAllZero = true;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    if (a[i]) isAllZero = false;
  }
  a[n] = numeric_limits<int>::max();

  int ans = 1;
  for (int i = 1; i <= n; ++i) {
    if (a[i] < a[i-1]) ans += 1;
  }

  if (!isAllZero) {
    if (a[n-1] == 0) ans -= 1;
    cout << ans << endl;
  } else {
    cout << 0 << endl;
  }
}

---

200, 300, 400って感じ