square869120Contest #1(E、G)
忘れそうなのでEとGも。E以降は「アレ?この難易度でいいのか?」と思いながら解いてました。
続きを読むsquare869120Contest #1(A〜D)
現在FとH以外は解いたけど、1つの記事にするとえげつない長さになるので2〜3回に分割します。
今回はA〜D問題。比較的簡単で、自分もコンテスト中(夕飯食べたり風呂入ったりで参加したのは実質1時間)でDまでは解きました。
続きを読むSRM679 Round1 Div.2
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
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
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 109, 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
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の対策ばっかだったのでネットワークフローがサッパリ分からないことに気がついた。やっておかないと。
第2回 ドワンゴからの挑戦状 予選(問題A,B)
タイトル通り2完でした。C問題の「最悪の時の最短時間」っていうのがゲームっぽいからアルファ・ベータ法か何かかな…とは思ったけど、ゲーム系はNimぐらいしか実装したこと無いのでさっぱりな人でした。
取り敢えずコンテスト終了と同時にBまでは解説を出そうと。
続きを読むyukicoder No.336 門松列列
やっと出来た…(1問前よりはマシ)
問題概要
長さNの1〜Nの数字が1つずつある数列でどの隣り合った3つの数字を選んでも門松列になっている数列は何通りあるか。1e9+7で割った余りを求めよ。
続きを読むyukicoder No.333〜335
RMQのセグメントツリー実装でバグが合ったらしく、かなりの時間悩んだ。
まだ336解いてませんが、取り敢えずここでコード載せておきます。
No.333 門松列を数え上げ
問題概要
左端、真ん中の門松の長さが与えられるので、右の門松で門松列を満たす長さの数を答えよ。
続きを読む