po

ARC 082 F. Sandglass

問題

F: Sandglass - AtCoder Regular Contest 082 | AtCoder

問題概要

容量Xの砂時計にはじめaだけ砂が入っている。時刻riに砂時計をひっくり返すとき、時刻tにおいて砂時計(の片側)に残っている砂の量はいくらか。(t, a)がクエリとして与えられるのでQ回答えよ。

方針

f(t):=時刻tにおいて砂時計(のパーツA)に残っている砂の量 としてグラフを考えてみます。f(0)=ajとすると各クエリにはf(tj)と答えられます。

砂が無限にあるときは、グラフがギザギザするだけなので簡単です。(f(0)+砂の増減とすればいいです)

実際は砂が落ちきることがあるので、\_/←こうなるところがあります。なので単純に増減分だけ調整すればいいことにはなりません。

クエリの数だけ(初期状態の異なる)砂時計が存在すると考えると、f(t)のグラフがQ個かけます。異なる砂時計でも砂の落ちる速さは一定なので、それぞれのグラフの大小が逆転することはありません(初期値f(0)=ajでの大小が保たれます)。つまり、f(0)=aj, akに対するfをそれぞれfj, fkとすると、fj(0)<fk(0)だがある時刻tでfj(t)>fk(t)となることはありません。fj(t)=fk(t)となりうることに注意します。これは、上に挙げたように砂が落ちきることがあるからです。また、ひとたびfj(t)=fk(t)となったとすると以降のτ≧tでfj(τ)=fk(τ)が成り立ちます。

初期値の最小・最大は0, Xなので全てのグラフはf(0)=0, Xで定まる2つのグラフに挟まれることが分かります。それぞれの時刻tにおける値をl(t), u(t)とします。クエリ(aj, tj)に答えるには、f(0)=ajとしてf(tj)が分かればいいのでした。f(tj)の値として考えられるのは、l(tj), u(tj), f(0)+(tjまでの砂の増減)の3つです。f(0)+(増減)<l(tj)のとき、f(tj)=f(0)+(増減)は不適なのでf(tj)=l(tj)になりそうです(きっとなります)。u(tj)のときも同様でです。l(tj)<f(0)+(増減)<u(tj)のとき、イライラ棒を抜けてきた感じがするのでf(tj)=f(0)+(増減)です。

入力例3に対して目に見えるようにしました→ARC082F in3

あまり良い例ではなかったかも。(t, a)=(231, 55)で何か感じとってください。

解答例

ARC082-F Sandglass

おわりに

gistbox無くなるんですか……。

難易度5

f:id:poyopoyoyon:20170824182709p:plain

JOIの難易度5を埋めました。→ AOJ/Atcoder-JOI

印象に残った問題を挙げます。だいたい解けなかったやつです。

続きを読む

CSAcademy 10 D. Subarray Medians

問題

https://csacademy.com/contest/round-10/task/subarray-medians/

続きを読む