回答
C++
Submission #552164 - AtCoder Beginner Contest 030 | AtCoder
Python3
Submission #552177 - AtCoder Beginner Contest 030 | AtCoder
移動先で,現在の時刻+移動時間 より大きい一番最初の値を配列の中から取り出す.
この操作を繰り返しながら,Aに到着した回数を数える.
って操作になります….
C++であれば, lower_boundが使えます.
これを使って移動し続ければOKですね….イテレータを初めてまともに使った気がする.
イテレータはポインタなので,扱い方が少しむずかしいですね.(もともとC言語書いてたので,久々にポインタ見て懐かしいとか言っているだけで,ハマりはしませんでいたが)
参考リンク
lower_boundとupper_bound - HPCメモ
lower_bound - C++ Reference
https://www.sist.ac.jp/~suganuma/cpp/man/STL/lower_bound.htm
http://www.cppll.jp/cppreference/cppmap_details.html
C++編(標準ライブラリ) 第20章 ソート済みの範囲を扱うアルゴリズム
int main(){ cin.tie(0); ios::sync_with_stdio(false); cout.precision(16); int N, M; int X, Y; cin >> N >> M; cin >> X >> Y; vector<int> airportA(N); vector<int> airportB(M); REP(i, N) cin >> airportA[i]; REP(i, M) cin >> airportB[i]; int res = 0; int current = 0; bool turn = true; vector<int>::iterator it; it = lower_bound(airportB.begin(), airportB.end(), airportA[0] + X); while(it != airportB.end() && it != airportA.end()) { current = *it; if(turn) { it = lower_bound(airportA.begin(), airportA.end(), current + Y); res++; } else { it = lower_bound(airportB.begin(), airportB.end(), current + X); } turn = !turn; } cout << res << endl; return 0; }
Pythonの場合は,bisectが使えます(が,いわく平衡でないので,処理速度が遅いみたい)
だいたい使い方は一緒.だけど,取り出せるのがポインタじゃないので,少し処理を書き換える必要がありました.
参考リンク
8.6. bisect — 配列二分法アルゴリズム — Python 3.3.6 ドキュメント
ライブラリ:bisect - Life with Python
import bisect N, M = map(int, input().split()) X, Y = map(int, input().split()) ali = [int(i) for i in input().split()] bli = [int(i) for i in input().split()] res, idx = 0, 0 func = lambda li, i: bisect.bisect_left(li, i) while True: if idx >= N: break idx = func(bli, ali[idx] + X) if idx >= M: break idx = func(ali, bli[idx] + Y) res += 1 print(res)