yukicoder No.540 格子点と経路 上界について

この記事では、

No.540 格子点と経路 - yukicoder

において、最大値と一致する上界をどう与えるかについて書きます。

実際の構成方法については他の記事を参考にしてください。

• 前提として

まず、y座標が0であるような横線はw個あります。

このうち、答えにカウントできるのは最大でもceil(w/2)個しかありません。(頂点を共有する横線同士を両方カウントできないことから来ています。)

この事実を頻繁に使用します。

• wまたはhが偶数の時

wを偶数とします。(wが奇数の時はhとwを入れ替えてください。)

この時、カウントできる横線の個数は(w/2)*(h+1)個です。

横線の前後にできるだけ縦線を入れることを考えると、上界として(w/2)*(h+1)*2+1が与えられます。

h=wの時は縦線も横線と同じ個数しか存在しないので、さらに良い上界として(w/2)*(h+1)*2が与えられます。

• wもhも奇数の時

上界として(h+1)*(w+1)-min(h,w)が与えられることを以下で書きます。

各y座標について、「良い横線の状態」を「(w+1)/2の横線をカウントする状態」として定義します。「良い縦線の状態」についても同様に定義します。

とりあえず、あるjが存在して、y座標として2*jと2*j+1がともに「良い横線の状態」であったとします。

この時、x座標として2*i,2*i+1をともに「良い縦線の状態」にしてしまうと、(2*i,2*j),(2*i,2*j+1),(2*i+1,2*j),(2*i+1,2*j+1)で四角形ができてしまい、破綻します。

したがって「良い縦線の状態」となるx座標は(w+1)/2個しか存在せず、カウントできる縦線の個数は(h+1)*(w+1)/2-(w+1)/2個で抑えられます。この縦線の前後に横線を入れることを考えても、最大値は((h+1)*(w+1)/2-(w+1)/2)*2+1=(h+1)*(w+1)-wで抑えられることが分かります。

次に、どのjについてもy座標として2*jと2*j+1のいずれかが「良い横線の状態」ではなかったとします。

この時はカウントできる横線の個数が(h+1)*(w+1)/2-(h+1)/2で抑えられるため、最大値を(h+1)*(w+1)-hで抑えることができます。

これらを組み合わせると、最大値を(h+1)*(w+1)-min(h,w)で抑えられることが分かります。