結果

問題 No.2708 Jewel holder
ユーザー mkreemmkreem
提出日時 2024-04-03 18:39:38
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 11,805 bytes
コンパイル時間 3,659 ms
コンパイル使用メモリ 268,752 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-01 00:01:07
合計ジャッジ時間 3,875 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 1 ms
6,820 KB
testcase_03 AC 2 ms
6,824 KB
testcase_04 AC 2 ms
6,820 KB
testcase_05 AC 1 ms
6,820 KB
testcase_06 AC 2 ms
6,824 KB
testcase_07 AC 1 ms
6,820 KB
testcase_08 AC 2 ms
6,820 KB
testcase_09 AC 2 ms
6,816 KB
testcase_10 AC 1 ms
6,820 KB
testcase_11 AC 1 ms
6,820 KB
testcase_12 AC 2 ms
6,820 KB
testcase_13 AC 1 ms
6,816 KB
testcase_14 AC 1 ms
6,824 KB
testcase_15 AC 1 ms
6,820 KB
testcase_16 AC 2 ms
6,824 KB
testcase_17 AC 1 ms
6,820 KB
testcase_18 AC 2 ms
6,816 KB
testcase_19 AC 2 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifdef READ_TEMPLATE

const ll mod = 998244353; using mint = atcoder::modint998244353;
//const ll mod = 1000000007; using mint = atcoder::modint1000000007;

//------------------------------------------------------------------------------------------------------------------

//------------------------------------------------------------------------------------------------------------------



int main(){
  fast();

  int h, w; cin >> h >> w;
  vector<string> a(h);
  fore(x, a) cin >> x;

  vvv(dp, ll, h, w, 109);
  dp[0][0][1] = 1;
  rep(i, 0, h){
    rep(j, 0, w){
      erep(k, 0, 100){
        if(i == 0 and j == 0) continue;

        auto check = [&](int s, int t){
          return (!OutOfGrid(s, t, h, w) and a[s][t] != '#');
        };
        if(a[i][j] == 'o'){
          if(check(i-1, j) and k > 0) dp[i][j][k] += dp[i-1][j][k-1];
          if(check(i, j-1) and k > 0) dp[i][j][k] += dp[i][j-1][k-1];
        }
        else{
          if(check(i-1, j)) dp[i][j][k] += dp[i-1][j][k+1];
          if(check(i, j-1)) dp[i][j][k] += dp[i][j-1][k+1];
        }
      }
    }
  }

  ll ans = 0;
  erep(k, 0, 100){
    ans += dp[h-1][w-1][k];
  }
  cout << ans << newl;

}

#else

#define READ_TEMPLATE

#include <bits/stdc++.h>
//// data structure
//#include <atcoder/fenwicktree>
//#include <atcoder/segtree>
#include <atcoder/lazysegtree>
//#include <atcoder/string>
//// math
#include <atcoder/math>
//#include <atcoder/convolution>
#include <atcoder/modint>
//// graph
//#include <atcoder/dsu>
//#include <atcoder/maxflow>
//#include <atcoder/mincostflow>
//#include <atcoder/scc>
//#include <atcoder/twosat>

void fast(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout << std::setprecision(15);
}
/*
バグが見つからないとき(RE)...
入力の仕方でミスっている可能性大
セグフォなら、配列の要素参照を、添字演算子から.at()に変えてみる
怪しい場所をコメントアウトしてコンパイルしてみる
*/
// g++ -ggdb -O2 hoge.cpp -I ~/.pml/ac-library -o zzz
/*
メイン関数内に記述すること
std::ifstream in("testcase/hoge"); std::cin.rdbuf(in.rdbuf());
*/

