スポンサーサイト

一定期間更新がないため広告を表示しています

スポンサードリンク | - | | - | - |

剰余演算練習

atcoderのとある問題がきっかけで剰余演算を勉強することになったわけだが、その問題では2^{N/2}を10^9+7で割った余りが必要になった。

剰余演算部分のコードは次の通り。

	long long ans = 1;
	for(int i=0; i<N/2; i++)
	{
		ans *= 2;
		ans %= 1000000007;
	}
	std::cout << ans << std::endl;
ジャジャガッチ | C/C++ | 22:39 | comments(0) | trackbacks(0) |

剰余演算

競技プログラミングの問題見てると時々解が非常に大きな数になるためある数の剰余を出力せよ、という形式のものがある。

これまではこりゃ無理だと思ってスルーしてたのだが挑戦してみた。

剰余演算と呼ばれるものの知識がいるらしい。

剰余演算の性質はwikipediaの剰余演算の項にまとまっている。

 

剰余演算の世界における積、和の性質を見てみる。

なお、数学ではa mod pと書いてaをpで割った時の余りと定義するようだが、なじまないのでC言語風にa%pと書くことにする。

 

(a%p)%p = a%p

(ab)%p = {(a%p)×(b%p)}%p = {(a%p)×b}%p

(a+b)%p = {(a%p)+(b%p)}%p = {(a%p)+b}%p

 

%p%p=%pのように考えて%pをくくり出しているようにみれば覚えやすいかな。

これが基本であるが、積、和が3つ以上になる場合は注意。

(abc)%p = {(ab)%p×(c%p)}%p = {(ab)%p×c}%p = [{(a%p)×b}%p×c]%p

のようになる。aの剰余をとる→bを掛けて更に剰余をとる→cをかけて更に剰余をとる、の手順でok。4つ以上も同じ。

 

aの逆元は

{(a%p)(b%p)}%p = 1%p

を満すbとして定義される。

逆元を使って

(a/b)%p = {(a%p)×(b^-1%p)}%p

が成り立つ。

逆元はフェルマーの小定理を使って計算できる。

a^{p-1}%p = 1%pよりaa^{p-2}%p = 1%pであるため

a^-1%p = a^{p-2}%p

となる。すなわち、

(a/b)%p = {(a%p)×(b^-1%p)}%p = {(a%p)×(b^{p-2})%p}%p

と積に帰着する。

例えば

(143/13)%7 = (143*13^5)%7

となるわけである。

ジャジャガッチ | C/C++ | 22:35 | comments(0) | trackbacks(0) |

yukicoder No47

 

元ネタと思われる童謡の歌詞では叩いた回数分と同じだけ増えるらしい。元ネタの方が問題としてははるかに簡単だ。

コレ面白い。面白いのでネタバレを避けるため解説は続きに書く。

続きを読む >>
ジャジャガッチ | C/C++ | 22:27 | comments(0) | trackbacks(0) |

しゃくとり法 POJ3061

蟻本でしゃくとり法のとこ読んでみた。

解説読む前に自分ならどういうコード書くか考えてみた。

 

POJ3061: 与えられた数列の部分列で総和がS以上となる数列の最小の長さを求めよ。

全探索はきつそうなので、まあとりあえずdp考えてみるかなあ。

dp[i] = 先頭がa[i]で最短の長さ

と定義すると、dp[i]とdp[i-1]の間に漸化式を立てるのは難しそうだ。部分列の総和に関する情報が欲しい。

dp[i] = dp[i] = (先頭がa[i]で最短の長さ, 部分列の和s)

と定義してみようか。うんいけそう。

dp[i] = (dp[i-1].first+(n-i), dp[i-1].second-a[i-1]+Σ{j=i-1+dp[i-1].first~n}a[j])

ただしnは部分列の総和がSを超える添字

あとはdp[0]を計算して漸化式を計算するのみ。

#include <iostream>
#include <vector>
#include <algorithm>
const int INF = 1e9;

