O(ElogV)ダイクストラのテンプレ
O(ElogV)ダイクストラのテンプレ
#include <queue> #include <vector> #include <functional> #include <utility> #include <algorithm> #include <iterator> using COST_T = uint32_t; constexpr uint32_t N_MAX = 変える; constexpr COST_T INF = 変える;//std::numeric_limits<double>::infinity() #if defined(_MSC_VER) && defined(_DEBUG) static_assert(false, "リリースでコンパイルしないと遅いよ!!"); #endif struct edge { uint32_t to; COST_T cost; edge() {} edge(uint32_t to_, COST_T cost_) :to(to_), cost(cost_) {} }; std::vector<edge> graph[N_MAX]; //O(ElogV)ダイクストラ COST_T D[N_MAX]; void Dijkstra(uint32_t s) { using P = std::pair<COST_T, uint32_t>;//cost pos std::priority_queue<P, std::vector<P>, std::greater<P> > que; std::fill(std::begin(D), std::end(D), INF); D[s] = 0; que.emplace(0, s); while (!que.empty()) { auto p = que.top(); que.pop(); const auto& nowpos = p.second; const auto& nowcost = p.first; if (D[nowpos] < nowcost) { continue; } for (const auto& e : graph[nowpos]) { auto cost = nowcost + e.cost; if (cost < D[e.to]) { D[e.to] = cost; que.emplace(cost, e.to); } } } }
使用例
Dijkstra(0);
N次元配列を同じ値で埋めるテンプレ2
N次元配列を同じ値で埋めるテンプレ
キャストが要らないバージョン
シンプルなのはこっち:N次元配列を同じ値で埋めるテンプレ - 永夜の記録
#include <type_traits> template<typename T, typename U> typename std::enable_if<std::rank<T>::value == 0>::type fill_all(T& arr, const U& v) { arr = v; } template<typename ARR, typename U> typename std::enable_if<std::rank<ARR>::value!=0>::type fill_all(ARR& arr, const U& v) { for (auto& i : arr) { fill_all(i, v); } }
使用例
long long dp[1000][1000]; fill_all(dp,-1);//キャストが要らない
C++14用mod_int
C++14用mod_intです。勝手にmodを取ります。
型名はmintです。
using mint = mint_base<1000000007>;
の1000000007がとるmodになります。
+-*/やインクリメント,デクリメントが出来ます。
~で逆元を取れますが、そのままでも割り算が使えます。(どちらもlogMODで、偶に定数倍でTLEするので、その時は事前計算してください)
ストリーム演算子があるので、>>や<<で入出力が出来ます。
繰り返し二乗法(ipow),階乗(fact_set),組み合わせ(combination)も一緒に入ってます。
ユーザー定義リテラル_miがあるので、mint(1)の代わりに1_miと出来ます。
#include <algorithm> #include <utility> #include <type_traits> #include <cstdint> template<typename Arithmetic, typename Integral> std::enable_if_t< std::is_unsigned<Integral>::value, Arithmetic> ipow(Arithmetic bace, Integral n) { //繰り返し二条法 auto res = (Arithmetic)(1); while (n > 0) { if (n & 1) res *= bace; bace *= bace; n >>= 1; } return res; } constexpr bool is_prime(uint32_t N) { if (N <= 1) { return false; } for (size_t i = 2; i*i <= N; ++i) { if (N%i == 0) { return false; } } return true; } template <uint64_t MOD> class mint_base; //mint_base_base型用の累乗関数 template <uint64_t MOD> constexpr mint_base<MOD> m_pow(mint_base<MOD> x, uint64_t n)noexcept; //mod計算を自動で行う整数テンプレートクラス template <uint64_t MOD_ = 1000000007> class mint_base { public: static constexpr auto MOD = MOD_; static_assert(!(MOD <= 2), "MOD cannot be below 2."); static_assert(MOD <= (0xFFFFFFFFFFFFFFFF / 2), "MOD is too big");//加算してオーバーフローしない static_assert(MOD <= 0xFFFFFFFF, "MOD is too big");//乗算してオーバーフローしない constexpr mint_base<MOD> operator+(const mint_base<MOD> &other)const noexcept { auto v = *this; return v += other; } constexpr mint_base<MOD> operator-(const mint_base<MOD> &other)const noexcept { auto v = *this; return v -= other; } constexpr mint_base<MOD> operator*(const mint_base<MOD> &other)const noexcept { auto v = *this; return v *= other; } constexpr auto operator/(const mint_base<MOD> &other)const noexcept { auto v = *this; return v /= other; } constexpr mint_base<MOD>& operator+=(const mint_base<MOD> &other) noexcept { a += other.a; if (MOD <= a) { a -= MOD; }; return *this; } constexpr mint_base<MOD>& operator-=(const mint_base<MOD> &other) noexcept { if (a >= other.a) { a -= other.a; } else { a = (a + MOD) - other.a; } return *this; } constexpr mint_base<MOD>& operator*=(const mint_base<MOD> &other) noexcept { #if 1 a *= other.a; a %= MOD; #else //MOD <= (MAXUINT64 / 2)条件下 uint64_t b = other.a, v = 0; while (b > 0) { if (b & 1) { v += a; if (v >= MOD)v -= MOD; } a += a; if (MOD <= a)a -= MOD; b >>= 1; } a = v; #endif return *this; } constexpr mint_base<MOD>& operator/=(const mint_base<MOD> &other) noexcept { return *this *= ~other; } constexpr mint_base<MOD> operator+()const noexcept { return *this; } constexpr mint_base<MOD> operator-()const noexcept { return{ MOD - a, mod_value_tag{} }; } constexpr mint_base<MOD>& operator++() noexcept { if (MOD <= ++a) { a = 0; }; return *this; } constexpr mint_base<MOD>& operator--() noexcept { if (a <= 0) { a = MOD; }; --a; return *this; } constexpr mint_base<MOD> operator++(int) noexcept { auto tmp = *this; ++*this; return tmp; } constexpr mint_base<MOD> operator--(int) noexcept { auto tmp = *this; --*this; return tmp; } constexpr mint_base<MOD> operator~()const noexcept { return ipow(*this, e_phi - 1); } constexpr mint_base<MOD>& operator=(const mint_base<MOD> &other) noexcept { a = other.a; return *this; } constexpr explicit operator uint64_t()const noexcept { return a; } constexpr explicit operator unsigned()const noexcept { return (unsigned)a; } static constexpr uint64_t getmod() noexcept { return MOD; } constexpr mint_base(uint64_t a_) noexcept :a(a_ % MOD) {} constexpr mint_base()noexcept : a(0) {} struct mod_value_tag {}; constexpr mint_base(uint64_t a_, mod_value_tag) :a(a_) {} private: static constexpr uint64_t get_e_phi()noexcept { //オイラー値の導出 uint64_t temp = MOD; uint64_t m_ = MOD; for (uint64_t i = 2; i * i <= m_; ++i) { if (m_ % i == 0) { temp = temp / i * (i - 1); for (; m_ % i == 0; m_ /= i); } } if (m_ != 1)temp = temp / m_ * (m_ - 1); return temp; } static constexpr uint64_t e_phi = get_e_phi();//オイラー値 uint64_t a; }; //mint_base型用の累乗関数 template<uint64_t MOD>constexpr mint_base<MOD> m_pow(mint_base<MOD> x, uint64_t n)noexcept { mint_base<MOD> res = 1; while (n > 0) { if (n & 1)res *= x; x *= x; n >>= 1; } return res; } //mint_baseの階乗計算 //O(x)時間が必要のため、fact_set関数を推奨する。 template<uint64_t MOD>constexpr mint_base<MOD> fact(mint_base<MOD> x)noexcept { mint_base<MOD> res(1); for (uint64_t i = 1; i <= (uint64_t)x; ++i) { res *= i; } return res; } //mint_baseの階乗計算 //0からxまでの階乗を返す //O(x)時間が必要 template<uint64_t MOD>std::vector<mint_base<MOD>> fact_set(mint_base<MOD> x = mint_base<MOD>(-1)) { mint_base<MOD> res(1); std::vector<mint_base<MOD>> set((uint64_t)(x)+1); set[0] = 1; for (uint64_t i = 1; i <= (uint64_t)x; ++i) { res *= i; set[i] = res; } return res; } //mint_base型のstreamへの出力 template<uint64_t MOD> std::ostream& operator<<(std::ostream& os, mint_base<MOD> i) { os << (uint64_t)i; return os; } //mint_base型のstreamからの入力 template<uint64_t MOD> std::istream& operator >> (std::istream& is, mint_base<MOD>& i) { uint64_t tmp; is >> tmp; i = tmp; return is; } typedef mint_base<1000000007> mint; namespace mint_literal { constexpr mint operator""_mi(unsigned long long x)noexcept { return mint(x); } } using namespace mint_literal; //mint_baseの階乗計算 //0からxまでの階乗を返す //O(N) template<int32_t X, uint64_t MOD = mint::MOD> /*constexpr*/ std::array<mint_base<MOD>, X + 1> fact_set_c() { mint_base<MOD> res(1); std::array<mint_base<MOD>, X + 1> set; set[0] = 1; for (int32_t i = 1; i <= X; ++i) { res *= i; set[i] = res; } return set; } template<typename RET = mint, typename Integral> RET combination(Integral all, Integral get) { assert(all >= get); get = std::min(all - get, get); #if 1 //時間計算量O(1)+初期化O(NlogMOD) static const auto fact_v = fact_set_c<要素数+1>(); static const auto fact_div_v = [&]() { auto tmp = fact_v; for (auto& i : tmp) { i = ~i; } return tmp; }(); //return fact_v[all] / (fact_v[get] * fact_v[all - get]); return fact_v[all] * fact_div_v[get] * fact_div_v[all - get]; #elif 0 //時間計算量O(1) //空間計算量、初期化時間計算量O(N^2) constexpr int32_t ALL_MAX = 要素数;// 10'000; static std::vector<RET> DP_comb[ALL_MAX + 1]; if (!DP_comb[all].empty()) { return DP_comb[all][get]; } if (DP_comb[0].empty()) { DP_comb[0].resize(1); DP_comb[0][0] = (RET)1; DP_comb[1].resize(1); DP_comb[1][0] = (RET)1; } for (int32_t i = 2; i <= all; i++) { if (DP_comb[i].empty()) { int32_t size = i / 2 + 1; DP_comb[i].resize(size); DP_comb[i][0] = (RET)1; for (int32_t j = 1; j < size - 1; j++) { DP_comb[i][j] = DP_comb[i - 1][j - 1] + DP_comb[i - 1][j]; } DP_comb[i][size - 1] = DP_comb[i - 1][size - 2] + DP_comb[i - 1][(i & 1) ? (size - 1) : (size - 2)]; } } return DP_comb[all][get]; #else //時間計算量O(get * logMOD) RET ret = (RET)1; for (Integral i = 1; i <= get; ++i) { ret *= all + 1 - i; ret /= i; } return ret; #endif }
N次元配列を同じ値で埋めるテンプレ
N次元配列を同じ値で埋めるテンプレを置いておきます
template<typename T> void fill_all(T& arr, const T& v) { arr = v; } template<typename ARR, typename U> void fill_all(ARR& arr, const U& v) { for (auto& i : arr) { fill_all(i, v); } }
使用例
int dp[1000][1000]; fill_all(dp,-1);//dpの全ての要素に-1を代入
long long dp[1000][1000]; fill_all(dp,(long long)-1);//型が同じでないといけないのでキャストしてください
キャストが要らないバージョン:N次元配列を同じ値で埋めるテンプレ2 - 永夜の記録
JOI2012予選4「暑い日々」のオーバーキル考察
JOI 2012-2013 予選 問題4
これの解答に触れられているものの解説されていない想定オーバーキル考察です。
幅優先探索の一般的な罠
幅優先探索でTLEする一般的な罠の解説です。
こういうグリッドを幅優先する問題で起こりやすいですね。
C: 幅優先探索 - AtCoder Beginner Contest 007 | AtCoder
簡単のためこのような迷路を考えます。(#壁、.通行可)
/abcdef 1###### 2####G# 3###..# 4##...# 5#...## 6#S.### 7######
この迷路の幅優先探索は本来こうあるべきです
{(b,6)} ->{(b,5),(c,6)} ->{(c,5)} ->{(c,4),(d,5)} ->{(d,4)} ->{(e,4),(d,3)}
ところが、このようなコードを書くと
struct Point { int y, x; }; char map[100][100]; //HW '.'通行可、'#'通行不可 bool visited[100][100] = {}; //HW 確認したらtrueに int dist[100][100]; //HW Sからの距離 que.push(S); dist[S.y][S.x] = 0; visited[S.y][S.x] = true; while (!que.empty()) { Point now = que.front(); que.pop(); visited[now.y][now.x] = true;//見たよ!(実はこれがマズイ) const int diff[] = { 1,0,-1,0,1 }; for (int i = 0; i < 4; ++i) { int nexty = now.y + diff[i], nextx = now.x + diff[i + 1]; if (map[nexty][nextx] == '.' && visited[nexty][nextx] == false) { //まだ見ていない que.push(Point{ nexty , nextx }); dist[nexty][nextx] = dist[now.y][now.x] + 1; } } } cout << dist[G.y][G.x] << endl;
queの中身がこうなってしまいます。
{(b,6)} ->{(b,5),(c,6)} ->{(c,5),(c,5)}//ん? ->{(c,4),(d,5),(c,4),(d,5)} ->{(d,4),(d,4),(d,4),(d,4)} ->{(e,4),(d,3),(e,4),(d,3),(e,4),(d,3),(e,4),(d,3)}//あれ?
このように指数的に増えていってしまうので、TLEしてしまいます。
なぜこのようになるのかというと、
・(b,5)を見ているとき、(c,5)はまだ行ったことが無いのでqueに追加します
・(c,6)を見ているとき、(c,5)はまだ行ったことが無いのでqueに追加します
という動作になってしまっているからです。
これを解消するには、同じものを二回以上見ないように、「そこはもう調べることになっている」という段階で枝狩りしてやります。
struct Point { int y, x; }; char map[100][100]; //HW '.'通行可、'#'通行不可 bool visited[100][100] = {}; //HW 確認したらtrueに int dist[100][100]; //HW Sからの距離 que.push(S); dist[S.y][S.x] = 0; visited[S.y][S.x] = true; while (!que.empty()) { Point now = que.front(); que.pop(); const int diff[] = { 1,0,-1,0,1 }; for (int i = 0; i < 4; ++i) { int nexty = now.y + diff[i], nextx = now.x + diff[i + 1]; if (map[nexty][nextx] == '.' && visited[nexty][nextx] == false) { //まだ見ていない que.push(Point{ nexty , nextx }); dist[nexty][nextx] = dist[now.y][now.x] + 1; visited[nexty][nextx] = true;//これから見るよ!(変更箇所) } } } cout << dist[G.y][G.x] << endl;
visitedに代入するタイミングを変えただけですね。
セグ木テンプレ
C++11用オレオレセグ木テンプレです。
「変更するコードここから」の下を書き換えて使います。
segment_tree<int, 1000> seg;
で要素int,大きさ1000のセグ木が出来ます。2の累乗には勝手に拡張するので1024でなくて良いです。
これをそのまま使うのではなく、これは一例と思っておいて自分用にカスタマイズするのが良いかと思います。
#include <cstdint> inline constexpr uint32_t get_min2pow(uint32_t value, uint32_t work = 1) { return ((value <= work) ? (work) : (get_min2pow(value, work * 2))); } template<typename value_type_, uint32_t N_RAW_MAX> class segment_tree { public: using value_type = value_type_; static constexpr uint32_t N_MAX = get_min2pow(N_RAW_MAX); private: value_type default_value; value_type value[N_MAX * 2 - 1] = {}; static inline constexpr int32_t getchild(int i) { return i * 2 + 1; } static inline constexpr int32_t getparent(int i) { return (i - 1) / 2; } void Init_impl(int k = 0) { if (k < N_MAX - 1) { //ノード auto c1 = getchild(k), c2 = c1 + 1; Init_impl(c1); Init_impl(c2); value[k] = merge(value[c1], value[c2]); } else { //葉 value[k] = default_value; } } value_type query_impl(int32_t a, int32_t b, int32_t k = 0, int32_t l = 0, int32_t r = N_MAX)const { if (r <= a || b <= l)return default_value; if (a <= l && r <= b)return value[k]; int m = (l + r) / 2; return merge(query_impl(a, b, getchild(k), l, m), query_impl(a, b, getchild(k) + 1, m, r)); } public: template<typename T, typename FUNC> void change(int32_t i, T&& v, FUNC&& operation = std::plus<>{}) { i += N_MAX - 1; //葉 value[i] = std::forward<FUNC>(operation)(std::move(value[i]), std::forward<T>(v)); i = getparent(i); //ノード for (;;) { auto c1 = getchild(i), c2 = c1 + 1; value[i] = merge(value[c1], value[c2]); if (i == 0) { break; } i = getparent(i); } } //-----------------------------変更するコードここから-----------------------------// private: static inline value_type merge(const value_type& l, const value_type& r) { ここを書く; //RMQ return std::min(l, r); //RSQ return l + r; } public: inline void init() { default_value = 例外値を書く; //全ての葉にdefault_valueを設定し、親はマージで算出(非効率だけど計算量(N)だし気にしない) Init_impl(); } inline value_type query(int32_t a, int32_t b)const { //デフォルト実装は区間をマージするだけ(たぶんいじることは少ない) return query_impl(a, b); } };
使い方追記
segment_tree<int, 1000> seg; seg.init();//必要です seg.change(5,10);//5番目の要素に10加算します seg.change(10,10,[](auto,auto v){return v;});//10番目の要素を10にします seg.query(0,10);//[0,10)にクエリをします