問題概要

辺にコストがある木が与えられる。
各頂点から最も遠い点を求めよ。

考察

木の直径を用いて解を求めることを考えます。

f:id:noy72:20180111095259p:plain:w500

まず、最長パス $p_0, p_1, p_2, ... , p_k$ を求めます。
赤い部分は最長パスに含まれることを表しています。

すると、最長パスに含まれる頂点と、最長パスに含まれない部分木に分けることができます。

最長パスに含まれる頂点 $p_i$ の最遠点

$p_0$ から $p_i$ までの距離と、 $p_i$ から $p_k$ の距離を比較すれば良いです。

部分木に含まれる頂点の最遠点

ある部分木 $s_{p_i}$ に含まれる全ての頂点の最遠点は、 $p_i$ の最遠点と一致します。
一致しないと仮定すると、最長パスであることと矛盾します。

最長パスの一部を含まないようなパスよりも、含むパスの方が必ず長くなる。
最長パスの一部を経由して別の部分木に入るようなパスよりも、入らないパスの方が必ず長くなる。

最遠点が複数ある場合は、頂点番号が小さいものを出力しなければいけないので、そこだけ注意します。

コード

※最長パスが複数ある場合を考えていないのにACしたコード

bfsで最長パスを求める
最長パスに含まれている頂点の最遠点を求める
部分木を求める
部分技に含まれる頂点の解を求める
出力

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
using namespace std;

#define int long long
const int INF = (1LL << 60);

const int MAX_V = 100005;

class Edge{
	public:
		int to, dis;
		Edge(){}
		Edge(int to, int dis): to(to), dis(dis)  {}
};

vector<Edge> g[MAX_V];
int dis[MAX_V];

vector<int> bfs(int s, int n, bool f){
	queue<int> q;

	rep(i,n) dis[i] = INF;
	dis[s] = 0;
	q.push(s);

	vector<int> pre(n,-1);
	while(not q.empty()){
		int d = q.front(); q.pop();

		rep(i,g[d].size()){
			Edge e = g[d][i];
			if(dis[e.to] == INF){
				pre[e.to] = d;
				dis[e.to] = dis[d] + e.dis;
				q.push(e.to);
			}
		}
	}

	int maxi = -1;
	rep(i,n){
		if(dis[i] == INF) continue;
		if(maxi == -1) maxi = i;
		if(dis[maxi] < dis[i]){
			maxi = i;
		}
	}
	if(f) return vector<int>() = {maxi};

	vector<int> path = {maxi};
	while(pre[maxi] != -1){
		maxi = pre[maxi];
		path.emplace_back(maxi);
	}
	reverse(all(path));
	return path;
}

//---------------------------- union-find
int par[MAX_V]; //親
int depth[MAX_V];//木の深さ

void init(int n){
	rep(i,n){
		par[i] = i;
		depth[i] = 0;
	}
}

int find(int x){
	if(par[x] == x){
		return x;
	}else {
		return par[x] = find(par[x]);
	}
}

void unite(int x, int y){
	x = find(x);
	y = find(y);
	if(x == y) return;

	if(depth[x] < depth[y]){
		par[x] = y;
	}else{
		par[y] = x;
		if(depth[x] == depth[y]) depth[x]++;
	}
}

bool same(int x, int y){
	return find(x) == find(y);
}
//----------------------------

signed main(){
	int n;
	cin >> n;

	vector<pair<int, int>> e(n - 1);
	rep(i,n - 1){
		int a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		e[i] = make_pair(a,b);
		g[a].emplace_back(b,c);
		g[b].emplace_back(a,c);
	}

	vector<int> path = bfs(bfs(0, n, 1).front(), n, 0); //最長パスを求める
	vector<bool> used(n,0);
	vector<int> ans(n);
	for(auto i : path){
		used[i] = true;
		if(dis[i] > dis[path.back()] - dis[i]){
			ans[i] = path.front();
		}else if(dis[i] < dis[path.back()] - dis[i]){
			ans[i] = path.back();
		}else{
			ans[i] = min(path.front(), path.back());
		}
	}

	init(n);
	rep(i,n - 1){ //部分木を求める
		if(used[e[i].first] and used[e[i].second]) continue;
		unite(e[i].first, e[i].second);
	}

	vector<int> par(n);
	for(auto i : path){
		par[find(i)] = ans[i];
	}
	rep(i,n){
		if(used[i]) continue;
		ans[i] = par[find(i)];
	}

	for(auto& i : ans){
		cout << i + 1 << endl;
	}
}

