問題
解説
体力を無くすことなく指定されたルートをたどり切ることができるか判定してくださいという問題です。移動中にアイテムを拾うこともあるようです。まず、1歩ごとに愚直に全てのアイテムに対して拾うことがあるか判定する実装を仮に組んだ場合を考えます。これだと、移動回数Nは$N≦10^5$でアイテムの数Mも$M≦10^5$であることから実行時間制限に間に合わないことが予想されます。そこで別の実装方法を考えます。
ここで、高橋君の移動した点に存在するアイテムを小さい計算量で検索できないかを考えます。これは連想配列と呼ばれるものを使えば実現できそうです。連想配列のキーに各アイテムの「位置」を、値に「消費されたかどうか」という情報を持たせます。そして高橋君が移動するたび、高橋君の位置に消費されていないアイテムがあるかを連想配列に対して確認しにいきます。あとは題意にそって実装を組むことで計算量が$O(NlogM)$となり、十分間に合いそうです。C++の場合、連想配列としてmapが使えます。
提出コード(コンテスト後)
ご不明点などがあれば教えていただけると幸いです。