fork download 
  1. #include <vector>
  2. #include <iostream>
  3.  
  4. // 【】: 計算量
  5. // L : レーンの長さ
  6. // P : 多重度
  7. // S : すしの数
  8. // T : すしの時間合計
  9. // T ≦ PL
  10. //【P(L+S+PP)】
  11.  
  12. struct SUSHI {
  13. 	int pos;
  14. 	int time;
  15. };
  16.  
  17. struct LANE {
  18. 	std::vector < SUSHI > sushi;
  19. 	int length;
  20. };
  21.  
  22. struct LANE_INFO {
  23. 	std::vector < int > pile;
  24. 	int pile_max;
  25. 	std::vector < std::vector < int > > pos2sushi;
  26. };
  27.  
  28. // nをLで割った余り [0～L-1]
  29. int modulo(int n, int L){
  30. 	return n < 0 ? L - 1 - (- n - 1) % L : n % L;
  31. }
  32.  
  33. // a |= b
  34. void or_equal(std::vector < bool > &a, const std::vector < bool > &b){
  35. 	if (a.size() < b.size()){
  36. 		a.resize(b.size(), false);
  37. 	}
  38. 	for (int i = 0; i < b.size(); i++){
  39. 		a[i] = a[i] || b[i];
  40. 	}
  41. }
  42.  
  43. // (a & b) != 0
  44. bool intersect(const std::vector < bool > &a, const std::vector < bool > &b){
  45. 	for (int i = 0; i < a.size() && i < b.size(); i++){
  46. 		if (a[i] && b[i]){
  47. 			return true;
  48. 		}
  49. 	}
  50. 	return false;
  51. }
  52.  
  53. // 情報取得
  54. //【T】
  55. void get_lane_info(const LANE &lane, LANE_INFO &info){
  56. 	int L = lane.length;
  57.  
  58. 	// 多重度
  59. 	//【T】
  60. 	info.pile.clear();
  61. 	info.pile.resize(L, 0);
  62. 	for (int i = 0; i < lane.sushi.size(); i++){
  63. 		const SUSHI &sushi = lane.sushi[i];
  64. 		for (int j = 0; j < sushi.time; j++){
  65. 			info.pile[modulo(sushi.pos + j, L)] ++;
  66. 		}
  67. 	}
  68.  
  69. 	// 多重度最大値
  70. 	//【L】
  71. 	info.pile_max = 0;
  72. 	for (int i = 0; i < L; i++){
  73. 		if (info.pile[i] >= info.pile_max){
  74. 			info.pile_max = info.pile[i];
  75. 		}
  76. 	}
  77.  
  78. 	// レーン位置からSUSHIデータ情報へ
  79. 	//【S】
  80. 	info.pos2sushi.clear();
  81. 	info.pos2sushi.resize(L);
  82. 	for (int i = 0; i < lane.sushi.size(); i++){
  83. 		const SUSHI &sushi = lane.sushi[i];
  84. 		info.pos2sushi[sushi.pos].push_back(i);
  85. 	}
  86. }
  87.  
  88.  
  89. // オーバーラン量計算
  90. //【LP+SP+PPP】
  91. int get_overrun(const LANE &lane, int pos){
  92. 	int L = lane.length;
  93.  
  94. 	LANE_INFO info;
  95. 	get_lane_info(lane, info);		//【T】
  96.  
  97. 	//【L】
  98. 	std::vector < int > over;
  99. 	for (int i = 0; i < lane.sushi.size(); i++){
  100. 		const SUSHI &sushi = lane.sushi[i];
  101. 		int n = modulo(pos - sushi.pos, L);
  102. 		if (0 < n && n < sushi.time){
  103. 			over.push_back(i);
  104. 		}
  105. 	}
  106.  
  107. 	//【P】
  108. 	std::vector < std::vector < bool > > connect(L, std::vector < bool >(over.size(), false));
  109. 	for (int i = 0 ; i < over.size() ; i++){
  110. 		const SUSHI &sushi = lane.sushi[over[i]];
  111. 		connect[sushi.pos][i] = true;
  112. 		connect[modulo(sushi.pos + sushi.time, L)][i] = true;
  113. 	}
  114.  
  115. 	//【LP+SP】
  116. 	for (int i = 0; i < L; i++){
  117. 		int p = modulo(pos + i, L);
  118. 		if (info.pile[p] < info.pile_max){
  119. 			or_equal(connect[modulo(p + 1, L)], connect[p]);
  120. 		}
  121. 		for (int j = 0; j < info.pos2sushi[p].size(); j++){
  122. 			const SUSHI &sushi = lane.sushi[info.pos2sushi[p][j]];
  123. 			or_equal(connect[modulo(p + sushi.time, L)], connect[p]);
  124. 		}
  125. 	}
  126.  
  127. 	//【PP】
  128. 	std::vector < std::vector < bool > > connect0;
  129. 	connect0.push_back(connect[pos]);
  130. 	for (int i = 0; i < over.size(); i++){
  131. 		connect0.push_back(connect[lane.sushi[over[i]].pos]);
  132. 	}
  133.  
  134. 	for (int i = 0; i < connect0.size(); i++){
  135. 		for (int j = i + 1; j < connect0.size(); j++){
  136. 			if (intersect(connect0[i], connect0[j])){
  137. 				or_equal(connect0[i], connect0[j]);
  138. 				if (j < connect0.size() - 1){
  139. 					connect0[j].swap(connect0.back());
  140. 				}
  141. 				connect0.pop_back();
  142. 				j = i;
  143. 			}
  144. 		}
  145. 	}
  146.  
  147. 	//【PP】
  148. 	int over_max = 0;
  149. 	for (int i = 1; i < connect0.size(); i++){
  150. 		int over_min = L;
  151. 		for (int j = 0; j < over.size(); j++){
  152. 			if (connect0[i][j]){
  153. 				const SUSHI &sushi = lane.sushi[over[j]];
  154. 				int o = modulo(sushi.pos + sushi.time - pos, L);
  155. 				if (o < over_min){
  156. 					over_min = o;
  157. 				}
  158. 			}
  159. 		}
  160. 		if (over_min > over_max){
  161. 			over_max = over_min;
  162. 		}
  163. 	}
  164. 	return over_max;
  165. }
  166.  
  167. // 最短時間計算
  168. //【LP+SP+PPP】
  169. int get_min_time(LANE lane, int start = 0, int time = 0){
  170. 	int L = lane.length;
  171. 	if (L == 0){
  172. 		return 0;
  173. 	}
  174.  
  175. 	// パラメーターの調整 ( 位置:[0～L-1], 長さ:[1～L]に )
  176. 	//【S】
  177. 	for (int i = 0; i < lane.sushi.size(); i++){
  178. 		SUSHI &sushi = lane.sushi[i];
  179.  
  180. 		int l = modulo(sushi.time-1, L) + 1;
  181. 		time -= l - sushi.time;
  182. 		sushi.time = l;
  183.  
  184. 		sushi.pos = modulo(sushi.pos, L);
  185. 	}
  186.  
  187. 	LANE_INFO info;
  188. 	get_lane_info(lane, info);		//【T】
  189. 	if (info.pile_max == 0){
  190. 		return 0;
  191. 	}
  192.  
  193. 	// 多重度最大の先頭を調べる
  194. 	//【L】
  195. 	int pile_max_top = 0;
  196. 	for (int i = 0; i < L; i++){
  197. 		if (info.pile[modulo(start + i, L)] >= info.pile_max){
  198. 			pile_max_top = modulo(start + i + 1, L);
  199. 		}
  200. 	}
  201.  
  202. 	// 分解1
  203. 	int ov1 = get_overrun(lane, start);		//【LP+SP+PPP】
  204. 	if (ov1 != 0 || pile_max_top == start){
  205. 		return info.pile_max * L + ov1 + time;
  206. 	}
  207.  
  208. 	// 分解2
  209. 	SUSHI dummy = { pile_max_top, modulo(start - pile_max_top, L) };
  210. 	lane.sushi.push_back(dummy);
  211. 	int ov2 = get_overrun(lane, pile_max_top);		//【LP+SP+PPP】
  212. 	return (info.pile_max - 1) * L + modulo(pile_max_top - start, L) + ov2 + time;
  213. }
  214.  
  215. const char * const LANE_DATA[] = {
  216. 	"12_3",
  217. 	"313__",
  218. 	"4_35_1264_23_434",
  219. 	"123456789123456789",
  220. 	"88967472612377988186",
  221. 	"19898693316679441672",
  222. 	"93769682716711132249893",
  223. 	"999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999",
  224. 	"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789",
  225. 	NULL
  226. };
  227.  
  228. int main(){
  229. 	for (int i = 0 ; LANE_DATA[i] != NULL ; i++){
  230. 		LANE lane;
  231. 		int L = 0;
  232. 		for (int j = 0; ; j++){
  233. 			char ch = LANE_DATA[i][j];
  234. 			if (ch == '\0') {
  235. 				break;
  236. 			}
  237. 			if ('1' <= ch && ch <= '9'){
  238. 				SUSHI sushi = { j, ch - '0' };
  239. 				lane.sushi.push_back(sushi);
  240. 			}
  241. 			L++;
  242. 		}
  243. 		lane.length = L;
  244.  
  245. 		std::cout << "----------------------------------------------------------------\n";
  246. 		std::cout << LANE_DATA[i] << "\n";
  247. 		std::cout << "time : " << get_min_time(lane) << "\n";
  248. 	}
  249. 	return 0;
  250. }
  251.  
