#1157426 (C++23) No.2641 draw X

提出ソース

結果

問題	No.2641 draw X
コンテスト
ユーザー	kwm_t
提出日時	2026-04-15 20:44:00
言語	C++23 (gcc 15.2.0 + boost 1.89.0) コンパイル: `g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_` 実行: `./a.out`
結果	AC
実行時間	176 ms / 2,000 ms
コード長	7,182 bytes
記録記録タグの例: 初AC ショートコード純ショートコード純主流ショートコード最速実行時間
コンパイル時間	4,546 ms
コンパイル使用メモリ	381,036 KB
実行使用メモリ	24,192 KB
最終ジャッジ日時	2026-04-15 20:44:08
合計ジャッジ時間	6,951 ms
ジャッジサーバーID （参考情報）	judge2_0 / judge3_1

このコードへのチャレンジ
（要ログイン）

ファイルパターン	結果
sample	AC * 3
other	AC * 41

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#include <atcoder/all>
//using namespace std;
using namespace atcoder;
//using mint = modint998244353;
//const int mod = 998244353;
//using mint = modint1000000007;
//const int mod = 1000000007;
const int INF = 1e9;
//const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n-1); i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define P pair<int,int>
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }
template <class T, class F>
T binarySearch(T ok, T ng, const F &f) {
	while (abs(ok - ng) > 1) {
		T mid = (ok + ng) / 2;
		(f(mid) ? ok : ng) = mid;
	}
	return ok;
}
#ifndef KWM_T_UTILITY_DIAGONAL_PREFIX_SUM_HPP
#define KWM_T_UTILITY_DIAGONAL_PREFIX_SUM_HPP

#include <vector>
#include <cassert>

namespace kwm_t::utility {

/**
 * @brief 斜め累積和（Diagonal Prefix Sum）
 *
 * 典型用途:
 *   - 斜め方向（↘ / ↙）の区間和を高速に求める
 *   - 斜め一直線上の部分列の和クエリ
 *   - グリッド問題で「対角方向のみ」の集計
 *
 * 計算量:
 *   - 構築: O(HW)
 *   - クエリ: O(1)
 *
 * @tparam T
 *   加算・減算が定義されている型（int, long long, double など）
 *
 * @param a
 *   元となる H×W の2次元配列
 *
 * 制約 / 注意:
 *   - 0-indexed
 *   - クエリは半開区間:
 *       diag_down : [ (x0,y0) → (x1-1,y1-1) ]
 *       diag_up   : [ (x0,y0) → (x1-1,y1+1) ]
 *   - (x1-x0) == abs(y1-y0) を満たす必要がある（同一対角線）
 *
 * 使用例:
 *   std::vector<std::vector<int>> a = {
 *       {1, 2, 3},
 *       {4, 5, 6},
 *       {7, 8, 9}
 *   };
 *
 *   kwm_t::utility::DiagonalPrefixSum<int> dps(a);
 *
 *   // ↘ 方向 (0,0) → (3,3) の対角和 = 1+5+9 = 15
 *   int x = dps.sum_down(0, 0, 3, 3);
 *
 *   // ↙ 方向 (0,2) → (3,-1) の対角和 = 3+5+7 = 15
 *   int y = dps.sum_up(0, 2, 3, -1);
 *
 * verified:
 *   - グリッド斜めクエリ系問題
 */
template <class T>
struct DiagonalPrefixSum {
private:
	int h, w;
	std::vector<std::vector<T>> down; // ↘
	std::vector<std::vector<T>> up;   // ↙

public:
	DiagonalPrefixSum() = default;

	explicit DiagonalPrefixSum(const std::vector<std::vector<T>>& a) {
		build(a);
	}

	void build(const std::vector<std::vector<T>>& a) {
		h = (int)a.size();
		w = h ? (int)a[0].size() : 0;

		down.assign(h + 1, std::vector<T>(w + 1, T{}));
		up.assign(h + 1, std::vector<T>(w + 1, T{}));

		// 初期値
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				down[i + 1][j + 1] = a[i][j];
				up[i + 1][j] = a[i][j];
			}
		}

		// 累積
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				down[i + 1][j + 1] += down[i][j];
				up[i + 1][j] += up[i][j + 1];
			}
		}
	}

	int height() const { return h; }
	int width() const { return w; }

	// ↘ 方向: (x0,y0) → (x1-1,y1-1)
	T sum_down(int x0, int y0, int x1, int y1) const {
		assert(0 <= x0 && x0 <= x1 && x1 <= h);
		assert(0 <= y0 && y0 <= y1 && y1 <= w);
		assert(x1 - x0 == y1 - y0);

		return down[x1][y1] - down[x0][y0];
	}

	// ↙ 方向: (x0,y0) → (x1-1,y1+1)
	T sum_up(int x0, int y0, int x1, int y1) const {
		assert(0 <= x0 && x0 <= x1 && x1 <= h);
		assert(-1 <= y1 && y0 < w);
		assert(x1 - x0 == y0 - y1);

		return up[x1][y1 + 1] - up[x0][y0 + 1];
	}
};

} // namespace kwm_t::utility

