ARC101 C問題 Candles

問題

C - Candles

解法

自分はひたすらどツボにハマった問題。
初期位置が与えられる配列のindexのどの箇所になるか考え、
そこからプラス・マイナスどちらに行くときも折り返すのは最悪1回のみと考えられる。

そして、折り返す位置さえ決まれば、どのろうそくにアクセスするのかは計算可能。
そのため、折り返す場合、折り返さない場合で場合分けを行い
折り返さない場合:初期位置から一番遠い箇所へのアクセスにかかる時間
折り返す場合:(初期位置から折り返す位置までのアクセスにかかる時間) +折り返した位置から最後にアクセスする場所までにかかる時間
を全探索し、出力する。

アクセスにかかる時間は単純にスタート位置からゴール位置までの距離のため、O(1)で計算できる。
決して間の位置までにかかるアクセス時間を足していくなんてことはしてはいけない。(自分はこれをfor文で回すような実装を最初に行いO(n)になりTLEで死んだ)

#include <bits/stdc++.h>
 
using namespace std;
 
#define DEBUG 0
#define lli long long int
#define REP(i,n) for(int i=0;i<n;i++)
#define VIN(VECTOR,n)\
REP(CNT,n){\
	lli TMP;\
	cin>>TMP;\
	VECTOR.push_back(TMP);\
}
 
lli zettai(lli a){
	if(a>=0)return a;
	else return -a;
}
 
lli minAB(lli a,lli b){
	if(a>=b)return b;
	else return a;
}
 
int main(){
 
	lli n,k;
	lli *x;
 
	cin>>n>>k;
	x = new lli[n];
	REP(i,n){
		cin>>x[i];
	}
	lli ans = 223372036854775807;
	for(lli i=0;i<n-k+1;i++){
		lli now;
		if(x[i]<0 && x[i+k-1] < 0){//両方マイナスパターン
			now = zettai(x[i]);
		}
		else if(x[i]<0 && x[i+k-1]>=0){//片方マイナス片方プラスパターン
			now = minAB(zettai(2*x[i])+zettai(x[i+k-1]),zettai(x[i])+zettai(2*x[i+k-1]));
		}
		else{//両方プラスパターン
			now = zettai(x[i+k-1]);
		}
		if(ans>=now)ans=now;
	}
	cout<<ans<<endl;
 
	return 0;
 
}
 

ABC105 C問題+D問題

C問題 (-2)進数

C - Base -2 Number


10進数を2進数に変換する方法(素因数分解)の流れで解く。
ただし、(-2)で割らないといけないため、(-2)で割り切れない場合、
1. もともとの数が負の数の場合、次に割る数を+1補正する
例) (-9) ÷ (-2) = 5 あまり 1 ( (-9)÷(-2)は本来4だが、4にするとあまりの数が-1になってしまうので、あまりを正の数になるように補正する)
2. もともとの数が正の数の場合は次に割る数の補正は行わない。
例 9 ÷ (-2) = (-4) あまり 1

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <set>

#define DEBUG 0

#define lli long long int
#define REP(i,n) for(int i=0;i<n;i++)

using namespace std;

string calc(lli num){
	string str="";

	while(num!=0){
		if(DEBUG)cout<<"num="<<num<<endl;
		lli flag=0;
		if(num < 0){
			if(num%2==0){
				num /= (-2);
			}
			else{
				flag = 1;
				num /= (-2);
				num += 1;
			}
		}
		else{
			flag = num % 2;
			num /= (-2);
		}
		if(flag){
			str = "1"+str;
		}
		else{
			str = "0"+str;
		}
	}
	if(str==""){
		str = "0";
	}
	return str;
}


int main(){

	lli num;
	cin>>num;

	cout<<calc(num)<<endl;

	return 0;
}

D問題

D - Candy Distribution

この問題は自力では解けなかった。

基本的には解説通り実装する。
B mod M の個数がx個数のとき、加算スべき数は x(x-1)/2であることと、
(i,r)=(0,0)の時のmod M を予め加算しておくことに気をつける。

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <set>

#define DEBUG 0

#define lli long long int
#define REP(i,n) for(int i=0;i<n;i++)

using namespace std;