using ll = long long;
using lll = __int128_t;
using ld = long double;
#define newl '\n'
#define debug(x) cout << #x << " = " << (x) << newl;
#define INF 1000000039
#define LLINF 393939393939393939
#define IMAX INT_MAX
#define IMIN INT_MIN
#define LLMAX LONG_LONG_MAX
#define LLMIN LONG_LONG_MIN
#define shift(i) (1LL<<(i))
#define PI acos(-1)
#define inr(l, x, r) (l <= x && x < r)
#define fore(i, a) for(auto &i : a)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define erep(i, a, b) for(int i = (a); i <= (b); i++)
#define rrep(i, a, b) for(int i = (a); i >= (b); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pcnt(x) __builtin_popcount(x)
#define llpcnt(x) __builtin_popcountll(x)
#define vv(name, type, a, ...) vector<vector<type>> name(a, vector<type>(__VA_ARGS__))
#define vvv(name, type, a, b, ...) vector<vector<vector<type>>> name(a, vector<vector<type>>(b, vector<type>(__VA_ARGS__)))
#define vvvv(name, type, a, b, c, ...) vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
#define vvvvv(name, type, a, b, c, d, ...) vector<vector<vector<vector<vector<type>>>>> name(a, vector<vector<vector<vector<type>>>>(b, vector<vector<vector<type>>>(c, vector<vector<type>>(d, vector<type>(__VA_ARGS__)))));
template <typename T>
int lwb(const std::vector<T>& vec, const T& x){
  return lower_bound(all(vec), x) - vec.begin();
}
template <typename T>
int upb(const std::vector<T>& vec, const T& x){
  return upper_bound(all(vec), x) - vec.begin();
}
template <typename T>
T max(const std::vector<T>& vec){ return *max_element(all(vec)); }
template <typename T>
T min(const std::vector<T>& vec){ return *min_element(all(vec)); }
template <typename T>
T rad(const T& x){ return x * PI/180; }
template <typename T>
using pq = std::priority_queue<T>;
template <typename T>
using minpq = std::priority_queue<T, std::vector<T>, std::greater<T>>;
// @brief シフト演算子を、__int128_t型用にオーバーロード
std::ostream& operator<<(std::ostream& os, __int128_t value){
  if(value == 0) return os << 0;

  static char buffer[128];
  if(value < 0){
    os << '-';
    value = -value;
  }
  int itr = 0;
  while(value > 0){
    buffer[itr++] = value%10 + '0';
    value /= 10;
  }
  std::reverse(buffer, buffer + itr);
  buffer[itr] = 0;
  return os << buffer;
}
// @brief string型の10進非負整数を、__128_t型に変換する
__int128_t parse(const std::string& s){
  __int128_t res = 0;
  for(int i = 0; i < s.length(); i++){
    res = 10*res + (s[i]-'0');
  }
  return res;
}
// 最大値・最小値の更新
template <typename T1, typename T2>
bool chmax(T1 &a, const T2& b){
  if(a < b){ a = b; return 1; }
  else return 0;
}
template <typename T1, typename T2>
bool chmin(T1 &a, const T2& b){
  if(a > b){ a = b; return 1; }
  else return 0;
}
template <typename T>
void iota(std::vector<T>& vec, bool greater = false){
  std::iota(all(vec), 0);
  std::sort(all(vec), [&](int i, int j){
    if(greater) return vec[i] > vec[j];
    return vec[i] < vec[j];
  });
}
// 2つのvectorをマージ
template <typename T>
std::vector<T> vmerge(std::vector<T>& a, std::vector<T>& b){
  std::vector<T> res;
  std::sort(a.begin(), a.end());
  std::sort(b.begin(), b.end());
  std::merge(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(res));
  return res;
}


// 辺
template <typename T>
class Edge{
public:
  int from, to;
  T cost;
  int ID;
  Edge(int to, T cost) : to(to), cost(cost) {} // for WG
  Edge(int from, int to, T cost) : from(from), to(to), cost(cost) {} // for Edges
  Edge(int from, int to, T cost, int ID) : from(from), to(to), cost(cost), ID(ID) {} // for Edges
  bool operator<(const Edge<T>& rhs) const { return cost < rhs.cost; };
  bool operator>=(const Edge<T>& rhs) const { return !(cost < rhs.cost); };
  bool operator>(const Edge<T>& rhs) const { return cost > rhs.cost; };
  bool operator<=(const Edge<T>& rhs) const { return !(cost > rhs.cost); };
  bool operator==(const Edge<T>& rhs) const { return cost == rhs.cost; };
  bool operator!=(const Edge<T>& rhs) const { return !(cost == rhs.cost); };
};
using G = std::vector<std::vector<int>>;
template <typename T>
using WG = std::vector<std::vector<Edge<T>>>;
template <typename T>
using Edges = std::vector<Edge<T>>;

template <typename T, typename F>
// @param ok 解が存在する値
// @param ng 解が存在しない値
// @remark ok > ng の場合は最小値、ok < ng の場合は最大値を返却
T Bsearch(T& ok, T& ng, const F& f){
  while(std::abs(ok-ng) > 1){
    T mid = (ok-ng)/2 + ng;
    (f(mid) ? ok : ng) = mid;
  }
  return ok;
}
template <typename T, typename F>
T Bsearch_double(T& ok, T& ng, const F& f, int itr = 80){
  while(itr--){
    T mid = (ok+ng)/2;
    //T mid = sqrtl(ok*ng);
    (f(mid) ? ok : ng) = mid;
  }
  return ok;
}


