読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

TopCoder SRM 144 div2

TopCoder

はじめてのTopCoder過去問。
一番最初のdiv2を解いてみました。
結構時間による減点がシビアでびっくりしてます。
普段はVisual Studioを使っているのですがTopCoderの環境にVSが適してないっぽいのでeclipseCoderプラグインをつかってeclipseでコーディングしています。
3問解いてみましたがこれくらいなら(英文が読めれば)できるかなって感じでした。

200点 「Time」

  • 問題概要

秒が与えられる。時:分:秒の形にしてstringを戻り値とせよ。

  • 解法

%60,/=60を繰り返して文字列にくっつけるだけ。
intからstringへの変換はstd:to_string()でOK。
これはC++11の関数なのでgccのバージョンに注意。

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<complex>

using namespace std;

class Time {
	public: string whatTime(int seconds) {
		string str="";
		str=":"+to_string(seconds%60);
		seconds/=60;
		str=":"+to_string(seconds%60)+str;
		seconds/=60;
		str=to_string(seconds)+str;
		return str;
	}
};

550点 「BinaryCode」

  • 問題概要

2進数列Pを整形してできた数列Qが与えられる。PとQの長さは共にN。
Q[i]=P[i-1]+P[i]+P[i+1]が成り立つ。
ただしPの存在しない要素は足さない(P[-1],P[N])
P[0]が0,1の場合のPをそれぞれ答えよ。存在しない場合はNONEと出力。

  • 解法

P[i]について、Q[i-1]とP[i-1],P[i-2]が分かっていれば
P[i]=Q[i-1]-P[i-1]+P[i-2]と求められる。
したがってP[i]をiの小さい順に求めていけばPは一意に求まる。
P[0]が0の場合と1の場合をそれぞれ求め、矛盾がないか確認してやれば良い。

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
using namespace std;

#define reE(i,a,b) for(auto (i)=(a);(i)<=(b);(i)++)
#define rE(i,b) reE(i,0,b)
#define reT(i,a,b) for(auto (i)=(a);(i)<(b);(i)++)
#define rT(i,b) reT(i,0,b)


class BinaryCode {

	private:
	bool calc(vector<int> &q,vector<int> &p,int n,int s){
		if(s>q[0])return(false);
		p.push_back(0);
		p.push_back(s);
		reT(i,1,n){
			int tmp=q[i-1]-p[i]-p[i-1];
			if(tmp==0||tmp==1)p.push_back(tmp);
			else return(false);
		}
		if(q[n-1]==p[n]+p[n-1])return true;
		else return(false);
	}
	public: vector<string> decode(string message) {
		vector<string> ans;
		int N=message.size();
		vector<int> Q;
		rT(i,N)Q.push_back(message[i]-'0');
		vector<int>P1,P2;
		if(calc(Q,P1,N,0)){
			string str="";
			reE(i,1,N)str=str+to_string(P1[i]);
			ans.push_back(str);
		}
		else ans.push_back("NONE");

		if(calc(Q,P2,N,1)){
			string str="";
			reE(i,1,N)str=str+to_string(P2[i]);
			ans.push_back(str);
		}
		else ans.push_back("NONE");
		return ans;
	}

};

1100点 「PowerOutage」

  • 問題概要

木構造の形をしたダクトがある。
全ての頂点に(何か)があってその(何か)を点検します。
根(頂点番号0)からスタートしたとき、全ての(何か)の点検にかかる時間は何秒か。
ただし(何か)の点検にかかる時間は0秒、頂点間の辺を移動するのにかかる秒が与えられる。
現れる頂点番号は0から49、与えられる辺の本数は(現れる頂点の個数)-1、辺の移動に要する秒は1以上2,000,000以下。

  • 解法

巡回セールスマン問題。
だが木構造をしているというのがポイント。
バックトラックをしていくと全ての辺を二回通ることが分かる。
しかしこの問題では全ての点検を終えるまでにかかるコストを答えるため、
最後に訪問した頂点から始点0に戻る必要はない。
したがって、解は
2(全ての辺の総和)-(始点から最後に訪問する頂点へのパスに含まれる辺の総和)
となる。
この値を最小化したい。
つまり、始点から最後に訪問する頂点へのパスに含まれる辺の総和を最大化すればよい。
最も始点から遠い辺への距離を求めれば良い。木構造なのでループが存在しないからBFS,DFSで求められる。
念のためにグラフは無向辺にしておきましょう。

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<complex>

using namespace std;

#define reE(i,a,b) for(auto (i)=(a);(i)<=(b);(i)++)
#define rE(i,b) reE(i,0,b)
#define reT(i,a,b) for(auto (i)=(a);(i)<(b);(i)++)
#define rT(i,b) reT(i,0,b)
#define LL long long

class PowerOutage {
	private:
	LL adj[51][51];
	int bfs(){
		LL res=0;
		queue<int> q;
		LL dist[51];
		rE(i,50)dist[i]=-1;
		dist[0]=0;q.push(0);
		while(q.empty()==false){
			int v=q.front();q.pop();
			rE(i,50)if(adj[v][i]>0&&dist[i]<0){
				dist[i]=dist[v]+adj[v][i];
				q.push(i);
			}
		}
		rE(i,50)res=max(res,dist[i]);
		return res;
	}
	public: int estimateTimeOut(vector<int> fromJunction, vector<int> toJunction, vector<int> ductLength) {
		LL res=0;
		rE(i,50)rE(j,50)adj[i][j]=0;
		rT(i,(int)fromJunction.size()){
			adj[fromJunction[i]][toJunction[i]]=ductLength[i];
			adj[toJunction[i]][fromJunction[i]]=ductLength[i];
			res+=2*ductLength[i];
		}

		return (res-bfs());
	}

};