JOI2021 参加記 - aspirator’s blog

初めに

みんな書いてたので参加記を書こうと思いました。

こういうのを書くのは初めてなので色々おかしくても多めに見てください。

予選

A問題

A - 往復すごろく (Round Sugoroku)

setで殴ることができ、 $O(NlogN)$ 。

予選A問題にしては割と難しかったように思いました。

B問題

まだB問題なのにパッと方針が出ずかなり焦りました。

3進法にパンケーキの状態を3進法に直し、BFSで前計算して $3^{N}N+Q$ という満点解法が思いつき、小課題と実装量が変わらなそうだったのでいきなり満点解法の実装を始めました。

しかし、実行したところバグったためBはいったん飛ばしてCを解くことにしました。

Cを解いた後

C問題

見た瞬間にダイクストラ解を思いつき、そのまま実装しました。

多少バグらせて時間を掛けるも満点を得ることができました。

B問題へ戻る

一回D問題に目を通すも解法が思いつかなかったためB問題に戻りました。

競技時間終了までデバッグするも部分点すら取れず競技時間終了。

競技終了してから今更になって部分点を取っていなかったことを後悔しました。

終了後

kichiさんによるスプレッドシートを見ると、僕と同様に200点を取っている人は多く、本選進出はかなり厳しいという印象を受けました。

しかし、ふたを開けてみるとボーダーは186点だったようで、本選進出することができました！yay!

また、双子によれば、200点は高確率で通ると予想していたようで、経験者の勘の強さに驚きました。

本選

開会式

動画のクオリティが凄かったです。（小並感）

自己紹介動画

twitterでしか知らない人の顔を見ることができ、おもしろかったです。

またdefineさんに絶起する呪いを掛けられました。

本選競技

前日は11時半に就寝し、無事絶起することなく7時半に起床。

前日の地震の影響で協議開始時刻が10時に延期されたため、開始までライブラリの整備などをしていました。

A問題

家庭菜園が趣味のビ太郎は自宅の庭でビバ草という植物を育てている.

庭には N 株のビバ草が東西方向に一列に植えられており，西側から順に $1$ から $N$ までの番号が付いている.

現在，ビバ草 $i (1 ≦ i ≦ N)$ の背丈は Ai である.
育てているビバ草は特別な品種改良の結果，水を与えるたびに背丈が $1$ 伸びる.

ビ太郎は庭の見栄えを良
くするために水やりを複数回行い，以下の条件を満たすようにしたいと考えている．

すべての水やりを行った後のビバ草 $i (1 ≦ i ≦ N)$ の背丈を $Bi$ とする. このとき，「 $1 \leqq j \leqq k-1$ に対しB_j < B_j+1]」かつ「 $k \leqq N-1$ に対し B_j > B_j+1」を満たすような整数 $k(1 \leqq k \leqq N)$ が存在する.

ただし，ビ太郎は不器用なため，1 回の水やりにおいて，ある区間上のビバ草に一斉に水を与えることしかできない.

すなわち，水やりを行うたびにある整数 $L, R (1 ≦ L ≦ R ≦ N)$ を選び，ビバ草 $L, L + 1, . . . , R$ に水を与える.
ビ太郎は水やりの回数をできるだけ少なくしたい．
ビバ草の数と現在の背丈の情報が与えられたとき，条件を満たすのに必要な水やりの回数の最小値を求めるプログラムを作成せよ.

制約

$2 ≦ N ≦ 200 000$ .

$1 ≦ Ai ≦ 1 000 000 000 (1 ≦ i ≦ N)$ .

左右からシミュレーションしていくのが一番最初に思いつきました。

しかし、やや実装が面倒くさいと思ったため、「端からi番目まで山なりにするのにかかる水やりの回数」を左右から累積和のように取っていき、水やりの回数を二分探索しました。

しかし、日ごろ二分探索になれていなかったせいか二分探索をバグらせまくって1時間半かけても0点しか取れませんでした。

その後、A問題を飛ばし、Bを解きに行きます。

B問題

JOI 平原は東西方向に広がるとても大きな平原である．この平原は数直線と見なすことができ，各地点は
東向きを正とする座標であらわされる．JOI 平原は冬を迎え $N$ 個の雪玉が異なる座標に作られた．雪玉に
は西から順に $1$ から $N$ までの番号が付いている．最初，雪玉 $i (1 ≦ i ≦ N)$ の座標は整数 $X_i$ であった．
また JOI 平原は冬に強い風が吹くことで知られている．あなたは $Q$ 日間の風の観測データを入手した．

$j$ 日目 $(1 ≦ j ≦ Q)$ の風のデータは整数 $W_j$ であらわされる．

$W_j$ が負のときは西向きに， $W_j$ が負でないときは東向きに，強さ $| W_{j} |$ の風が吹いたことを意味する．
風が吹くと，雪玉は風と同じ向きに，風の強さと同じ距離だけ転がる．

すなわち $j$ 日目 $(1 ≦ j ≦ Q)$ の始
めに座標 $x$ に雪玉があったとき，その雪玉は座標 $x$ から座標 $x + W_j$ まで転がる．

$j$ 日目の終わりには，その雪玉の座標は $x + Wj$ になる．ただし，各日においてすべての雪玉が同時に，同じ速さで転がる．
最初，JOI 平原全体に雪が積もっていた．雪が積もっている範囲を雪玉が転がると，雪が付着し，雪玉の重さが増え，その範囲の雪はなくなる.

すなわち， $a$ を整数とし，座標 $a$ から座標 $a + 1$ までの範囲に雪が残っているとするこのとき，雪玉がこの範囲を転がると，その雪玉の重さが $1$ 増えて，座標 $a$ から座標 $a + 1$ までの範囲の雪がなくなる.

ただし，雪が残っていない範囲を雪玉が転がったとしても，雪玉の重さは変わらない．
最初，すべての雪玉の重さは $0$ であった．

また，観測した $Q$ 日間に新たに雪は降らなかった．
あなたは $Q$ 日目の終わりにおける雪玉の重さを知りたい．
雪玉の最初の座標， $Q$ 日間の風の観測データが与えられたとき， $Q$ 日目の終わりにおける，それぞれの雪
玉の重さを求めるプログラムを作成せよ．

制約

$1 ≦ N ≦ 200 000$ .

$1 ≦ Q ≦ 200 000$ .

$|X_i| ≦ 1 000 000 000 000 (= 10^{12}) (1 ≦ i ≦ N)$ .

X_{i} < X_{i+1} (1 ≦ i ≦ N − 1).

$|W_{j}| ≦ 1 000 000 000 000 (= 10^{12}) (1 ≦ j ≦ Q)$ .

小課題

1.(33点) $N\leqq 2000, Q\leqq 2000$ .