test/yukicoder/1106.test.cpp

• View this file on GitHub
• Last update: 2024-10-11 11:57:14+09:00
• Problem: https://yukicoder.me/problems/no/1106

Depends on

• オートマトン上のDP (src/Misc/Automaton.hpp)

Code

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/1106
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include "src/Misc/Automaton.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 vector alp= {-2, -1, 0, 1, 2};
 int64_t N;
 cin >> N;
 auto tr_le= [&](int64_t s, int c) { return (s - c + 5) / 5 - 1; };
 Automaton dfa_le(alp, N, tr_le, [](int64_t) { return true; }, int64_t(-1));
 auto tr_pos= [&](bool s, int c) {
  if (c > 0) s= 1;
  else if (c < 0) s= 0;
  return s;
 };
 Automaton dfa_pos(alp, false, tr_pos, [](bool s) { return s; });
 auto tr_eq= [&](int s, int c) {
  if (abs(s) > 100) return s;
  return s + c;
 };
 Automaton dfa_eq(alp, 0, tr_eq, [](int s) { return s == 0; });
 auto dfa= dfa_le & dfa_pos & dfa_eq;
 cout << dfa.num<int64_t>(60) << '\n';
 return 0;
}

#line 1 "test/yukicoder/1106.test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/1106
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#line 2 "src/Misc/Automaton.hpp"
#include <type_traits>
#include <set>
#include <map>
#include <unordered_map>
#line 7 "src/Misc/Automaton.hpp"
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <cassert>
template <class symbol_t> class Automaton {
 std::vector<int> table;
 std::vector<int8_t> info;
 std::vector<symbol_t> alph;
 const int m;
 template <class Map, class state_t, class F, class G, class H> void build(const state_t &initial_state, const F &transition, const G &is_accept, const H &abs_reject) {
  static_assert(std::is_same_v<bool, std::invoke_result_t<G, state_t>>);
  static_assert(std::is_same_v<bool, std::invoke_result_t<H, state_t>>);
  Map encode;
  std::vector<state_t> decode;
  int ts= 0;
  decode.push_back(initial_state), encode.emplace(initial_state, ts++);
  for (int i= 0, k= 0; i < ts; ++i) {
   auto s= decode[i];
   table.resize(table.size() + m);
   for (int j= 0; j < m; ++j) {
    if (auto t= transition(s, j); abs_reject(t)) table[k++]= -1;
    else if (auto it= encode.find(t); it != encode.end()) table[k++]= it->second;
    else table[k++]= ts, decode.push_back(t), encode.emplace(t, ts++);
   }
  }
  info.resize(ts);
  for (int i= ts; i--;) info[i]= is_accept(decode[i]);
 }
 Automaton(const std::vector<symbol_t> &alphabet): alph(alphabet), m(alph.size()) {}
public:
 template <class state_t, class F, class G, std::enable_if_t<std::is_invocable_r_v<state_t, F, state_t, symbol_t>, std::nullptr_t> = nullptr> Automaton(const std::vector<symbol_t> &alphabet, const state_t &initial_state, const F &transition, const G &is_accept): alph(alphabet), m(alph.size()) {
  std::sort(alph.begin(), alph.end());
  auto tr= [&](const state_t &s, int i) { return transition(s, alph[i]); };
  auto rej= [](const state_t &) { return false; };
  if constexpr (std::is_integral_v<state_t>) build<std::unordered_map<state_t, int>, state_t>(initial_state, tr, is_accept, rej);
  else build<std::map<state_t, int>, state_t>(initial_state, tr, is_accept, rej);
 }
 template <class state_t, class F, class G, std::enable_if_t<std::is_invocable_r_v<state_t, F, state_t, symbol_t>, std::nullptr_t> = nullptr> Automaton(const std::vector<symbol_t> &alphabet, const state_t &initial_state, const F &transition, const G &is_accept, const state_t &abs_rej_state): alph(alphabet), m(alph.size()) {
  std::sort(alph.begin(), alph.end());
  auto tr= [&](const state_t &s, int i) { return transition(s, alph[i]); };
  auto rej= [abs_rej_state](const state_t &s) { return s == abs_rej_state; };
  if constexpr (std::is_integral_v<state_t>) build<std::unordered_map<state_t, int>, state_t>(initial_state, tr, is_accept, rej);
  else build<std::map<state_t, int>, state_t>(initial_state, tr, is_accept, rej);
 }
 template <class state_t, class F, class G, std::enable_if_t<std::is_invocable_r_v<std::set<state_t>, F, state_t, symbol_t>, std::nullptr_t> = nullptr> Automaton(const std::vector<symbol_t> &alphabet, const state_t &initial_state, const F &transition, const G &is_accept): alph(alphabet), m(alph.size()) {
  static_assert(std::is_same_v<bool, std::invoke_result_t<G, state_t>>);
  std::sort(alph.begin(), alph.end());
  auto tr= [&](const std::set<state_t> &s, int i) {
   std::set<state_t> ret;
   for (const auto &x: s) {
    auto ys= transition(x, alph[i]);
    ret.insert(ys.begin(), ys.end());
   }
   return ret;
  };
  auto ac= [&](const std::set<state_t> &s) { return std::any_of(s.begin(), s.end(), is_accept); };
  auto rej= [](const std::set<state_t> &s) { return s == std::set<state_t>(); };
  build<std::map<std::set<state_t>, int>, std::set<state_t>>(std::set<state_t>({initial_state}), tr, ac, rej);
 }
 template <class state_t, class F, class G, class H, std::enable_if_t<std::is_invocable_r_v<std::set<state_t>, F, state_t, symbol_t>, std::nullptr_t> = nullptr> Automaton(const std::vector<symbol_t> &alphabet, const state_t &initial_state, const F &transition, const G &is_accept, const H &eps_trans): alph(alphabet), m(alph.size()) {
  static_assert(std::is_same_v<bool, std::invoke_result_t<G, state_t>>);
  static_assert(std::is_same_v<std::set<state_t>, std::invoke_result_t<H, state_t>>);
  std::sort(alph.begin(), alph.end());
  auto eps_closure= [&](std::set<state_t> s) {
   for (std::set<state_t> t; s != t;) {
    t= s;
    for (const auto &x: t) {
     auto ys= eps_trans(x);
     s.insert(ys.begin(), ys.end());
    }
   }
   return s;
  };
  auto tr= [&](const std::set<state_t> &s, int i) {
   std::set<state_t> ret;
   for (const auto &x: s) {
    auto ys= transition(x, alph[i]);
    ret.insert(ys.begin(), ys.end());
   }
   return eps_closure(ret);
  };
  auto ac= [&](const std::set<state_t> &s) { return std::any_of(s.begin(), s.end(), is_accept); };
  auto rej= [](const std::set<state_t> &s) { return s == std::set<state_t>(); };
  build<std::map<std::set<state_t>, int>, std::set<state_t>>(eps_closure({initial_state}), tr, ac, rej);
 }
 Automaton operator&(const Automaton &r) const {
  assert(alph == r.alph);
  const int S= info.size();
  auto tr= [&](int s, int q) {
   auto [s1, s0]= std::div(s, S);
   int t1= r.table[s1 * m + q], t0= table[s0 * m + q];
   return t0 == -1 || t1 == -1 ? -1 : t1 * S + t0;
  };
  auto ac= [&](int s) {
   auto [s1, s0]= std::div(s, S);
   return info[s0] == 1 && r.info[s1] == 1;
  };
  auto rej= [](int s) { return s == -1; };
  Automaton ret(alph);
  return ret.build<std::unordered_map<int, int>, int>(0, tr, ac, rej), ret;
 }
 template <class T, class A, class F> T dp_run(int n, const A &op, const T &ti, const F &f, const T &init) const {
  static_assert(std::is_same_v<T, std::invoke_result_t<A, T, T>>);
  static_assert(std::is_same_v<T, std::invoke_result_t<F, T, symbol_t, int>>);
  const size_t S= info.size();
  std::queue<std::pair<int, int>> que;
  T dp[2][S], ret= ti;
  bool in[2][S];
  for (std::fill_n(dp[0], S, ti), std::fill_n(dp[1], S, ti), std::fill_n(in[0], S, 0), std::fill_n(in[1], S, 0), dp[0][0]= init, que.emplace(0, 0), in[0][0]= 1; que.size();) {
   auto [s, i]= que.front();
   bool b= i & 1;
   T tmp= dp[b][s];
   if (que.pop(), in[b][s]= 0, dp[b][s]= ti; i == n) {
    if (info[s] == 1) ret= op(ret, tmp);
    continue;
   }
   auto l= table.cbegin() + s * m;
   for (int j= m; j--;)
    if (int t= l[j]; t != -1)
     if (dp[!b][t]= op(dp[!b][t], f(tmp, alph[j], i)); !in[!b][t]) que.emplace(t, i + 1), in[!b][t]= 1;
  }
  return ret;
 }
 template <class T> T num(int n) const {
  return dp_run(n, [](const T &l, const T &r) { return l + r; }, T(), [](const T &x, const auto &, auto) { return x; }, T(1));
 }
};
#line 7 "test/yukicoder/1106.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 vector alp= {-2, -1, 0, 1, 2};
 int64_t N;
 cin >> N;
 auto tr_le= [&](int64_t s, int c) { return (s - c + 5) / 5 - 1; };
 Automaton dfa_le(alp, N, tr_le, [](int64_t) { return true; }, int64_t(-1));
 auto tr_pos= [&](bool s, int c) {
  if (c > 0) s= 1;
  else if (c < 0) s= 0;
  return s;
 };
 Automaton dfa_pos(alp, false, tr_pos, [](bool s) { return s; });
 auto tr_eq= [&](int s, int c) {
  if (abs(s) > 100) return s;
  return s + c;
 };
 Automaton dfa_eq(alp, 0, tr_eq, [](int s) { return s == 0; });
 auto dfa= dfa_le & dfa_pos & dfa_eq;
 cout << dfa.num<int64_t>(60) << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	_sample00	AC	6 ms	4 MB