int main(){

	lli n,m;
	cin>>n>>m;
	vector<lli> a;
	map<lli,lli> b;
	lli sum = 0;
	b[0]++;
	for(lli i=0;i<n;i++){
		lli tmp;
		cin>>tmp;
		a.push_back(tmp);
		sum += tmp;

		b[sum%m]++;
	}

	lli ans = 0;

	for(auto itr = b.begin();itr != b.end(); itr++){
		lli cnt = itr->second;
		ans += ((cnt -1)*(cnt)/2);
	}

	cout<<ans<<endl;

	return 0;
}

ARC073 B問題

D - Equals

与えられるデータセットにて、どことどこが交換できるかについて教えてもらえる。
その交換できる木の中で目的の場所まで移動できればOK
木の作り方は幅優先探索を選択


#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>

using namespace std;

int main(){

	int n,m;
	vector<int> p;
	map<int,vector<int>> xy;
	char flag[100010];

	for(int i=0;i<100010;i++){
		flag[i]=0;
	}

	cin>>n>>m;
	for(int i=0;i<n;i++){
		int tmp;
		cin>>tmp;
		p.push_back(tmp-1);
	}
	for(int i=0;i<m;i++){
		int tmpX,tmpY;
		cin>>tmpX>>tmpY;
		xy[tmpX-1].push_back(tmpY-1);
		xy[tmpY-1].push_back(tmpX-1);
	}

	/*学習実施、どことどこが繋がってるのか?*/
	
	int ans=0;
	for(int i=0;i<n;i++){
		if(flag[i]==1)continue;
		queue<int> q;
		q.push(i);
		set<int> touch;
		touch.insert(i);
		flag[i]=1;
		while(q.size()!=0){
			int now = q.front();
			q.pop();
			if(xy[now].size()==0)continue;
			int size = xy[now].size();
			for(int j=0;j<size;j++){
				int next = xy[now].at(j);
				if(flag[next]==0){
					touch.insert(next);
					flag[next]=1;
					q.push(next);
				}
			}
		}
		for(auto itr = touch.begin(); itr != touch.end();itr++){
			int targetPos = p[*itr];
			if(touch.count(targetPos)==1){
				ans++;
			}
		}
	}
	cout<<ans<<endl;
	return 0;

}

2018_0502_0505 種子島+桜島旅行

ということで、GW後半の5月2日から5月5日、3泊4日にて種子島鹿児島市周辺の観光したのでその写真をまとめたいと思います。

日程

