Codeforces Round #763 感想

A. Robot Cleaner

なんか頭がぼーっとしていて、もたつきました。

問題文

ロボット掃除機が $n \times m$ のマス目に置かれています。このマス目の $r$ 行 $c$ 列目を $(r, c)$ と表すことにします。
ロボット掃除機は $(r_b, c_b)$ に置かれています。

ロボット掃除機は $1$ 秒ごとに $(dr, dc)$ 移動します。つまり $(r, c)$ から $(r + dr, c + dc)$ になります。
$(dr, dc)$ ははじめ $(1, 1)$ 、つまり右下方向に進むようになっています。
ロボットが上下左右にある壁にぶつかると、進行方向が反射します。上下の壁にぶつかると進行方向は $(-dr, dc)$ になり、左右の壁にぶつかると $(dr, -dc)$ になります。

汚れたマス目が $1$ つあり、それは $(r_d, c_d)$ です。ロボットはこの汚れたマス目を掃除する必要があります。
ロボットは自分と同じ行または同じ列のマス目をすべて掃除します。

ロボットが汚れたマス目を掃除するまでに必要な秒数を求めてください。

制約

• $1 \le t \le 10^4$
• $1 \le n \le 100$
• $1 \le r_b, r_d \le n$
• $1 \le c_b, c_d \le m$

解法

縦と横を独立に考えます。

まず、横を考えると、ロボットは右へ進んでいって、それから右端を折り返して左へ進みます。

• このとき、 $c_b \le c_d$ なら、右へ進んでいく途中で掃除できます。答えは $c_d - c_b$ になります。
• そうでなければ、右へ折り返した後で掃除できます。答えは $(m - c_b) + (m - c_d)$ です。

縦についても同様に考えます。
縦と横の答えの小さい方を答えます。

B. Game on Ranges

未証明の、直感です…。

問題文

アリスとボブがゲームをします。
アリスは互いに重ならない整数の区間の集合 $S$ を持っています。最初は $S = \{[1, n]\}$ です。
毎ターンで、アリスは区間 $[l, r] \in S$ を適当に選び、ボブに適当な整数 $d \in [l, r]$ を質問します。アリスは区間 $[l, r]$ を $S$ から取り除き、代わりに $[l, d - 1]$ と $[d + 1, r]$ を追加します。ただし、空になるような区間は入れません。
$S$ が空集合になったらゲームは終わりです。ターン数は必ず $n$ 回になります。

ゲームをした後、アリスは質問した区間 $[l, r]$ をすべて覚えていますが、ボブは自分が答えた整数 $d$ を忘れます。
しかしボブは賢いので、 $[l, r]$ すべてから $d$ を復元することができます。あなたは復元できますか？

制約

• $1 \le t \le 1000$
• $1 \le n \le 1000$
• $1 \le l_i \le r_i \le n$
• $\sum_\text{testcase} n \le 1000$

解法

まず、区間を幅の昇順でソートします。
小さい方から答えを決定していきます。
区間 $[l, r]$ について、

• $l = r$ なら答えは $l$ です。
• そうでないなら、区間に含まれる整数のうち、以前答えていないものが答えです。
  • これは、必ずひとつに定まります。なぜなら、今見ている区間に答えた後は長さは $1$ 以上減るので、これに含まれる区間はすべて、以前に処理したはずだからです。

C. Balanced Stone Heaps

典型なのですんなりいきました。

問題文

$n$ 個の石の山があります。 $i$ 番目の山には $h_i$ 個の石があります。あなたは今から以下の手順で石を動かそうとしています。

• $3$ から $n$ まで順番にします。今見ている山の番号を $i$ とします。
• 適当な整数 $d \in [0, \frac{h_i}{3}]$ を選びます。
• $i$ 番目の山から $i - 1$ 番目の山へ、 $d$ 個の石を動かします。
• $i$ 番目の山から $i - 2$ 番目の山へ、 $2d$ 個の石を動かします。

操作をした後の、 $\min_i h_i$ の最大値を求めてください。

制約

• $1 \le t \le 2 \times 10^5$
• $3 \le n \le 2 \times 10^5$
• $1 \le h_i \le 10^9$
• $\sum_{\text{testcase}} n \le 2 \times 10^5$

解法

最小値の最大値なので、まず二分探索を疑います。実際、 $x \in [1, 10^9]$ で二分探索をすることによって答えを求めることが可能です。

判定は、後ろから操作を考えることで行います。とはいっても、実際の操作は前から行うので、後ろの山からもらってきた石を前の山にあげることはできません。
今ある石と、後ろの山からもらってきた石の合計が $x$ 以上となる最小限の石だけを残して、ほかは全部前の山にあげます。もし、それができないなら、最小値を $x$ 以上にすることは不可能です。