【c++】ABC361 A-F問題解説【ACコード付き】（毎日ABC day25）

AtCoder Beginner Contest 361

A,B,Cの3完。

E, F問題がもしかしたら解けるかもしれないと思い、D問題より前に解いていたら時間がなくなってしまった。無念。

安定してD問題までは解けるようになって、E問題で勝負できるようになりたい。

A - Insert

長さ $N$ の整数列 $A$ と整数 $K,X$ が与えられる。
整数列 $A$ の $K$ 要素目の直後に整数 $X$ を 1 つ挿入した整数列を出力してください、という問題。

$K$番目まで要素を順番に出力して、$X$を出力すればOK。

ll N, K , X;
ll A[109];

int main()
{
	cin >> N >> K >> X;
	for (int i = 0; i < N ; i++) cin >> A[i];
	for (int i = 0; i < N ; i++)
	{
		if (i > 0) cout <<  " ";
		cout <<  A[i];
		if (i + 1 == K ) cout << " " << X;
	}
    return 0;
}

B - Intersection of Cuboids

3次元空間内で2つの直方体が与えられるので、それらが共通の体積を持つか、という問題。

2次元でまず考えるとわかりやすいが、長方形同士が重複する面積を持つ場合は、X軸Y軸ともに重複していなければならない。3次元でも同様で、X, Y, Z軸の全てにおいて重複がある場合に共通の体積を持つので、軸それぞれに対して重なりがあるかを判定すればOK。

ll a,b,c,d,e,f,g,h,i,j,k,l;
ll A[109];

int main()
{
	cin >> a >> b >> c >> d >> e >> f >> g >> h >> i >> j >> k >> l;
	if (d <= g || j <= a) 
	{
		cout << "No" << endl;
		return 0; 
	}
	if (e <= h || k <= b) 
	{
		cout << "No" << endl;
		return 0; 
	}
	if (f <= i || l <= c) 
	{
		cout << "No" << endl;
		return 0; 
	}
	cout << "Yes" << endl;
	return 0; 
}

C - Make Them Narrow

$N$個の数字のうち、$K$回だけ任意に削除できる。残りの要素での絶対値の一番大きな組の絶対値をいくつまで小さくできるか、という問題。

1つずつ数字を取り除くことを考えるとき、一番大きな絶対値の組の絶対値を小さくするために取り除くべきは最大の数か最小の数かの2択である。その2択を決めるのは、それらの数が一番近い要素との絶対値の大きさである。

よって$K$回だけその操作を繰り返し、残った数の最大値と最小値の差分を出力すればOK.

cppでは配列の前からも後ろからも要素を削除できる、便利なデータ型にdequeというものが準備されている。

ll N, K;

int main()
{
    cin >> N >> K;
    deque<ll> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    sort(A.begin(), A.end());
    // 要素を1つずつ取り除いていく
    for (int i = 0; i < K; i++)
    {
        if (A[1] - A[0] > A[A.size() - 1] - A[A.size() - 2]) A.pop_front();
        else A.pop_back();
    }
    // 残った数の中で最大の絶対値を出力
    cout << A.back() - A.front() << endl;
    return 0;
}

D - Go Stone Puzzle

コンテスト中にも幅優先探索だな、と思ってはいた。
しかし、E,Fの考察に時間をかけすぎてしまい、結局3問ともACできなかった泣。

mapに盤面情報としてのstringとスタートから到達できる最短移動回数であるllを保持させておいてやる方法はシンプルながら応用先も広いと感じた。以下は解説のYoutubeで実装されていたコードを見ながら実装したもの。

