1# from titan_pylib.others.SA import SA
2import sys
3from time import process_time
4from math import exp
5from typing import TypeVar
6# from titan_pylib.algorithm.random.random import Random
7from typing import Any
8
9
10class Random:
11 """Random
12 乱数系のライブラリです。
13 標準ライブラリよりも高速なつもりでいます。
14 """
15
16 def __init__(self) -> None:
17 self._x = 123456789
18 self._y = 362436069
19 self._z = 521288629
20 self._w = 88675123
21
22 def _xor(self) -> int:
23 t = (self._x ^ ((self._x << 11) & 0xFFFFFFFF)) & 0xFFFFFFFF
24 self._x, self._y, self._z = self._y, self._z, self._w
25 self._w = (self._w ^ (self._w >> 19)) ^ (
26 t ^ ((t >> 8)) & 0xFFFFFFFF
27 ) & 0xFFFFFFFF
28 return self._w
29
30 def random(self) -> float:
31 """0以上1以下の一様ランダムな値を1つ生成して返すはずです。
32 :math:`O(1)` です。
33 """
34 return self._xor() / 0xFFFFFFFF
35
36 def randint(self, begin: int, end: int) -> int:
37 """``begin`` 以上 ``end`` **以下** のランダムな整数を返します。
38 :math:`O(1)` です。
39
40 制約:
41 :math:`begin \\leq end`
42 """
43 assert begin <= end
44 return begin + self._xor() % (end - begin + 1)
45
46 def randrange(self, begin: int, end: int) -> int:
47 """``begin`` 以上 ``end`` **未満** のランダムな整数を返します。
48 :math:`O(1)` です。
49
50 制約:
51 :math:`begin < end`
52 """
53 assert begin < end
54 return begin + self._xor() % (end - begin)
55
56 def shuffle(self, a: list[Any]) -> None:
57 """``a`` をインプレースにシャッフルします。
58 :math:`O(n)` です。
59
60 Args:
61 a (list[Any]): ``a`` をシャッフルします。
62 """
63 n = len(a)
64 for i in range(n - 1):
65 j = self.randrange(i, n)
66 a[i], a[j] = a[j], a[i]
67
68
69class State:
70
71 def __init__(self) -> None:
72 pass
73
74 def copy(self) -> "State":
75 pass
76
77
78class SA:
79
80 Changed = TypeVar("Changed")
81
82 def __init__(self):
83 self.random = Random()
84
85 def make_ans_init(self) -> tuple[State, int]:
86 return
87
88 def modify(self, state: State) -> tuple[int, Changed]:
89 # state は変更される
90 return
91
92 def rollback(self, state: State, changed: Changed) -> None:
93 return
94
95 def sovle(
96 self, START_TEMP: float = 100, END_TEMP: float = 10, TIME_LIMIT: float = 1.8
97 ) -> tuple[State, int]:
98 START_TIME = process_time()
99 random = self.random
100 ans, score = self.make_ans_init()
101 vest_ans = ans.copy()
102 vest_score = score
103 cnt = 0
104 while True:
105 now_time = process_time() - START_TIME
106 if now_time > TIME_LIMIT:
107 break
108 cnt += 1
109 diff_score, changed = self.modify(ans)
110 new_score = score + diff_score
111 temp = START_TEMP + (END_TEMP - START_TEMP) * now_time / TIME_LIMIT
112 arg = new_score - score
113 if arg >= 1 or exp(arg / temp) > random.random():
114 score = new_score
115 if new_score > vest_score:
116 vest_score = new_score
117 vest_ans = ans.copy()
118 else:
119 self.rollback(ans, changed)
120 print(f"{cnt=}", file=sys.stderr)
121 return vest_ans, vest_score