Coderunner2015 に参加しました

coderunner 2015 に参加しました。

もうちょっと順位上げられたなぁとは思うんですが本戦自体も, その後の懇親会もとても楽しめました。
来年ももしあったらぜひ参加したいです。

このページでは本戦の問題の紹介と自分の考えたことを書きたいと思います。

問題はこちら↓
https://coderunner.jp/mypage-problem-final.html

うーん, 長い。

で, 自分の解法です。

この問題では, 外注された仕事を受けるのがローリスクハイリターンで有利です。

外注する側の立場からすると, 自分の会社で仕事をしきれない場合, その仕事は外注すると, 仕事をやらないことによって余計な時間を使わずに済み, かつ罰金を払わなくて済むので, ある意味では 仕事を行うことによる利益 + 罰金 の価値がある可能性はあるわけです(まぁ普通 利益+α 程度で収めますが)。

なので, 外注で仕事を出すときに他の人に確実に処理してもらうためにちょっと色目をつけて報酬をつける可能性があるわけです。
まず一点として, このようなことがあるので, 外注された仕事を受けるのが有利です。

また, 外注された仕事は罰金を取られるのは外注した会社なので全くリスクがありません。

そして, これが一番重要だと思うのですが, 外注された仕事には, 報酬/仕事量 (これは問題文によると乱数です) の値が大きい物, つまり利益が大きい仕事が存在する可能性が, 自分で受注してガチャを回すよりはるかに高いです。

以上の理由から, 自分では受注しないで外注された仕事をひたすら引き受けるのが better です。

下のコードでは, 自分で受注した仕事, 市場にある仕事を input して, 利益率が高い順にソートした後, 出来る仕事を引き受けています。引き受ける際は, その種類の仕事を得意な人が優先して仕事に取り組むようにします。

バグバグしててここまでしか書けませんでしたが(でも多分終了 1 時間前にこれだけかけてれば 20 位には入れていた気がする), 仕事量で割り算するのではなく, 今いる社員でやるとどれだけ時間がかかるのかをちゃんと計算して, きっちり利益率を計算するとかやると少し点数の伸びが良くなりそうです。

const string token  = "";
const string getInfoURL    = "http://game.coderunner.jp/getinfo?token=" + token;
const string assignURL = "http://game.coderunner.jp/assign?token="+token;
const string getWorkURL = "http://game.coderunner.jp/taketask?token="+token;
const string outWorkURL = "http://game.coderunner.jp/outsource?token="+token;
const string filename = "info.txt";
const string filename2 = "outsource.txt";

string query(string url) {

    FILE *f = popen(("curl -s -k \"" + url + "\"").c_str(), "r");

    if (f == NULL) {
        perror("error!");
    }
    char buf[1024];
    string res;
    while (!feof(f)) {
        if (fgets(buf, 1024, f) == NULL) break;
        res += (string)(buf);
    }

    pclose(f);
    return res;
}

struct Worker {
    int id;
    vector<int> ability; // 消化速度
    int restTime; // 次に仕事が出来るようになるまでの時間
    int exp; // 経験値
    Worker() {}
    Worker(int num) {init(num);}
    void init(int syurui) {ability.resize(syurui);}
};

struct Task {
    int id;
    int time; // 残り時間
    int load; // 仕事量
    int pattern; // 仕事の種類
    int reward; // 報酬
    int risk; // 賠償
    Task() {}
};

void think() {
    // 入力
    ifstream ifs(filename);
    ifstream ifs2(filename2);
    ll score;
    ifs >> score;
    int buka_num, syurui_num;
    ifs >> buka_num >> syurui_num;
    vector<Worker> worker(buka_num);
    for (int i = 0; i < buka_num; i++) {
        worker[i].init(syurui_num);
        ifs >> worker[i].id;
        for (int j = 0; j < syurui_num; j++) {
            ifs >> worker[i].ability[j];
        }
        ifs >> worker[i].restTime >> worker[i].exp;
    }
    int task_num;
    ifs >> task_num;
    vector<Task> task(task_num);
    for (int i = 0; i < task_num; i++) {
        ifs >> task[i].id >> task[i].time >> task[i].load >> task[i].pattern >> task[i].reward >> task[i].risk;
    }
    {
        int out_num;
        ifs2 >> out_num;
        for (int i = 0; i < out_num; i++) {
            Task t;
            ifs2 >> t.id >> t.time >> t.load >> t.pattern >> t.reward;
            task.push_back(t);
        }
    }
    int gaityu_num;
    ifs >> gaityu_num;
    // アルゴリズム
    vector<Worker> restWorker;
    for (int i = 0; i < buka_num; i++) {
        if (worker[i].restTime == 0) restWorker.push_back(worker[i]);
    }
    sort(task.begin(), task.end(), [&](const Task& lhs, const Task& rhs) {return 1.*lhs.reward/lhs.load > 1.*rhs.reward/rhs.load;});
    bool notask = true;
    // 能力が高いやつ優先に仕事を割り当てる
    cout << task.size() << endl;
    for (int i = 0; i < (task.size()); i++) {
        int id = task[i].pattern;
        sort(restWorker.begin(), restWorker.end(), [&](const Worker& lhs, const Worker& rhs) {return lhs.ability[id] < rhs.ability[id];});
        int cur = restWorker.size()-1;
        int load = task[i].load;
        vector<int> IDs;
        while (cur >= 0 && load >= 0) {
            IDs.push_back(restWorker[cur].id);
            load -= worker[cur].ability[id]*task[i].time;
            cur--;
        }
        if (cur > 0) {
            for (int i = 0; i < 3; i++) {
                if (cur-i < 0) break;
                IDs.push_back(restWorker[cur-i].id);
            }
        }
        if (load > 0) {
            cout << "cannot complete this task" << endl;
            continue;
        }
        notask = false;
        string assignSuruzo = assignURL;
        assignSuruzo += "&task=" + to_string(task[i].id);
        int idnum = IDs.size();
        assignSuruzo += "&worker=";
        for (int j = 0; j < idnum; j++) {
            assignSuruzo += to_string(IDs[j]);
            if (j < idnum-1) assignSuruzo += ",";
            cout << IDs[j] << endl;
            restWorker.pop_back();
        }
        string result = query(assignSuruzo);
        cout << result << endl;
    }
    if (notask && task_num == 0) {
        cout << "no task" << endl;
        if (restWorker.size() > 10) {
            cout << "get Work" << endl;
            query(getWorkURL);
        }
    }
}

int main() {
    while (1) {
        string info_result = query(getInfoURL);
        std::ofstream ofs(filename);
        std::ofstream ofs2(filename2);
        string out_result = query("http://game.coderunner.jp/getout?token="+token);
        ofs << info_result << endl;
        ofs2 << out_result << endl;
        think();
        usleep(1010000);
    }
    return 0;
}