D - Lazy Faith

[kenchanbomber]

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

寺と神社のどちらも訪れるとして、最小の移動距離を高速に求める。

x以上の値のidxについてはlower_boundで求められるが、x以下の値をどう求める？

[kenchanbomber]

以下でx以下の値のidxを求められる。

upper_bound(v.begin(), v.end(), x) - v.begin()

[kenchanbomber]

見つかる場合、見つからない場合を分けないといけない。。。

最終的には距離が問題となるので、とても遠い距離の番兵を入れておくとその場合わけがなくなる。

[kenchanbomber]

寺／神社 前に進む／後ろに進む これらの場合分けを行うと以下のようになる。

先に神社に行く。 前に進み寺に行く／後ろに進み寺に行く

先に寺に行く。 前に進み神社に行く／後ろに進み神社に行く

[kenchanbomber]

rep(i, 2) {
            if (i) {
                // front
                ll place1 = front(s, x);
                rep(j, 2) {
                    if (j) {
                        // front
                        ll place2 = front(t, place1);
                        chmin(ans, distance(x, place1) + distance(place1, place2));
                    } else {
                        ll place2 = back(t, place1);
                        chmin(ans, distance(x, place1) + distance(place1, place2));
                    }
                }
            } else {
                // back
                ll place1 = back(s, x);
                rep(j, 2) {
                    if (j) {
                        // front
                        ll place2 = front(t, place1);
                        chmin(ans, distance(x, place1) + distance(place1, place2));
                    } else {
                        ll place2 = back(t, place1);
                        chmin(ans, distance(x, place1) + distance(place1, place2));
                    }
                }
            }
        }
        // 寺→神社
        rep(i, 2) {
            if (i) {
                // front
                ll place1 = front(t, x);
                rep(j, 2) {
                    if (j) {
                        // front
                        ll place2 = front(s, place1);
                        chmin(ans, distance(x, place1) + distance(place1, place2));
                    } else {
                        ll place2 = back(s, place1);
                        chmin(ans, distance(x, place1) + distance(place1, place2));
                    }
                }
            } else {
                // back
                ll place1 = back(t, x);
                rep(j, 2) {
                    if (j) {
                        // front
                        ll place2 = front(s, place1);
                        chmin(ans, distance(x, place1) + distance(place1, place2));
                    } else {
                        ll place2 = back(s, place1);
                        chmin(ans, distance(x, place1) + distance(place1, place2));
                    }
                }
            }
        }

[kenchanbomber]

三項演算子で短くかける

rep(i, 2) {
            ll place1 = i ? front(s, x) : back(s, x);
            rep(j, 2) {
                ll place2 = j ? front(t, place1) : back(t, place1);
                chmin(ans, distance(x, place1) + distance(place1, place2));
            }
        }
        // 寺→神社
        rep(i, 2) {
            ll place1 = i ? front(t, x) : back(t, x);
            rep(j, 2) {
                ll place2 = j ? front(s, place1) : back(s, place1);
                chmin(ans, distance(x, place1) + distance(place1, place2));
            }
        }