切り下げ関数と切り上げ関数の適用について（Competitive Programming Advent Calendar）

この記事は，partake.inの21日目の記事です．

この記事では，問題を解くための道具として，切り下げ関数と切り上げ関数を紹介します．対象は，TopCoder SRM Div.1 Easy (or Div.2 Medium)レベルでたまに出てくる問題だと思います．若干堅苦しい内容になっていますが，興味がある方は読んでみて下さい．

切り下げ関数と切り上げ関数

まず，切り下げ関数 $\lfloor x \rfloor$ と切り上げ関数 $\lceil x \rceil$ を次で定義します．

$\lfloor x \rfloor=x$ 以下の整数のうち最大のもの
$\lceil x \rceil=x$ 以上の整数のうち最小のもの

例えば， $\lfloor \pi \rfloor=3$ ， $\lceil \pi \rceil=4$ ， $\lfloor -e \rfloor=-3$ ， $\lceil -e \rceil=-2$ ， $\lfloor 3 \rfloor=\lceil 3 \rceil = 3$ ，等です．

切り下げ関数をコードで表現するならば，

double x=hoge();
int m=fuga(), n=piyo();
int floor;
floor=(int)floor(x); // 実数の切り下げ
floor=(int)x; // x>=0
floor=n/m; // m>=1, n>=0

ですが，本来はx=5であるところがx=4.99999999999994等になっていると上述のコードでは爆死するので，x+EPSとするのが無難です．切り上げ関数は，(int)ceil(x)で可能です（こちらは逆にx-EPSとするのが無難です）．整数の割り算については後述．

これらの関数には以下のような性質があります．
$x-1 < \lfloor x \rfloor \leq x \leq \lceil x \rceil < x+1$
また，これから実数xと整数nに関する以下の関係式を導きだすことが出来ます．
$x < n \Longleftrightarrow \lfloor x \rfloor < n$
$n < x \Longleftrightarrow n < \lceil x \rceil$
$x \leq n \Longleftrightarrow \lceil x \rceil \leq n$
$n \leq x \Longleftrightarrow n \leq \lfloor x \rfloor$
これを使って，1つ問題を解いてみましょう．

SRM 296 Div1 Easy NewAlbum

http://community.topcoder.com/stat?c=problem_statement&pm=6085&rd=9817
1曲length分の曲nSongs曲をCDに入れたい．CDは1枚当たりcdCapacity分の容量を持っており，曲と曲の間には1分間の空白を入れる必要がある．2枚以上のCDをまたぐ等して曲が途切れてはいけない．また，各CDの曲の数が13で割りきれてはいけない．必要なCDの最小枚数を求めよ．
制約条件

1≦nSongs≦100
1≦cdCapacity≦10000
1≦length≦cdCapacity

この問題を，以下の方針に従って解いてみましょう．

CD1枚に入る曲の最大数を求める．
曲を貪欲にCDに詰めていき，必要なCDの最小枚数を求める．
13で割り切れる場合の調整

1.CD1枚に入る曲の最大数を求める

まず3曲入れる事を考えてみます．この時CDの中身は次のようになります．

総再生時間は，3*length+2分となります．従って，n曲入れた場合の総再生時間は
$n\times length+(n-1)$
となることが分かります．これがcdCapacityを超えてはいけないので，1枚当たりの曲数をnSongsPerCdと置くと，
$nSongsPerCd\times length+(nSongsPerCd-1) \leq cdCapacity$
という不等式が成立します．これをnSongsPerCdについて解くと，
$nSongsPerCd \leq \frac{cdCapacity+1}{length+1}$
となり，
$n\leq x \Longleftrightarrow n\leq \lfloor x \rfloor$
を使うと，
$nSongsPerCd \leq \lfloor \frac{cdCapacity+1}{length+1} \rfloor$
となります．欲しいのは不等式を満たす最大の値なので結局，
$nSongsPerCd = \lfloor \frac{cdCapacity+1}{length+1} \rfloor$
となります．ここで，nSongsPerCdが13で割り切れる場合はnSongsPerCdを1減らします．以上をコードに落としたものを以下に示します．

int nSongsPerCd = (cdCapcity + 1) / (length + 1);
if(nSongsPerCd % 13 == 0){
  nSongsPerCd--;
}

2.曲を貪欲にCDに詰めていき，必要なCDの最小枚数を求める

次に，先ほど求めたnSongsPerCdを用いて必要なCDの最小枚数を求めます．必要最小枚数をnCdとすれば，
$nSongsPerCd \times nCd \geq nSongs$
という不等式が成立します．
$nCd \geq \frac{nSongs}{nSongsPerCd}$
ここで，
$n \geq x \Longleftrightarrow n \geq \lceil x \rceil$
を使うと，
$nCd \geq \lceil \frac{nSongs}{nSongsPerCd} \rceil$
切り上げ関数が出てきました．切り上げ関数をそのままコードに落とすのは若干面倒ですので，少し変形しましょう．

方法1.不等号から等号を取り除く

