結果
問題 | No.874 正規表現間距離 |
ユーザー |
![]() |
提出日時 | 2019-08-30 22:58:10 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,959 bytes |
コンパイル時間 | 479 ms |
コンパイル使用メモリ | 63,676 KB |
最終ジャッジ日時 | 2024-11-14 21:36:13 |
合計ジャッジ時間 | 1,123 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In function 'void n91::main_()': main.cpp:120:51: error: 'numeric_limits' is not a member of 'std' 120 | md_vec(a.size() + 1_z, b.size() + 1_z, std::numeric_limits<usize>::max()); | ^~~~~~~~~~~~~~ main.cpp:120:71: error: expected primary-expression before '>' token 120 | md_vec(a.size() + 1_z, b.size() + 1_z, std::numeric_limits<usize>::max()); | ^ main.cpp:120:74: error: '::max' has not been declared; did you mean 'std::max'? 120 | md_vec(a.size() + 1_z, b.size() + 1_z, std::numeric_limits<usize>::max()); | ^~~ | std::max In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/algorithm:61, from main.cpp:77: /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algo.h:5756:5: note: 'std::max' declared here 5756 | max(initializer_list<_Tp> __l, _Compare __comp) | ^~~
ソースコード
//#define NDEBUG#include <cstddef>#include <cstdint>#include <iostream>#include <vector>namespace n91 {using i8 = std::int_fast8_t;using i32 = std::int_fast32_t;using i64 = std::int_fast64_t;using u8 = std::uint_fast8_t;using u32 = std::uint_fast32_t;using u64 = std::uint_fast64_t;using isize = std::ptrdiff_t;using usize = std::size_t;constexpr usize operator"" _z(unsigned long long x) noexcept {return static_cast<usize>(x);}class rep {const usize f, l;public:class itr {friend rep;usize i;constexpr itr(const usize x) noexcept : i(x) {}public:void operator++() noexcept { ++i; }constexpr usize operator*() const noexcept { return i; }constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }};constexpr rep(const usize first, const usize last) noexcept: f(first), l(last) {}constexpr itr begin() const noexcept { return itr(f); }constexpr itr end() const noexcept { return itr(l); }};class revrep {const usize f, l;public:class itr {friend revrep;usize i;constexpr itr(usize x) noexcept : i(x) {}public:void operator++() noexcept { --i; }constexpr usize operator*() const noexcept { return i; }constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }};constexpr revrep(usize first, usize last) noexcept : f(--first), l(--last) {}constexpr itr begin() const noexcept { return itr(l); }constexpr itr end() const noexcept { return itr(f); }};template <class T> using vec_alias = std::vector<T>;template <class T> auto md_vec(const usize n, const T &value) {return std::vector<T>(n, value);}template <class... Args> auto md_vec(const usize n, Args... args) {return std::vector<decltype(md_vec(args...))>(n, md_vec(args...));}template <class T> constexpr T difference(const T &a, const T &b) {return a < b ? b - a : a - b;}template <class T> T scan() {T ret;std::cin >> ret;return ret;}} // namespace n91#include <algorithm>#include <iostream>#include <string>#include <utility>namespace n91 {void main_() {enum exp_type {normal,question,asterisk,};struct node_type {char x;exp_type t;};const auto input = []() {std::string s;std::cin >> s;std::vector<node_type> ret;for (usize i = 0_z; i != s.size(); ++i) {if (i != s.size()) {if (s[i + 1_z] == '?') {ret.push_back({s[i], question});++i;} else if (s[i + 1_z] == '*') {ret.push_back({s[i], asterisk});++i;} else {ret.push_back({s[i], normal});}} else {ret.push_back({s[i], normal});}}return ret;};const auto a = input();const auto b = input();auto dp =md_vec(a.size() + 1_z, b.size() + 1_z, std::numeric_limits<usize>::max());dp[0_z][0_z] = 0_z;for (const auto i : rep(0_z, a.size() + 1_z)) {for (const auto j : rep(0_z, b.size() + 1_z)) {if (i != 0_z) {usize temp = dp[i - 1_z][j];if (a[i - 1_z].t == normal && (j == 0_z || b[j - 1_z].t != asterisk ||a[i - 1_z].x != b[j - 1_z].x)) {++temp;}dp[i][j] = std::min(dp[i][j], temp);}if (j != 0_z) {usize temp = dp[i][j - 1_z];if (b[j - 1_z].t == normal && (i == 0_z || a[i - 1_z].t != asterisk ||b[j - 1_z].x != a[i - 1_z].x)) {++temp;}dp[i][j] = std::min(dp[i][j], temp);}if (i != 0_z && j != 0_z) {usize temp = dp[i - 1_z][j - 1_z];if (a[i - 1_z].x != b[j - 1_z].x) {++temp;}dp[i][j] = std::min(dp[i][j], temp);}}}std::cout << dp[a.size()][b.size()] << std::endl;} // namespace n91} // namespace n91int main() {n91::main_();return 0;}