2017-12-30

ARC 088 E - Papple Sort

競技プログラミング

Indeed study session に競プロ的な愚直解コードを投げてしまった話

参加記

Indeed study session に参加して思ったこと。

Indeed study sessionとは

提出したコードをレビューしてもらえる勉強会。
書いたコードについて色々言ってもらえる。

ちなみに２次募集の締め切りが 12/20 です。

学んだこと

競プロの気持ちでやってはダメだよ

競プロをやる気持ちで書いたコードを投げてはいけない（それはそう）。

無駄な部分は減らそう

AC or TLE で考えると無意味な高速化もちゃんとやらないといけない。

競プロ的に丁寧に書いても読めない

競プロの丁寧は、読めないを読めるようにはしない。

includeを減らす

いらない部分は消す。

参照渡しを使う

for(auto &i : data) とか。
競プロ的にはあまり変わらなくても、無駄は減らす。

using namespace stdはダメ

それはそう。

感想

コードレビューに使うコードは90分で書く必要がある。
簡単に言えば、一問だけの90分コンテスト。
解法が思いつかず、時間ギリギリに愚直解で書いたのが悪かった。
自明に高速化できる部分が多々あった。それでもTLEにはかわりないが。

このような形式であれば、さっさと見切りをつけて部分点解法を書く気持ちで取り掛かった方が良いかもしれない。
アルゴリズムの部分はほぼ触れられていないので、考える部分を間違えた感がある（それはそう）。

コードをきっちりかかないと、それだけレビューの内容も薄くなってしまう。
つめるところはきっちりとつめよう。

全体的に”それはそう”という感想しか出てこない。

2017-11-26

dein.vimとdeopleteをmacにインストールする。

開発環境

環境
dein.vim
- インストール
deoplete.nvim
- インストール
参考

環境

mac
vim 8.0.1300

暗黒のVimmer（見習い）

dein.vim

github.com

dein.vimは暗黒のプラグインマネージャです。
元々neobundleを使っていましたが、後継が1.5年前に出ているのでさすがに乗り換えました。

インストール

githubのQuick start、dein.vimのインストール自体にハマってしまったメモ - Qiitaを参照。

１、Run below script.

$ curl https://raw.githubusercontent.com/Shougo/dein.vim/master/bin/installer.sh > installer.sh
$ sh ./installer.sh {specify the installation directory}

これを実行すると、最後に「今表示したscriptをvimrcに貼り付けてね（意訳）」と表示されるので見逃さずに貼り付けましょう（1敗）。

" If you want to install not installed plugins on startup.
if dein#check_install()
  call dein#install()
endif

この部分のコメントアウトを外して起動時にインストールするようにします。

You can specify revision/branch/tag.
call dein#add('Shougo/deol.nvim', { 'rev': 'a1b5108fd' })

vim8だとこの部分で deol.nvim requires Neovim と言われます。
, { 'rev': 'a1b5108fd' } の部分を消して、deol.nvimを削除、その後インストールすれば使えます。

deoplete.nvim

github.com

自動補完プラグイン。

インストール

vimrcに以下を記述。
C++の補完のため、deoplate-clangもインストールする。
GitHub - deoplete-plugins/deoplete-clang: deoplete.nvim source for C/C++/Obj-C/Obj-C++ with clang-python3

brew install cmake
brew install llvm --with-clang

必要なものを揃える。