int main()
{
	int T; std::cin >> T;
	for(int t=0; t<T; t++)
	{
		int N; std::cin >> N;
		int S; std::cin >> S;
		std::vector<int> a(N);
		for(int n=0; n<N; n++)
		{
			std::cin >> a[n];
		}

		std::vector<std::pair<int, int> > dp(N);
		int sum = 0;
		for(int n=0; n<N; n++)
		{
			sum += a[n];
			if(sum >= S)
			{
				dp[0].first = n + 1;
				dp[0].second = sum;
				break;
			}
		}
		if(sum < S) std::cout << 0 << std::endl;
		else
		{
			for(int i=1; i<N; i++)
			{
				int sum = dp[i-1].second - a[i-1];
				dp[i].first = dp[i].second = -1;
				if(sum >= S)
				{
					dp[i].first = dp[i-1].first - 1;
					dp[i].second = sum;
				}
				else
				{
					for(int j=i-1+dp[i-1].first; j<N; j++)
					{
						sum += a[j];
						if(sum >= S)
						{
							dp[i].first = dp[i-1].first + j - (i-1+dp[i-1].first);
							dp[i].second = sum;
							break;
						}
					}
				}
				if(dp[i].first==-1)
				{
					for(int j=i+1; j<N; j++) dp[j].first = dp[j].second = -1;
					i=N;
				}
			}
			int ans = INF;
			for(int i=0; i<dp.size(); i++)
			{
				if(ans > dp[i].first && dp[i].first!=-1) ans = dp[i].first;
			}
			std::cout << ans << std::endl;
		}
	}
	return 0;
}

見た目は蟻本のものよりごついけど、多分これしゃくとり法と同じ。

条件を満たすように前と後ろを交互に進めていっている。

ジャジャガッチ | C/C++ | 22:45 | comments(0) | trackbacks(0) |

プリム法について

プリム法の証明もダイクストラ法とほぼ同じかと思ったけどそんなに単純な話じゃないのか。

背理法使った証明ばっかだけど、そうじゃない証明方法あるのかな?

ジャジャガッチ | C/C++ | 01:13 | comments(0) | trackbacks(0) |

ダイクストラ法の証明

ダイクストラ法をいい加減に証明する。

今、スタートsからの最短距離が確定した頂点の集合Uが与えられているとする。

未確定頂点の集合Vからひとつ頂点をサンプリングしてUに加え、新たに最短距離が確定した集合が作れるかが問題である。

今、u_vをUに含まれる頂点vの隣接nodeとする。vをVに含まれる頂点とし、

L(s→u_v→v) < L(s→u_v'→v')

を満たすような頂点vを考える。L(s→u_v→v)はsから最短距離でu_vへ移動し、vへ移る距離とする。v'はvでないVの元である。

このような点vの最短経路はs→u_v→vである。何故ならば、u_vを経由しない場合s→u_v'→v'→vという経路を辿る必要があり、これは上式よりs→u_v→vよりも距離が長くなるためである。(証明終)

 

こんなん完全に動的計画法やん。

dp[i]を頂点数iの最短経路確定グラフとする。次の漸化式で計算していけばok。

dp[i] = dp[i-1] + 未確定nodeのうち暫定コストが最小の頂点

暫定コストはdp[i-1]に隣接する未確定nodeについて逐次更新するものとする。dp[1]は自明だからiteration回せば最短経路が求まるわけだ。

ようやく腑に落ちた気がする。

ジャジャガッチ | C/C++ | 00:32 | comments(0) | trackbacks(0) |

プリム法

グラフ勉強中。

今日は最小全域木を求めるアルゴリズム、プリム法の実装。

AOJのALDS1_12_Aがお題。

#include <iostream>
#include <queue>
#include <vector>
#include <numeric>

class Edge
{
public:
	Edge(){}
	Edge(int cost, int to)
	{
		this->cost = cost;
		this->to = to;
	}
	int cost, to;
	bool operator>(const Edge &e) const
	{
		return this->cost > e.cost;
	}
};

class Vertex
{
public:
	int no;
	std::vector<Edge> ve;
};