1日目:移動日(成田→種子島
2日目:種子島
3日目:種子島
4日目:桜島鹿児島市街観光+移動日(鹿児島空港→成田)

なんで種子島に?

今回、大学時代の友人達と一緒に旅行に行ってきました。
この一緒に行く友人達が昔から様々な場所に車で旅行しており、国内で有名なところはだいたい回ったことがあるとのことでした。
そこで、関東出発で車だとなかなか行けない箇所が候補にあがり、最終的に種子島に決定しました。

1日目(5月2日):移動日

鹿児島までは飛行機で行くことにしました。
飛行機のチケットを取るタイミングが少し遅かったため、羽田からの便は価格がなかなか高い物が多かったため、
成田から出発することにしました。

だいたい成田空港から鹿児島空港まで飛行機で約1時間45分近くで着きました。
到着した後、鹿児島空港から鹿児島中央駅までバスで40分
鹿児島中央駅から鹿児島港までバスで15分くらいでまず港まで向かいました。
その後、鹿児島港から、高速船を使い、1時間半近く乗ることで種子島にようやく着くことができました。

f:id:soto_ohuton:20180506175426j:plain
高速船のチケット

この日はすでに移動だけで夕方になってしまったので、レンタカー回収とホテルにチェックインだけし、
その後西之表市の中心あたりの居酒屋で酔っぱらいマンになって一日を終えました。

f:id:soto_ohuton:20180506175344j:plain
西之表市の居酒屋で楽しんでたときの写真

2日目(5月3日):種子島

この日はレンタカーを使っていろいろ見て回る一日でした。
主な目的地は種子島南に位置する種子島宇宙センターです。

www.jaxa.jp

自分たちが泊まっていたのは西之表市、種子島の北の方だったため、北から南へ約50km移動するような形です。
その途中途中で良さげなところがあったら寄っていく形で観光してました。

西之表市~種子島宇宙センター

f:id:soto_ohuton:20180506203514j:plain
車からの風景、海沿いを車で移動するのが気持ちいい


f:id:soto_ohuton:20180506203621j:plain
道端のお花、今年も夏が近づいてきた感じがします。


f:id:soto_ohuton:20180506204641j:plain
f:id:soto_ohuton:20180506203813j:plain
秒速5センチメートルの聖地にもなってる種子島中央高等学校、1日目夜に友人と秒速を見てから来たためなかなかの気分にさせられます。。。
高校生だったときが僕にもありました。。。


f:id:soto_ohuton:20180506204332j:plainf:id:soto_ohuton:20180506204352j:plainf:id:soto_ohuton:20180506204407j:plainf:id:soto_ohuton:20180506204434j:plain
熊野海岸、種子島上陸初の海岸でスケールの広さに感動して写真を撮りまくってました。

種子島宇宙センター

f:id:soto_ohuton:20180506204759j:plain
ということで種子島宇宙センターに着きました。


f:id:soto_ohuton:20180506204842j:plainf:id:soto_ohuton:20180506204859j:plain
ロケットの原寸大模型、90mくらいだった気がしますがとても大きいです。


f:id:soto_ohuton:20180506205022j:plain
ここは宇宙センターから少し離れたロケットの丘と呼ばれる場所です。
実際にロケットを打ち上げるときはここで見学する方が多いとのことです。


f:id:soto_ohuton:20180506205209j:plain
ロケットが打ち上げられるときはこの赤い塔の真ん中に設置され、そこからあげられるようです。

種子島宇宙センター見学後

種子島宇宙センターを一通り見て回った後、ご飯を食べ、種子島の南端にある門倉岬へ行きました。

f:id:soto_ohuton:20180506205529j:plain
種子島、火縄銃伝来の地ということでその像がありました。

f:id:soto_ohuton:20180506205757j:plain
どこにでもある(?)おみくじ、100円入れてみたところ、何も出ずに吸い込まれてしまいました。。(中のおみくじが尽きてしまったのでしょうか。。)

f:id:soto_ohuton:20180506205927j:plain
幸せの鐘と書いてありました。ひたすら友人が鳴らしまくってました。

その後、日の入りを見たいということで、西の方の海岸へ移動し、夕日を見てました。

f:id:soto_ohuton:20180506210158j:plainf:id:soto_ohuton:20180506210311j:plainf:id:soto_ohuton:20180506210326j:plainf:id:soto_ohuton:20180506210418j:plainf:id:soto_ohuton:20180506210440j:plain
カメラの設定をいろいろ変えて太陽の形をなんとか捉えられる感じになりました、勉強しないとなあ。。。

こんな感じで2日目を終えました。

3日目(5月4日)

3日目は種子島のまだ回ってない細かいスポットを回っていきました。

種子島空港

種子島空港 (初代) - Wikipedia

2006年に現在の種子島空港ができ、廃止された空港です。
f:id:soto_ohuton:20180506211117j:plain
f:id:soto_ohuton:20180506211127j:plain
こちらも秒速5センチメートルの聖地となってます。

中山海岸

www.furusato-tanegashima.net


ここも秒速の聖地です。登場人物のかなえちゃんがサーフィンしてる場所ですね。

f:id:soto_ohuton:20180506211517j:plainf:id:soto_ohuton:20180506211531j:plain

なんにせよ海が綺麗すぎる

浦田海水浴場


www.kagoshima-kankou.com


日本水浴場88選の1つとのことです。ここでは地元の人達が5月ですが既に海に入って遊んでいました。

f:id:soto_ohuton:20180506212416j:plainf:id:soto_ohuton:20180506212425j:plainf:id:soto_ohuton:20180506212454j:plainf:id:soto_ohuton:20180506212520j:plain

あまりにも海と砂浜が綺麗すぎて友人たちと海に入ってしまいました!
海に入ったの覚えてる限りで15年ぶりとかだったので本当に久しぶりでした。
気持ちよすぎたのでまた入りたい。。。

そして3日目はまた高速船に乗り鹿児島港に戻って終えました。
3日目、宿を取りそこねており、ネカフェで夜を過ごすことになってしまいました。。
皆さんは旅行は予め宿を取るようにしましょう。。。

4日目(5月5日)

この日は余った時間を使い桜島観光をして、霧島の温泉に入り帰りました。
桜島 - Wikipedia
霧島市 - Wikipedia

桜島

行き方としては、鹿児島港からフェリーが出てるのでそれに乗ります。
車でフェリーに乗る人達も多かったです。


f:id:soto_ohuton:20180506213141j:plain
桜島を撮りました。めっちゃもくもくしてます・・・


f:id:soto_ohuton:20180506213216j:plain
フェリーに乗って鹿児島港の方を撮った写真です。ミニチュア感がなんかすごい・・・


f:id:soto_ohuton:20180506213318j:plain
桜島上陸後です。ここのレンタカーを借りて島を一周しました。


f:id:soto_ohuton:20180506213531j:plain
長渕剛さんが桜島でライブをやった時を記念した像だそうです。最初見た時はなんなのか全くわかりませんでした。。。


f:id:soto_ohuton:20180506213628j:plain
桜島火口付近?人為的に何かを設置してるものがあるように見えます。


f:id:soto_ohuton:20180506213717j:plain
桜島の高いところから鹿児島市を撮りました。街を囲うように森があるのがわかります。


この他にも噴火の際の影響で埋まってしまった鳥居など見てきました。
種子島の観光に比べて、火山の存在を感じるスポットになってます。


この後霧島へ行き、目的の霧島ホテルにバスで向かい、温泉に入った後、鹿児島空港から成田空港へ移動し帰宅しました。
自分はあまり旅行はしない方なのですが、今回ここまで楽しめるとは思いませんでした。
種子島、最高の夏を感じれる場所がとても多く、今調べてみると行ってないスポットがおすすめされてたりと思ったより観光できるところは多そうなので皆さんもぜひ行ってみることをおすすめします!
自分ももう1回は絶対にいきたいと思ってます。(   ´ω`  )bb

ABC011 D問題 大ジャンプ(部分点)

部分点自分の解法

1<=N<=30ということで、N個のうち、x方向へのジャンプの回数がi回とすると、y方向へのジャンプの回数がN-i回
そのx方向へのジャンプ回数がi回のうち、プラス方向がj回、マイナス方向がi-j回として、nCrの組み合わせの計算をひたすら実施していく。
nCrの求め方はパスカルの三角形を用いて予め必要な分計算しておく。

#include <iostream>

#define lli long long int

using namespace std;

lli nCr[100][100];

void calc(){
	nCr[0][0]=1;
	nCr[1][0]=1;
	nCr[1][1]=1;
	for(int i=2;i<100;i++){
		for(int j=0;j<=i;j++){
			if(j==0 || j==i)nCr[i][j]=1;
			else nCr[i][j] = nCr[i-1][j-1]+nCr[i-1][j];
		}
	}
}

int main(){

	lli n,d;
	lli x,y;
	lli ans=0,sum=0;
	lli nowX,nowY;
	cin>>n>>d;
	cin>>x>>y;

	calc();

	//n個をどのようにxとyに分けるか
	for(int i=0;i<=n;i++){
		lli localX=0,localY=0;
		lli ansSumX=0,ansSumY=0;
		lli rate=nCr[n][i];
		//xはi個,その中で+方向がj個
		for(int j=0;j<=i;j++){
			nowX = d*j - d*(i-j);
			localX += nCr[i][j];
			if(nowX == x){
				ansSumX=nCr[i][j];
			}
		}
		for(int j=0;j<=(n-i);j++){
			nowY = d*j - d*(n-i-j);
			localY+=nCr[n-i][j];
			if(nowY == y){
				ansSumY=nCr[n-i][j];
			}
		}
		ans += rate*(ansSumX)*(ansSumY);
		sum += rate*(localX)*(localY);
	}
	printf("%0.16f\n",(double)ans/sum);

	return 0;
}

ABC010 D問題 浮気予防 (部分点)

問題:
D - 浮気予防

解答:

www.slideshare.net


グラフを作成し、ある点からある点に行くまでに通る辺をどれくらいカットするか、もしくはある点にたどり着いた時コストを1増やす場合、この2つの操作をどれだけ行うかを求める。

まずは部分点のみ、人間関係の数が12個でこれをそれぞれカットするかしないかを求める→2^12→4096通り
全探索で計算が可能なため、
1.カットする人間関係をどれにするか決定
2.幅優先探索
3.仮に目的地にたどり着いてしまった場合、1で実施した数をインクリメントする。
1から3を繰り返し、min(カットした人間関係+目的地にたどり着いた数)が解答となる。

#include <iostream>
#include <vector>
#include <queue>
#include <map>

using namespace std;

#define lli long long int
#define REP(i,n) for(int i=0;i<n;i++)

int min(int a,int b){
	if(a>=b){return b;}
	else{return a;}
}

int main(){

	int n,g,e;
	int tmp1,tmp2;
	vector<int> p;
	vector<int> a;
	vector<int> b;
	queue<int>  q;

	int *flag;
	int ans=0xFFFFF;

	cin>>n>>g>>e;

	flag = new int[120];

	/*今回e>12の問題は対象としない*/
	if(e>12){
		return 0;
	}

	REP(i,g){
		cin>>tmp1;
		p.push_back(tmp1);
	}

	REP(i,e){
		cin>>tmp1>>tmp2;
		a.push_back(tmp1);
		b.push_back(tmp2);
	}

	/*ビットによる全探索を実施*/

	int bitNum;
	for(int i=0;i<(1<<e+1);i++){ //2^(e+1)回計算を実施する。
		bitNum=0;
		map< int , vector<int> > x;	
		REP(j,e){
			if( (i>>j)&0x1 )continue; //今回カット対象とする人間関係があったら幅優先探索には使用しない。
			x[a.at(j)].push_back(b.at(j));
			x[b.at(j)].push_back(a.at(j));
		}
		//人間関係をカットした回数を数えておく
		REP(j,20){
			bitNum += (i>>j)&0x1;
		}

		/*ここから幅優先探査*/
		/*目的の女の子に到達してしまった場合はそいつをログインさせない方針で幅優先探索を実施*/

		q.push(0);//スタートは高橋くんから

		REP(i,32){
			flag[i]=0;
		}
		flag[0]=1;


		while(q.size()){
			int top = q.front();
			q.pop();
			if(DEBUG)cout<<top<<endl;
			/*もしマークしてる女の子が出てきたらそいつをログインさせなくする。*/
			REP(j,g){
				if(top == p.at(j)){
					bitNum++;
				}
			}
			REP(j,x[top].size()){
				if(flag[x[top].at(j)]==0){
					q.push(x[top].at(j));
					flag[x[top].at(j)]=1;
				}
			}
		}

		//解答はカットした人間関係の数の最小値
		ans = min(ans,bitNum);
	}

	cout<<ans<<endl;

	return 0;
}

ARC095 A問題 B問題

今日久しぶりにARCに出たので解法をメモしておきます。

ARC095 A問題

C - Many Medians
与えられた数列のうち、1つ抜いたときの中央値はいくつになるか計算する問題。
与えられた数列をまず昇順にソートし、中央値候補を2つ出す。
その後、抜く数字が中央値候補の1つ目以下であれば、2つ目が答え。
それ以外であれば、1つ目が解答になる。

#include <iostream>
#include <vector>
#include <algorithm>

#define lli long long int

using namespace std;

int main(){

	lli n;
	vector<lli> x;
	vector<lli> y;

	cin>>n;

	for(int i=0;i<n;i++){
		lli tmp;
		cin>>tmp;
		x.push_back(tmp);
		y.push_back(tmp);
	}
	sort(x.begin(),x.end());

	lli a = x.at(n/2-1);
	lli b = x.at(n/2);

	for(int i=0;i<n;i++){
		lli now = y.at(i);
		if(now<=a){
			cout<<b<<endl;
		}
		else{
			cout<<a<<endl;
		}
	}

	return 0;

}

ARC095 B問題

D - Binomial Coefficients
全列挙、もしくは計算をしようとしても与えられる値がでかすぎて計算が出来ない。(10^9!なんてしたらもう大変なことに。。)
組み合わせの計算方法として、n個の中からr個を選ぶ場合、rがn/2に近ければ近いほど値が大きくなることを利用する。
また、rが固定されていたとしても、nが大きければ大きいほど、組み合わせの数も大きくなることより、
nCrのnは与えられた数列の最大値、rは与えられた数列の中で最もn/2に近い値を選択する。

#include <iostream>
#include <vector>
#include <algorithm>

#define lli long long int

lli abs2(lli a){
	if(a>=0)return a;
	else return -a;
}

using namespace std;

int main(){

	int n;
	vector<lli> a;

	cin>>n;

	for(int i=0;i<n;i++){
		lli tmp;
		cin>>tmp;
		a.push_back(tmp);
	}

	sort(a.begin(),a.end());

	lli ans=0;
	lli max = a.at(n-1);
	lli center = max/2;
	for(int i=0;i<n;i++){
		if( abs2(center-ans) >= abs2(center-a.at(i))){
			if(a.at(i) != max){
				ans = a.at(i);
			}
		}
	}

	cout<<max<<" "<<ans<<endl;

	return 0;
}