105. 昨日解いた問題（2022.04.17）

問題一覧

D - Handstand (Diff: 1138)
E - Train (Diff: 1135)
D - Grid Components (Diff: 1445)
E - Stronger Takahashi (Diff: 1423)

自分の解法など

D - Handstand

24分。

連続で並ぶ 1 の数を増やす必要があるので、反転させる区間は全て 0 であるのが最適です。この問題を言い換えると、「連続して 0 が並ぶ区間のうち、最大 $K$ 個を選択して反転させた結果、最大で何個の 1 を連続して並べられるか」です。連続して並ぶ数を増やしたいので、選択する区間は（1 の区間を除いて）連続である必要があります。ここまで来ると、しゃくとり法的なイメージが出てきます。

$S$ をランレングス圧縮する
（1 の区間を除いて）連続な 0 の区間を最大 $K$ 個選択して、1 が連続で並ぶ最大数をしゃくとり法的に探索する

という感じで解けます。最大 $K$ 個というのが厄介そうに見えますが、選択できる最大数を選択する方が明らかによいので、最初の方の $K$ 個に満たない区間に気をつけるだけです。

計算量は $O(N)$ 。

E - Train

14分。

出発点が決まっていて、コスト（所要時間）が正なのでダイクストラ法を使いたくなります。ただし、各列車の出発タイミングが決まっているので、単純な方法では無理です。

ダイクストラ法でコスト最小の頂点から次の頂点へ向かうコスト計算に、このタイミング計算を組み込みます。現在の頂点へ到達できる最小コストを $c$ 、列車の出発タイミングを $k$ 、所要時間を $t$ とすると、次の頂点へ到達したときの総コストは $\lceil \frac{c}{k} \rceil \cdot k + t$ です。

計算量は $O( (N + M)\log (N) )$ 。

D - Grid Components

40分。

よく分からないので、 $A = 1, B = 1$ から始めて 1 つずつ増やしていく方法を考えてみます。たとえば $A$ を 1 つ増やしたければ、黒マスの海の中に 1 つ白を作ればよいイメージです。以下のような初期状態を考えます。

f:id:ibako_piyo:20220416174927p:plain — 初期状態

初期状態は $A=1, B=1$ です。ここから $A=3, B=4$ という状態を作りたければ、以下のように点を打っていけばよさそうです。

f:id:ibako_piyo:20220416175143p:plain — $A=3, B=4$

このような手順で考えます。なお、複数行に渡る場合は以下のように打てばよさそうです（盤面の大きさを変えています）。

f:id:ibako_piyo:20220416175459p:plain — $A=8, B=1$

ところで、この手順で大丈夫なのでしょうか。白点を打っているのに白の海に突入したり、連結したりすると破綻してしまいます。ここで最悪状態を考察します。どのような条件でも $100 \times 100$ の盤面を取った方がよいので、その前提で考えます。

$A, B \le 500$ なので、たとえば白は下から $2 \times \lceil \frac{499}{50} \rceil - 1 = 19$ 行目までを使います。黒で塗りつぶすのは下から 50 行目までなので、十分足りています。黒についても同様です。よって、問題ないことが分かりました。