int main()
{
	int n; std::cin >> n;
	int a[100][100];

	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
		{
			int tmp; std::cin >> tmp;
			a[i][j] = tmp;
		}
	std::vector<Vertex> vv(n);
	for(int i=0; i<n; i++)
	{
		vv[i].no = i;
		for(int j=0; j<n; j++)
		{
			if(i!=j && a[i][j]!=-1) vv[i].ve.push_back(Edge(a[i][j],j));
		}
	}

	std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge> > q;
	for(auto &x : vv[0].ve)
	{
		q.push(x);
	}
	std::vector<bool> MST(n);
	for(int i=0; i<n; i++) MST[i] = false;
	MST[0] = true;
	std::vector<Edge> lMST;

	while(!q.empty())
	{
		Edge e;
		while(!q.empty())
		{
			e = q.top(); q.pop();
			if(MST[e.to]==false) break;
		}
		if(MST[e.to]==false)
		{
			MST[e.to] = true;
			lMST.push_back(e);
			for(auto &x : vv[e.to].ve)
			{
				q.push(x);
			}
		}
	}
	int ans = 0;
	for(auto &x : lMST)
	{
		ans += x.cost;
	}
	std::cout << ans << std::endl;

	return 0;
}

最小全域木はEdgeの集合で表現することにした。

まず好きな頂点を一つ選び、使用済みとする。そこから出てる全てのEdgeをプラオリティキューにpushする。

これが初期化。

次にプライオリティキューからpopしてそこから繋る頂点を使用済とする。そこから出てる全てのEdgeをプライオリティキューにpushする。これを繰り返す。

ダイクストラ法に似ている。しばらくプリム法の練習してから証明を考えたい。

ダイクストラ法の証明も改めて考えたい。

ジャジャガッチ | C/C++ | 15:56 | comments(0) | trackbacks(0) |

ALDS1_7

蟻本が難しすぎると思う人におすすめとあった本「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」買ってみた。

新しい本なのに何故かamazonに新品が見当たらない。

この本、なかなか面白い。

Aizu Online Judge Systemの開発者が著者で、本の中の問題がAOJ内に用意されていて、オンラインジャッジシステムを使って演習できる。

これはとてもいい。

内容は確かに蟻本に比べると圧倒的に簡単。

流し読みして自分が弱い所を補強することにする。

とりあえずTreeのところを読んでみることにする。

 

というわけで問題ALDS1_7_A: Rooted Trees。

これは各nodeのchild nodeのidが与えられた時、各nodeの詳しい情報を出力する問題。

parent nodeの番号とかrootかleafかとか。

解説読まずにやってみたけど、簡単だ。

#include <iostream>
#include <vector>
#include <stack>
#include <string>

class Node
{
public:
	Node()
	{
		this->parent = NULL;
	}
	int id;
	Node *parent;
	std::vector<Node*> children;
	int depth;
};

int main()
{
	int n; std::cin >> n;
	Node *nodes = new Node[n];
	for(int i=0; i<n; ++i)
	{
		int id; std::cin >> id;
		nodes[id].id = id;
		int k; std::cin >> k;
		for(int j=0; j<k; ++j)
		{
			int child_id; std::cin >> child_id;
			nodes[id].children.push_back(&nodes[child_id]);
			nodes[child_id].parent = &nodes[id];
		}
	}
	Node *root;
	for(int i=0; i<n; i++)
	{
		if(nodes[i].parent==NULL) root = &nodes[i];
	}
	std::stack<Node*> st;
	root->depth = 0;
	st.push(root);
	while(!st.empty())
	{
		Node *p = st.top(); st.pop();
		for(auto &x : p->children)
		{
			x->depth = p->depth + 1;
			st.push(x);
		}
	}

	for(int id=0; id<n; id++)
	{
		std::string info;
		info += "node " + std::to_string(id) + ": ";
		if(nodes[id].parent==NULL) info += "parent = -1, ";
		else info += "parent = " + std::to_string(nodes[id].parent->id) + ", ";
		info += "depth = " + std::to_string(nodes[id].depth) + ", ";
		if(nodes[id].parent==NULL)
		{
			info += "root, ";
		}
		else if(nodes[id].children.empty())
		{
			info += "leaf, ";
		}
		else
		{
			info += "internal node, ";
		}
		info += "[";
		for(int j=0; j<nodes[id].children.size(); j++)
		{
			info += std::to_string(nodes[id].children[j]->id);
			if(j!=nodes[id].children.size()-1)
			{
				info += ", ";
			}
		}
		info += "]";
		std::cout << info << std::endl;

	}

	delete[] nodes;
	return 0;
}

