抄録
Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Challenging Exploratory Research, Fund Type: -, Overall Grant Amount: - (direct: 2900000, indirect: 870000)
We considered new frameworks on algorithms mainly on puzzles and games, and have obtained the following results: (I) For the cake-cutting problem, we presented a framework on sublinear-time algorithms and gave some algorithms in the framework. (II) For the generalized shogi problem, we presented a constant-time algorithm, i.e., we showed that it is constant-time solvable. (III) For river crossing problems, we presented a new formulation that requires prohibited states for inputs and gave a polynomial-time algorithms by using expanders. (IV) For generalized shogi with n signs, we considered jankens in which draws between different signs are allowed, and found some properties, e.g., tight upper and lower bounds of the number of draws.