call dein#add('Shougo/deoplete.nvim')
call dein#add('zchee/deoplete-clang')
if !has('nvim')
  call dein#add('roxma/nvim-yarp')
  call dein#add('roxma/vim-hug-neovim-rpc')
endif

上記をvimrcに追加。

g:deoplete#sources#clang#libclang_path
g:deoplete#sources#clang#clang_header

この二つの設定は必須です。
libclang_pathにはlibclang.dylibへのpath、clang_headerはclangディレクトリへのpathです。
libclang_pathと同じディレクトリにclangのディレクトリがあれば、それへのpathをclang_headerにします。

denite.vimはうまく動かないので諦めました。

参考

NeovimでモダンなPython環境を構築する - Qiita

2017-10-29

AtCoder Beginner Contest D問題ジャンル分け

競技プログラミングアルゴリズム

imos法

D - 感雨時刻の整理

全探索

D - 派閥
 D - バレンタインデー
 D - 語呂合わせ
 D - 画像処理高橋君
 D - Axis-Parallel Rectangle

DP・メモ化再帰

未分類

D - マーブル
別解：最小費用流

D - トランプ挿入ソート
 D - 金塊ゲーム
 D - 高橋くんの苦悩
 D - サプリメント
 D - 25個の整数
 D - ナップサック問題
 D - 経路
 D - No Need
D - Mixing Experiment
別解：半分全列挙

D - Simple Knapsack

ダブリング

D - 阿弥陀
別解：巡回置換

幾何

D - 一刀両断
 D - Big Bang

セグメントツリー | Binary Indexed Tree

D - プレゼント

考察

D - ロボット
 D - 3N Numbers
D - Insertion

シミュレーション

D - へんてこ辞書

2017-10-27

ARC016 - C ソーシャルゲーム

競技プログラミング

問題概要

商品が n 種類、くじが m 種類あります。
くじを一度引くのにお金がかかります。
くじからは、ある確率である商品が手に入ります。

最善を尽くしたとき、全ての商品を集める金額の期待値を求めてください。

考えたこと

期待値についてはこちら期待値と条件付確率 - math314のブログ、
問題文についてはこちら ARC016-C「ソーシャルゲーム」の記事が非常に参考になります。

こちら期待値と条件付確率 - math314のブログの記事で例として挙げられているコイントスの期待値についてです。
頂点の値が、連続で表が出た回数を示しています。
青矢印が表が出たことを、橙矢印が裏が出たことを表しています。
期待値はこのように状態の遷移から式を立てることができます。
f:id:noy72:20171027164545j:plain:w500

単純なくじで、期待値を求める式を立ててみます。
E は、その状態から全ての商品を集めるためにくじを引く回数を表しています。

頂点の値は、商品の入手を bit で表しています。
00 の状態からそれぞれ 10, 01 の状態へ遷移し、最後は 11 となります。
11 は全て揃った状態でありこれ以上はくじを引く必要がないため E_11 = 0 です。
10 の状態から 11 になるに 1 番目の商品を引かなければなりません。
このとき、 5% の確率で引けるので、くじを引く回数の期待値は 100 / 5 回です。
もう片方は 95% なので、 100 / 95 回です。

00 からは 5% の確率で 01 になり、 01 からは 100 / 95 回で全て揃います。
また、 95% の確率で 10 になり、 10 からは 100 / 5 回で全て揃います。
これで、 00 から 11 までの期待値が計算できました。
f:id:noy72:20171027164552j:plain:w500

式を実際に立ててみると、後ろから計算することで解がわかることに気付けます。
f:id:noy72:20171027164617j:plain:w500
f:id:noy72:20171027164624j:plain:w500
f:id:noy72:20171027164641j:plain:w500
あとは式を計算できるように実装します。

実装

sum が自分自身に返ってこない場合の期待値を表しています。
100 / (100 - k) が自分自身に返ってくる確率の逆数（期待値）を表しています。

手計算した式をどうにか実装したらうまくいった、という感じです。

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
const int INF = 1e8;
using namespace std;

