アルゴリズマーの備忘録

Med解くまでにどんだけ時間かけたんだ…

Easy ListeningSongs

問題概要

You have two favorite music bands. Each of them has just recorded a new album. You have bought both albums. You know the durations (in seconds) of songs on each of the album. You are given these duration in vector s durations1 and durations2. Elements of durations1 are the durations of songs on one of the album, elements of durations2 correspond to the songs of the other album. You only have a limited amount of time before you have to leave for work. This amount of time is given in the int minutes. (Note that the durations are given in seconds while this time is given in minutes.) Given this time, you want to listen to as many different songs as possible. However, there is a constraint: as you are a fan of both bands, you have to listen to at least T different songs from each album. Each song only counts if you listened to it from its beginning to its end. You can play the songs in any order you like. Selecting the next song to play and switching between albums takes zero time. If the input data is such that it is impossible to listen to T different songs from each album in the time you have, return -1. Otherwise, return the largest number of different songs you can listen to.

minute分間に2つのCD？からなるべく多くの楽曲を聞きたい。しかし、欲張りなので両方のCDから音楽を最低T曲は聞きたい。最大何曲聞くことが出来るか。条件を満たせないなら-1を返せ。

解法

取り敢えず、各CD内で再生時間の短い順にソートします。その後、各CDでT曲目までの再生時間の総和を求め、minuteよりも長いなら-1（CDがT曲なくても-1）。

これらの条件を満たせば-1を返すことはないので、両方のCDから再生時間の短い順に曲を聞ける限り聞けばOK。自分は普通にソートしたけど、マージソートっぽくこの処理をした人の方が多そう。

#include <bits/stdc++.h>
using namespace std;
class ListeningSongs{
    public:
    int listen(vector<int> durations1,vector<int> durations2,int minutes,int T){
        minutes*=60;
        sort(durations1.begin(),durations1.end());
        sort(durations2.begin(),durations2.end());
        int sum=0;
        if(durations1.size()<T||durations2.size()<T)    return -1;
        for(int i=0;i<T;i++) sum+=durations1[i]+durations2[i];
        if(sum>minutes)    return -1;
        vector<int> ls;
        int ans=2*T;
        for(int i=T;i<(int)durations1.size();i++)    ls.push_back(durations1[i]);
        for(int i=T;i<(int)durations2.size();i++)    ls.push_back(durations2[i]);
        sort(ls.begin(),ls.end());
        for(int i=0;i<(int)ls.size();i++){
            if(sum+ls[i]>minutes)  return ans;
            sum+=ls[i]; ans++;
        }
        return ans;
    }
};

Med ContestScoreboard

問題概要

Some teams have competed in a programming contest. Each team has made one or more submissions. Each submission received some positive score. The total score of a team is the sum of the scores of all their submissions. The scoreboard is computed by sorting the teams according to their total scores. If multiple teams are tied, they are sorted lexicographically, with smaller names being higher in the scoreboard. The team on the top of the scoreboard is winning. (Only one team is winning at any moment, even if there are multiple teams tied for the winning total score.)

The scoreboard contains one line for each team. For each team, the line has the following format: "TeamName S1/T1 S2/T2 ... SN/TN". Here:

TeamName is the name of the team
N is the number of submissions they made
the values S1 through SN are the scores of those submissions
the values T1 through TN are times in minutes: submission Si was made after Ti minutes of the contest have elapsed

Different teams may have different numbers of submissions, worth a different number of points, and submitted at different times. The submissions are not necessarily ordered: neither by score, nor by submission time.

You are given a vector scores: the scores of all teams, generated long after the contest was over. Each element of scores describes one team in the format shown above. The elements of scores are not necessarily ordered: neither by total score, nor by team name.

You would like to know who won the contest. However, this isn't necessarily the team that is currently winning. This is because it is possible that the scoreboard contains some submissions that happened after the end of the contest.

You know that the duration of the contest was an integer between 1 and 10⁹, inclusive. Apart from that, you have no information about the exact duration. If the duration of the contest is D minutes, only the submissions that have Ti strictly smaller than D should be counted towards the correct total scores.

Given the content of scores, we say that a team could have won the contest if it was winning for some value of D from the above range. For each team, determine whether that team could have won the contest. Return a vector with the same number of elements as scores. For each valid i, element i of the return value should be 1 if the team described by scores[i] could have won the contest, or 0 if it couldn't.

scoresに「（チーム名）　（得点）/（その得点を得るまでの時間）　（得点）/（その得点を得るまでの時間）…」というデータが与えられる。コンテストの時間が1〜1e9のどれかだった時、そのチームが優勝する可能性があるなら1、無いなら0を持つ配列を返せ。

解法

まずは翻訳。その際に得点と時間をpairで持たせて、時間順にソート。1と1e9を含めたsetに全チームの得点する時間を入れて、その各タイミングでどのチームが優勝するのかシミュレーション。

逆に言えば、どのチームも得点していない時間帯にチームの順位が入れ替わることはあり得ないです。

#include <bits/stdc++.h>
using namespace std;
class ContestScoreboard{
    public:
    vector <int> findWinner(vector <string> scores){
        int n=scores.size();
        vector<string> name[n];
        vector<pair<int,int>> data[n];
        vector<int> time;
        for(int i=0;i<n;i++){
            string names;
            int k=0;
            while(scores[i][k]!=' '){
                names+=scores[i][k];    k++;
            }
            name[i].push_back(names);
            for(;k<(int)scores[i].size();k++){
                int s=0,t=0;
                while(scores[i][k]!='/'){
                    if(scores[i][k]==' ')    k++;
                    else{
                        s=s*10+(scores[i][k]-'0');
                        k++;
                    }
                }
                while(k<scores[i].size()&&scores[i][k]!=' '){
                    if(scores[i][k]=='/')        k++;
                    else{
                        t=t*10+(scores[i][k]-'0');
                        k++;
                    }
                }
                data[i].push_back(make_pair(t,s));
                time.push_back(t);
            }
            sort(data[i].begin(),data[i].end());
        }
        time.push_back(0);
        sort(time.begin(),time.end());
        time.erase(unique(time.begin(),time.end()),time.end());
        vector<int> ret;
        vector<int> now;
        for(int i=0;i<n;i++){
            ret.push_back(0);  now.push_back(0);
        }
        for(int i=0;i<(int)time.size();i++){
            int t=time[i];
            for(int j=0;j<n;j++){
                while(data[j].size()&&data[j][0].first<t){
                    now[j]+=data[j][0].second;
                    data[j].erase(data[j].begin());
                }
            }
            int win=0,score=0;
            for(int i=0;i<n;i++){
                if(score<now[i]){
                    score=now[i];
                    win=i;
                }
                else if(score==now[i]){
                    if(name[i]<name[win])      win=i;
                }
            }
            ret[win]=1;
        }
        return ret;
    }
};

翻訳の部分で失敗していたらしく、落とされました。その後も苦労してやっと出来た。

感想

文字列操作弱い。対策しなきゃ。

あと、JOIの対策ばっかだったのでネットワークフローがサッパリ分からないことに気がついた。やっておかないと。

アルゴリズマーの備忘録

square869120Contest #1(E、G)

square869120Contest #1(A〜D)

SRM679 Round1 Div.2

Easy ListeningSongs

問題概要

解法

Med ContestScoreboard

問題概要

解法

感想

第2回ドワンゴからの挑戦状予選(問題A,B)

yukicoder No.336 門松列列

問題概要

yukicoder No.333〜335

No.333 門松列を数え上げ

問題概要

Codeforces Round #339 (Div. 2)

A. Link/Cut Tree

問題概要

解法