投稿日 11/20/2019最終更新日 11/20/2019

# 問題

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全探索バージョン

C++

// 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;

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;
}

# 貪欲法バージョン

C++

// 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;

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;
}

シュン

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

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

ARC029 A - 高橋君とお肉