g++-13	_sample01	AC	5 ms	4 MB
g++-13	_sample02	AC	5 ms	4 MB
g++-13	_sample03	AC	5 ms	4 MB
g++-13	_sample04	AC	6 ms	4 MB
g++-13	test00	AC	5 ms	4 MB
g++-13	test01	AC	5 ms	4 MB
g++-13	test02	AC	5 ms	4 MB
g++-13	test03	AC	5 ms	4 MB
g++-13	test04	AC	5 ms	4 MB
g++-13	test05	AC	5 ms	4 MB
g++-13	test06	AC	5 ms	4 MB
g++-13	test07	AC	5 ms	4 MB
g++-13	test08	AC	5 ms	4 MB
g++-13	test09	AC	5 ms	4 MB
g++-13	test10	AC	5 ms	4 MB
g++-13	test11	AC	5 ms	4 MB
g++-13	test12	AC	5 ms	4 MB
g++-13	test13	AC	5 ms	4 MB
g++-13	test14	AC	5 ms	4 MB
g++-13	test15	AC	5 ms	4 MB
g++-13	test16	AC	5 ms	4 MB
g++-13	test17	AC	5 ms	4 MB
g++-13	test18	AC	6 ms	4 MB
g++-13	test19	AC	6 ms	4 MB
g++-13	test20	AC	6 ms	4 MB
g++-13	test21	AC	6 ms	4 MB
g++-13	test22	AC	6 ms	4 MB
g++-13	test23	AC	6 ms	4 MB
g++-13	test24	AC	6 ms	4 MB
g++-13	test25	AC	6 ms	4 MB
g++-13	test26	AC	6 ms	4 MB
g++-13	test27	AC	6 ms	4 MB
g++-13	test28	AC	6 ms	4 MB
g++-13	test29	AC	6 ms	4 MB
g++-13	test30	AC	6 ms	4 MB
g++-13	test31	AC	6 ms	4 MB
g++-13	test32	AC	6 ms	4 MB
g++-13	test33	AC	6 ms	4 MB
g++-13	test34	AC	6 ms	4 MB
g++-13	test35	AC	6 ms	4 MB
g++-13	test36	AC	6 ms	4 MB
g++-13	test37	AC	6 ms	4 MB
g++-13	test38	AC	6 ms	4 MB
g++-13	test39	AC	6 ms	4 MB
g++-13	test40	AC	6 ms	4 MB
g++-13	test41	AC	6 ms	4 MB
g++-13	test42	AC	6 ms	4 MB
g++-13	test43	AC	6 ms	4 MB
g++-13	test44	AC	6 ms	4 MB
g++-13	test45	AC	6 ms	4 MB
g++-13	test46	AC	6 ms	4 MB
g++-13	test47	AC	6 ms	4 MB
g++-13	test48	AC	6 ms	4 MB
g++-13	test49	AC	6 ms	4 MB
g++-13	test50	AC	6 ms	4 MB
g++-13	test51	AC	6 ms	4 MB
g++-13	test52	AC	6 ms	4 MB
g++-13	test53	AC	6 ms	4 MB
g++-13	test54	AC	6 ms	4 MB
g++-13	test55	AC	6 ms	4 MB
g++-13	test56	AC	6 ms	4 MB
g++-13	test57	AC	6 ms	4 MB
g++-13	test58	AC	6 ms	4 MB
g++-13	test59	AC	6 ms	4 MB
g++-13	test60	AC	6 ms	4 MB
g++-13	test61	AC	6 ms	4 MB
g++-13	test62	AC	6 ms	4 MB
g++-13	test63	AC	6 ms	4 MB
g++-13	test64	AC	6 ms	4 MB
g++-13	test65	AC	6 ms	4 MB
g++-13	test66	AC	6 ms	4 MB
g++-13	test67	AC	6 ms	4 MB
g++-13	test68	AC	6 ms	4 MB
g++-13	test69	AC	6 ms	4 MB
g++-13	test70	AC	6 ms	4 MB
g++-13	test71	AC	6 ms	4 MB
g++-13	test72	AC	6 ms	4 MB
g++-13	test73	AC	6 ms	4 MB
g++-13	test74	AC	6 ms	4 MB
g++-13	test75	AC	6 ms	4 MB
g++-13	test76	AC	6 ms	4 MB
clang++-18	_sample00	AC	6 ms	4 MB
clang++-18	_sample01	AC	5 ms	4 MB
clang++-18	_sample02	AC	5 ms	4 MB
clang++-18	_sample03	AC	5 ms	4 MB
clang++-18	_sample04	AC	6 ms	4 MB
clang++-18	test00	AC	5 ms	4 MB
clang++-18	test01	AC	5 ms	4 MB
clang++-18	test02	AC	5 ms	4 MB
clang++-18	test03	AC	5 ms	4 MB
clang++-18	test04	AC	5 ms	4 MB
clang++-18	test05	AC	5 ms	4 MB
clang++-18	test06	AC	5 ms	4 MB
clang++-18	test07	AC	5 ms	4 MB
clang++-18	test08	AC	5 ms	4 MB
clang++-18	test09	AC	5 ms	4 MB
clang++-18	test10	AC	5 ms	4 MB
clang++-18	test11	AC	5 ms	4 MB
clang++-18	test12	AC	5 ms	4 MB
clang++-18	test13	AC	5 ms	4 MB
clang++-18	test14	AC	5 ms	4 MB
clang++-18	test15	AC	5 ms	4 MB
clang++-18	test16	AC	5 ms	4 MB
clang++-18	test17	AC	6 ms	4 MB
clang++-18	test18	AC	6 ms	4 MB
clang++-18	test19	AC	6 ms	4 MB
clang++-18	test20	AC	6 ms	4 MB
clang++-18	test21	AC	6 ms	4 MB
clang++-18	test22	AC	6 ms	4 MB
clang++-18	test23	AC	6 ms	4 MB
clang++-18	test24	AC	6 ms	4 MB
clang++-18	test25	AC	6 ms	4 MB
clang++-18	test26	AC	6 ms	4 MB
clang++-18	test27	AC	6 ms	4 MB
clang++-18	test28	AC	6 ms	4 MB
clang++-18	test29	AC	6 ms	4 MB
clang++-18	test30	AC	6 ms	4 MB
clang++-18	test31	AC	6 ms	4 MB
clang++-18	test32	AC	6 ms	4 MB
clang++-18	test33	AC	6 ms	4 MB
clang++-18	test34	AC	6 ms	4 MB
clang++-18	test35	AC	6 ms	4 MB
clang++-18	test36	AC	6 ms	4 MB
clang++-18	test37	AC	6 ms	4 MB
clang++-18	test38	AC	6 ms	4 MB
clang++-18	test39	AC	6 ms	4 MB
clang++-18	test40	AC	6 ms	4 MB
clang++-18	test41	AC	6 ms	4 MB
clang++-18	test42	AC	6 ms	4 MB
clang++-18	test43	AC	6 ms	4 MB
clang++-18	test44	AC	6 ms	4 MB
clang++-18	test45	AC	6 ms	4 MB
clang++-18	test46	AC	6 ms	4 MB
clang++-18	test47	AC	6 ms	4 MB
clang++-18	test48	AC	6 ms	4 MB
clang++-18	test49	AC	6 ms	4 MB
clang++-18	test50	AC	6 ms	4 MB
clang++-18	test51	AC	6 ms	4 MB
clang++-18	test52	AC	6 ms	4 MB
clang++-18	test53	AC	6 ms	4 MB
clang++-18	test54	AC	6 ms	4 MB
clang++-18	test55	AC	6 ms	4 MB
clang++-18	test56	AC	6 ms	4 MB
clang++-18	test57	AC	6 ms	4 MB
clang++-18	test58	AC	6 ms	4 MB
clang++-18	test59	AC	6 ms	4 MB
clang++-18	test60	AC	6 ms	4 MB
clang++-18	test61	AC	6 ms	4 MB
clang++-18	test62	AC	6 ms	4 MB
clang++-18	test63	AC	6 ms	4 MB
clang++-18	test64	AC	6 ms	4 MB
clang++-18	test65	AC	6 ms	4 MB
clang++-18	test66	AC	6 ms	4 MB
clang++-18	test67	AC	6 ms	4 MB
clang++-18	test68	AC	6 ms	4 MB
clang++-18	test69	AC	6 ms	4 MB
clang++-18	test70	AC	6 ms	4 MB
clang++-18	test71	AC	6 ms	4 MB
clang++-18	test72	AC	6 ms	4 MB
clang++-18	test73	AC	6 ms	4 MB
clang++-18	test74	AC	6 ms	4 MB
clang++-18	test75	AC	6 ms	4 MB
clang++-18	test76	AC	6 ms	4 MB

Back to top page