//i番目のビットを返す
bool getBit(int num, int i){
	return ((num & (1 << i)) != 0);
}

//i番目を1にする
int setBit(int num, int i){
	return num | (1 << i);
}

int main(){
	int n, m;
	cin >> n >> m;

	vector<int> c(m), cost(m);
	vector<vector<pair<int, int>>> kuji(m); //番号、確率
	rep(i,m){
		cin >> c[i] >> cost[i];
		rep(j,c[i]){
			int a, b;
			cin >> a >> b;
			a--;
			kuji[i].emplace_back(a,b);
		}
	}

	double dp[1 << 10];
	rep(i,1 << 10) dp[i] = INF;
	dp[(1 << n) - 1] = 0;

	for(int s = (1 << n) - 1; s >= 0; s--){
		rep(i,m){
			double sum = cost[i], k = 0;
			for(auto j : kuji[i]){
				if(not getBit(s, j.first)){
					sum += dp[setBit(s, j.first)] * j.second / 100.0;
				}else{
					k += j.second;
				}
			}
			dp[s] = min(dp[s], sum * 100.0 / (100 - k));
		}
	}

	cout << fixed << setprecision(10) << dp[0] << endl;
}

2017-10-26

ARC067 - E Grouping

競技プログラミング

E - Grouping

問題概要

N 人をグループ分けします。
一つのグループにつき A ~ B 人で構成し、
同じ人数のグループは 0 か C ~ D 個作らなければいけません。
このようなグループ分けは何通りありますか。

DPの解説

DPテーブルを書いてみます。

横軸が、グループ分けしていない、残っている人の数。
縦軸が、i 人以下のグループのみでグループ分けしていることを表します。

dp[i][j] = i 人以下のグループのみにでグループ分けした時、グループ分けされていない人の数が j 人の時の通り数
f:id:noy72:20171026131458j:plain:w500

入力は、3 1 2 1 2 だとします。

まず、0 人以下のグループのみでグループ分けした場合を考えます。
「誰も選べない」の 1 通りしかないので、dp[0][n] = 1。
残りの人数を減らせないので、その他はすべて0。

次に、1 人のグループのみでグループ分けした場合を考えます。
残り 3 人いるときに、1 人グループを 1 個作った場合、3 人のうちから 1 人選ぶので、 $_3 C _1$ 。
f:id:noy72:20171026131501j:plain:w500

残り 3 人いるときに、1 人グループを 2 個作った場合、3 人のうちから 1 人選んで、 2 人のうちから 1 人選ぶ。
そして、重複を消せばよいので、 $\frac{_3 C _1 \times _2 C _1}{2!}$ 。
f:id:noy72:20171026131505j:plain:w500

同じグループは 3 個以上作れないので、次に進みます。
残り2 人いるときに、1 人グループを 1 個作った場合……ですが、
dp[0][2] = 0 のため、dp[1][1] += $_2 C _1 \times 0$ となります。
計算をしても +0 するだけなので省略。
f:id:noy72:20171026131509j:plain:w500

これで 1 人グループを作る場合をすべて試せました。
この計算結果は、1 人グループのみでグループ分けした結果の通り数を表しています。
f:id:noy72:20171026131514j:plain:w500

縦軸は、i 人以下のグループのみでグループ分けしていることを表すので、0 行の結果を加える必要があります。
f:id:noy72:20171026131523j:plain:w500

次に、2 人以下のグループのみでグループ分けした場合を考えます。
残り 3 人いるときに、2 人グループを 1 個作った場合、 $_3 C _2$ 。
f:id:noy72:20171026131527j:plain:w500

2 人グループは 1個以上作れないので、次に進みます。
残り 2 人いるときに、2 人グループを 1 個作った場合、 $_2 C _2$ 。
f:id:noy72:20171026131531j:plain:w500

2人グループを作る場合が終わりました。
f:id:noy72:20171026131535j:plain:w500

あとは先と同様に、1行の結果を加えます。
f:id:noy72:20171026131541j:plain:w500

