解説 | Blocks

解説

簡単のため、原点を $(0,0,0)$ とし、ブロックは $x,y,z \ge 0$ を満たすマス $(x,y,z)$ にのみ置くことができるとします。マス $u=(x,y,z)$ の原点からのマンハッタン距離を $d(u)=x+y+z$ と表します。

原点からのマンハッタン距離が小さい順からブロックを置いていくことでできる三角錐の形状が最適になります。よって、できるだけ大きな三角錐を作り、端数をうまく処理することで正答を得ます。

なぜ三角錐の形状が最適かの説明

配置したブロックのうち、条件を満たしていない外側のマス $A=(x,y,z)$ に着目します。
マス $A$ のブロックを取り除いたときに条件を満たさなくなるマスは、 $x,y,z$ の各方向について「 $A$ を最も外側のブロックとして依存していたマス」の高々 $1$ マスずつしか存在しないため、自身を除いて高々 $3$ マスです。

ブロックを最も効率よく使うには、外側にあるブロックの多くがこの上限である「 $3$ マス」を同時に支えている必要があります。

ここで、ブロック $A$ が $3$ マス { $X=(x',y,z),Y=(x,y',z),Z=(x,y,z')$ ( $x'<x,y'<y,z'<z$ )} を同時に支えているとします。各マスのマンハッタン距離を考えると、 $d(X) \le d(A)-1, d(Y) \le d(A) - 1, d(Z) \le d(A) - 1$ が成り立ちます。

隙間なく最も効率よく支えるとき、これら $3$ マスは $A$ のすぐ手前（ $x' = x - 1, y' = y - 1, z' = z - 1$ ）となり、 $d(X) = d(Y) = d(Z) = d(A) - 1$ とマンハッタン距離がすべて等しく一致します。

外側のブロックすべてにこの高効率な関係（ $3$ マスを同時に支える状態）を成り立たせるためには、条件を満たすマスの境界がどこでも同じマンハッタン距離で揃っていなければなりません。

したがって、原点からのマンハッタン距離が一定以下のマスをすべて満たすような三角錐の形状を考えるのが最適となります。

サイズ $m$ の三角錐に必要な総ブロック数は、 $F(x)=\frac{x(x+1)(x+2)}{6}$ で求まります。 $N$ 個で構築可能な最大の三角錐のサイズ $S_3$ はこの関数をもとにオーバーフローに二分探索をすることで求まります。条件を満たすブロックは $F(S_3-1)$ で、残りのブロック数は $N-F(S_3)$ です。以降 $N'$ とします。

三角錐の斜面を覆うように三角形状に配置します。サイズ $x$ の三角面を追加するのに必要なブロック数は $G(x)=\frac{(x+1)(x+2)}{2}$ 個です。 $N'$ 個で構築可能な最大の三角形のサイズ $S_2$ は、この関数をもとにオーバーフローに気をつけて二分探索をすることで求まります。新たに条件を満たすブロックは $G(S_2-1)$ です。残りのブロック数は $N'-G(S_2)$ です。以降 $N''$ とします。

三角錐と三角面の間にできた溝に残りのブロック数をすべて配置します。端の1個のみ外壁が2つ必要であり、ほかは1個の外壁につき1個埋めることができます。よって新たに条件を満たすブロックは $\max(0, N''-1)$ 個であり、これを $S_1$ とします。

最終的な答えは $S_1+S_2+S_3$ になります。計算量は $O(\log(X^\frac{1}{3}))$ であり、テストケース辺り十分高速に動作します。

実装例(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<typename T, typename F>
T bs(T ok, T ng, F is_ok){
    while(abs(ok-ng)>1){
        T mid = midpoint(ok, ng);
        if(is_ok(mid)){
            ok = mid;
        }else{
            ng = mid;
        }
    }
    return ok;
}
int main(){
    int t;
    cin>>t;
    auto f = [](ll v)->__int128_t{
        __int128_t x = v;
        return x*(x+1)*(x+2)/6;
    };
    auto g = [](ll v)->__int128_t{
        __int128_t x = v;
        return (x+1)*(x+2)/2;
    };
    while (t--){
        ll n;
        cin >> n;
        auto is_f = [&](ll x){return f(x)<=(__int128_t)n;};
        ll s3 = bs<ll>(0, 1LL<<22LL, is_f);
        n -= (ll)f(s3);
        auto is_g = [&](ll x){return g(x)<=(__int128_t)n;};
        ll s2 = bs<ll>(0, 1LL<<32LL, is_g);
        ll ans = (ll)f(s3-1)+(ll)g(s2-1)+max(0LL, n-(ll)g(s2)-1);
        cout<<ans<<'\n';
    }
}

実装例(Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14def bs(ok, ng, is_ok):
    while abs(ok-ng)>1:
        m=(ok+ng)//2
        ok, ng=(m, ng) if is_ok(m) else (ok, m)
    return ok
t=int(input())
n_list=[int(input()) for _ in range(t)]
f=lambda x: x*(x+1)*(x+2)//6
g=lambda x: (x+1)*(x+2)//2
for n in n_list:
    s3=bs(0, 1<<30, lambda x: f(x)<=n)
    n-=f(s3)
    s2=bs(0, 1<<30, lambda x: g(x)<=n)
    print(f(s3-1)+g(s2-1)+max(0, n-g(s2)-1))

実装例(Rust)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26use proconio::input;
fn bs<F: Fn(u64) -> bool>(mut ok: u64, mut ng: u64, is_ok: F) -> u64{
    while ok.max(ng)-ok.min(ng)>1{
        let mid = if ng>ok{
            ok+(ng-ok)/2
        }else{
            ok-(ok-ng)/2
        };
        (ok, ng) = if is_ok(mid){(mid, ng)}else{(ok, mid)};
    }
    ok
}
fn main(){
    input!{t: usize, n_vec: [u64; t]}
    let f = |x: u64|x.checked_mul(x+1).and_then(|a|a.checked_mul(x+2)).map(|a|a/6).unwrap_or(u64::MAX);
    let g = |x: u64|(x+1).checked_mul(x+2).map(|a|a/2).unwrap_or(u64::MAX);
    for n in n_vec{
        let mut ans = 0;
        let s3=bs(0, u64::MAX, |x|f(x)<=n);
        ans += f(s3-1);
        let n = n-f(s3);
        let s2=bs(0, u64::MAX, |x|g(x)<=n);
        ans += g(s2-1)+(n-g(s2)).saturating_sub(1);
        println!("{}", ans);
    }
}

難易度評価

外部サイトへ移動します

Blocks

解説

ユーザー解説