ABC126 D問題 Even Relation

完全に決め打ちで解きました。。。

問題

atcoder.jp

解説

始点を適当に決めて、そこからの距離を幅優先探索を用いて、全点計算する。
始点から任意の点までの距離が、偶数だった場合、白で塗り、奇数だった場合黒で塗ればAC(もちろん逆の色でもいい)
一つの点からの距離が偶数奇数で振り分けていいとする考え方としては2通りある
始点をA,任意の点を適当にB,Cとする。
1. Aを経由して、BとCをつなぐ場合
→ AtoBが偶数、AtoCが偶数なら BtoCはAtoB + AtoC = 偶数 + 偶数なので偶数

2. Aを経由せず、別の点(D)を経由する場合
→AtoBが偶数、 AtoCが偶数のとき、
AtoDが奇数の場合はBtoDが奇数、CtoDが奇数 、つまり BtoC = BtoD + CtoD =奇数+奇数で偶数
AtoDが偶数の場合はBtoDも偶数、CtoDも偶数、つまり BtoC = BtoD + CtoD =奇数+奇数で偶数

このため、一つの点から偶数のもの同士のグループと奇数のもの同士のグループが組めることがわかる。

#include <bits/stdc++.h>
 
using namespace std;
 
#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
#define MOD 1000000007
 
signed main(){
 
	lli n;
	map<pair<lli,lli>,lli> d;
	map<lli,vector<lli>> m;
 
	cin>>n;
	for(lli i=0;i<n-1;i++){
		lli u,b,w;
		cin>>u>>b>>w;
		u--,b--;
		d[make_pair(u,b)] = w;
		d[make_pair(b,u)] = w;
		m[u].push_back(b);
		m[b].push_back(u);
	}
 
	lli ds[100010];
	for(lli i=0;i<100010;i++)ds[i]=-1;
 
	ds[0]=0;
	/*始点0から幅優先探索する*/
	queue<lli> q;
	q.push(0);
	while(q.size()!=0){
		lli now = q.front();
		q.pop();
		lli nowDs = ds[now];
		for(lli i=0;i<m[now].size();i++){
			lli e = m[now].at(i);
			if(DEBUG)cout<<"e="<<e<<endl;
			if(ds[e] == -1){
				ds[e] = nowDs + d[make_pair(now,e)];
				q.push(e);
			}
		}
	}
	
	for(lli i=0;i<n;i++){
		if(ds[i]%2==0)cout<<0<<endl;
		else cout<<1<<endl;
	}
 
 
	return 0;
}

ABC126 C問題

かっこいい実装最初しようとしたせいで大変なことになりました。。。

問題

atcoder.jp

解説

1つ1つ数字を見て、その数字を何回2倍すればよいかを計算する。
答えは sum( (1/2)^目標2乗回数)/n )

#include <bits/stdc++.h>

using namespace std;

#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
#define MOD 1000000007

signed main(){

	lli n,k;

	cin>>n>>k;

	/*コインで出た目がaのとき、何回2乗すればいいか?*/
	/*逆にkから考えて、2で割っていってその数より大きければ1回で済む*/
	/*まず、k以上出たらそれで終了なのでそれが正解*/
	vector<double> a(n+1);
	a[0]=0;
	lli base = 1;
	double ans = 0;
	for(lli i=n;i>0;i--){
		if(i*base < k){
			i++;
			base*=2;
		}
		else{
			ans += (double)(1)/(double)(n*base);
		}
	}
	printf("%.013f\n",ans);
	return 0;
}

ABC126 B問題 YYMM or MMYY

場合分けがめっちゃ難しい。。。

問題

atcoder.jp

解説

YYにはどのような値でも成り立つ。
そのため、例外が存在する(0月と13(以上)月)MM月のほうから検討する。
片方がMM確定 → YYMM or MMYY
両方ともMMではない →NA
両方ともMMになれる → AMBIGUOUSとなる

#include <bits/stdc++.h>

using namespace std;

#define lli unsigned long long int
signed main(){

	string str;
	cin>>str;

	lli mae = (str.at(0)-'0')*10 + (str.at(1)-'0');
	lli usiro = (str.at(2)-'0')*10 + (str.at(3)-'0');

	/*maeがMMの可能性をなくす*/
	if(mae == 0 || mae > 12){
		/*usiroもMMではないとありえない*/
		if(usiro == 0 || usiro > 12)cout<<"NA"<<endl;
		else {/*usrioがMMならYYMM*/
			cout<<"YYMM"<<endl;
		}
	}
	else{/*maeがMMの可能性がある*/
		/*usiroがNNではないならMMYY*/
		if(usiro == 0 || usiro>12)cout<<"MMYY"<<endl;
		else cout<<"AMBIGUOUS"<<endl;
	}
	return 0;
}

ABC126 A問題 Changing a Character

問題

atcoder.jp

解説

与えられた文字列から指定の箇所にて'A'を引いて、'a'を足すことで文字の大小変換が可能

応用例としては、文字列を1桁の数字にすることなどが可能('0'で引けばいい)

#include <bits/stdc++.h>
using namespace std;
#define lli unsigned long long int

