読者です 読者をやめる 読者になる 読者になる

水面下の夢

競プロやイラストに興味があります.メインブログがここ.ソシャゲの話はこっち(http://ameblo.jp/0n0-yumechi/).ブログアイコンはYaQ(@8_9_00)さんから.

ABC030 C - 飛行機乗り

回答

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)