【競プロ】すべての行and列が○○を満たす行列を構築シリーズの典型？要素
突然ですが次のタイプの問題、見おぼえありますか？
- N*Nの行列がある。すべての行と列において、○○という条件を満たす(もしくは行が○○という条件、列が××という条件を満たす)ように、そのN*Nの行列を構築せよ。構築不能なら-1を出力せよ。
トラウマ要素重めの問題ですね。01Matrixとか01Matrixとか01Matrixとかでレートを溶かして、300に置く問題じゃねえ、mar〇〇nrk殺意高杉るなどと話題になりましたね。
最近でいうと、AGC041のtourist回で、C問題がパズルすぎて多くの方も嘆いてました。
この問題で、まだ経験値が少ないですが、僕なりの知見を纏めようと思います。ずばり、
対角線状に、条件を満たす要素を並べろ！
対角線状に置くと、何かと良い性質があります。行列を扱う線形代数でも、行列を何とかして対角線状にしか成分がないように変形する方法(対角化)を学びます。線形代数では、対角線状にしか成分がないときは、計算上非常に扱いやすいのです。
パズル構築の世界でも、実はそれに通じたりするものがあります。
対角線状に2つの正方形を並べました。2つの正方形以外は、要素0だとします。これらを囲う大きな正方形Xを考えるとき、Xの辺の赤い部分が相当する行と列は、2つ並べてXを作る前の、左上の正方形の辺が相当する行と列と性質が同じです。
同様に、Xの辺の青い部分が相当する行と列は、2つ並べてXを作る前の、右下の正方形の辺が相当する行と列の性質と同じです。
つまり、対角線状に並べることで、一定の条件を満たすような小さい正方形から、より大きい正方形を作れる！(天地開闢)
この性質から、行列の構築パズルの問題で、ひとまず、対角線状に成分を並べて考えてみる、というのも操作をする選択肢は普通にアリということです。
以下にみんなのトラウマであろう問題とその簡単な解説を載せます。
01Matrix
「すべての行は条件A、すべての列は条件Bを満たす」なので、対角線状に置くことをまず念頭に考えてみます。
1行のうち、少ないものがA個で、1列のうち、少ないものがB個なので、とりあえず対角線の左上に、A*Bのサイズのブロックを載せます。
すると、あら不思議、Editorialのように、行と列の条件を満たしちゃうんですね。
この問題は、対角線状に置くことで、答えの正方形のサイズを広くするというテクニックには結局関係はなかったのですが、対角線状におく、という考えがあるかないかで、ACの分水嶺になると思います。このように、関係があまりない問題でも、とりあえず対角線状に置いてみて試すのは悪い選択ではないと思います。
Domino Quality
より小さい正方形をいくつかくっつけることで、より大きいのが作れる構築の典型でした。
次出たら、今より成長した僕でこのような構築を解きます。解きます。