Success #stdin #stdout 0.01s 5424KB
comments (?)
stdin 
Standard input is empty
stdout 
----------------------------------------------------------------
12_3
time : 6
----------------------------------------------------------------
313__
time : 8
----------------------------------------------------------------
4_35_1264_23_434
time : 60
----------------------------------------------------------------
123456789123456789
time : 98
----------------------------------------------------------------
88967472612377988186
time : 149
----------------------------------------------------------------
19898693316679441672
time : 170
----------------------------------------------------------------
93769682716711132249893
time : 170
----------------------------------------------------------------
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
time : 2162
----------------------------------------------------------------
123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789
time : 1268
https://ideone.com/qPsn3a
_9333777_9
8973_299453_

4496184_47948
194497_76_169759

-------------

巡回問題の一種
路は有向円
円上に線分があり、線分をすべて巡回するのが目的
スタート位置は固定
ゴール位置は最後の線分を通り抜けたところ
(同じ点から開始する線分は高々１本)

コストはスタートからゴールまでの道のり

以下を仮定しても一般性を失わない
一周の長さは自然数であり、グリッドのマス上に線分が来るとする
線分の長さは 1 ～ L である

------------------------------------

レーン、線、辺
部分レーン
多重度
閉路、周回数、完備
任意の線を含む閉路の存在
閉路が接する、接点がある
閉路融合
閉路分解