int main() {
    ll N;
    string S, T;
    cin >> N >> S >> T;
    S += "..";
    T += "..";
    // 幅優先探索の準備
    map<string, ll> dist;
    queue<string> Q;
    dist[S] = 0; Q.push(S);
    // 幅優先探索の実行
    while (!Q.empty())
    {
        string tmp = Q.front(); Q.pop();
        int index = 0;
        while (tmp[index] != '.') index++;
        for (int i = 0; i < N + 1; i++)
        {
            if (tmp[i] == '.' || tmp[i+1] == '.') continue;
            string nex = tmp;
            swap(nex[i], nex[index]);
            swap(nex[i+1], nex[index+1]);
            if (dist.count(nex)) continue;
            dist[nex] = dist[tmp] + 1; Q.push(nex);
        }
    }
    if (dist.count(T)) cout << dist[T] << endl;
    else cout << -1 << endl;
    return 0;
}

E - Tree and Hamilton Path 2

まず簡単な場合である、スタート地点に戻ってこないといけない場合を考えると、全ての辺を2回通ることになる。

そこから最長の長さ（木の直径）を求めて引いた値が答えとなる。

vector<vector<pair<ll, ll>>> Graph;
ll ans = 0;

pair<ll, ll> ft_dfs(ll current_node, ll cumulative_distance = 0, ll parent_node = -1)
{
    pair<ll, ll> result = make_pair(cumulative_distance, current_node);
    for (int i = 0; i < Graph[current_node].size(); i++)
    {
        ll next_node = Graph[current_node][i].first;
        ll edge_cost = Graph[current_node][i].second;
        // 親ノードに戻る場合はスキップ
        if (next_node == parent_node) continue;
        result = max(result, ft_dfs(next_node, cumulative_distance + edge_cost, current_node));
    }
    return result;
}

int main()
{
    ll N;
    cin >> N;
    Graph.resize(N);
    for (int i = 0; i < N - 1; i++)
    {
        ll A, B, C;
        cin >> A >> B >> C;
        A--; B--; // ノード番号を0から始める
        Graph[A].push_back(make_pair(B, C));
        Graph[B].push_back(make_pair(A, C));
        ans += C * 2;
    }
    // 木の片側の端を求める
    pair<ll, ll> dfs_first = ft_dfs(0);
    ll farthest_node = dfs_first.second;
    // 逆側の端までの距離を求める
    pair<ll, ll> dfs_second = ft_dfs(farthest_node);
    ll max_distance = dfs_second.first; // ここで累積距離を取得
    // 最長の片道分だけ答えから引く
    ans -= max_distance;
    cout << ans << endl;
    return 0;
}

F - x = a^b

$2^{60} > 10^{18}$より、60までの指数を全探索する。

それぞれの指数における基数の範囲は二分探索法で求める。

2^4とも4^2とも記述できる16のような数が重複カウントになってしまうことに注意。

// nまでの整数で、x^b乗の形で記述できるものの数を求める
ll calc(int b, ll n) {
    ll ac = 0;      // ac：ac^b <= nを満たす最大の整数
    ll wa = n + 1;  // wa：wa^b > nを満たす最小の整数
    // acとwaが隣接するまで2分探索を回す
    while (ac + 1 < wa) {
        ll mid = (ac + wa) / 2;
        bool judge = true;  // judge：mid^b <= n を判定するためのフラグ
        ll x = 1;
        for (int i = 0; i < b; ++i) {
            // オーバーフロー対策
            if (n / x < mid) {
                judge = false;
                break;
            }
            x *= mid;
        }
        if (judge && x <= n) {
            ac = mid;
        } else {
            wa = mid;
        }
    }
    // 今回1乗はカウントしないので1引く
    return ac - 1;
}

int main() {
    ll n;
    cin >> n;

    const int M = 60;
    vector<ll> f(M, 0);
    ll ans = 1;
    // 60乗までを全探索
    for (int b = M - 1; b >= 2; b--) {
        f[b] = calc(b, n);
        // 重複削除：上位の累乗で求められた数を引く
        for (int i = b * 2; i < M; i += b) {
            f[b] -= f[i];
        }
        ans += f[b];
    }
    
    cout << ans << endl;
    return 0;
}