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

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

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

D - Squares

問題

  • グリッド上に、左下が $(0,0)$、右上が $(N,N)$ に揃えて置かれた白い正方形がある
  • この中に、一辺が $A$ の赤の正方形と 一辺が $B$ の青の正方形を置く
    • 白からはみだしてはいけない
    • 赤と青が重なってはいけない
    • 各辺が軸に平行に、四隅が整数座標になるようにのみ置ける
  • 置き方としてあり得る個数を $10^9+7$ で割ったあまりで求めよ
  • 1つの入力に $T$ 個のテストケースが与えられるので、全てに答えよ
  • $1 \le T \le 10^5$
  • $1 \le A,B,N \le 10^9$

解法

各質問に $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

問題

  • $H \times W$ のグリッド、'.' が空きマスで '#' が壁
  • ある空きマスに照明を置くと、上下左右一直線に、壁に阻まれるまでの全ての空きマスを照らす
  • 空きマスの個数を $K$ 個とすると、照明の置き方は $2^K$ 個ある
  • 各置き方で、少なくとも1個の照明に照らされているマスの数を計算し、その総和を $10^9+7$ で割ったあまりを求めよ
  • $1 \le H,W \le 2000$

解法

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

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

あるマスから上下左右に繋がる空きマスの個数を $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

問題

  • $N$ 個の確率変数が与えられ、$i$ 番目の確率変数は $[L_i,R_i]$ の実数を一様ランダムに取る
  • これらの確率変数の最大値の期待値を求めよ
    • 答えは、$\displaystyle (N+1)! \times \prod_{i}(R_i-L_i)$ をかけると必ず整数になるので、それを $10^9+7$ で割ったあまりで求めよ
  • $1 \le N \le 1000$
  • $0 \le L_i \lt R_i \le 10^9$
  • 入力は全て整数

解法

  • 微分積分
    • 数学寄りだけど、まぁ微分積分の使い方としては素直
  • 変曲点毎に区間を分けて区間毎に処理
  • プログラム上でのMODを取りながらの微分積分

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

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

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

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

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

  • $x \lt L_i$ の時、$0$
  • $L_i \le x \le R_i$ の時、$\dfrac{x-L_i}{R_i-L_i}$
  • $R_i \lt 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)$ とすると、以下の式を区間毎に計算し、合計したもの(に、かけろと言われている数をかけたもの)が答えとなる。

  • $\displaystyle \int_P^Q xf'(x)dx$

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

  • $(a_0+a_1x+a_2x^2+\ldots)$ と $b_0+b_1x$ をかける
  • $(a_0+a_1x+a_2x^2+\ldots)$ を $b_0+b_1x$ で割る(割り切れることは保証される)
  • $(a_0+a_1x+a_2x^2+\ldots)$ を微分する
  • $(a_0+a_1x+a_2x^2+\ldots)$ を積分する
  • $(a_0+a_1x+a_2x^2+\ldots)$ の $x$ に具体的な値を代入する

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

  • もし $L_{max} \lt Q$ なら、その区間は答えに寄与するので、$\displaystyle \int_P^Q xf'(x)dx$ を答えに加算する
  • $Q$ が $L_i$ 由来なら、$f(x)$ にその確率変数の $\dfrac{x-L_i}{R_i-L_i}$ をかける
  • $Q$ が $R_i$ 由来なら、$f(x)$ をその確率変数の $\dfrac{x-L_i}{R_i-L_i}$ で割る

とすればよい。

Python3

1)
厳密ではない表現
本WebサイトはcookieをPHPのセッション識別および左欄目次の開閉状況記憶のために使用しています。同意できる方のみご覧ください。More information about cookies
programming_algorithm/contest_history/atcoder/2020/1010_hhkb2020.txt · 最終更新: 2020/10/16 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0