[AtCoder] ABC 099 D – Good Grid

問題

方針

題意

良いグリッドであるときのマスの状況は、必ず \( 3 \) 色に塗り分けられています。ここで次の集合を考えます。マス \( (i, j) \) に対して、 \( G_k\) は \( i + j \mod 3 = k\) を満たす集合とします。したがって、集合は \( 3 \) 個あることになります。ある集合のグリッドはすべて同じ色で塗られ、それぞれの集合は異なる色で塗られています。

全探索

\( G_k \) のグリッドを全て色 \( i \) にしたときの違和感を \( A[i][k]\) とします。\( A \) を求めるために必要な計算量は、\( O(CN^2)\) となります。良いグリッドにしたときの違和感の和は、
\[ A[i][0] + A[j][1] + A[k][2]\]
となります。ただし、\( i, j, k\) はそれぞれ異なる値です。この和を計算するために必要な計算量は \( O(C^3) \) となります。

 

コード

提出したコード

AtCoder,探索全探索

Posted by ヤマカサ