先ほどの関係式に，
$x < n \Longleftrightarrow \lfloor x \rfloor < n$
というものがありました．これを適用できれば，切り下げ関数のみで不等式を記述することが出来ます．整数m，nに関する自明な規則
$m \leq n \Longleftrightarrow m < n + 1$
を用いると，
$nSongsPerCd \times nCd + 1 > nSongs$
$nCd > \frac{nSongs-1}{nSongsPerCd}$
ここで先の規則を適用すると，
$nCd > \lfloor \frac{nSongs-1}{nSongsPerCd} \rfloor$
となり，さらに等号を付加すると，
$nCd \geq \lfloor \frac{nSongs-1}{nSongsPerCd} \rfloor + 1$
結局，nCdは以下の式で求められます．
$nCd = \lfloor \frac{nSongs-1}{nSongsPerCd} \rfloor + 1$

int nCd = (nSongs - 1) / nSongsPerCd + 1;

方法2.切り上げ関数を切り下げ関数に変形

nが整数，mが正整数の時，以下の等式が成立します．
$\lceil \frac{n}{m} \rceil = \lfloor \frac{n+m-1}{m} \rfloor$
これを用いると
$nCd \geq \lfloor \frac{nSongs+nSongsPerCd-1}{nSongsPerCd} \rfloor$
最終的に，nCdは以下の式で求められます．
$nCd = \lfloor \frac{nSongs+nSongsPerCd-1}{nSongsPerCd} \rfloor$

int nCd = (nSongs + nSongsPerCd - 1) / nSongsPerCd;

3.曲の数が13で割り切れる場合の調整

現在nSongs曲がnCd枚のCDに貪欲に詰められているので，各CDの曲数は図のようになっています．

一番右のCD以外の各CDは，nSongsPerCdが13の倍数ではないことから条件を満たしていますが，一番右のCDは，何も調べていないので怪しいです．この「怪しい」CDの曲数は，
$doubt=nSongs-nSongsPerCd \times (nCd-1)$
です．doubt mod 13 ≠ 0であれば，何もする必要はありません．doubt mod 13 = 0の時は，あるCDから怪しいCDに1or2曲移せるかを確かめれば調整可能かどうかを調べられます．

そもそも移せない

怪しくないCDが1枚も無い場合は，どうしようもないのでCDを1枚追加します．

1曲移せるか

nSongsPerCd mod 13 ≠ 1であれば，あるCDから1曲を怪しいCDに移せばOKです．あるCDの曲数は13m+2,…,13m+12から13m+1,…,13m+11になり，怪しいCDの曲数は13m'から13m'+1と変化します（13m'+1>nSongsPerCdとなることはありません）．

2曲移せるか

nSongsPerCd mod 13 = 1の時は，2曲移せるかを確かめます．2曲移せない時，というのは2曲移すと怪しいCDの曲数がnSongsPerCdをオーバーしてしまう時です．（nSongsPerCd = 1の時は，そもそも2曲移すことが出来ませんが，doubtは必ず1なので問題ありません．）つまり，
$nSongsPerCd\;mod\;13 = 1,\;doubt=nSongsPerCd-1$
の時はCDを増やさざるを得ないということです．新しくCDを1枚増やした後は，怪しいCDから1曲を新しいCDに移します．
以上をコードに落とすと，以下のようになります．

int doubt = nSongs - nSongsPerCd * (nCd - 1);
if(doubt % 13 == 0){
  if(nCd == 1){
    nCd++;
  }else if(nSongsPerCd % 13 == 1 && doubt == nSongsPerCd - 1){
    nCd++;
  }
}

さて，最終的なコードは次のようになります．

int leastAmountOfCDs(int nSongs, int length, int cdCapacity){
  int nSongsPerCd=(cdCapacity+1)/(length+1);
  if(nSongsPerCd%13==0){
    nSongsPerCd--;
  }
  int nCd=(nSongs+nSongsPerCd-1)/nSongsPerCd;
  // int nCd=(nSongs-1)/nSongsPerCd+1;
  int doubt=nSongs-nSongsPerCd*(nCd-1);
  if(doubt%13==0){
    if(nCd==1){
      nCd++;
    }else if(nSongsPerCd%13==1&&doubt==nSongsPerCd-1){
      nCd++;
    }
  }
  return nCd;
}

区間内の整数の個数

次に区間内の整数の個数を紹介します．
$m\leq a\leq n$ （m，nは整数）を満たす整数aの個数は，n-m+1という明らかな規則から出発します．まず，閉区間 $[\alpha..\beta]$ （ $\alpha$ ， $\beta$ は実数）に入る整数の個数を計算します．．
$n \in [\alpha..\beta] \Longleftrightarrow \alpha \leq n \leq \beta \Longleftrightarrow \lceil \alpha \rceil \leq n \leq \lfloor \beta \rfloor$
従って， $[\alpha..\beta]$ に入る整数の個数は， $\lfloor \beta \rfloor - \lceil \alpha \rceil + 1$ となります．他の区間についても同様に求めると，以下のようになります．