#endif // KWM_T_UTILITY_DIAGONAL_PREFIX_SUM_HPP


#ifndef KWM_T_UTILITY_DIAGONAL_IMOS_HPP
#define KWM_T_UTILITY_DIAGONAL_IMOS_HPP

#include <vector>
#include <cassert>

namespace kwm_t::utility {

/**
 * @brief 斜めいもす法（Diagonal Imos）
 *
 * 典型用途:
 *   - 斜め方向（↘ / ↙）への区間加算
 *   - 対角線上の区間に一括で値を加える
 *   - 「斜めに影響が伝播する」グリッド問題
 *
 * 計算量:
 *   - 更新: O(1)
 *   - 構築: O(HW)
 *   - 取得: O(1)
 *
 * @tparam T
 *   加算・減算が定義されている型
 *
 * 制約 / 注意:
 *   - 0-indexed
 *   - add は半開区間:
 *       ↘ : (x0,y0) → (x1-1,y1-1)
 *       ↙ : (x0,y0) → (x1-1,y1+1)
 *   - (x1-x0) == abs(y1-y0) を満たす必要あり
 *   - build() を呼ぶまで値は確定しない
 *
 * 使用例:
 *   DiagonalImos<int> imos(3, 3);
 *
 *   // ↘ に +1
 *   imos.add_down(0, 0, 3, 3, 1);
 *
 *   // ↙ に +2
 *   imos.add_up(0, 2, 3, -1, 2);
 *
 *   imos.build();
 *
 *   int v = imos.get_down(1, 1); // 取得
 *
 * verified:
 *   - 斜め伝播系グリッド問題
 */
template <class T>
struct DiagonalImos {
private:
	int h, w;
	std::vector<std::vector<T>> down; // ↘
	std::vector<std::vector<T>> up;   // ↙

public:
	DiagonalImos() = default;

	DiagonalImos(int h_, int w_) : h(h_), w(w_) {
		init();
	}

	void init() {
		down.assign(h + 1, std::vector<T>(w + 1, T{}));
		up.assign(h + 1, std::vector<T>(w + 1, T{}));
	}

	int height() const { return h; }
	int width() const { return w; }

	// ↘ 方向: (x0,y0) → (x1-1,y1-1)
	void add_down(int x0, int y0, int x1, int y1, T val) {
		assert(x1 - x0 == y1 - y0);
		down[x0][y0] += val;
		down[x1][y1] -= val;
	}

	// ↙ 方向: (x0,y0) → (x1-1,y1+1)
	void add_up(int x0, int y0, int x1, int y1, T val) {
		assert(x1 - x0 == y0 - y1);
		up[x0][y0 + 1] += val;
		up[x1][y1 + 1] -= val;
	}

	void build() {
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				down[i + 1][j + 1] += down[i][j];
				up[i + 1][j] += up[i][j + 1];
			}
		}
	}

	// ↘ の値取得
	T get_down(int i, int j) const {
		return down[i][j];
	}

	// ↙ の値取得
	T get_up(int i, int j) const {
		return up[i][j + 1];
	}
};

} // namespace kwm_t::utility

#endif // KWM_T_UTILITY_DIAGONAL_IMOS_HPP

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int h, w; std::cin >> h >> w;
	std::vector<std::string>s(h);
	rep(i, h)std::cin >> s[i];
	std::vector b(h, std::vector<int>(w));
	rep(i, h)rep(j, w) {
		if ('#' == s[i][j])b[i][j] = 1;
	}
	// 斜め累積和
	kwm_t::utility::DiagonalPrefixSum crossPrefixSum(b);
	// 斜めImos
	kwm_t::utility::DiagonalImos<int> crossImos(h, w);
	rep(i, h)rep(j, w) {
		if ('.' == s[i][j])continue;
		auto f = [&](long long x)->bool {
			int y = x * 2 + 1;
			return crossPrefixSum.sum_down(i - x, j - x, i + x + 1, j + x + 1) >= y
				&& crossPrefixSum.sum_up(i - x, j + x, i + x + 1, j - x - 1) >= y;
		};
		int lim = std::min({ i,j,h - 1 - i,w - 1 - j }) + 1;
		auto get = binarySearch<int>(0, lim, f);
		if (0 == get)continue;
		crossImos.add_down(i - get, j - get, i + get + 1, j + get + 1, 1);
		crossImos.add_up(i - get, j + get, i + get + 1, j - get - 1, 1);
	}
	crossImos.build();
	bool chk = true;
	rep(i, h)rep(j, w) {
		if ('.' == s[i][j])continue;
		int cnt = crossImos.get_down(i, j) + crossImos.get_up(i, j);
		if (0 == cnt)chk = false;
	}
	std::cout << (chk ? "Yes" : "No") << std::endl;
	return 0;
}

yukicoder

結果

ソースコード