結果
| 問題 |
No.866 レベルKの正方形
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:15:02 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 8,341 bytes |
| コンパイル時間 | 1,102 ms |
| コンパイル使用メモリ | 84,960 KB |
| 実行使用メモリ | 545,536 KB |
| 最終ジャッジ日時 | 2025-05-14 13:16:06 |
| 合計ジャッジ時間 | 10,024 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 3 |
| other | AC * 8 MLE * 1 -- * 13 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
// Use long long for the answer count to avoid potential overflow, although unlikely given constraints.
using ll = long long;
// Precompute column prefix frequencies
// col_freq[j][i][c] will store the count of character with index c ('a' corresponds to 0, 'b' to 1, etc.)
// in column j (0-based index), covering rows from 0 to i-1 (0-based index).
std::vector<std::vector<std::vector<int>>> col_freq;
// Store the grid characters
std::vector<std::string> grid;
int H, W, K; // Grid dimensions and target distinct count K
// Helper function to update character counts and the distinct character count.
// It's used when incrementally building the first square S(i1, 0, s) for each row pair (i1, i2).
// `counts`: array storing frequency of each character 'a'-'z'.
// `distinct_count`: current number of distinct characters with count > 0.
// `char_idx`: index of the character (0-25) being updated.
// `delta`: change in count (+1 for adding, -1 for removing).
inline void update_counts(std::vector<int>& counts, int& distinct_count, int char_idx, int delta) {
// Store original count before modification
int original_count = counts[char_idx];
// Update count
counts[char_idx] += delta;
// Check if the distinct count needs to change based on transitions to/from zero count
// If the count was positive and becomes zero or less (should strictly be zero)
if (original_count > 0 && counts[char_idx] <= 0) {
distinct_count--; // A character type is now gone
}
// If the count was zero or less (should strictly be zero) and becomes positive
else if (original_count <= 0 && counts[char_idx] > 0) {
distinct_count++; // A new character type appeared
}
}
int main() {
// Use fast I/O operations
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
// Read input dimensions H, W, and target K
std::cin >> H >> W >> K;
// Read the grid characters
grid.resize(H);
for (int i = 0; i < H; ++i) {
std::cin >> grid[i];
}
// Initialize and compute column prefix frequencies
// Dimensions: W columns, H+1 rows (index 0 to H), 26 characters
col_freq.assign(W, std::vector<std::vector<int>>(H + 1, std::vector<int>(26, 0)));
for (int j = 0; j < W; ++j) { // Iterate through columns
for (int i = 1; i <= H; ++i) { // Iterate through rows (using 1-based index logic for prefix sums)
// Copy frequencies from the row above
for (int c = 0; c < 26; ++c) {
col_freq[j][i][c] = col_freq[j][i - 1][c];
}
// Increment the frequency for the character at grid[i-1][j]
// Need boundary check for grid access (i-1 >= 0 guaranteed by loop i=1..H)
if (i - 1 < H && j < W) { // grid is HxW, 0-indexed
col_freq[j][i][grid[i - 1][j] - 'a']++;
}
}
}
// Variable to store the total count of level K squares found
ll total_k_level_squares = 0;
// Iterate through all possible top rows `i1` (0-based index)
for (int i1 = 0; i1 < H; ++i1) {
// `counts_1`: Frequencies for the square starting at (i1, 0) with current side length s
std::vector<int> counts_1(26, 0);
// `distinct_1`: Distinct character count for the square S(i1, 0, s)
int distinct_1 = 0;
// Iterate through all possible bottom rows `i2` (0-based index), starting from `i1`
for (int i2 = i1; i2 < H; ++i2) {
// Calculate current side length `s`
int s = i2 - i1 + 1;
// If square width `s` exceeds grid width `W`, it's invalid. Break inner loop for `i2`.
if (s > W) break;
// Update `counts_1` and `distinct_1` incrementally for the square S(i1, 0, s)
// This update corresponds to expanding the square from size (s-1)x(s-1) to s x s.
// This happens when `i2` increments by 1, which also increments `s` by 1.
// The new cells added are in row `i2` (columns 0 to s-1) and column `s-1` (rows `i1` to `i2-1`).
// Add cells from the new row `i2`, columns 0 to `s-1`
for(int j = 0; j < s; ++j) {
if (i2 < H && j < W) { // Check grid bounds before access
int char_idx = grid[i2][j] - 'a';
update_counts(counts_1, distinct_1, char_idx, 1); // Add character
}
}
// Add cells from the new column `s-1`, rows `i1` to `i2-1`
int col_idx = s - 1; // column index is s-1 (0-based)
// Check if column index `col_idx` is valid
if (col_idx >= 0 && col_idx < W) {
for (int row = i1; row < i2; ++row) { // Iterate rows i1 to i2-1
if (row < H) { // Check row bounds
int char_idx = grid[row][col_idx] - 'a';
update_counts(counts_1, distinct_1, char_idx, 1); // Add character
}
}
}
// After the O(s) update, `counts_1` and `distinct_1` represent the square S(i1, 0, s).
// Check if this square (top-left at (i1, 0), side s) has K distinct characters.
if (distinct_1 == K) {
total_k_level_squares++;
}
// Now perform horizontal sliding window for squares starting at row `i1` with side `s`
// Copy the state of the first square S(i1, 0, s) to use for sliding
std::vector<int> current_counts = counts_1;
int current_distinct = distinct_1;
// Slide the window horizontally. The loop variable `j1` represents the starting column index (0-based).
// We slide from column 1 up to W-s.
for (int j1 = 1; j1 <= W - s; ++j1) {
// Update state from square S(i1, j1-1, s) to S(i1, j1, s)
// This involves removing column `j1-1` and adding column `j1+s-1`.
// The rows involved in these columns are `i1` to `i2`.
int remove_col_idx = j1 - 1;
int add_col_idx = j1 + s - 1;
// Defensive check for column indices validity although loop bounds should ensure this
if (remove_col_idx < 0 || remove_col_idx >= W || add_col_idx < 0 || add_col_idx >=W) {
continue;
}
// Update using column prefix sums. Takes O(alpha) = O(26) time.
for (int c_idx = 0; c_idx < 26; ++c_idx) {
// Calculate count of char `c_idx` in the column segment to remove
// Rows `i1` to `i2` (0-based) correspond to prefix sum range `[i1, i2+1)`
int to_remove = col_freq[remove_col_idx][i2 + 1][c_idx] - col_freq[remove_col_idx][i1][c_idx];
// Calculate count of char `c_idx` in the column segment to add
int to_add = col_freq[add_col_idx][i2 + 1][c_idx] - col_freq[add_col_idx][i1][c_idx];
// Store original count before modifying `current_counts`
int original_count = current_counts[c_idx];
// Calculate the final count after remove and add operations
int final_count = original_count - to_remove + to_add;
// Update the count array
current_counts[c_idx] = final_count;
// Check if the distinct count changes based on transitions to/from zero count
if (original_count > 0 && final_count <= 0) { // Character type disappeared
current_distinct--;
} else if (original_count <= 0 && final_count > 0) { // New character type appeared
current_distinct++;
}
}
// Check if the new square S(i1, j1, s) has K distinct characters
if (current_distinct == K) {
total_k_level_squares++;
}
}
}
}
// Print the final total count
std::cout << total_k_level_squares << std::endl;
return 0;
}