区間	含まれる整数	制限
$[\alpha..\beta]$	$\lfloor \beta \rfloor - \lceil \alpha \rceil + 1$	$\alpha \leq \beta$
$[\alpha..\beta)$	$\lceil \beta \rceil - \lceil \alpha \rceil$	$\alpha \leq \beta$
$(\alpha..\beta]$	$\lfloor \beta \rfloor - \lfloor \alpha \rfloor$	$\alpha \leq \beta$
$(\alpha..\beta)$	$\lceil \beta \rceil - \lfloor \alpha \rfloor - 1$	$\alpha < \beta$

制限を満たさないと，区間に含まれる整数の個数が負になる，という不条理な結果が出るので注意しましょう．

これを使って，問題を解いてみます．

SRM 465 Div.1 Easy TurretPlacement

http://community.topcoder.com/stat?c=problem_statement&pm=10840&rd=14182
平面上の点(x[i], y[i])がn個与えられる．2点を選び，各点を中心とする一辺の長さが正整数の正方形を置く．正方形は中心に関して回転させることができるが，2つの正方形が互いに重複してはいけない．中心座標あるいは一辺の長さが異なる正方形の配置は互いに異なるものとする．以上の条件を満たす正方形の配置は何通りあるか．
制約条件

2≦n≦50
-10000≦x[i], y[i]≦10000
i≠jならば(x[i], y[i])≠(x[j], y[j])

この問題を，以下の方針に従って解いてみましょう．

2つの正方形が互いに重複しない条件を求める．
全ての中心座標対について重複しない正方形の配置の総数を求める．

1.2つの正方形が互いに重複しない条件を求める

2つの正方形の中心座標をp，q，一辺の長さをm，nとします．この時，2つの正方形が重複しないようにするためには，下図のように，辺p-qについて正方形の辺を平行（or垂直）にすれば十分だということが分かります．

平行にしても重複してしまう場合は，どのように回転させても重複してしまいます．
即ち，2つの正方形が互いに重複しない条件は，以下の式で表されます．
$\frac{m}{2} + \frac{n}{2} \leq |p-q|$
これは等価な式
$m + n \leq \lfloor 2 \times |p-q| \rfloor$
に変形することが出来ます．以降，簡単化のため $\alpha = \lfloor 2 \times |p-q| \rfloor$ と置きます．また，自明な条件 $m\geq 1$ ， $n\geq 1$ も付け加えておきます．

2.全ての中心座標対について条件を満たす正方形の配置の総数を求める．

ここで，アイヴァースンの記法を紹介します．Pが真ならば1で偽ならば0を表します．
$[P]=\left\{\begin{array}1 &\mathrm{if\;}P\;\mathrm{is\;true;}\\ 0 &\mathrm{otherwise.}\end{array}\right.$
これを使うと，和の記述を
$\sum_{x\in X}1=\sum_{x}[x\in X]$
のように変形できるため，柔軟な計算が可能になります．上の式は，条件を満たすものの個数を表しています．この問題の条件（3つ）についても同様に和をとると，それが求めたい配置の数になります．
$\sum_{m,n}[m\geq1][n\geq1][m+n\leq\alpha]=\sum_{m}[m\geq1]\sum_{n}[1\leq n\leq\alpha-m]$
$[1..\alpha-m]$ に含まれる整数の個数はα-mなので，1≦α-mという条件を加えつつ変形します．
$=\sum_{m}[m\geq1](\alpha-m)[1\leq\alpha-m]$
条件を合成します．
$=\sum_{m}[1\leq m\leq\alpha-1](\alpha-m)$
この式でも，全体の計算のオーダーはO(n²α)になるため，TLEを回避することが出来ます（最大ケースで200[ms]）が，ここでは更にオーダーを減らしてみます．
αとmのそれぞれについて考えます．αは定数なので，総和を簡単に計算できます．
$\sum_{m}[1\leq m\leq\alpha-1]\alpha=\alpha\time((\alpha-1)-1+1)$
また，mに関する総和は有名な公式 $\sum_{i=1}^{n}i=\frac{n(n+1)}{2}$ を使って，
$\sum_{m}[1\leq m\leq\alpha-1]m=\frac{\alpha(\alpha-1)}{2}$
最終的な答えは，
$\frac{\alpha^{2}-\alpha}{2}$
となり，コードは以下のように簡単なものになります（最大ケースで8[ms]）．

long count(int[] x, int[] y) {
  int n=x.length;
  long ans=0;
  for(int j=0;j<n;j++){
    for(int i=j+1;i<n;i++){
      long alpha=(long)(2*Math.sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))+EPS);
      ans+=(alpha*alpha-alpha)/2;
    }
  }
  return ans;
}

と，ここまで書いて，区間に含まれる整数の個数の表をあまり使っていないことに気づいてしまいました．最近の問題で該当するものとしては，SRM 523 Div.1 Easy CountingSeriesが挙げられます．ある性質（等差数列）を満たす整数がある区間にいくつあるかという問題に（ある程度）適用可能です．

以上，切り上げ関数と切り下げ関数の適用について，問題とともに紹介しました．知ってる，あるいは自然とこのような問題への対処法が身に付いている方も多いと思いますが，既存の手法を上手く使うことで，ある程度機械的かつバグを出さないようにコードを書くことが出来るようになると思います．