競技プログラミング練習記 No.33【ABC127練習】

初回 -> はじめに

ABC127を解きました。
4完です！

問題	時間	アルゴリズム	実行時間
A	1min	-	8ms
B	3min	漸化式	9ms
C	7min	imos法	24ms
D	48min	ヒストグラム	89ms

A - Ferris Wheel

	int a, b;
  cin >> a >> b;
  if (a <= 5) cout << 0;
  else if (a <= 12) cout << b / 2;
  else cout << b;

if文が3つありますね。
条件を書く順番に気を付けて書きましょう。

B - Algae

  int r, d, x;
  cin >> r >> d >> x;
  for(int i = 0; i < 10; ++i)
  {
    cout << (x = r * x - d) << endl;
  }

漸化式が与えられるので、その数列の要素を順に列挙する問題です。
今回は大丈夫ですがオーバーフローに注意しましょう。

C - Prison

  int n, m, l, r;
  cin >> n >> m;
  int imos[100005];
  fill(imos, imos + 100005, 0);
  for(int i = 0; i < m; ++i)
  {
    cin >> l >> r;
    imos[l]++;
    imos[r + 1]--;    
  }

  int ans = 0;
  for(int i = 0; i < 100004; ++i)
  {
    imos[i + 1] += imos[i];
    if(imos[i + 1] == m) ans++;
  }
  cout << ans;

いもす法を使って解きました。
ただこの問題はそこまでする必要はなくて、[Lの最大値, Rの最小値] の範囲の長さが答えになります。
解説を見てわかりました。
ABC169-Eで似たものが出てましたね。気付きたかった。

D - Integer Cards

  ll n, m, b, c;
  cin >> n >> m;
  map<ll, ll> a;
  ll input;
  for(int i = 0; i < n; ++i)
  {
    cin >> input;
    a[input]++;
  }
  
  for(int i = 0; i < m; ++i)
  {
    cin >> b >> c;
    int loop_cnt = 0;
    for(auto& val : a)
    {
      if (val.first >= c) break;

      if (val.second > b)
      {
        a[c] += b;
        val.second -= b;
        break;
      }

      loop_cnt++;
      b -= val.second;
      a[c] += val.second;
      val.second = 0;
    }
    a.erase(begin(a), next(begin(a), loop_cnt));
  }

  ll ans = 0;
  for(auto& val : a)
  {
    ans += (val.first * val.second);
  }
  cout << ans;

std::mapを使いました。keyがカードの値、valueが枚数です。
b枚のcが与えられたとき、cより値が小さいカードを捨ててcを取り入れています。

上のプログラムでは捨てたカードは削除しているのですが、削除は不要でした。
入力のカードをすべてひとつのpriority_queue< pair<int, int> >に入れて、最後にM枚取り出して和を計算すれば答えになります。
最大値だけが欲しいのでpriority_queueを使っています。

気付きたかった。
削除すると最後の和を求める部分で楽なのですが、途中の処理が複雑になります。
計算量も多くなりますね。

以上です。ありがとうございました。