ABC334 勉強メモ

先日開催された、AtCoder Beginner Contest 334の勉強メモです。
問題への言及がありますので、今後解く予定の方はご注意ください。
使用言語はPython・提出はPyPy3です。

公式解説

A Christmas Present

解法
FAはUntitleさんでした。おめでとうございます。
コードゴルフをするならprint('GBlaotv e'[::2])が便利です。

B Christmas Trees

解法
$L \leq A+kM \leq R$を満たすkを数える問題です。
この不等式の読み替えができた時点でほとんど終わりです。

1. 与式は$\frac{L-A}{M} \leq k \leq \frac{R-A}{M}$と変形できます。
   kは整数範囲なので $\lceil \frac{L-A}{M} \rceil \leq k \leq \lfloor \frac{R-A}{M} \rfloor$になります。
   ここで$\lceil \frac{A}{B} \rceil$、つまり切り上げ除算は-(-A//B)で可能です。
2. 切り捨て・切り上げの処理が面倒な場合、近傍探索が有効です。
   切り捨て除算で答えを概算してから、$\frac{L-A}{M} \leq k \leq \frac{R-A}{M}$ を満たすまで周辺の値を全探索すればよいです。
   計算量は少々悪化しますが、安全かつ確実です。
3. Pythonは多倍長整数が使えるので、二分探索が可能です。
   $L \leq A+kM$を満たす最小のk, ならびに $A+kM \leq R$ を満たす最大のkを調べましょう。
   kは$\pm 2×10^{18}$までとり得るので、初期化はそれより大きくしてください。
4. math.ceilとmath.floorを使う解法の罠を紹介します。
   Pythonの小数型(float)は精度が52bit・約16桁ぶんしかありません。
   なので単にmath.ceil(A/B)のように表現すると、A/Bの部分で小数を経由するため、演算精度が落ちてしまいます。
   小数表現にdecimal.Decimalを使い、高精度演算を挟めば大丈夫です。

float型の罠

import math
import decimal

X = 10 ** 18 + 65
Y = X / 1
print(X)             #1000000000000000065
print(Y)             #1.0000000000000001e+18
print(int(Y))        #1000000000000000128 : 誤差が生じる
print(math.ceil(Y))  #1000000000000000128

Z = decimal.Decimal(X) / decimal.Decimal(1)
print(Z)             #1000000000000000065
print(math.ceil(Z))  #1000000000000000065

提出例: 式変形・切り捨て・切り上げ, 二分探索

C Socks 2

解法
ものすごく難しいです。
貪欲法に帰着した後、DPや累積和で解きます。

直感的に、色が近い靴下どうしを組み合わせたほうがよいことが分かります。
厳密な証明は省略しますが、1 2 4 5や1 3 3 6で実験すれば予想ができます。
さらに「同じ色の靴下どうしを優先的にくっつけてもよい」とも分かりますが、この性質は使わなくても以降の部分は解けます。

貪欲法を使うと、靴下の枚数が偶数のときは解けます。
問題は奇数のとき、すなわち余らせる靴下をどれか選ぶ時です。
この場合、累積和・尺取法・DPのどれかを使う必要があります。

1. 奇数のときは、(貪欲に組んだペア) + 1枚余り + (貪欲のペア)という形になります。
   左右のペアの部分は事前に累積和で前計算しておけば、各区間$O(1)$で計算できます。
2. 累積和の添字ミスが怖い場合、尺取法がおすすめです。
   靴下2枚ぶん進めて、貪欲マッチングし直すを繰り返せばよいです。
3. DPの場合、使用状況を持つDPを組みます。
   DP[i][f]: i枚目まで見たとき、残す靴下を決めていたらf = True としたときの最小の奇妙さ
   とすればDPができます。

どの解法も、時間計算量は$O(N)$です。
提出例(尺取法・DP)

D Reindeer and Sleigh

解法
必要なソリ数が少ない順にトナカイを割り振ることにしてよいです。
するとソリ数の累積和に対する二分探索で解けます。

累積和の代わりに、クエリ先読みと尺取法を使うことでも解けます。
クエリをソートして、トナカイの頭数が広義単調増加になるようにします。
すると「トナカイが○匹増えたとき、ソリは何個増やせるか？」という問題になり、これはヒープでシミュレートできます。
提出例

E Christmas Color Grid 1

解法
まず、グリッドの緑色の部分を連結成分ごとに採番します。
これはBFSやUnionFindで可能です。

赤色のマスを緑色に変えたときの処理を考えます。
これは、上下左右で隣り合う連結成分がすべて同じ値に変化すると考えればよいです。setを使うと実装が楽です。
提出例

F Christmas Present 2

解法
便宜上、 サンタの家を0番目の子供の家とします 。
すなわち、子供は1-indexedで考えます。

事前に以下の値を計算しておきます。
dist[i]: サンタの家から家1, 家2, ･･･ , 家iと巡ったときの累積距離
home[i]: 家iからサンタの家への直線距離
家xから家yまで、寄り道せず移動する場合の距離はdist[y] - dist[x]です。

子供達の番号順に配る制約があるので、動的計画法に落とせそうです。
愚直なDPを書くとこうなります。
DP[i][k]: 家iに寄った後、手持ちのプレゼントがk個となる場合の最短距離
初期化: DP[0][K] = 0
直線移動: DP[i+1][k-1] ← DP[i][k] + (dist[i+1] - dist[i])
荷物補充: DP[i+1][K] ← DP[i][k] + home[i] + home[i+1]

しかし、これだと計算量が$O(NK)$でTLEします。
そこで遷移を見ると、おおむねkが1ずつずれているだけと気づきます。
なのでkに注目すると遷移が高速化できそうです。

プレゼント数に注目した定義を考えると、このように定義できます。
DP[i]: 家iまで配った後にサンタの家に戻ってきた場合の最短距離
初期化: DP[0] = 0
遷移: DP[i] ← DP[i-k] + home[i-k+1] + (dist[i] - dist[i-k+1]) + home[i]

遷移は家i-k+1に向かい、最短距離で家iまで配り、サンタの家に戻る場合です。
この遷移の最小値を考えればよいです。

遷移の式を変形すると
DP[i] ← min(DP[i-k] + home[i-k+1] - dist[i-k+1]) + dist[i] + home[i]
となり、kに対する区間最小値の形になりました。
これはセグメント木があれば$O(NlogN)$と高速に計算できます。
スライド最小値なら$O(N)$まで落ちますが、少し実装が難しいです。
提出例(スライド最小値)

おわりに

おわりです。
Gはlowlinkがわかったらときたいなとおもいました。