名もなき未知

エンジニアリングとか、日常とかそういうのをまとめる場所。アクセス解析のためGAを利用、Googleに情報を送信しています。商品紹介のためAmazonアフィリエイトを利用、Amazonに情報を送信しています。記事に関しては私が書いていない引用文を除いて自由にご利用ください。

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)