これで本当に正しいのか、組み合わせを列挙してみます。

残り 3 人のとき
{ $\phi$ } (空集合)
より 1 通り。

残り 2 人のとき
{1}
{2}
{3}
より 3 通り。

残り 1 人のとき
{1, 2}
{1, 3}
{2, 3}
{ {1}, {2} }
{ {1}, {3} }
{ {2}, {3} }
より 6 通り。

残り 0 人のとき
{ {1, 2}, {3} }
{ {1, 3}, {2} }
{ {2, 3}, {1} }
より 3 通り。

どうやら正しいようです。

実装

先に組み合わせ、階乗の逆元を計算しておきます。
あとは遷移させます。

計算結果がどんどん加算されていくDPなので、更新する方向に気をつければ 1 次元配列で計算できます。

残り 1000 人を 1 人グループに分ける場合、
1 個のとき： $_{1000} C _1$
2 個のとき： $\frac{_{1000} C _1 \times _{999} C _1}{2!}$
3 個のとき： $\frac{_{1000 }C _1 \times _{999} C _1 \times _{998} C _1}{3!}$
....
と組み合わせの計算に時間がかかるので、前回の計算結果を用いて計算量を落としています。

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
//const int INF = 1e8;
using namespace std;

const long long M = 1000000007;

long long nCr[1005][1005];
void Pascals(){
	nCr[0][0] = 1;
	range(i,1,1001){
		rep(j,i + 1){
			if(j == 0) nCr[i][j] = nCr[i - 1][j];
			else if(j == i) nCr[i][j] = nCr[i - 1][j - 1];
			else nCr[i][j] = (nCr[i - 1][j] + nCr[i - 1][j - 1]);
			nCr[i][j] %= M;
		}
	}
}

//べき乗 x^n mod M
long long power(long long x, long long n){
	long long res = 1;
	if(n > 0){
		res = power(x, n / 2);
		if(n % 2 == 0) res = (res * res) % M;
		else res = (((res * res) % M) * x ) % M;
	}
	return res;
}

//階乗
long long fact[1005];
long long factorial(long long n, long long r){
	long long res = 1;
	range(i,r,n + 1){
		res*= i;
		res%= M;
		fact[i] = res;
	}
	return res;
}

int main(){
	Pascals();
	factorial(1000,1);
	long long fact_rev[1005];
	rep(i,1001) fact_rev[i] = power(fact[i], M - 2);

	long long n, a, b, c, d;
	cin >> n >> a >> b >> c >> d;

	long long dp[1005] = {0};
	dp[n] = 1;
	range(i,a,b + 1){
		range(k,i * c,n + 1){
			long long person = k;
			long long comb = 1;

			range(j,1,d + 1){
				long long join = i * j;
				if(k - join < 0) break;

				(comb *= nCr[person][i]) %= M;
				person-=i;

				if(j >= c){
					(dp[k - join] += dp[k] * comb % M * fact_rev[j] % M) %= M;
				}
			}
		}
	}

	cout << dp[0] << endl;
}

問題概要

考察

最長パスに含まれる頂点 の最遠点

部分木に含まれる頂点の最遠点

コード

問題概要

考察

外側から決める方法

計算量

実装

Indeed study sessionとは

学んだこと

競プロの気持ちでやってはダメだよ

無駄な部分は減らそう

競プロ的に丁寧に書いても読めない

includeを減らす

参照渡しを使う

using namespace stdはダメ

感想

環境

dein.vim

インストール

deoplete.nvim

インストール

参考

imos法

全探索

DP・メモ化再帰

未分類

桁DP

TreeDP

BitDP

行列累乗

2次元累積和

フロー

数学（組み合わせの計算など）

二分探索

グラフ

Union-find

ダブリング

幾何

セグメントツリー | Binary Indexed Tree

考察

シミュレーション

問題概要

考えたこと

実装

問題概要

DPの解説

実装

最長パスに含まれる頂点 $p_i$ の最遠点