- Translate each rule into one explicit state update.
- Maintain the invariant after every processed item.
- Return the accumulated state once all relevant input has been handled.
Code notes
- 56 lines of Python from the credited upstream file abc302_b.py.
- The implementation visibly relies on sequence storage, ordered lookup.
- No explicit loop blocks detected.
Complexity
Count the number and nesting of passes over the input, then include the maintained containers in the memory estimate.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
12 3 4def main():5 import sys6 7 input = sys.stdin.readline8 9 h, w = map(int, input().split())10 s = [input().rstrip() for _ in range(h)]11 12 dxy = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (1, -1), (-1, 1), (1, 1)]13 14 15 from typing import List16 17 def is_in_grid(nx: int, ny: int, w: int = w, h: int = h) -> bool:18 if not (0 <= nx < w):19 return False20 if not (0 <= ny < h):21 return False22 23 return True24 25 def is_exist_word_in_grid(grid: List[str], word: str):26 word_size = len(list(word))27 28 for dx, dy in dxy:29 for y in range(h):30 for x in range(w):31 candidate = ""32 pos = list() 33 34 for k in range(word_size):35 nx, ny = x + dx * k, y + dy * k36 37 if not is_in_grid(nx, ny):38 continue39 40 candidate += grid[ny][nx]41 pos.append((ny + 1, nx + 1))42 43 if candidate == word:44 return True, pos45 46 return False, []47 48 _, pos = is_exist_word_in_grid(s, "snuke")49 50 for ri, ci in pos:51 print(ri, ci)52 53 54if __name__ == "__main__":55 main()56