Codeforces Round #540 C Palindromic Matrix 〜証明編①〜
前回示した解法（貪欲法）の証明をしたいと思う。
解法のポイントは、箱の方は小さい方から埋めていき、ブロックは大きい方から使っていくという点である。 箱を小さい方から埋めるのは、大きい箱を埋めるのに小さいブロックを先に使ってしまって後で困らないようにするためであり、大きいブロックから使うのは、同じ大きさならば分割できないブロック一個より分かれているブロック複数個を残しておく方が後々有利だからである。
さて、示すべきことは、
「もし解が存在するならば、貪欲法で解の一つを構築できる」
であり、対偶を取れば
「貪欲法で解が構築できないならば、解は存在しない」
である。
ここで、「貪欲法で解が構築できない場合」というのはどういう場合だろうか？ それは、前回の手順3.で条件を満たすjが見つからない場合である。
このとき、解が存在しないというのは何故言えるのだろう。 それは、貪欲法で構築した状態が「最善」の状態だからである。 最善の状態から最善を尽くして解を探したのに見つからなかったということは、解はない、というわけである。
従って、ちゃんとした証明のためにはこの「最善」の状態というのを定義すれば良さそうだ。 そのためには、２つの状態に対して優劣をつける基準が必要だ。
状態A,Bがあるとしよう。これらは、残っているブロックの数が互いに同じだとする。 このとき、状態Aが状態Bより優れているとは、次のような状態だと定義する。
状態A、Bにおいて、箱の埋まっていないスペースで連続しているものの大きさをそれぞれとする。
また状態Aにおいて、残っているブロックjの個数を
、状態Bにおいて残っているブロックjの個数を
とする。
さらに、「AがBより優れている」をA>Bと書くことにすると、
ならばA>B. 逆も同じ
のとき、
ならばA>B.逆も同じ
のとき
と定義する
すなわち、箱の空きスペースの最小値が大きい方が優れているとする。さらに、 が等しいときには
ベクトルの（辞書順での）大小で優劣を決める。ただし、
ベクトルの辞書順での大小は次のように定義する：
ならば
のとき、
ならば
のとき、
ならば
または
のいずれかが成り立つとき、
と書く。
[なお、こうして定義された状態空間上の順序<は（残っているブロックの数を固定しても）全順序を成さない。
しかし、関係による同値類を考えれば、その商空間では全順序を成す。]
そして、「Aが最善の状態である」とは、「任意の（残っているブロック数が同じ）状態Bに対してが成り立つ」ことと定義する。
以下で示すべきことは、
貪欲法で構築された状態は、常に最善の状態であること
最善の状態において
となるブロックjが残っていなければ、解は存在しない
である。 これらを次回以降で示していこう。
