目次

HHKB プログラミングコンテスト 2020 D,E,F問題メモ

HHKB プログラミングコンテスト 2020

個人的にはテンキーやファンクションキーは独立したものが好みだが、それはそれとしてHHKB、打鍵心地がとても好き。

D - Squares

D - Squares

問題

解法

各質問に $O(1)$ とかその辺で答える必要がある。結構場合分けが面倒くさい。

まず、$N \lt A+B$ の場合、どうあがいても重ならずに置けないので0。以下それ以外とする。

プロペラみたいに分割すると重複無く数えられる。

●●○○○○
●●○○○○
●●○○○○
●●赤赤■■
●●赤赤■■
□□□□■■

全ての赤の位置に対して、「■の中に青が置かれる」「○と■にまたがって青が置かれる」パターン数を数えると、その合計の4倍が答えとなる。 (●、○、□に置かれるパターン数は、これを回転させたものと合致し、それぞれ同数だけ存在する)

$A \lt B$ だと $A$ より前に $B$ が下端の制約を受けるので、場合分けが増えてしまう。$A \ge B$ とする。

赤を上から $p$、左から $q$ の位置に置くとすると、$(p=0~N-A,q=0~N-A-B)$

$p \le B-1$

青は、縦 $N$、横 $N-q-A$ の範囲からはみ出さないような位置に置ける。

$$\displaystyle \sum_{p=0}^{B-1}\sum_{q=0}^{N-A-B}(N-B+1)(N-q-A-B+1)$$

Wolfram Alpha先生で式変形すると、以下のようになる。

$$\dfrac{1}{2}B(N-B+1)(N-A-B+2)(N-A-B+1)$$

$p \ge B$

青は、縦 $N-p+B-1$、横 $N-q-A$ の範囲からはみ出さないような位置に置ける。

\begin{eqnarray} & \sum_{p=B}^{N-A}\sum_{q=0}^{N-A-B}(N-p)(N-q-A-B+1) \\ =& \frac{1}{4}(N-A-B+2)(N-A-B+1)^2(N+A-B) \end{eqnarray}

これを計算して合計して4倍すればよい。

Python3

E - Lamps

E - Lamps

問題

解法

典型的な、“縦に見るものを横に見る” 問題。

「このマスが照らされるような置き方の個数」を、全ての空きマスについて合計すると、それが答えとなる。

あるマスから上下左右に繋がる空きマスの個数を $L$ とすると、この中のどれか一つさえ照明が置かれていれば、そのマスは照らされることになる。

    │
    │
──○─
    │

少なくともどれか1つに置かれる場合は $2^L-1$ 通り。また、これに関わらない他の空きマスはどうなっていてもよいので、$2^{K-L}$ 通り。

これを掛け合わせた $(2^{L}-1)2^{K-L}$ が、あるマスが照らされる置き方の個数となる。

$L$ の求め方は、空きマスが横にいくつ連続するか、縦にいくつ連続するかをそれぞれ個別に求めておくと、その合計-1が $L$ となる。

$2000 \times 2000$ のグリッドを何回か走査することになるので、素のPythonだと厳しい。NumbaやPyPyなどを使った方がよい。

Python3

F - Random Max

F - Random Max

問題

解法

このあたりがポイントとなる。

以下の2つの確率変数があったとき、$L,R$ に出現する値で区切る。

i   0  1  2  3  4  5  6  7  8  9 10
1      |--------------|
2            |--------------------|
    ↓
       |-----|--------|-----------|

区間毎に、「全ての確率変数が、その区間内の実数 $x$ 以下の値を取る場合の確率」を、多項式で表現できる。($f(x)$ とする)

1つの確率変数についてみれば、

これを掛け合わせたのが、全体の確率となる。

i   0  1  2  3  4  5  6  7  8  9 10
1      |--------------|
2            |--------------------|

       |-----|--------|-----------|
         x-1     x-1
変数1   -----   -----       1
         6-1     6-1

                 x-3       x-3
変数2     0     -----     -----
                10-3      10-3

かけあわせる↓
              (x-1)(x-3)    x-3
各区間の  0  ------------  -----
  f(x)        (6-1)(10-3)  10-3

最初に $L,R$ で区切ったのは、各確率変数がそこで滑らかでなくなり、それを掛け合わせた $f(x)$ も滑らかでなくなるから(滑らかでないと微分できない)。

さて、これはあくまで $x$ 以下の確率なので、$x$ ちょうどになる確率1)を求めたい。
これは微分した式 $f'(x)$ がそれに当たる。

求めるのは期待値なので、$xf'(x)$ が、「最大値が $x$ だった場合に答えに寄与する値」となる。

これを、今度は積分を取ると、「区間全体が答えに寄与する値」を求められる。

よって、区間の両端を $[P,Q)$ とすると、以下の式を区間毎に計算し、合計したもの(に、かけろと言われている数をかけたもの)が答えとなる。

実装上は、多項式を表現できるクラスを作っておいて、

等ができるようにしておくと、$f(x)=1$ で初期化しておいて、区間 $[P, Q)$ を昇順に

とすればよい。

Python3

1)
厳密ではない表現