本日のっていうと毎日やっている感がありますが、実は疲れたときとかはやってないです。 更に解いた問題全部にブログを書いているかというとそういうわけでもなく、結構適当です。

本日の問題

C - Sequence Growing Easyです。

問題概要

長さが$N$の数列$A$と$X$が存在します。$X$の各要素は最初は$0$です。

以下の操作を繰り返すことで$X$を$A$に一致させることができるかを判定し、可能な場合はその最小回数を求めてください。

• $1 \le i \le N-1$を一つ選び、$X_{i+1} = X_i + 1$とする

制約

• $2 \le N \le 2 \times 10^5$
• $1 \le A_i \le 10^9 \quad (1 \le i \le N)$

考察

最初に考えたこと

操作からすぐ分かることとして、先頭の数字を変更することはできません。従って$A_0$が$0$でない場合はその時点で不可能です。また、少し考えると$1, 3$のような差が$2$以上の部分列を含む場合もダメであることが分かります。

ぱっと思いつく反例はこのくらいで、逆にこれら以外の数列は構成できることが分かります。具体的には数列全体を$1,2,3,\dots$と後ろからボトムアップさせ、$A_i$の値に到達した$X_i$から更新をやめればよいです。

この構成の仕方は明らかに無駄が多そうです。なので、ここまで考えた後にどのようにやれば最小になるか、ということを考え始めました。

最小手数を求める

まず、$0,1,2,3$と$0,1,2,1$という例を考えました。これはどちらも$3$回で達成可能です。

実際にここら辺を頭でシミュレーションすると、単調増加部分列になっている部分は前から順番に処理してやるとその長さで処理できそうに見えます。

次に、$0,1,2,2$みたいなのを考えました。これを構成するためには、まず後ろの$2$を作るために$0,0,1,2$みたいな風に$X$を更新する必要があります。その後は普通にやればいいです。

この例を眺めている間に、ぼくは以下の解法を思いつきました。

• 単調増加部分列を全部列挙する
• そのすべての部分列に対し$(最初の値) - 1 + \mathrm{length}$を求める
• 上で求めた値の総和が最小手数になっている

計算量は前から順にみてやればよいので$O(N)$で間に合います。また、ある値$a$を生成するためには必ず$a$回の操作が必要なのは明らかなので最小性も満たしていそうです。

というわけで実装したんですがWAが出ました。

WAの原因

最初はなんか考察が違うのかなとかいろいろ考えてみたんですが、どうも穴がないように見えます。

色々考えて分からなかったので、とりあえずintからlong long intに変えてみるかと思って変えたところ、なんとこれだけでACしました。

通った後に答えの最大値について考察してみたのですが、例えば$0$から$1$ずつ増えて$10^5$になり、その後ずっと$10^5$を取り続ける数列を考えるとこれの答えは確かに$10^{10}$程度になるのでオーバーフローしていることが分かります。もったいないミスでした。

あと、冷静になって考えてみると$(最初の値) - 1 + \mathrm{length}$ってつまり最大値なんですよね。これは解説読んだ後に気づいてなるほどってなってました。なんで気づかないかったんだろう……。

反省点

• 数式はなるべく簡潔な表現を目指そう
• 答えの概算はしよう！
  • 面倒だったらとりあえずlong long intにしておけばよい(最悪)

割とスムーズな実装ができたので良かったなあと思っています。オーバーフローに気をつけようという自戒のために生やした記事でした。