Zenn
🍣

【緑】ABC397

に公開
AtCoder
abc397
tech

こんにちは．tokidasakanaです．AtCoder Beginner Contest 397の自分の結果をまとめます．
https://atcoder.jp/contests/abc397

結果


tokidasakanaさんのオムロンプログラミングコンテスト2025（AtCoder Beginner Contest 397）での成績：2355位
パフォーマンス：1166相当
レーティング：801→846 (+45) :)
Highestを更新しました！

A-Dの4完でした．まだレートが下がったことがないので，この調子であげていこうと思います．

A問題(100点)

  • 問題文（要約）
    X が38.0以上なら1，37.5以上38.0未満なら2，37.5未満なら3を出力せよ
  • 制約
    • 30 \leq X \leq 50
    • X は少数第1位まで与えられる

自分のコード

a.cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    double x; cin >> x;
    if (x >= 38.0) cout << 1;
    else if (x >= 37.5) cout << 2;
    else cout << 3;
    cout << '\n';

    return 0;
}

問題文の通りにやるだけでした．ちゃんとdouble型の正しい処理をしないと不正解になると思います．知らんけど．

B問題(250点)

  • 問題文（要約）
    i, oのみからなる文字列Sが与えられます．Sの任意の位置に文字を0文字以上挿入することで，変更後の文字列が以下の条件を満たすようにしたいです．

    • 長さが偶数であり，奇数文字目がiで偶数文字目がoである．

    挿入する必要のある文字数の最小値を求めて下さい．

  • 制約

    • Sはi,oからなる長さ1以上100以下の文字列

自分のコード

a.cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s; cin >> s;
    vector<char> t;
    for (char c : s) {
        int cnt = t.size() + 1;
        if (cnt % 2 == 1) {
            if (c == 'o') t.push_back('i');
            t.push_back(c);
        } else {
            if (c == 'i') t.push_back('o');
            t.push_back(c);
        }
    }
    if (t.size() % 2 == 1) t.push_back('o');
    cout << t.size() - s.size() << '\n';

    return 0;
}

おそらく想定解法は，Sを見ながら答えをカウントし，それを出力するというやり方だと思います．
自分はSを見ながら新しい文字列Tを作成し，文字数の差を出力するというやり方でこの問題を解きました．
やり方は置いておくにしても，vectorを使用する必要はありませんでした．無駄な構造やライブラリは使用しないように心掛けているので，少し反省．
というわけで以下のコードでも正解しました．

a.cpp
#include <bits/stdc++.h>
using namespace std;
using ll = __int128_t;

string s, t;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> s;
    for (char c : s) {
        int cnt = t.size() + 1;
        if (cnt % 2 == 1) {
            if (c == 'o') t += 'i';
            t += 'o';
        } else {
            if (c == 'i') t += 'o';
            t += 'i';
        }
    }
    if (t.size() % 2 == 1) t += 'o';
    cout << t.size() - s.size() << '\n';

    return 0;
}

C問題(350点)

  • 問題文（要約）
    長さNの整数列A = (A_1, A_2, ... , A_N)が与えられます．
    Aを1か所で区切って2個の空でない連続する部分列に分割するとき，数列に含まれる数の種類数の和としてありえる最大値を求めてください．

  • 制約

    • 2 \leq N \leq 3 \times 10^5
    • 1 \leq A_i \leq N (1 \leq i \leq N)
    • 入力はすべて整数

自分のコード

a.cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, a[3<<17];
int sm[2][3<<17];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    set<int> s, t;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        s.insert(a[i]);
        sm[0][i] = s.size();
    }
    for (int i = n - 1; i >= 0; i--) {
        t.insert(a[i]);
        sm[1][i] = t.size();
    }
    int ans = 0;
    for (int i = 1; i <= n - 1; i++) {
        ans = max(ans, sm[0][i - 1] + sm[1][i]);
        // cout << sm[0][i - 1] << sm[1][i] << '\n';
    }
    cout << ans << '\n';

    return 0;
}

setを使用したので，計算量はO(NlogN)ですが，答えの探索はO(N)でできます．
左右それぞれから種類数を累積する配列を用意し，区切る箇所の左右で配列を見ればよいです．
具体的には以下のように考えました(入力例1より)

配列名 中身
A [3, 1, 4, 1, 5]
SM_1 [1, 2, 3, 3, 4]
SM_2 [4, 3, 3, 2, 1]

種類数は重複をカウントしないようにsetを使いましたが，これも別の配列で管理できるので不要だということがあとでわかりました(O(N)で実現可能)．とはいえ個人的にはきれいにかけたコードだと思っています．

D問題(425点)

  • 問題文
    正整数Nが与えられます．x^3 - y^3 = Nを満たす正整数の組(x, y)が存在するか判定し，存在する場合はそのような(x, y)を一つ出力してください．(ない場合は-1を出力)
  • 制約
    • 1 \leq N \leq 10^{18}
    • 入力はすべて整数

自分のコード

a.cpp
#include <bits/stdc++.h>
using namespace std;
using ll = __int128_t;

long n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    n = (ll)n;
    for (ll k = 1; k * k * k <= 4 * n; k++) {
        ll t2 = 3 * k * (4 * n - k * k * k);
        for (ll t = (ll)sqrt(t2) - 1; t <= (ll)sqrt(t2) + 1; t++) {
            if ((t - 3 * k * k) % (6 * k) == 0) {
                ll y = (t - 3 * k * k) / (6 * k);
                ll x = y + k;
                if (y == 0 || x == 0) continue;
                if ((x - y) * (x * x + x * y + y * y) == n) {
                    cout << (long)x << ' ' << (long)y << '\n';
                    return 0;
                }
            }
        }
    }
    cout << -1 << '\n';

    return 0;
}

計算量はO(\sqrt[3]{N})です．
まずは以下のように変形しました．

\begin{aligned} x^3 - y^3 = (x-y)(x^2+xy+y^2) &= N \end{aligned}

そして，x-y=Kと置きます．ここまでは解答と同じです．このKを1から\sqrt[3]{N}まで動かして考えることで答えを導きます．私はここから以下のように変形しました．

\begin{aligned} x &= y+K \\ N &= K(x^2+xy+y^2) = K\{(y+K^2)+(y+K)y+y^2\} \\ &= K(3y^2+3Ky+K^2) \\ y &= \frac{\sqrt{3K(4N-K^3)}-3K^2}{6K} \end{aligned}

これでyを求めれば，x=y+Kなのでxがわかり，これが元の式を満たすなら，答えであるということになります．
コード上では，t_2=3K(4N-K^3)と置き，浮動小数点が怖いので，for文上でt=\sqrt{3K(4N-K^3)}としました．こうすれば，y=\displaystyle\frac{t-3K^2}{6K}となり整数yが求まります．あとはx=y+Kとし，(x-y)(x^2+xy+y^2)=Nが成り立てばそれを出力し終了します．
ここで当たった壁がオーバーフローです．単純にこれらは数値によっては64bitで計算できずオーバーフローします．コンテスト中の私はこれ以上なにも考えたくなかったので，多倍長整数を使うことにしました．これで128bitまで対応し，このコードで正解できました．
解答では二分探索を行っていました．たしかによく考えてみれば二分探索できれいにかける気がしました．コンテスト中は冷静ではいられません．

感想

今回は配点がおかしいものの，C問題350点までを比較的早くとったのでD問題を余裕もって考えることができました．ゆえの4完だったと思います．途中でE問題も見ましたができそうになかったので，D問題を集中して考えました．目標は水色，できるなら一回も下がらずに到達したいです．

Discussion