ABC076-D : AtCoder Express
D問題 AtCoder Express
はじめに
この記事は、解説のeditorial
(https://img.atcoder.jp/abc076/editorial.pdf)
および
AtCoder Beginner Contest 076 解説放送 - YouTube
を参考にして執筆した。
理解の助けになると思われるので、それぞれのリンクを参照されたい。
また、紹介するソースコードのforループは以下のようなマクロを使用している。
| 書き方 | 意味 |
|---|---|
| REP(i, N) | for (int i = 0; i < N; ++i)と同義 |
| RREP(i, N) | for (int i = N - 1; i >= 0; --i)と同義 |
考え方
本記事では、この問題を以下の4段階(+1)の考察で解説している。
1. 列車の総走行時間を考える。
2. t[s]からt+1[s]の間の変化を考える。
3. 0.5[s]間隔で考えた時の列車の移動距離を考える。
4. (0 ≦ t ≦ T)の範囲のv[t][m/s]の求め方を考える。
5. 以上の考察をまとめてコーディングする。
順を追って説明する。
1. 列車の総走行時間を考える
列車の総走行時間をT[s]としたとき、文章中に書いてある通り
]である1。
したがって、以下のようにforループで総和を求めれば良い。
// 全体のT秒を求める int T = 0; REP(i, N) { T += t[i]; }
2. t[s]からt+1[s]の間の変化を考える
1.で総走行時間Tを求めた。
t[s] (0 ≦ t ≦ T)について、t[s]からt+1[s]までの変化を考える。
しかし、入力例4から分かる通り、t[s]からt+1[s]の変化は単調増加、もしくは単調減少ではない。
したがって、時間の区切りをt[s]からt+0.5[s]までの変化を考える。
ここで、t[s] (0 ≦ t ≦ T)について、0.5[s]間隔のt[s]ををmaxV[t]として保持する。
0.5秒間隔であることから、配列の要素数は2 * T + 1である2。
今回は、t[s]の時の最大速度をmaxV[t][m/s]とする。
このmaxVは0.5秒間隔なので、t[s]のv[t]に対してt * 2個目とt * 2 + 1個目の配列の要素と対応している。
また、最後に閉区間の重なっている部分は2つの要素の最小値を求める必要があることに留意したい。
これらは、以下のように実装できる3。
const int INF = 1e9 + 1; vector< double > maxV(2 * T + 1, (double)INF); // maxVのスピードをv[i]で初期化 int nowT = 0; REP(i, N) { REP(ti, t[i]) { int t1 = nowT + ti * 2; int t2 = nowT + ti * 2 + 1; maxV[t1] = min(maxV[t1], v[i]); maxV[t2] = min(maxV[t2], v[i]); } nowT += t[i] * 2; maxV[nowT] = min(maxV[nowT], v[i]); }
3. 0.5[s]間隔で考えた時の列車の移動距離を考える
2.で示した0.5秒間隔の移動を考えると以下の図のようになる。
この図において、移動距離は台形の面積として表せるため、
として表せる。
したがって、総移動距離はtsの範囲でS_tの総和を求めれば良い。
これを求めるためには、以下のようにforループを用いれば容易に実装できる。
double ans = 0.0; REP(i, 2 * T + 1) { // (上底 + 下底) * 高さ / 2 ans += (maxV[i] + maxV[i + 1]) * 0.5 / 2.0; }
4. (0 ≦ t ≦ T)の範囲のmaxV[t][m/s]の求め方を考える
まず、問題文の
走行開始時と走行終了時には列車は止まっていなければならない
という記述から、
0[s]およびT[s]の時のmaxVは0[m/s]である。
次に、問題文の
加速度±1[m/s2]以内でなければならない
という記述から、
v[t]からv[t+1]の変化は±1以内に収まることが分かる。
ただし、2.でmaxV[m/s]は0.5[s]間隔としたので、
maxV[t]からmaxV[t + 1]の変化は0.5以内に収まるはずである。
これが成り立つようにするには、
0[s]からT[s]までの変化について、
maxV[t] = min(maxV[t], maxV[t - 1] + 0.5)
であり、
T[s]から0[s]までの変化について、
maxV[t] = min(maxV[t], maxV[t + 1] + 0.5)
と表せる。
したがって、(0 ≦ t ≦ T)の範囲のmaxV[t][m/s]は以下のように2つのforループで求められる。
// 0秒とT秒は0(静止) maxV[0] = maxV[T * 2] = 0.0; // 前から比較 REP(ti, 2 * T + 1) { maxV[ti + 1] = min(maxV[ti + 1], maxV[ti] + 0.5); } // 後ろから比較 RREP(ti, 2 * T + 1) { maxV[ti] = min(maxV[ti], maxV[ti + 1] + 0.5); }
5. 以上の考察をまとめてコーディングする
まとめたものがこちらになります(提出コード)。
Submission #3017041 - AtCoder Beginner Contest 076
#include <bits/stdc++.h> using namespace std; #define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i) #define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i) #define REP(i,n) FOR(i,0,n) #define RREP(i,n) RFOR(i,0,n) const int INF = 1e9 + 1; int main() { int N; scanf("%d", &N); vector< double > t(N); vector< double > v(N); REP(i, N) { scanf("%lf", &t[i]); } REP(i, N) { scanf("%lf", &v[i]); } // 全体のT秒を求める int T = 0; REP(i, N) { T += t[i]; } vector< double > maxV(2 * T + 1, (double)INF); // maxのスピードをv[i]で初期化 int nowT = 0; REP(i, N) { REP(ti, t[i]) { int t1 = nowT + ti * 2; int t2 = nowT + ti * 2 + 1; maxV[t1] = min(maxV[t1], v[i]); maxV[t2] = min(maxV[t2], v[i]); } nowT += t[i] * 2; maxV[nowT] = min(maxV[nowT], v[i]); } // 0秒とT秒は0(静止) maxV[0] = maxV[T * 2] = 0.0; // 前から比較 REP(ti, 2 * T + 1) { maxV[ti + 1] = min(maxV[ti + 1], maxV[ti] + 0.5); } // 後ろから比較 RREP(ti, 2 * T + 1) { maxV[ti] = min(maxV[ti], maxV[ti + 1] + 0.5); } double ans = 0.0; REP(i, 2 * T + 1) { // (上底 + 下底) * 高さ / 2 ans += (maxV[i] + maxV[i + 1]) * 0.5 / 2.0; } printf("%.4f\n", ans); return 0; }
感想
以前見た時はeditorialを見たのに意味がわからなかったが、
順序立てて考えたら割とスッキリしたコーディングができた。
求めたいものは何なのか？
そして、それをそれを求めるためには何が必要なのか？
ということを考えるのが重要だと感じた。
