[AtCoder] ABC099 D – Good Grid

Good Grid

https://atcoder.jp/contests/abc099/tasks/abc099_d

考え方

題意

良いグリッドであるときのマスの状況は、必ず \( 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) \) となります。

コード

感想

解説を読んで題意を理解しました。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする