AtCoder Beginner Contest 119

C - Synthetic Kadomatsu

https://atcoder.jp/contests/abc119/tasks/abc119_c
コンテスト中に解けませんでした。。。悲しい。

方針

まず 本の全ての竹について、「Aで使う、Bで使う、Cで使う、使わない」の4通りに分類します。この分類のときに A, B, C を得るのに必要な魔力を求めることは簡単で、まず使うものについては最初に A 用, B 用, C 用それぞれで合成してしまい、あとは A, B, C との差分を延長か短縮すればよいです。
分類の方法は 通りですが、 なので全ての分類方法について必要な魔力を求められます。それらのうちの最小値が答えとなります。
A, B, C それぞれについて、少なくとも 1 本は元となる竹を選ぶ必要があることに注意します。

竹の分類の実装についてですが、4 進数表記で N 桁になる数(ただし、上位桁に 0 が来ても良いものとする)を用います。このような数は 0 から です。各桁について 1 なら A、2 なら B、3 なら C で使い、0 なら使わないと考えればよいです。

下図のようなイメージです( )。

ソースコード

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

int main(){
    int N, A, B, C;
    cin >> N >> A >> B >> C;
    vector<int> l(N);
    for(int i=0; i<N; i++) cin >> l[i];

    int ans = 1e9;
    for(int i=0; i<pow(4,N); i++){
        int n = i;
        int a = 0, b = 0, c = 0; // a,b,cをそれぞれA,B,Cにする
        int tmp = 0;  // この分類方法のときに必要な魔力
        int d = 0; // いま n の 4 進数表記で下から何桁目を見ているかを表す
        while(n>0){
            // n%4 が 1, 2, 3のとき、それぞれ a, b, c に使う。
            if(n%4==1){
                if(a!=0) tmp+=10; // a!=0 に l[d] を合成するには魔力10が必要。以下同様。
                a += l[d];
            }else if(n%4==2){
                if(b!=0) tmp+=10;
                b += l[d];
            }else if(n%4==3){
                if(c!=0) tmp+=10;
                c += l[d];
            }
            n/=4;
            d++;
        }
        // 最低 1 本は元になる竹を選ぶ(無から竹を延長していくのはNG)
        if(a==0 || b==0 || c==0) continue;

        // 不足分を延長or短縮する
        tmp += abs(a-A) + abs(b-B) + abs(c-C);
        ans = min(ans, tmp);
    }
    cout << ans << endl;
}

D - Lazy Faith

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

方針

位置 以東にある、位置 に最も近い神社・寺の位置をそれぞれ とします。
同様に、位置 以西にある、 に最も近い神社・寺の位置をそれぞれ とします。
これら などは二分探索によって求めることが出来ます。

すると、移動の方法は図の (1)～(4) のどれかになるので、これらを全通り試して最も移動距離の小さいものを出力すればよいです。ただし、図では および としていますが、他の場合もあります。

(1) のとき
に訪問します。どちらにも到達しなければならないので、この 2 つのうち遠い方まで行く必要があります。
移動距離は です。

(2) のとき
(1)と全く同じように考えて、 です。

(3) のとき
と訪問する場合と、 と訪問する場合とがあります。
よって、 です。

(4) のとき
(3)と全く同じように考えて、 です。

以上で求めた の中で最も小さいものを出力します。

ところで、以下の2つの場合に注意する必要があります。神社について書きますが、もちろん寺でも同様です。
・ が全ての神社より東のとき
このとき は存在しないことになりますが、 としておけば上記の議論をそのまま適用できます。

・ が全ての神社より西のとき
このとき は存在しませんが、同様に とすればよいです。

以上二つは、あらかじめ の中に inf と -inf を入れておくことで実現できます。 は昇順に並んでいることに注意します。

ソースコード

#include <bits/stdc++.h>
#define inf 1e15
using namespace std;
typedef long long ll;

int main(){
    int A, B, Q;
    cin >> A >> B >> Q;
    vector<ll> s(A+2), t(B+2);
    for(int i=1; i<=A; i++) cin >> s[i];
    for(int i=1; i<=B; i++) cin >> t[i];
    // -inf と inf を追加しておく
    s[0] = -inf;  s[A+1] = inf;
    t[0] = -inf;  t[B+1] = inf;

    while(Q>0){
        ll x; cin >> x;
        ll sr, sl, tr, tl;
        // x 以東で x に最も近い s, t の index を is, it とする。 
        int is = lower_bound(s.begin(), s.end(), x) - s.begin();
        int it = lower_bound(t.begin(), t.end(), x) - t.begin();
        sr = s[is];  sl = s[is-1];
        tr = t[it];  tl = t[it-1];

        ll ans = 1e18;
        ans = max(sr-x, tr-x);  // (1)
        ans = min(ans, max(x-sl, x-tl)); // (2)
        ans = min(ans, 2*(x-sl) + tr-x); // (3)
        ans = min(ans, 2*(x-tl) + sr-x); // (3)
        ans = min(ans, 2*(sr-x) + x-tl); // (4)
        ans = min(ans, 2*(tr-x) + x-sl); // (4)
        cout << ans << endl;

        Q--;
    }
}