template <typename T>
// @brief (k, n-k)-shuffleである0, 1, ..., N-1 の置換Aを、辞書順で列挙する
bool next_shuffle(std::vector<T>& vec, const int& k){
  int n = vec.size();
  if(n <= k){
    return false;
  }

  // 前K項 := L
  // 後ろN-K項 := R
  auto left = vec.begin();
  auto right = vec.begin() + k;
  T R_max = *std::max_element(right, vec.end());
  T tmp = (std::numeric_limits<T>::min)();
  // @param i Lの要素の中で、Rの要素の最大値よりも小さいもののうち、最大のもののイテレータ(*i := L_(i))
  auto tmpi = left, i = right;
  while(tmpi != right){
    if(tmp <= *tmpi && *tmpi < R_max){
      tmp = *tmpi;
      i = tmpi;
    }
    tmpi++;
  }
  if(i == right){
    return false;
  }

  // @param j Rの要素の中で、L_(i)よりも大きいもののうち、最小のもののイテレータ(*j := R_(j))
  tmp = (std::numeric_limits<T>::max)();
  auto tmpj = right, j = vec.end();
  while(tmpj != vec.end()){
    if(tmp >= *tmpj && *tmpj > *i){
      tmp = *tmpj;
      j = tmpj;
    }
    tmpj++;
  }

  std::iter_swap(i, j); // L_(i)とR_(j)をswap
  i++, j++;
  // やりたいこと：L_(i+1)～L_(k-1)(:= X)とR_(j+1)～R_(n-k-1)(:= Y)を接続し、R_(j+1)が先頭に来るように回転する
  int X_len = k-std::distance(left, i);
  int Y_len = n-k-std::distance(right, j);
  int swap_len = std::min(X_len, Y_len);
  // Xの末尾swap_len項とYの末尾swap_len項をswapする
  std::swap_ranges(right-swap_len, right, j);
  if(swap_len == X_len){
    std::rotate(j, j+swap_len, vec.end());
  }
  else{
    std::rotate(i, right-swap_len, right);
  }

  return true;
}

int log2ll(long long N){
  int B = -1;
  while(N != 0){
    B++;
    N /= 2;
  }
  return B;
}
template <typename T>
// @brief (2,...,2)-shuffleである0, 1, ..., 2*N-1 の置換Aを、辞書順で列挙する
bool next_pairing(std::vector<T>& vec){
  int n = vec.size();
  // @param used vecに含まれるどの数が使用済みであるか
  ll used = 0;
  for(int i = n-1; i >= 0; i--){
    used |= (1<<vec[i]);
    if(i%2 == 1 && vec[i] < log2ll(used)){ // インクリメントできる
      vec[i] = __builtin_ctzll(used >> (vec[i]+1)) + vec[i]+1;
      used ^= (1<<vec[i]);
      for(int j = i+1; j < n; j++){
        vec[j] = __builtin_ctzll(used);
        used ^= (1<<vec[j]);
      }
      return true;
    }
  }
  return false;
}


const int di4[4] = {-1, 0, 1, 0};
const int dj4[4] = {0, 1, 0, -1};
const int di8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dj8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const std::vector<std::tuple<int, int, int>> line3{{0,1,2}, {3,4,5}, {6,7,8}, {0,3,6}, {1,4,7}, {2,5,8}, {0,4,8}, {2,4,6}};
const std::vector<std::tuple<int, int, int, int>> line4{{0,1,2,3}, {4,5,6,7}, {8,9,10,11}, {12,13,14,15}, {0,4,8,12}, {1,5,9,13}, {2,6,10,14}, {3,7,11,15}, {0,5,10,15}, {3,6,9,12}};

bool OutOfGrid(const int& i, const int& j, const int& h, const int& w){
  if(i < 0 || j < 0 || i >= h || j >= w) return true;
  return false;
}

// @brief 繰り返し二乗法を利用した、x^nの求値
ll power(ll x, ll n){
  ll res = 1;

  while(n){
    if(n & 1) res *= x;
    x *= x;
    n >>= 1;
  }
  
  return res;
}

ll power_mod(ll x, ll n, const ll& m){
  ll res = 1;

  while(n){
    if(n & 1){
      res = (res*x) % m;
    }
    x = (x*x) % m;
    n >>= 1;
  }

  return res;
}

// @brief x/mのfloor（x/m以下の最大の整数）を求める
ll floor(const ll& x, const ll& m){
  ll r = (x%m + m) % m; // xをmで割った余り
  return (x-r)/m;
}

// @brief x/mのceil（x/m以上の最小の整数）を求める
ll ceil(const ll& x, const ll& m){
  return floor(x+m-1, m); // x/m + (m-1)/m
}

// @brief prefix_sum[i][j] := [0, i)×[0, j) での二次元配列の総和
// @brief f(i, j) := a[i][j]の値
// @rem 貰う遷移で埋めていく
template <typename T>
std::vector<std::vector<T>> prefix_sum(const int& h, const int& w, const std::function<T(int, int)>& f) {
  std::vector<std::vector<T>> sum(h+1, std::vector<T>(w+1, T()));
  for(int i = 0; i < h; ++i){
    for(int j = 0; j < w; ++j){
      sum[i+1][j+1] = f(i, j) + sum[i][j+1] + sum[i+1][j] - sum[i][j];
    }
  }
  return sum;
}

// @brief suffix_sum[i][j] := [0, i)×[0, j) での二次元配列の総和
// @brief f(i, j) := a[i][j]の値
// @rem 貰う遷移で埋めていく
template <typename T>
std::vector<std::vector<T>> suffix_sum(const int& h, const int& w, const std::function<T(int, int)>& f) {
  std::vector<std::vector<T>> sum(h+1, std::vector<T>(w+1, T()));
  for(int i = h-1; i >= 0; --i){
    for(int j = w-1; j >= 0; --j){
      sum[i][j] = f(i, j) + sum[i+1][j] + sum[i][j+1] - sum[i+1][j+1];
    }
  }
  return sum;
}

using namespace std;

#include __FILE__

#endif
0