AtCoder Beginner Contest 145 D～F問題メモ

AtCoder Beginner Contest 145

D - Knight

• チェスのナイトのコマが1個、座標 $(0,0)$ に置かれている
• 1回の操作で $(x,y)$ から $(x+1,y+2)$ または $(x+2,y+1)$ に移動できる
• 移動を繰り返して $(X,Y)$ に到達するパターン数を、$\mod{10^9+7}$ で求めよ
• $1 \le X,Y \le 10^6$

まず、あり得ない $X,Y$ を考える。

• どちらの移動も合計が3ずつ増えるのは変わらないので、最終的な $X+Y$ も3の倍数でナイトおかしい
• 移動回数 $d$ は $\frac{X+Y}{3}$ とわかるが、1回の操作で $x,y$ 軸の両方に最低1ずつ進むので、$X \ge d,Y \ge d$ でナイトおかしい

移動回数がわかれば、$A:(x+1,y+2),B:(x+2,y+1)$ それぞれを採用した回数は鶴亀算の要領でわかる。仮に $d$ 回全てAを使ったら $X=d$ になるはずだが、そこからBに置き換えていったら、1回ごとに $x$ 座標は1ずつ増えるので、結局Aで移動したのは $X-d$、Bは $Y-d$ 回となる。

あとは ${}_dC_{X-d}$ を求めればよい。

よくある、格子上の道路を上か右にのみ移動する経路の個数を求める問題の、それぞれの移動に+1しただけとも考えられる。

E - All-you-can-eat

• とある食べ放題の店には $N$ 種類の料理がある
• $i$ 番目の料理を食べるのにかかる時間は $A_i$、満足度は $B_i$
• 以下に従って、好きな料理を好きな順に食べることができる
  • 1度に1つの料理のみ注文できる
  • 注文と同時に食べ始められ、食べ終わるまでは次の料理を注文できない
  • 同じ種類の料理を2回以上注文できない
  • オーダーストップの時間は開始から $T$。ちょうどの時刻にはもう注文できないが、$T$ を過ぎても提供済みの料理はそのまま食べ続けることができる
• 得られる満足度の合計の最大値を求めよ
• $1 \le N,T,A_i,B_i \le 3000$

DPの典型であるナップサック問題だが、1個だけなら溢れてもいい、というところがポイント。

ざっくり考えると、時間がかかる料理を最後に1つだけとっておき、それ以外で $T$ 未満ぎりぎりまで食べ、最後に取っておいた料理を注文、という流れがよさそう。 実際、食べる料理の集合が決まっているとすると、一番時間のかかる料理を最後に注文するとして問題ない。

通常のナップサックなら、$i$ 番目の料理を考慮中、それを食べれば時間切れになる遷移はスキップするが、 それをスキップせず、最後に注文したとして満足度の最大値を更新すればよい。

$dp[i][j] = i$ 番目の料理まで考慮して、時間 $j$ かけることで得られる満足度の最大値

擬似コード
ans = 0
for i番目の料理の所要時間a, 満足度b in 料理リスト:
    for 時間t, 満足度s in dp[i]:
        if i番目の料理を食べたら時間切れ:
            ans = max(ans, s + b)
        else:
            dp[i+1][t+a] = max(dp[i+1][t+a], s + b)

その際、時間のかかる料理を先に処理してしまうと、タイムリミットまでに他の料理をさらに食べられるのに、最適化されないまま満足度を確定させてしまう。 これを避けるには時間の短い料理から順に処理すればよい。

N=3 T=10
    Ai  Bi
1    3  10
2   10  50
3    5  30

1→2→3の順に処理すると、料理2でオーバーしてしまうため、
10+50=60が暫定解となってしまい、以降更新されない

1→3→2の順に処理すると、料理2の処理時点では既に1,3が考慮されているので
10+30+50=90が暫定解となり、これは正しい

F - Laminate

• 縦$10^9$行、横$N$列のマス目があり、最初、全てのマスは白い
• 数列 $H_1,H_2,...,H_N$ が与えられ、これに従ってマスを黒く塗ろうとしている
  • $i$ 列目は、下から $H_i$ マスを黒く塗る
  • 最終的にヒストグラムのようになる
• マスの塗り方は、以下の通りである
  • 1行ずつ横方向に塗っていく
  • 黒く塗るマスが連続する限り、1回の操作で塗ることができる
• ただし、塗り始める前に、合計 $K$ 回まで以下の変更を行える
  • 任意の列を1つ選び、$H_i$ を任意の値に変更する
• マスを塗るのに必要な操作回数を最小化し、その最小操作回数を求めよ
• $1 \le N \le 300$
• $0 \le K \le N$
• $1 \le H_i \le 10^9$

DP。問題EもDPだったから連想しやすかった。

