Infinite RGB Tiling

原点は赤である。他のマスは $r=\max(|x|,|y|)$ の正方形の外周に属する。赤、緑、青を $0,1,2$ と表す。

上辺のドミノを左から $k=0,\ldots,r-1$ と番号付けすると、色は $(r+k)\bmod3$ となる。右辺を下から番号付けすると、色は $(r+1+k)\bmod3$ となる。下辺と左辺の色は、それぞれ上辺と右辺を原点の周りに $180$ 度回転したものに一致する。

この規則は最初の緑のドミノと赤い原点に一致する。同じドミノの二マスには同じ値が付く。同じ外周上の隣接、連続する二つの外周間の隣接、四隅での隣接を、偶奇と $3$ で割った余りに応じて代入すると、異なるドミノの色は常に異なる。したがってすべての条件を満たし、一意性より求める色付けである。

上の領域は $y>0$、$-y\leq x<y$ であり、$r=y$、$k$ となる。右の領域は 、 であり、、 となる。下または左なら先に を に変換する。対角線上の不等号に注意する。

各マスを $O(1)$ で求める。出力面積の合計を $A$ とすると、時間計算量は $O(T+A)$、逐次出力時の追加空間は $O(1)$ である。

サブタスク 1 ではドミノの隣接グラフを作る。原点と最初の緑のドミノを固定し、二色の隣接図形が確定したドミノを残りの色にする処理をキューで伝播する。この配置では全ドミノが確定する。各外周では内側の二色に接するドミノを起点に残りが強制される。座標上限 $C$ に対して時間 $O(C^2+A+T)$、空間 $O(C^2+T)$ である。付属の naive は色の公式を使わずにこの方法を実行する。

座標の絶対値は $10^{18}$ 以下で、主解法の式は $2\cdot10^{18}+1$ 以下、独立解法の式も絶対値 $4\cdot10^{18}+1$ 以下である。符号付き ビット整数で十分である。入力検証では面積を掛け算する前に割り算で上限を確認する。

Solution written by GPT6