----
◆レーンの、区間、辺、点
円周が単位区間に分けらている
この単位区間を単位として、円周上に複数の線が乗っている
円周を固定して、レーンを線の集合と同一視する

◆線

◆部分レーン、差レーン、レーンの和
レーンを線の集合とした時の
部分集合、差集合、和集合

◆多重度、最大多重度
レーンの単位区間中の線の重なり具合を多重度
レーン上の多重度の最大値を最大多重度

◆閉路
レーンをn周(n≧1)して同一点に戻ってくる順路
このときのnを周回数
閉路が通る線の集合を、レーンの部分集合と同一視する

◆閉路の接点、閉路融合
共通の線が無い閉路同士において、
閉路が接するとは
閉路上の共通の点であって、
それぞれに、線の内部ではない状態が存在する
ことを言う

閉路融合
共通の線が無い閉路同士が接点を持つ場合、
以下を満たす閉路が存在する
各閉路の線すべてを通る
周回数は、融合する閉路の周回数の和

◆完備
閉路が完備であるとは、
閉路の周回数 ＋ 『レーン － 閉路』の最大多重度 ＝ レーンの最大多重度
となること

※このとき、閉路の最大多重度 ＝ 閉路の周回数

◆同値関係の定義
線a, 線b を含む完備閉路が存在することを
a ∽ b と書くことにする
これは同値関係となっている

線a, 線a を含む完備閉路の存在
線a, 線b を含む完備閉路が存在し、線a, 線c を含む完備閉路が存在するなら、線b, 線c を含む完備閉路が存在する

◆完備閉路分解、最小完備閉路分解
レーンを完備閉路の和で表すことを、完備閉路分解と呼ぶ




◆手順
線の長さを 1～L に補正

int ov1 = get_overrun(lane, start);
if (ov1 != 0 || pile_max_top == start){
return info.pile_max * L + ov1 + time; // 式１
}

SUSHI dummy = { pile_max_top, modulo(start - pile_max_top, L) };
lane.sushi.push_back(dummy);
int ov2 = get_overrun(lane, pile_max_top);
return (info.pile_max - 1) * L + modulo(pile_max_top - start, L) + ov2 + time; // 式２

◆閉路分解
多重度MAX = Σ[閉路iの周回数]
となる閉路に分解

閉路の存在
任意の線に対し、閉路が存在する
閉路の検索開始点から、多重度を保ったままスキャン
開始点で、線の途中か途中じゃないかに分かれる
途中であれば、多重度をたもったままスキャンが可能
途中でなければ、そこで閉路となる

最小分解の存在
線abを含む閉路と、線acを含む閉路が存在する場合、線abcを含む閉路が存在する
A:線abを含む閉路
B:線acを含む閉路

L - A の中に、
L - A と B との共通部分の中で cを含む部分路
を含んだ閉路が存在する

この閉路は A と接しているので


◆証明２ 式１の証明 (ov1 != 0 の時)
下限の証明
overrunがMAXでない閉路分解要素を(最大効率で)周回する時間 ＋ SからはじめてoverrunがMAXの閉路分解要素の時間

存在の証明
分解をoverrun昇順にソートし、それぞれoverrunの点からスタート

◆証明３ 式２の証明
下限の証明
overrunがMAXでない閉路分解要素を(最大効率で)周回する時間 ＋ SからはじめてoverrunがMAXの閉路分解要素の時間 － ダミー時間

存在の証明
閉路分解をoverrun昇順にソート、
overrun = 0 の周回は、ダミーを捨ててSからGまで
それ以外は、ダミーをの除いてGから開始



-/-----
---/---
-----
--








************************************************************************
************************************************************************
************************************************************************
************************************************************************

"12_3" > 6秒
"313__" > 8秒
"4_35_1264_23_434" > 60秒
"123456789123456789" > 98秒
"88967472612377988186" > 149秒
"19898693316679441672" > 170秒
"93769682716711132249893" > ?

// http://i...content-available-to-author-only...e.com/FrRkof
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!