signed main(){

	lli n,k;
	string s;
	cin>>n>>k>>s;

	s[k-1] = s[k-1] -'A' + 'a';

	cout<<s<<endl;

	return 0;
}

ABC042 D問題 いろはちゃんとマス目

問題

atcoder.jp

解説

高校数学にありそうな問題
一部が通れない場合の経路数を求める。
制限がない時の場合の数は組み合わせの計算で行えるため、
高速計算のアルゴリズムを下記ページより持ってくる(いつもお世話になっております。。。)
drken1215.hatenablog.com

一部が通れないため、一発では計算できない。
そのため、必ず通る個所を足し合わせる形で解くことにする。
f:id:soto_ohuton:20190516233038p:plain
このように、左下の箇所が通れないことが分かっている場合、
SからGまでに行く経路はかならず、A,B,C,Dを通ることがわかる。
そのため、S->A->Gの経路数 + S->B->Gの経路数 + S->C->Gの経路数 + S->D->Gの経路数を求めることで解を出せる。

また、S->B->Gの経路すうは、S->Bの経路数 × B->Gの経路数で出せるので、下図のように分解することで、組み合わせの計算を用いて解ける。

f:id:soto_ohuton:20190516233443p:plain

ソース

組み合わせの箇所はコピペでなんとかさせてもらってます。。

#include <iostream>
using namespace std;

const int MAX = 510000;
const int MOD = 1000000007;

#define lli long long 
#define DEBUG 0

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
    // 前処理
    COMinit();

    lli h,w;
    lli a,b;
    cin>>h>>w>>a>>b;
    h--;
    w--;

    lli ans = 0;
    for(lli i=0;i<=h-a;i++){
    	ans += (COM(b+i-1,i) * COM(h-i+w-b,h-i)) % MOD;
    }
    
    cout<<ans%MOD<<endl;
}

ABC074 ARC083 D問題 Restoring Road Network

問題

atcoder.jp

解説

問題文章を読み解くのが難しいが題意を満たす場合下記のように読み取った。
1.与えられる表Aに記載されているのはすべて最短経路である。
2.求めるのは表Aを満たす必要最低限の道の和(余計な道を置かない)

条件1は表Aをワーシャルフロイト法を行うことで更新されなければOK
更新された場合、最短経路ではない道が表Aに記載されているからである。

条件2は同じようにワーシャルフロイト法を行うが、
a[i][j] == a[i][k] + a[k][j]のように、どこかの街を経由するのが最短ということがわかった道は除去が可能である(というより経由しているのが正しい姿)
上記の除去を行って最後まで残った道の長さの和が求める答え

#include <bits/stdc++.h>

using namespace std;

#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)

signed main(){

	lli n;
	cin>>n;

	lli a[310][310];
	REP(i,0,n)REP(j,0,n)cin>>a[i][j];

	/* ワーシャルフロイトやって、1回でも変わったらアウト*/
	REP(k,0,n)REP(i,0,n)REP(j,0,n){
		if(a[i][j] > a[i][k]+a[k][j]){
			cout<<-1<<endl;
			return 0;
		}
	}

	/*変わらなかった場合、もう1度ワーシャルフロイトを行う*/
	/*そして、a[i][j] == a[i][k] + a[k][j]を満たす要素のa[i][j]を取り除く*/
	REP(k,0,n)REP(i,0,n)REP(j,0,n){
		if(i==j || j==k || k==i)continue;
		/*条件2を満たしたら除去した印をつける*/
		if(a[i][j] == a[i][k]+a[k][j]){
			a[i][j] = INF;
		}
	}


	lli ans=0;
	REP(i,0,n){
		REP(j,0,n){
			/*除去した道でなければ足し合わせていく*/
			if(a[i][j] != INF)ans += a[i][j];
		}
	}

	/*同じ個所を2重カウントしているので最後に割って出力*/
	cout<<ans/2<<endl;

	return 0;
}

ABC034 D問題 食塩水

問題

atcoder.jp

解説

無事DPしようとしてドツボにはまり死亡した問題

解説を見て、平均最大化の問題→二分探索ということを理解。
目標の濃度を決定し、その濃度を達成できるかどうかの判定関数を準備する。
達成できる場合はさらなる濃い濃度も達成できるか確認。
達成できない場合は薄い濃度でなら達成できるかを確認。
これを100回程度回すことで、とることができる最大平均値に収束する。

#include <bits/stdc++.h>

using namespace std;

#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define MOD 1000000007
#define INF (1LL<<50)

const int MAX_N = 200010;
lli n,k;
lli w[MAX_N];
lli p[MAX_N];

lli calc(double pp){
	vector<double> v;
	REP(i,0,n)v.push_back( (p[i]-pp) *w[i]);
	sort(v.rbegin(),v.rend());

	double m=0;
	REP(i,0,k)m+=v[i];
	return m>=0;
}

signed main(){

	cin>>n>>k;
	REP(i,0,n)cin>>w[i]>>p[i];

	double large=1000;
	double small=-1;
	double middle;
	lli cnt=0;
	for(cnt=0;cnt<200;cnt++){
		middle = (large+small)/2.0;
		if(calc(middle)) small=middle;
		else large = middle;
	}

	printf("%.9f\n",large);

	return 0;
}