各nodeをポインタで繋いで、全探索で各種情報を生成していった。

もう全探索はお手のものです。

ジャジャガッチ | C/C++ | 14:35 | comments(0) | trackbacks(0) |

Atcoder Beginner Contest 051

今年の目標は

TOEIC 700点と競技プログラミングコンテスト参加。

なのだが早速後者は達成してしまった。

初心者向けのコンテスト、通称ABC。参加してみました。

 

参加登録はとても簡単。

時間になったら問題が公開されるので解いてコード送ればOK。

 

A:

問題文

イルカは、新年に長さ 19 の文字列 s を受け取りました。
文字列 s の形式は [英小文字 5 文字],[英小文字 7 文字],[英小文字 5 文字] で表されます。
イルカは、カンマで区切られた文字列 s を、スペースで区切られた文字列に変換したいと思っています。
イルカの代わりに、この処理を行うプログラムを作ってください。

#include <iostream>
#include <string>

int main()
{
	std::string str; std::cin >> str;
	str[5] = ' ';
	str[13] = ' ';
	std::cout << str << std::endl;
	return 0;
}

これは簡単過ぎて解説不要でしょう。

 

B:

問題文

2 つの整数 K,S が与えられます。
3 つの変数 X,Y,Z があり、0≦X,Y,ZK を満たす整数の値を取ります。
X+Y+Z=S を満たす X,Y,Z への値の割り当ては何通りありますか。

#include <iostream>

int main()
{
	int K; std::cin >> K;
	int S; std::cin >> S;
	int ans = 0;
	for(int X=0; X<=K; X++)
		for(int Y=0; Y<=K; Y++)
		{
			int Z = S - X - Y;
			if(Z>=0 && Z<=K) ans++;
		}
	std::cout << ans << std::endl;
	return 0;
}

これは単純にX, Y, Zをループで回すと最悪O(10^9)でTLEになると思われるので、ちょっと工夫してZのループを削除した。まあ簡単。

 

C:

問題文

イルカは x 軸正方向を右、y 軸正方向を上とする 2 次元座標平面にいます。
イルカは現在点 (sx,sy) にいて、1 秒あたり上下左右に距離 1 だけ進むことができます。
このとき、移動前と移動後の x 座標、y 座標はともに整数でなければなりません。
イルカはここから sx<txsy<ty を満たす点 (tx,ty) に行き、その後点 (sx,sy) に戻り、また点 (tx,ty) に行き、その後点 (sx,sy) に戻ります。
このとき、イルカは点 (sx,sy) と点 (tx,ty) を除いて、途中で同じ座標を複数回通らないように移動しなければなりません。
このような条件を満たすイルカの最短経路を 1 つ求めてください。

#include <iostream>
#include <string>

int main()
{
	int sx; std::cin >> sx;
	int sy; std::cin >> sy;
	int tx; std::cin >> tx;
	int ty; std::cin >> ty;

	std::string path1;
	for(int j=0; j<ty-sy; j++)
	{
		path1 += "U";
	}
	for(int i=0; i<tx-sx; i++)
	{
		path1 += "R";
	}

	std::string path2;
	for(int j=0; j<ty-sy; j++)
	{
		path2 += "D";
	}
	for(int i=0; i<tx-sx; i++)
	{
		path2 += "L";
	}

	std::string path3;
	path3 += "L";
	for(int j=0; j<ty-sy+1; j++)
	{
		path3 += "U";
	}
	for(int i=0; i<tx-sx+1; i++)
	{
		path3 += "R";
	}
	path3 += "D";

	std::string path4;
	path4 += "R";
	for(int j=0; j<ty-sy+1; j++)
	{
		path4 += "D";
	}
	for(int i=0; i<tx-sx+1; i++)
	{
		path4 += "L";
	}
	path4 += "U";


	std::cout << path1+path2+path3+path4 << std::endl;
	return 0;
}

