提出 #38172961

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) ;
#endif

// clang-format off
#define rep(i, n) for (int i = 0; (i) < (int)(n); (i)++)

template<class T> bool chmax(T &a, const T &b) {if(a<b) {a=b; return true;} return false; }
template<class T> bool chmin(T &a, const T &b) {if(a>b) {a=b; return true;} return false; }

template<class T> istream& operator>>(istream& is, vector<T>& vec){ rep(i, vec.size()) is >> vec[i]; return is;}
template<class T> ostream& operator<<(ostream& os, vector<T>& vec){ rep(i, vec.size()) os << vec[i] << (i+1==(int)vec.size() ? "" : " "); return os;}
// clang-format on

using ll = long long;
using ull = unsigned long long;

// valより大きい最小の要素を返す
// @note 条件を満たす要素がない場合はendイテレータを返す
template <class T>
typename set<T>::const_iterator find_min_greater(const set<T>& val_set, const T& val) {
   auto it = val_set.upper_bound(val);
   return it;
}

using P = pair<ll, ll>;

P next_pos(char c, int x, int y) {
   if (c == 'L') x--;
   if (c == 'R') x++;
   if (c == 'U') y++;
   if (c == 'D') y--;
   return P(x, y);
};

pair<int, int> move(string S) {
   int x = 0, y = 0;

   for (auto c : S) {
      tie(x, y) = next_pos(c, x, y);
   }

   return {x, y};
}

string normalize(string S) {
   auto [X, Y] = move(S);

   if (X == 0 && Y == 0) {
      set<P> p_set;
      int x = 0, y = 0;

      S += 'X';

      for (auto c : S) {
         if (c == 'X') break;

         p_set.emplace(x, y);
         tie(x, y) = next_pos(c, x, y);
      }

      cout << p_set.size() << endl;
      exit(0);
   }

   if (X < 0) {
      // L,R flip
      rep(i, S.size()) {
         auto c = S[i];
         if (c == 'L') S[i] = 'R';
         if (c == 'R') S[i] = 'L';
      }

      X *= -1;
   }

   if (Y < 0) {
      // U, D flip
      rep(i, S.size()) {
         auto c = S[i];
         if (c == 'U') S[i] = 'D';
         if (c == 'D') S[i] = 'U';
      }

      Y *= -1;
   }

   if (X == 0) {
      // X, Y flip
      rep(i, S.size()) {
         auto c = S[i];
         if (c == 'R') S[i] = 'U';
         if (c == 'L') S[i] = 'D';
         if (c == 'U') S[i] = 'R';
         if (c == 'D') S[i] = 'L';
      }
   }

   return S;
}

int main() {
   string oS;
   ll K;
   cin >> oS >> K;

   string S = normalize(oS);
   ll X, Y;
   tie(X, Y) = move(S);

   // X>0, Y>=0
   assert(X > 0 && Y >= 0);

   vector<P> pl;
   ll x = 0, y = 0;
   pl.emplace_back(0, 0);

   for (auto c : S) {
      tie(x, y) = next_pos(c, x, y);
      pl.emplace_back(x, y);
   }

   map<ll, ll> min_val;

   auto calc_group = [&](ll x, ll y) -> pair<ll, ll> {
      ll c = X * y - Y * x;
      ll group = ((x % X) + X) % X;
      return {c, group};
   };

   map<pair<ll, ll>, set<ll>> line_info;

   for (auto [x, y] : pl) {
      auto gi = calc_group(x, y);

      line_info[gi].insert(x);
   }

   ll ans = 0;
   set<P> visited;

   for (auto [x, y] : pl) {
      if (visited.count({x, y})) continue;
      visited.emplace(x, y);

      auto gi = calc_group(x, y);
      ll sub_ans = 0;

      auto it = find_min_greater(line_info[gi], x);

      if (it == line_info[gi].end()) {
         // debug(x, y, k, K);
         sub_ans = K;
      } else {
         auto diff_k = (*it - x) / X;
         // debug(x, *it, X, diff_k);
         sub_ans = min(K, diff_k);
         // debug(x, y, k, diff_k);
      }

      ans += sub_ans;
   }

   cout << ans << endl;

   return 0;
}

提出情報

ジャッジ結果