AGC041 C - Domino Quality (900)
手動で3でクオリティ1、4と5でクオリティ2の場合を作れた
対角線上に設置することで、クオリティが同じNとMからN+Mが作れる
例えば6はクオリティ2でも作れるが、3を左上と右下に置くことで1でも作れる
4と5のパターンを組み合わせると7以上では7と11を除いてすべての数を作ることができる
12以上なら$ N % 4の回数だけ5を使って残りを4にして埋める
7は6のクオリティ2のパターンに縦横いずれかに3並んでいる列と行を追加することでクオリティ3が作れた
11は4+7で作れるのでこれで全パターン作成可能に
ソースコードにパターンを作る関数を埋め込んで条件分岐を愚直に書けば良い
盤面の作成と出力が一番重く$ O(N^2)
問題: https://atcoder.jp/contests/agc041/tasks/agc041_c
提出: https://atcoder.jp/contests/agc041/submissions/9189228
#AGC #900pt #AGC #C #AtCoder
#O(N^2)