これも簡単。最初の往復はずーっと上に行って右に行って、ずーっと下に行って左にいって元にもどればok。次はその一つ外側を通ればok。この文章で意味が伝わるかは怪しい。絵を描けば簡単。

 

D:

問題文

自己ループと二重辺を含まない N 頂点 M 辺の重み付き無向連結グラフが与えられます。
i(1≦iM) 番目の辺は頂点 ai と頂点 bi を距離 ci で結びます。
ここで、自己ループは ai=bi(1≦iM) となる辺のことを表します。
また、二重辺は (ai,bi)=(aj,bj) または (ai,bi)=(bj,aj)(1≦i<jM) となる辺のことを表します。
連結グラフは、どの異なる 2 頂点間にも経路が存在するグラフのことを表します。
どの異なる 2 頂点間の、どの最短経路にも含まれない辺の数を求めてください。

#include <iostream>
#include <vector>
#include <stack>
const int INF = 1e9;

struct Edge
{
	int cost, to;
};

class Vertex
{
public:
	int no;
	int cost;
	std::vector<Edge> ve;
};

int main()
{
	int N; std::cin >> N;
	int M; std::cin >> M;

	int d[128][128];
	for(int i=0; i<N; i++)
		for(int j=0; j<N; j++)
		{
			d[i][j] = INF;
		}
	for(int i=0; i<N; i++)
	{
		d[i][i] = 0;
	}
	std::vector<std::vector<std::pair<int, int> > > edge(N);
	int num[128][128];//num[i][j]:iとjを繋ぐ辺の番号
	for(int m=0; m<M; m++)
	{
		int a; std::cin >> a;
		int b; std::cin >> b;
		int c; std::cin >> c;
		a--; b--;
		d[a][b] = c; d[b][a] = c;
		edge[a].push_back(std::pair<int, int>(b,c));
		edge[b].push_back(std::pair<int, int>(a,c));
		num[a][b] = m; num[b][a] = m;
	}

	//ワーシャルフロイド法
	for(int k=0; k<N; k++)
		for(int i=0; i<N; i++)
			for(int j=0; j<N; j++)
			{
				d[i][j] = std::min(d[i][j], d[i][k]+d[k][j]);
			}

	std::vector<bool> used(M);
	for(auto x : used)
	{
		x = false;
	}
	for(int i=0; i<N; i++)
		for(int j=i+1; j<N; j++)
		{
			std::stack<std::vector<int> > st;
			std::vector<int> tmp; tmp.push_back(i);
			st.push(tmp);

			while(!st.empty())
			{
				std::vector<int> path = st.top(); st.pop();
				if(path.back()==j)
				{
					for(int k=0; k<path.size()-1; k++)
					{
						used[num[path[k]][path[k+1]]] = true;
					}
				}
				else
				{
					for(auto &x : edge[path.back()])
					{
						if(d[i][x.first]==d[i][path.back()]+x.second)
						{
							tmp = path;
							tmp.push_back(x.first);
							st.push(tmp);
						}
					}
				}
			}

		}
	int ans = 0;
	for(auto x : used)
	{
		if(x==false) ans++;
	}
	std::cout << ans << std::endl;

	return 0;
}

これがくやしかった。頂点番号を-1してるところで間違えてコストも一緒に-1してるバグに気が付かなくてタイムオーバーしてしまった。

任意の二点間の最短距離ならワーシャルフロイド法で求められると蟻本に書いてあったのを覚えていたので、実装したことはなかったが蟻本をそのまま写した。

その後経路復元して使った辺を調べただけ。

工夫も何もないけどこれでAC。

 

今年の目標早くも半分クリアしてしまった。

目標が低すぎたか。

ABCでレートが付かないっぽいレーティング1200以上を目指すか。

ジャジャガッチ | C/C++ | 00:40 | comments(0) | trackbacks(0) |

yukicoder No.160 (3)

ようやく通った。

前回深さ優先探索を辞書順に行っても子ノードのスタックに時間がかかり過ぎてだめだった。

解説を斜め読みしてもよくわからなかったのでじっくり読んでみた。

ほほう、なるほど!

 

経路復元をGから行うとどの経路も必ずSに到達することが保証されている。この時小さい番号の付いているノードを優先的に選ぶことも考えたが、これは辞書順にはならない。

そこで、経路復元をSから行うことを考えたが、これでは全ての経路がGに到達することが保証されない。うーん。

そこでだ!ダイクストラ法をG→S方向へ行う。こうすればSから経路復元して全ての経路がGに到達することが保証される。ノードの選び方を小さい番号から優先的に選べば自動的に辞書順最小のルートが得られる!

なるへそー。方向を逆にするだけだからコード変更もほとんどいらない。

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
const int INF = 1e9;

struct Edge
{
	int to, cost;
	bool operator>(const Edge &e) const
	{
		return this->to > e.to;
	}
	bool operator<(const Edge &e) const
	{
		return this->to < e.to;
	}
};

class Vertex
{
public:
	int cost;
	int no;
	bool operator>(const Vertex &v) const
	{
		return this->cost > v.cost;
	}
	std::vector<Edge> v_edge;
};

int main()
{
	int N; std::cin >> N;
	int M; std::cin >> M;
	int S; std::cin >> S;
	int G; std::cin >> G;

	std::vector<Vertex> v_vertex(N);
	for(int m=0; m<M; m++)
	{
		int a; std::cin >> a;
		int b; std::cin >> b;
		int c; std::cin >> c;
		v_vertex[a].v_edge.push_back(Edge{b,c});
		v_vertex[b].v_edge.push_back(Edge{a,c});
	}
	for(auto &x : v_vertex)
		{
			std::sort(x.v_edge.begin() , x.v_edge.end());
		}
	for(int n=0; n<N; n++)
	{
		v_vertex[n].no = n;
		v_vertex[n].cost = INF;
	}
	v_vertex[G].cost = 0;
	std::priority_queue<Vertex , std::vector<Vertex> , std::greater<Vertex> > q;
	q.push(v_vertex[G]);

	while(!q.empty())
	{
		Vertex v = q.top(); q.pop();
		if(v_vertex[v.no].cost < v.cost) continue;
		for(auto &x : v.v_edge)
		{
			if(v_vertex[x.to].cost > v.cost+x.cost)
			{
				v_vertex[x.to].cost = v.cost+x.cost;
				q.push(v_vertex[x.to]);
			}
		}
	}

	std::stack<std::vector<int> > st;
	std::vector<int> tmp; tmp.push_back(S);
	st.push(tmp);
	std::vector<int> ans;
	while(!st.empty())
	{
		std::vector<int> current = st.top(); st.pop();
		if(current[current.size()-1]==G)
		{
			ans = current;
			break;
		}
		else
		{
			for(auto &x : v_vertex[current.back()].v_edge)
			{
				if(v_vertex[x.to].cost+x.cost==v_vertex[current.back()].cost)
				{
					std::vector<int> tmp = current;
					tmp.push_back(x.to);
					st.push(tmp);
					break;
				}
			}
		}
	}

	for(int i=0; i<ans.size(); ++i)
	{
		std::cout << ans[i];
		if(i==ans.size()-1) std::cout << std::endl;
		else std::cout << " ";
	}
	return 0;
}

余裕でACが取れる。

なるほど。辞書順最小の解を出力しろ、というのは解がたくさんあるからとりあえず辞書順最小のものを出力してね、ということではなく、それ以外の解を求めるのが難しいということか。なるほど。こういうのは競技プログラミングならではのノウハウですな。

経路復元の勉強にもなった。

ダイクストラ法の練習にうってつけのいい問題だった!

 

 

 

ジャジャガッチ | C/C++ | 15:09 | comments(0) | trackbacks(0) |
2/15PAGES | << >> |

07
--
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
--
>>
<<
--
PR
RECOMMEND
RECENT COMMENT
MOBILE
qrcode
OTHERS
Since 2013/09/17
LATEST ENTRY
CATEGORY
ARCHIVE
LINKS
PROFILE
SEARCH