ABC119 D Lazy Faith を二分探索を使わずに解く(C++) - あるエンジニアのAtCoder奮闘記

irisruneです。一昨日のAGCは所用で参加できなかったので今日も過去問になります。

前回と同様、今回もC++での提出コードです。

https://atcoder.jp/contests/abc119/tasks/abc119_d

この問題のポイントは

$x_i$ に（東西それぞれで）最寄りの神社と寺を高速で求める方法
最寄りの神社と寺から要求された解を求める方法

…らしいです¹。自分は完全に1.で引っかかった口でした。

回答と方針

割と思いつきやすい二分探索が模範解答だったわけですが、自分の回答はというと…

#include <bits/stdc++.h>
using namespace std;

int a, b, q;
vector<long long> va;
vector<long long> vb;
int idxA, idxB;

class X {
    public : int idx;
    public : long long x;
    public : long long l;
    X(int i, long long s){
        idx = i;
        x = s;
    }
};
vector<X> vX;

bool cmp_idx(const X &a, const X &b){
    return a.idx < b.idx;
}

bool cmp_x(const X &a, const X &b){
    return a.x < b.x;
}

void init() {
    cin >> a >> b >> q;
    for(int i = 0; i < a; i++){
        long long s;
        cin >> s;
        va.push_back(s);
    }
    for(int i = 0; i < b; i++){
        long long s;
        cin >> s;
        vb.push_back(s);
    }
    for(int i = 0; i < q; i++){
        long long x;
        cin >> x;
        X X(i, x);
        vX.push_back(X);
    }
    sort(vX.begin(), vX.end(), cmp_x);
}

long long solve(long long x){
    for(int i = idxA; i < a; i++){
        if(x < va.at(i)) break;
        idxA++;
    }
    for(int i = idxB; i < b; i++){
        if(x < vb.at(i)) break;
        idxB++;
    }
    long long westA, eastA, westB, eastB;
    if(idxA == 0) westA = -50000000000;
    else westA = va.at(idxA - 1);
    if(idxA == a) eastA = 50000000000;
    else eastA = va.at(idxA);
    if(idxB == 0) westB = -50000000000;
    else westB = vb.at(idxB - 1);
    if(idxB == b) eastB = 50000000000;
    else eastB = vb.at(idxB);
    long long minL = max(x - westA, x - westB);
    minL = min(minL, (eastA - x) + (eastA - westB));
    minL = min(minL, (x - westB) + (eastA - westB));
    minL = min(minL, (eastB - x) + (eastB - westA));
    minL = min(minL, (x - westA) + (eastB - westA));
    minL = min(minL, max(eastA - x, eastB - x));
    return minL;
}

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    init();

    for(int i = 0; i < q; i++){
        vX.at(i).l = solve(vX.at(i).x);
    }
    sort(vX.begin(), vX.end(), cmp_idx);

    for(int i = 0; i < q; i++){
        cout << vX.at(i).l << "\n";
    }
    return 0;
}

一応方針を説明すると、