無限グリッド上の座標値を O(1) 算術式で算出
無限に上方向へ伸びるグリッドが与えられる。底辺が第 1 行、行は下から上へ増加、列は左から右へ増加する。行 r・列 c に位置するセルの値を求める問題。
フローの説明：
1. 入力 (r, c) を受け取る
2. グループ番号 g を整数除算で計算
3. グループ先頭値 base = 10 × g を求める
4. 列オフセット = 2×(c−1) を加算
5. 行オフセット = (r−1) mod 2 を加算
6. 3値の和を出力
from __future__ import annotations import os def strangeGrid(r: int, c: int) -> int: """ Strange Grid の (r, c) セルの値を返す。 公式: g = (r - 1) // 2 # 0-indexed グループ番号 base = 10 * g # グループ先頭値 col_offset = 2 * (c - 1) # 列方向増分 row_offset = (r - 1) % 2 # グループ内行位置 (0 or 1) Time Complexity: O(1) Space Complexity: O(1) """ g: int = (r - 1) // 2 base: int = 10 * g col_offset: int = 2 * (c - 1) row_offset: int = (r - 1) % 2 return base + col_offset + row_offset if __name__ == "__main__": fptr = open(os.environ["OUTPUT_PATH"], "w") first_multiple_input = input().rstrip().split() r = int(first_multiple_input[0]) c = int(first_multiple_input[1]) result = strangeGrid(r, c) fptr.write(str(result) + "\n") fptr.close()
| 手法 | 時間 | 空間 | 備考 |
|---|---|---|---|
| 本実装（算術式） 採用 | O(1) | O(1) | 除算・剰余・加算のみ |
| 行単位スキャン | O(r) | O(1) | 行を順次計算 |
| 全探索（仮想） | O(r×c) | O(r×c) | グリッド全体を生成 |
| r | c | 期待値 | 計算値 | 備考 |
|---|