SRM647参加しました。前回と前々回は都合が合わなかったやら、完全に開催を忘れるなどがあり、今年(ratingありでは)、初SRM参加です。(前回参加のSRM644がunrated)
今回も、日本時間的には参加しづらい時間での開催でしたが、実際私もChallengePhaseではかなり眠かったのです。すぐに落とせそうなのが無いか確認した後、自分自身が(寝)落ちました。
また、今回でやっと復帰前落としまくっていたraitingを緑まで上げることが出来ました。
(rating: 841 -> 925)
ただ、今回もコンテスト中にhardが解けず、また解き直しも他の予定もあり、なかなか時間が取れずどんどん未消化の問題が増えているため、早めに解き直しをしたいところです。
250 : PeacefulLine
問題概要
数列が1列入力される。
この数列で、同じ値同士が隣り合わせにならない組み合わせがあるか否かを返す。
解法
この問題では同じ値がいくつあるかをカウントすることで解くことができます。
仮にその数列で一番和の多い値を値xとした時、値xの数がその数列全体の半数だったとしても、その間にそれ以外の数値をいれれば同じ値が隣り合わない数列を作ることができます。
数列の要素数が偶数の時、値xの個数が数列の半数を超えている、もしくは数列の要素数が奇数の時、値xの個数が数列の半数+1を超えている場合のみ要求の数列を作ることはできず、それ以外の時は必ず作成することができます。
コード
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class PeacefulLine { | |
| public: | |
| string makeLine(vector<int> x) { | |
| sort(x.begin(),x.end()); | |
| int ans=0; | |
| int cnt=1; | |
| for (int i=1; i < x.size(); i++) { | |
| if(x[i-1]==x[i]) | |
| { | |
| cnt++; | |
| ans=max(cnt,ans); | |
| } | |
| else | |
| cnt=1; | |
| } | |
| if(ans<=(x.size()+1)/2) | |
| return "possible"; | |
| else | |
| return "impossible"; | |
| } | |
| }; |
500 : TravellingSalesmanEasy
問題概要
M個の街があり、city[i]の街でprofit[i]の価値で売ることができるものを各1つずつ持っている。
あなたのcity巡回ルートがvisitで与えられるので、あなたが売ることができる価値の合計の最大を求めよ。
なお、1回訪れた時に最大で1つしか売ることはできない。(同一の街に複数回訪れた場合はその回数売れる)
解法
この問題は、訪れた街で売れるもの、かつ今持っているものの中で最大の価値のものを売り続けて、その合計を求めることで得ることができます。
そのため、町ごとに価値の高い順に値を取り出せるqueue等にデータを入れて管理、処理をしていけばOKです。
私は街1つずつにpriority_queueを作成して処理しましたが、後からの挿入は無いので、入力が終わった時点でソートして先頭から取り出す形でも十分のはずです。
ただし、売れるものがない街を訪れる場合もあるので、queue等がからの時の例外処理を忘れないようにしておく必要があります。
コード
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class TravellingSalesmanEasy { | |
| public: | |
| int getMaxProfit(int M, vector<int> profit, vector<int> city, vector<int> visit) { | |
| int ans=0; | |
| priority_queue<int> qu[M]; | |
| for (int i=0; i < profit.size(); i++) { | |
| qu[city[i]-1].push(profit[i]); | |
| } | |
| for (int i=0; i < visit.size(); i++) { | |
| if(qu[visit[i]-1].empty()) | |
| continue; | |
| ans+=qu[visit[i]-1].top(); | |
| qu[visit[i]-1].pop(); | |
| } | |
| return ans; | |
| } | |
| }; |
950 : BuildingTowers
問題概要
N個のビルを以下のルールにしたがって建てる。
- 隣り合うビル同士の差はK以下
- x[i]番目のビルの高さはt[i]
- 1番目のビルの高さは0
この条件でビルを建てるとき、最も高いビルの高さを返す。
解法
ビルiの高さを決めるときにその先にtで高さを決められたビルがあるとき、ビルiの高さ+(K差のビルの個数)<=t+(K差のビルの数)となる箇所があればそこまでビルを高くして、その後ビルを低くするといった形で立てればできるだけ高いビルを作ることができるので、この箇所を2分探索等で探せば…ともいましたが、コンテスト中に実装できなかったため、検証出来ていません…