Educational Codeforces Round 3（CF）に参加しました

2完．コンテスト後に通らなかったテストを考えつつ，他の人のコードを読んで，Cも通せた．

本当は自分で見つけないと駄目なレベルのミスでしたね．

A問題

要約

n本のUSBメモリが渡される．
メモリの容量はそれぞれa1, a2, a3, ... という形で改行で区切られ，与えられる．
m MBのデータを保管するために必要な最小本数は何本か？（整数で答えよ）

入力例
n
m
a1
a2
....
an

n: USBメモリの数
m: 保存したいMB数
a1..an: それぞれのUSBメモリの容量

条件から，容量の多いUSBメモリから使用していけば，最小の本数を求めることができる．なので，USBメモリの容量を配列に入れて，ソートして適応させる．（貪欲法？）

Submission #14882824 - Codeforces

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout.precision(16);

    int n, m;
    cin >> n >> m;

    int arr[n];
    REP(i, n) cin >> arr[i];
    sort(arr, arr+n);

    int res = 0;
    RREP(i, n) {
        m -= arr[i];
        res++;
        if(m <= 0) break;
    }

    cout << res << endl;
    return 0;
}

B問題

Problem - B - Codeforces

要約

本を2冊プレゼントしたい．本にはそれぞれジャンルがある．
色んな本を読んで欲しいから，異なるジャンルの本を選びたい．
選ぶ組み合わせは何通りか？

入力例
n m
a1 a2 a3 ... an

n: 本の数
m: ジャンルの数
a1..an: その本のジャンルナンバー

各ジャンルごとに何冊本があるのかを数え，その組み合わせの数を求める．

1,2  1,3  1,4
2,3  2,4
3,4

のように組み合わせていくと，組み合わせの漏れも重複もなく求められるので，良いと思う（実際，自分はそうしたが，もっと良い方法があるのかもしれない）

Submission #14884033 - Codeforces

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout.precision(16);

    int n, m;
    cin >> n >> m;

    int arr[m];
    REP(i, m) arr[i] = 0;
    REP(i, n) {
        int t;
        cin >> t;
        arr[t-1]++;
    }

    ll ret = 0;
    REP(i, m) {
        int tret = 0;
        FOR(j, i+1, m) {
            tret += arr[i] * arr[j];
        }
        ret += tret;
    }

    cout << ret << endl;
    return 0;
}

C問題

Problem - C - Codeforces

要約

n 台のサーバーにタスク（整数値）を割り振っているのだが，それを平均的にしたい．
移動コストを1として，最小のコストを求めてください．

入力例
n
a1 a2 a3 ... an

n: サーバーの数
a1..an: それぞれのサーバーに割り振られている現在のタスク量

まず，平均値を求める．（総タスク量をサーバー数で割る）

タスク量を平均的に割り振っていく必要があるが，タスク量は整数値であるため，あくまで平均的に割り振る必要がある．

そのため，総タスク量をサーバー数で割った時の余りを求め，その数分だけ平均値+1になるようにサーバーの仕事量を割り振り，残りを平均値になるように割り振る．ように計算し，移動コストを求める（実際には配列の操作とかしないので）

計算のしやすさを考えて，一応降順ソートしています．

Submission #14888819 - Codeforces

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout.precision(16);

    int n;
    cin >> n;

    int sum = 0;
    int arr[n];
    REP(i, n) {
        cin >> arr[i];
        sum += arr[i];
    }

    int ave = sum/n;
    sort(arr, arr+n, greater<int>());

    ll res = 0;
    int cnt = sum % n;
    REP(i, n) {
        int t = arr[i] - ave;
        if(t > 0) res += (cnt-- > 0 ? t-1 : t);
    }

    cout << res << endl;
    return 0;
}

C問題の本番は，平均値と平均値+1にしなければいけないサーバーの数が合わず，その結果総移動コストがずれてしまい，WAを生やしまくっていたようです．（もう少し単純に求められると思っていたけれども，手元で幾つか自分で考えたテストケース実行してもなんかおかしかったので，多分これであっているだろうと思って修正しきれなかったのは甘さですね…）

D問題以降は触れる機会があれば，やってみましょうかね．
先に解説を読んでみようと思います．