貪欲法 bit全探索 深さ優先探索 atcoder

ARC029 A - 高橋君とお肉

ARC029 A - 高橋君とお肉
Feb. 2, 2020, 1:52 p.m.

目次

問題

https://atcoder.jp/contests/arc029/tasks/arc029_1

入力

$N$
$t_1$
$t_2$
...
$t_N$

  • $N$ - タスクの数
  • $t_N$ - タスクにかかる時間

出力

2並列でタスクを処理していく場合にかかる最短合計時間

解説

すべてのタスクについて2つの選択肢があるので、bit全探索で求められます.
$N$が4と小さいので正解です.

一方で、

「より時間がかかるタスク順に、その時点で空いている方に追加していく」

という貪欲法でも求められます.
一般に貪欲法が適用出来る場合はこちらの方が高速になります.

計算量

bit全探索の場合

$$O(2^N)$$

貪欲法の場合

最初のソートのために$O(N \log{N})$.
貪欲法自体は$O(N)$.

$$
O(N \log{N})
$$

解答

bit全探索バージョン

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Int N, _t;
vector<Int> T;

void input() {
  cin >> N;
  while (cin >> _t) T.push_back(_t);
}

Int dfs(Int t, Int time1, Int time2) {
  if (t >= N) return max(time1, time2);
  return min(
    dfs(t + 1, time1 + T[t], time2),
    dfs(t + 1, time1, time2 + T[t])
  );
}

void solve() {
  cout << dfs(0, 0, 0) << endl;
}

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

貪欲法バージョン

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
Int greedy() {
  Int a = 0, b = 0;
  for (auto t: T) {
    if (a < b) a += t;
    else b += t;
  }
  return max(a, b);
}

void solve() {
  sort(span_all(T));
  reverse(span_all(T));
  cout << greedy() << endl;
}