2020/5/31バチャ反省

百年くらい競プロしていなかったのでバチャをしました。最近レートを上げる気力が無いのでコンテストに出ずあとで解いたりしています。そのうちやる気が出たら再開します。

バチャ

リンク

茶色diff*6, 緑diff*4問でやってみました。

結果

f:id:nanigasi_san:20200531020746p:plain 1時間9完でした。Lampムズ過ぎてウケる。全体的には茶色でバグらせがちだったかな？

解説

すぬけ君の塗り絵 2 イージー

方針と実装

黒ではなく、白の範囲について考えます。すなわち、白の長方形を構成する4頂点を更新していきます。では実装していきます(雑)

まず、xyそれぞれの左端と右端を初期化します。左端をl、右端をrとすると $x_l = 0, x_r = W, y_l = 0, y_r = H$ です。

次に、各aについて問題文の通りに更新していきます。

最終的な4頂点からなる長方形の面積が答えですが、左端が右端を超えているときに辺の長さを0にする処理を忘れるとバグるので気を付けましょう

提出

atcoder.jp

Attention

西と東を間違えていて一生バグらせていました(恥ずかしい)

方針と実装

$N \leqq 3\times10^ 5$ なので、全点に対して毎回計算していては $O(N^ 2)$ になってしまい間に合いません。こういう時は前計算してから各点について細かい更新をしていくのがセオリーです。

ある人がリーダーになった時に、その人が振り向かせる必要があるのは「自分より西にいて西を向いている人」と「自分より東にいて東を向いている人」です。

一番西にいる人がリーダーの時を考えると、「自分より西にいて西を向いている人」は当然0人です(まず人がいません)。「自分より東にいて東を向いている人」の人数は、「東を向いている人」から自分が東を向いているかどうかを引くことで求められます。

すると、一番西の人がリーダーの時の答えは「0(自分より西にいる西を向いている人数)」 + 「全体のうち東を向いている人数」 - 「自分が東を向いていたら1, 西を向いていたら0」とおけます。

答えを計算したあとは、自分が西を向いていたら「自分より西にいる西を向いている人数」に1を足します。次の人にとって自分は「自分より西にいる西を向いている人」だからです。

二番目以降の人については、

自分が東を向いていたら「自分より東の東を向いている人数」を1減らす
答えを小さい方に更新する(どのリーダーについても、西西+東東で求められます)
自分が西を向いていたら「自分より西の西を向いている人数」を1増やす

を繰り返していくことで、答えが求まります。

提出

atcoder.jp

怪文書

方針と実装

各文字列で使われている文字と回数を集合に見立てて、その積集合を取ればよいです。

Pythonのsetは重複を許さないので、Counterを使いました。

バグったポイントとしては、更新するときにA-Zの全てのアルファベットについて更新していかないとダメです(初回だけ出てきたアルファベットがあると、それが使用可能と判定されてしまう)

提出

atcoder.jp

引越しできるかな？

方針と実装

ある目線から見たときに最悪の状態を再現して、それの最大値を取ります。

めちゃくちゃふわっとした言い方になってしまいました。x <= y <= zになるように箱をみて、それぞれの軸について最大値であるようなサイズの箱を用意すればよさそうです(証明ができません、直感で戦っていこうな)

実装するうえでは、荷物のサイズをソートして箱のサイズをmaxで更新していきます。

提出

atcoder.jp

Streamline

方針と実装

ある点 $X _ i$ から $X _ {i+1}$ に行くためのコストは $X _ {i+1}-X _ i$ です。ランダムにいくより一番近い点に行ったほうが全体的なコストが抑えられるのは自明なので、Xは事前にソートしておきましょう。

次に、N個の駒があるということについて考えてみます。Xはソート済みなので、当然各駒が交差するような動き方は最適ではありません。[1, 2, 3, 4]と並んでいるときに、(1->3)と(4->2)という動き方をさせるよりは(1->2)と(3->4)の方がコストが小さく済むからです。こう考えると、M個のマスからなるM-1個のコストを、全体でN個に分割できるということが分かります。この時、分割された狭間については移動が必要ないので、その分のコストを消費する必要がありません。(上の例でいう(2->3))

次に、 $各iについてX _ {i+1}-X _ i$ のコスト(M-1個になります)を計算します。すると、この問題は「M-1個のコストがあり、それをN個まで消すことができる。残ったコストの総和を求めよ」と言い換えることができます。