geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

AtCoder Beginner Contest 297 メモ

コンテストページ: AtCoder Beginner Contest 297 - AtCoder
コンテスト中AC: A〜D
コンテスト後にE,Fを自力AC

D - Count Subtractions

基本的な動きはユークリッドの互除法と同じなので、その通りにすれば概ね問題ないですが、一点注意が必要です。
A,Bの大きい方をa、小さい方をbとします。baの倍数となった時、ユークリッドの互除法ではaが0となるまでbを引きますが、今回の問題はa=bとなった時点で終了するようにしなければいけません。

実装はコンテスト後に見直し

実装: Submission #40555022 - AtCoder Beginner Contest 297

E - Kth Takoyaki Set

個数制限の無い部分和問題の解き方をベースにして解けます。

まず、Aの要素をただ1つ使う場合の部分和問題を考えます。
以下のDPテーブルを考えます。

dp[i][j]:=Ai番目までを使ってjが作れるなら1、作れないなら0

iからi+1への配るDPでの遷移は、

  • dp[i][j]が1ならdp[i+1][j]を1にする
  • dp[i][j]が1ならdp[i][j+A_{i+1}]を1にする

です。
次に、個数制限がない場合の部分和問題を考えます。
上記の遷移に対し、以下を追加します。

  • dp[i+1][j]が1ならdp[i+1][j+A_i]を1にする

この遷移を追加すると、
dp[i][j]が1ならdp[i][j+A_{i+1}]が1になる
dp[i][j+A_{i+1}]が1ならdp[i][j+2A_{i+1}]が1になる
dp[i][j+2A_{i+1}]が1ならdp[i][j+3A_{i+1}]が1になる
...

となるので、i+1番目のjが1なら、任意の自然数kに対して、i+1番目のj+kA_{i+1}は全て1になり、個数が無制限である状況が作られます。
なお、jの小さい方から順にテーブルを更新していく必要があります。

また、この配列は使い回すことができるので、

dp[j]:=jが作れるなら1、作れないなら0

として、i=0,1,...,N-1のそれぞれについて、j=0,1,2,...の順に、

  • dp[j]が1ならdp[j+A_{i+1}]を1にする

をしていけばよいです。

K番目の最大値が配列に持てる大きさならこのまま解けますが、今回は最大値が2\times 10^{10}なので不可能です。
配列では作成できない値も管理しているため、無駄が多いです。
そこで、作成可能な値そのものを集合で管理するようにします。すると、集合には小さいほうから順にK個だけ管理すればよいです(0除く)。

そこで、順序付き集合S (C++ならset)で作成可能な値の集合を管理できないか考えます。

前述のDPの遷移から以下の方法が考えられます。

  • Sの要素の小さい順にA_{i+1}を足した値をSに挿入する

これだと、以下のような問題点が発生します。

  • Sに存在する要素が小さい順に網羅されず、終了時点が不明
  • Sがsetなら、要素の追加により木の構造が動的に変化するため、小さい順に走査するイテレータが正常に機能するか不明(確かめていませんが、問題なく機能するのかもしれません)

そこで、作成可能な値を小さい順に管理する集合Tを追加し、以下のようにします。

T=\{0\}として、Tに値がK個追加されるまで、以下を繰り返す

Sから最小値を取り出しxとする(xSから削除する)。 xTに挿入し、x+A_{i+1}Sに追加する

このようにすると、TにはSの要素及びA_{i+1}で作成可能な値が小さい順にK個の記録されます。
また、繰り返し部分はO(K)となります。

これで、O(NK)で問題を解くことができました。

実装: Submission #40502322 - AtCoder Beginner Contest 297

F - Minimum Bounding Box 2

包除原理で解けます。

長方形の縦の長さと横の長さを全探索してもO(N^2)なので、全探索可能です。

i、横j、面積m=i\times jの長方形Rがグリッド上にできる方法が何通りか考えていきます。

一旦、Rができる位置は固定してRができるマスの選び方が何通りあるか考えます。

まず、R外のマスが選ばれた場合はRができないので、以下、マスは全てR内から選ばれるとします。

この時、Rができる条件は以下のとおりです。

  • Rの上下左右のそれぞれの辺について、1つ以上選ばれたマスが存在する

となります。
さて、これが成立する条件はかなり複雑です。辺上に選ばれるマスは何個あってもよく、頂点となるマスは2つの辺を共有していることなどが理由です。

そこで、Rとならない数を全体から引くことを考えます。
Rとならない条件は、

  • Rの辺について1つ以上、選ばれたマスが0の辺が存在する

よって、以下の計算ができます。

Rとなる通り数 =
R内のマスが選ばれる全通り数
- 選ばれたマスが0の辺がちょうど1つの通り数
- 選ばれたマスが0の辺がちょうど2つの通り数
- 選ばれたマスが0の辺がちょうど3つの通り数
- 選ばれたマスが0の辺がちょうど4つの通り数

  • 選ばれたマスが0の辺がちょうどxつの通り数

というのは求めるのが難しいです。
一方で、

  • 選ばれたマスが0の辺がx以上の通り数

というのは、求めるのが容易です。

全てを記載すると長くなるので、x=2の場合についてのみ示します。他も同様に求められます。

"選ばれたマスを0にする辺"に含まれるマスの個数をkとします。残りのm-k個のマスからK個のマスを選ぶような、_{m-k}C_K通りが、選ばない辺を決めた時の通り数です。

2つの辺の選び方は、(左、上)、(左、下)、(右、上)、(右、下)、(右、左)、(上、下)があります。

(左、上)、(左、下)、(右、上)、(右、下)は、k=i+j-1です。
(右、左)は、k=2jです。
(上、下)は、k=2iです。

この6パターンを合計することで、選ばれたマスが0の辺が2つ以上の通り数を得ることができます。

x=1,2,3,4についてこれらを計算すると、包除原理により、以下のようにRとなる通り数を計算できます。

Rとなる通り数 =
R内のマスが選ばれる全通り数
- 選ばれたマスが0の辺が1つ以上の通り数
+ 選ばれたマスが0の辺が2つ以上の通り数
- 選ばれたマスが0の辺が3つ以上の通り数
+ 選ばれたマスが0の辺が4つ以上の通り数

なお、R内のマスが選ばれる全通り数は_mC_Kです。

これにより、グリッド内で位置を固定した時に、縦i、横jの長方形Rができる通り数が求まりました。これをXとします。

グリッド内でRは、(H-i+1)(W-j+1)個配置できます。全て同様の計算ができるので、グリッド内でRができる全通り数は、(H-i+1)(W-j+1)X通りです。

また、Rのスコアはmなので、グリッド上でできるRによって得られる全スコアは、m(H-i+1)(W-j+1)Xです。
これを全てのi,jについて合計します。それを、グリッド全体からK個選ぶ通り数_{HW}C_Kで割ったものが求める期待値となります。

実装: Submission #40549600 - AtCoder Beginner Contest 297