abc076-D丁寧に説明してみた
問題ページ:
D: AtCoder Express - AtCoder Beginner Contest 076 | AtCoder
自分の回答:
Submission #1732260 - AtCoder Beginner Contest 076 | AtCoder
先週に開かれたabc076ですが、筆者はビジネスコンテストを参加している真っ最中なので、Bまでだけ解いた。そのあとC、D問題を見て、なかなか面白い問題と初めて気づいた。解説をみて、うーん、わからない！w（一応自分もプログラミング初心者なので...）
改めて問題文をみて、自分の考えた解説をここに乗せておこう。変数名は筆者のコードで使用するものと一致するものを使用する。
問題概要
特急列車がN個の「制限時間」内で走ってる。それぞれの「制限時間」内に、制限速度があって、特急列車がこの速度を超えないように-1[m/s2]~1[m/s2]で加速する。これらを満たす時、列車の最大走行距離を求めなさい。
すぐ分かったこと
1. 加速する時1[m/s2]、減速する時-1[m/s2]。「制限時間」内では最初は加速、最後は減速になっている。
2. 横軸t,縦軸vの時、走行距離は走る速度がx軸との間で出来る面積そのもの。
自分の考えたこと
まず、設問にv[n]というものは、今回ではlimv[n]とさせてもらう前提で話を進める(だってそのvはその区間の制限速度と思うので)。
上記の図のように、区間n,n+1,n+2があるけれど、それぞれの隣接する点に置いて、速度がvと設定する。もちろん一番右端はv[n+3]である。
設定完了と、全ての区間は、左端の速度left、右端の速度right、制限速度limit、その区間である時間timeの四つの要素を用いて面積を計算できる。もちろん全区間の一番左区間のleftは0で、一番右区間のrightは0の設定にはなっている。
こうなると、問題はいかに節点の速度を決めることがこの問題の肝になる。これは以下の3ステップで設定できる:
1. 初期値はもちろん、与えられた制限速度を用いて設定する。v[0]=0, v[N]=0以外のv[i+1]は、区間iと区間i+1に挟まれているので、その間の小さい方min(limv[i], limv[i+1])が自分の速度になる。
2. 左から右に順番で見て行くと、v[i+1]>v[i]の対に対してのみ、v[i+1]=min(v[i+1], v[i]+t[i])というふうに更新する。これは、いくら加速しても、制限時間内での加速限界が両サイトの制限にも達してないと言うことです。減速についてはみなくて大丈夫。（理由を話すとややこしいけど、それでも気になる方がご連絡ください。）
3. 右から左に順番で見て行く。v[i-1]>v[i]の対に対してのみ、上記2のように更新する。
この3ステップで更新すると、全ての境界通過時の速度は必ず計算できる。
次は囲まれた形で台形を計算するだけ。この計算方法は以下のようになる:
1. その区間に入る時、まずは両サイドの小さい方をlに保存して、大きい方をrに保存する。制限上限の速度をlimに保存する。swapなどの機能を使って、必ずl<rにすると計算しやすくなる。
2. 出来上がる台形の場合分けは2ケースのみ。一つはlim=r, もう一つはそれ以外。
2-1:
例えばlimv[n]=rの時、以上の二つの形ができる。左の図の面積は、台形の面積の中から、斜線の三角形の面積を引いた結果だ。右は、この三角形の面積が0と思って一行でコードが書ける。
2-2:
limv[n]>rの場合は、上のようになる。一応コード内で使用する変数名も図の中に表記するようにした。x,yについてはx+y=t[i], x-y = r-lと言う連立方程式から得られるはず。左の場合は、「底が l,l+xで、高さx」の台形と、「底が r,r+yで、高さy」の台形と、真ん中が「top * (x+l)」の長方形で計算した。上記の2-1のように、全体から斜線の三角形を引いたやり方もできる。もちろん後者の方がコードが見やすくなる。
まとめ
一応自分の解き方を載せておいて、解答より理解しやすいのではないかなと思ってる。プログラミングの方が初心者に近い者なので、綺麗さには欠けてることが存じ上げておる。初記事なので、ご意見、ご質問がありましたら是非ご連絡ください。
宜しくお願い致します。
