AtCoder Beginner Contest 361

A - Insert

配列の指定したindexに要素を追加しましょう。
C++ならinsertです。

C++

#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int N, K, X;
    cin >> N >> K >> X;
    vector<int> A(N);
    rep(i, N) cin >> A[i];

    A.insert(A.begin() + K, X);

    rep(i, N+1){
        cout << A[i];
        if(i < N) cout << ' ';
        else cout << endl;
    }

    return 0;
} 

B - Intersection of Cuboids

２つの直方体があり、重なっている部分の体積が0以上か求める問題です。
数学の問題ですね。
矩形から復習しましょう。

まず２つの矩形の重なっている部分の面接が0以上か

上記の矩形にて、x軸の重なっている部分は、

txt

min(x1の座標　+　|x1の1辺の長さ|, x2の座標　+　|x2の1辺の長さ|) - max(x1座標, x2座標)

から

txt

min(0 + |0 - 6|, 3 + |3 - 9|) - max(0, 3))
よって、
6 - 3 = 3

となります。
これをx軸のプログラムの式にすると、

C++

int x = max(0, min(x1 + abs(x1 - x2), x5 + abs(x5 - x6)) - max(x1, x5))

となります。
下記のような矩形でも大丈夫か、今度はy軸も含めて検算しましょう。

txt

int x = min(0 + |0 - 6|, -3 + |-3 - 9|) - max(0, -3))
(int x = 6 - 0 = 6)

int y = min(0 + |0 - 6|, 3 + |3 - 9|) - max(0, 3))
(int x = 6 - 3 = 3)

x軸は６、y軸は3ほど重なっている事が分かりました。
重なっている面積は、6*3=18です。
これでx, y軸の計算式のプログラムができました。

C++

int x = max(0, min(x1 + abs(x1 - x2), x5 + abs(x5 - x6)) - max(x1, x5))
int y = max(0, min(y1 + abs(y1 - y2), y5 + abs(y5 - y6)) - max(y1, y5))

z軸も拡張しましょう。

C++

int x = max(0, min(x1 + abs(x1 - x2), x5 + abs(x5 - x6)) - max(x1, x5))
int y = max(0, min(y1 + abs(y1 - y2), y5 + abs(y5 - y6)) - max(y1, y5))
int z = max(0, min(z1 + abs(z1 - z2), z5 + abs(z5 - z6)) - max(z1, z5))

これで問題が解けます。

C++

#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int a, b, c, d, e, f;
    int g, h, i, j, k, l;
    cin >> a >> b >> c >> d >> e >> f;
    cin >> g >> h >> i >> j >> k >> l;

    double x = max(0, min(a+abs(a-d), g+abs(g-j)) - max(a, g));
    double y = max(0, min(b+abs(b-e), h+abs(h-k)) - max(b, h));
    double z = max(0, min(c+abs(c-f), i+abs(i-l)) - max(c, i));

    if(x*y*z>0) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
} 

C - Make Them Narrow

O(K+1)
各要素を取り除くかの全探索は、　2^Nの計算量になるのでTLEになります。

また辺の左右から、
A[1] - A[0]　< A[A.size()-1] - A[A.size()-2]
を判定して取り除くパターンも下記のinputでダメになります。

txt

12 4
1 3 5 7 9 10 15 20 31 32 33 34 

O(K＋1)で探索しましょう。
上記の入力だと8個の要素は必ず残さないといけないです。
Aをソートして、配列の8個の要素の最大値、最小値をK＋1だけ探索しましょう。

C++

#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int N, K;
    cin >> N >> K;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];

    sort(A.begin(), A.end());

    ll ans = NUM_MAX;
    ll M = N - K;
    rep(i, K+1){
        ans = min(ans, A[i+(M-1)] - A[i]);
    }
    cout << ans << endl;

    return 0;
}