横には1行ずつしか塗れないので、最終的な $H$ の最大値の回数は最低限必要。1つだけ高くても全体が高くても回数は変わらないが、谷があるとそこで分断されるため回数がかさむ。

□□■□□    ■■■■■    ■■□■■
□□■□□    ■■■■■    ■■□■■
□□■□□    ■■■■■    ■■□■■
□□■□□    ■■■■■    ■■□■■
■■■■■    ■■■■■    ■■■■■
5回           5回           9回

よって、山を削る、谷を埋める、というのが塗る回数を減らすのに効果的。

山はどこまで削ればよいかというと、中途半端に削るより一気に削った方がいいし、削りすぎて谷になってしまっても逆効果。なるべく左右隣と合わせるのがよい。 左右の高さが違う場合、その間の高さなら塗る回数に影響は及ぼさない。ので、左に合わせると決め打っても問題ない。

だが、左と揃えればよいとはいえ、並んだ2列以上を同時に変更する場合もあることを考えると、1列単独では決められない。

もし左列を変更していたとしたら、さらにその左列（も変更していた場合はさらに……）と同じ高さに揃えているはずなので、 最後に変更しなかった列の高ささえわかれば、その高さに揃えればよい。

よって、以下のDPが構成できる。

$dp[i][j][k]=i$ 列目まで見て、変更回数が $j$ 回、最後に変更しなかった列の高さが $k$ である場合の、最小塗る回数

塗る回数は、塗りを新たに開始する行（左端）でカウントしておけば、終わる時（右端）では特にカウントなど考慮する必要は無い。

計算量は……詳しくは分からないが、まぁ $i,j,k$ ともに300が上限で $300^3$、これに状態の被りで何分の1かになって、まぁ大丈夫だろ～くらい。 実際、それまでに $j$ 回変更していて $i$ 列目は変更しないと決めたら、どこを変更していたかに依らず遷移は $dp[i][j][H_i]$ に集約される。

遷移には直前の列の情報しか不要なので、以降、$i$ は省略して、現在考慮中のを $dp[j][k]$、前の列の結果を $dp_p[j][k]$ とする。

初期状態は $dp_p[0][0]=0$

遷移は、左列の高さ $k$ と自身の高さ $H_i$ を比較する。

• 同じなら変更の必要は無い
  • $dp[j][k] ← dp_p[j][k]$
• 自身が低いなら、新たに開始する塗りはない
  • 変更しない場合、$dp[j][H_i] ← dp_p[j][k]$
  • 変更する場合、$dp[j+1][k] ← dp_p[j][k]$
• 自身が高い場合のみ、その差分だけ新たに塗りを開始する行がある
  • 変更しない場合、$dp[j][H_i] ← dp_p[j][k] + H_i - k$
  • 変更する場合、$dp[j+1][k] ← dp_p[j][k]$

（※“←”は、現在の値があればそれと比較して小さければ更新、という代入を表す）

実際の実装では、$H_i$ は $10^9$ まで取り得るので、indexで持つ、座標圧縮、辞書で持つなどする必要がある。

以下の実装は、$(j, k)$ ごとタプルをキーにした辞書で管理している。 実装は楽だが、速度はどうしても遅くなり、いくつかのケースでTLEになる。 タプルをキーにしているのが遅いので、bitshiftして2変数を1つの整数にまとめると通った。 可読性が下がるが、アルゴリズム自体に手は入れないのでコンテスト中にあともうちょっとを詰めるには有効。

NumPyを使っても書ける。遷移を2次元で整理する。

$k$ を、最後に変更していない列の高さではなく列のindexとし、便宜上、$H_0=0$ を追加する。

初期状態
     j
     0  1  2
k 0  0  -  -
  1  -  -  -
  2  -  -  -
  3  -  -  -

$i=3$ 列目を処理中とする。

• (1) 今の列を変更するという操作は、$k=0～i-1$ をそのまま右に1つずらす操作となる
• (2) 今の列を残すという操作は、各 $j=0～K-1$ につき、自分より前の $dp[j][k]$ のうち、自分より低い $H_k$ は差分（新たに塗りを開始する行）を加算した上で、最小値で更新する操作となる

i-1までのDP状態                             iのDP状態
        j                 j
k Hk    0  1  2           0  1  2            0  1  2
0  0    -  -  0    ==>    -  -  -    --->    -  -  -
1  8    -  8  -    (1)    -  -  8    統合    -  -  8
2  1    8  1  -           -  8  1            -  8  1
3  6    -  -  -           -  -  -     ,->   13  6  -
                                      |
↓(2) 差分を加算                      |
                                      |
k Hk 差   0  1  2           0  1  2   |
0  0 +6   -  -  0    ==>    -  -  -   |
1  8  0   -  8  -    (2)    -  -  -   |
2  1 +5  13  6  -  縦方向   -  -  -   |
3  6      -  -  -  最小値  13  6  -  -'