ABC104 C - All Green

Calendar Clock iconCalendar Clock icon

atcoder

目次

# 問題

https://atcoder.jp/contests/abc104/tasks/abc104_c

# 入力

DGD G
p1c1p_1 c_1
...
pDcDp_D c_D

問題ランク数DD、目標スコアGGDD個の問題セットが与えられます.
問題セットは問題数pip_iと全問解いた場合のボーナスcic_iからなります.
問題セットiiの点数は100×i100 \times iです.

# 出力

GGを達成するような最小の問題数を答える問題です.

# 解説

問題数の最大値は10310^3個です.
なので計算量を1秒に間に合う10810^8に収めるには最大でもO(N2logN)O(N^2 \log N)程度に抑える必要があります.

すべての問題について解くか否かの組み合わせを考えればその中で最も問題数が少なくて目標スコアを満たすものが答えになります.
当然答えは求まりますが、2n2^nとなり間に合いません.

そこで得点は問題のランクが高いほど高くなることに着目します.
ボーナスが無いとすると貪欲法的に最後の問題から目標スコアに達するまで解いていくのが答えはなずです.
これはO(N)O(N)で解けます.
今回はボーナスがあるので、得点が高い問題の部分点よりも低い問題のボーナスの方が高い可能性があります.
この方法は使えません.

そこで今度は問題1つずつに着目するのではなくランクに着目してみます.
ランクは最大で1010個なのでこれで解ければビット全探索でも計算量2102^10で間に合います.

すべてのランクについて解くか否かの組み合わせをすべて考えます.
解く、とは全問解いてボーナスまでもらうことを指します.
解かない、とは1問も解かないことを指します.
どちらのケースでも、目標スコアに足りていなければ解かれていないランクの内で最大のものから部分的に解いて良いこととします(O(1)O(1)).
部分的に解く、とは問題数の内数問解くがボーナスは得られないことを指します.

これで正解が得られます.
部分的に解くのは1ランクのみで良くてO(1)O(1)で可能な理由は、2ランク以上部分的に解くよりはまず優先して得点が高い方の1ランクを集中して解いた方が常に良いからです.
部分的に解くのでボーナスは考慮する必要がなく貪欲法的です.

# 計算量

O(2D)O(2^D)

# 解答

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;
#define MAX_D 11

struct Rank {
  Int numProblems, score, bonus;

  Rank(): numProblems(0), score(0), bonus(0) {}

  Rank(Int n, Int s, Int b): numProblems(n), score(s), bonus(b) {
  }
};

Int D, G, c, p;
Rank ranks[MAX_D];

struct State {
  Int index = 0, numTaken = 0, score = 0, partialIndex = 0;

  State() {
  }

  bool success() {
    return score >= G;
  }

  bool end() {
    return index >= D;
  }

  State takePart() {
    State copy = *this;
    Int need = (G - score) / ranks[index].score;
    if (need > ranks[index].numProblems) return copy;
    copy.score += ranks[index].score * need;
    copy.numTaken += need;
    return copy;
  }

  State take() {
    State copy = *this;
    copy.score += ranks[index].score * ranks[index].numProblems + ranks[index].bonus;
    copy.numTaken += ranks[index].numProblems;
    return copy;
  }

  State inc() {
    State copy = *this;
    copy.index++;
    return copy;
  }
};

void input() {
  cin >> D >> G;
  loop(d,1,D+1) {
    cin >> p >> c;
    ranks[d-1] = Rank(p, 100*d, c);
  }
}

State dfs(State state) {
  if (state.success() || state.end()) return state;
  if (state.takePart().success()) return state.takePart();

  State not_take = dfs(state.inc());
  State take = dfs(state.take().inc());
  if (not_take.success() && take.success())
    return (not_take.numTaken < take.numTaken) ? not_take : take;
  if (take.success()) return take;
  else return not_take;
}

void solve() {
  State init;
  State result = dfs(init);
  cout << result.numTaken << endl;
}

int main(void) {
  input();
  solve();
  return 0;
}

リモートフリーランス。ウェブサービス、スマホアプリエンジニア。
東アジアを拠点に世界を移動しながら活動してます!

お仕事のご依頼・お問い合わせはこちら

コメント