2021-06-23

AtCoder Beginner Contest 206 C - Swappable

AtCoder ABC-C

問題

問題文へ

N個の整数からなる数列 $A= \left( A_1, A_2, ..., A_N \right)$ が与えられるので、次の条件を全て満たす整数組 $\left( i, j \right)$ の数を求めてください。

$1 \leq i \lt j \leq N$
$A_i \neq A_j$

制約

入力は全て整数
$2 \leq N \leq 3 \times 10^5$
$1 \leq A_i \leq 10^9$

考えたこと

制約から、全ての整数組を試すのでは間に合いません。ですが、一度それで考えてみて改善できるか確認してみます。

入力例２に注目しました。10個の違う数が含まれた数列では答えは45です。 $A_1$ に対して残りすべてが条件に当てはまるので9個。 $A_2$ は8個と続きます。数列に含まれる数が全て異なるならば、Nとループインデックスで計算できそうです。

数列に等しい数が含まれる場合を考えます。 $A_i$ に注目した時に $A_i = A_j$ になる数がいくつあるかわかればよさそうです。事前に、数列に数が出現する回数を数えておきます。mapを使いました。

最終的には数列の先頭から見ていきます。数列に含まれる数が全て異なる場合から、事前に調べておいた等しい個数を引いてから答えに足していきました。

二重ループから、2回のループになり制限時間に間に合いました。

コード

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


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

    map<ll, int> mp;
    rep(i, N) mp[A[i]]++;

    ll ans = 0;
    for (ll i = 0; i < N - 1; ++i) {
        ll residue = N - 1 - i;
        mp[A[i]]--;
        ans += residue - mp[A[i]];
    }

    cout << ans << endl;
    
    return 0;
}

解説を読んで

整数組 $\left( i, j \right)$ が $\frac{N \times \left(N - 1 \right)}{2}$ が、パッと浮かばないのがつらい。

2021-05-17

AtCoder Beginner Contest 200 C - Ringo's Favorite Numbers 2

AtCoder ABC-C

問題

問題文へ

200という整数が大好きなりんごさんのために、次の問題を解いてください。

N個の正整数からなる数列Aが与えられるので、以下の条件をすべて満たす整数の組(i,j)の個数を求めてください。

$1 \leqq i$ < $j \leqq N$
$A _ i - A _ j は200の倍数である。$

制約

入力は全て整数
$2 \leqq N \leqq 2 \times 10^5$
$1 \leqq A _ i \leqq 10^9$

考えたこと

(i,j) = (1,3),(1,4)ならば、(3,4)も該当し、かつ3と4は調べなくてよさそうです。というおそらくそうだろうでゴリ押しました。

コード

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;

bool b[2 * 100000 + 10];

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

    ll ans = 0;
    for (int i = 0; i < A.size() - 1; ++i) {
        if (b[i]) continue;
        ll count = 0;
        for (int j = i + 1; j < A.size(); ++j) {
            if ((A[i] - A[j]) % 200 == 0) {
                ++count;
                ++ans;
                ans += count - 1;
                b[j] = true;
            }
        }
    }

    cout << ans << endl;
    
    return 0;
}

解説を読んで

計算式が条件にあり、全探索でだめなら計算式の変換が必要のようです。

2021-05-17

AtCoder Beginner Contest 201 C - Secret Number

AtCoder ABC-C

問題

問題文へ

高橋くんは、暗証番号を忘れてしまいました。暗証番号は0から9までの数字のみからなる4桁の文字列で、0から始まる場合もあります。

0から9までの各数字について、高橋くんは以下のように記憶しています。彼の記憶は長さ10の文字列 $S _ 0S _ 1...S _ 9$ によって表されます。

$S _ i$ がoのとき:数字iは暗証番号に確実に含まれていた。
$S _ i$ がxのとき:数字iは暗証番号に確実に含まれていなかった。
$S _ i$ が?のとき:数字iは暗証番号に確実に含まれているかわからない。

高橋くんが忘れてしまった暗証番号としてあり得るものは何通りありますか？

制約

Sはo,x,?のみからなる長さ10の文字列

考えたこと

暗証番号は0000から9999までなので、条件に合うかすべて調べます。どの数字が何回登場したか数え、それと条件と比較します。

oに対する数字が一度も登場していない場合と、xに対する数字が登場していれば条件に合いません。

コード

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


int main(void) {
    string S;
    cin >> S;

    int ans = 0;
    rep(i, 10) rep(j, 10) rep(k, 10) rep(l, 10) {
        vector<int> v(10, 0);
        v[i]++;
        v[j]++;
        v[k]++;
        v[l]++;
        bool ok = true;
        rep(m, v.size()) {
            if (v[m] > 0 && S[m] == 'x') ok = false;
            if (v[m] == 0 && S[m] == 'o') ok = false;
        }
        if (ok) ++ans;
    }

    cout << ans << endl;
    
    return 0;
}

解説を読んで

何回登場したかは必要ない情報でした。暗証番号すべてを調べればよいことに気づくまで時間がかかってしまいました。

2021-03-22

AtCoder Beginner Contest 196 C - Doubled

ABC-C

問題

問題文へ

整数Nが与えられます。以下の条件を満たす1以上N以下の整数xは何個あるでしょうか？ * xの十進表記（先頭に0を付けない）は偶数桁であり、その前半と後半は文字列として等しい。

制約

Nは整数
$1 \leq N \lt 10^{12}$

考えたこと

前半と後半にわけてそれぞれ作ってみようと思いました。

コード

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


int main(void) {
    string N;
    cin >> N;

    if (stoll(N) < 11) {
        cout << 0 << endl;
        return 0;
    }

    ll ans = 0;
    if (N.length() % 2 != 0) {
        string n;
        rep(i, N.length() - 1) {
            n.push_back('9');
        }
        N = n;
    }

    string l = N.substr(0, N.length() / 2);
    string r = N.substr(N.length() / 2);

    ll numl = stoll(l);
    ll numr = stoll(r);

    if (numl <= numr) ans = numl;
    else ans = numl - 1;
    
    cout << ans << endl;

    return 0;
}

解説を読んで

全探索でいいとは…。

2021-03-01

キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193) C - Unexpressed

ABC-C AtCoder

問題

問題文へ

整数Nが与えられます。1以上N以下の整数のうち、2以上の整数a,bを用いて $a^b$ と表せないものはいくつあるでしょうか？

制約

Nは整数
$1 \leq N \leq 10^{10}$

考えたこと

bは2以上なので、 $10^{5*2}$ まで調べればよいです。

コード

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


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

    set<ll> st;
    for (ll a = 2; a <= 100000; ++a) {
        ll num = a;
        num *= a;
        while (num <= n) {
            st.insert(num);
            num *= a;
        }
    }

    cout << n - st.size() << endl;
    
    return 0;
}

解説を読んで

a * a <= Nって書けばよかったです。

2021-02-22

SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192) C - Kaprekar Number

ABC-C

問題

問題文へ 0以上の整数xに対して、 $g_1(x),g_2(x),f(x)$ を次のように定めます。

$g_1(x)$ = xを10進法で表したときの各桁の数字を大きい順に並び替えてできる整数
$g_2(x)$ = xを10進法で表したときの各桁の数字を小さい順に並び替えてできる整数
$f(x) = g_1(x) - g_2(x)$

整数N,Kが与えられるので、 $a_0 = N, a_{i+1} = f(a_i)(i \leq 0)$ で定まる数列の $a_k$ を求めてください。

制約

$0 \leq N \leq 10^9$
$0 \leq K \leq 10^5$
入力はすべて整数

考えたこと

各関数を実装します。Kが最大で $10^5$ なので、 $a_k$ までシミュレートしても間に合います。

コード

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;

int g1(int a) {
    vector<int> v;
    while (a > 0) {
        v.push_back(a % 10);
        a /= 10;
    }
    sort(v.begin(), v.end(), greater<int>());

    int res = 0;
    for (auto i : v) {
        res *= 10;
        res += i;
    }
    return res;
}

int g2(int a) {
    vector<int> v;
    while (a > 0) {
        v.push_back(a % 10);
        a /= 10;
    }
    sort(v.begin(), v.end());

    int res = 0;
    for (auto i : v) {
        if (i == 0) continue;
        res *= 10;
        res += i;
    }
    return res;
}

int f(int a) {
    return g1(a) - g2(a);
}

int main(void) {
    int N, K;
    cin >> N >> K;

    int ans;
    for (int i = 0; i <= K; ++i) {
        if (i == 0) {
            ans = N;
            continue;
        }

        ans = f(ans);
    }

    cout << ans << endl;
    
    return 0;
}

解説を読んで

stringを使うことで実装が楽になる。それ以前に関数で切り出すべきでしたね。

2021-01-13

AtCoder Beginner Contest 188 C - ABC Tournament

AtCoder ABC-C

問題

問題文へ

選手1から選手 $2^N$ までの $2^N$ 人の選手がトーナメント形式のプログラミング対決をします。

選手iのレートは $A_i$ です。どの2人の選手のレートも異なり、2人の選手が対戦すると常にレートが高いほうが勝ちます。

トーナメント票は完全二分木の形をしています。より正確には、このトーナメントは以下の要領で行われます。

i=1,2,3,...,Nについて順に、以下のことが行われる。
- 各整数j（ ${1 \leqq j \leqq 2^{N-i}}$ ）について、まだ負けたことのない選手のうち、 $2_j-1$ 盤面番号の小さい選手と $2_j$ 番目に小さい選手が対戦する。

準優勝する、すなわち最後に行われる対戦において負ける選手の番号を求めてください。

制約

${1 \leqq N \leqq 16}$
${1 \leqq A_i \leqq 10^9}$
$A_i$ は相違なる
入力に含まれる値はすべて整数である。

考えたこと

制約より、トーナメントをシミュレートしても間に合うと考えました。番号とレートをペアにして、結果を前に詰めていくことで配列を1つですませました。

コード

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


int main(void) {
    ll N;
    cin >> N;

    ll num = 2 << (N-1);
    vector<pair<int, int>> A(num);
    rep(i, num) {
        A[i].first = i + 1;
        cin >> A[i].second;
    }

    num /= 2;
    for (int i = 0; i < N - 1; ++i) {
        for (int j = 0; j < num; ++j) {
            if (A[j * 2].second > A[j * 2 + 1].second) {
                A[j].first = A[j * 2].first;
                A[j].second = A[j * 2].second;
            } else {
                A[j].first = A[j * 2 + 1].first;
                A[j].second = A[j * 2 + 1].second;
            }
        }
    }

    if (A[0].second < A[1].second) {
        cout << A[0].first << endl;
    } else {
        cout << A[1].first << endl;
    }
    
    return 0;
}

解説を読んで

トーナメントの前半と後半でわける、キューを使う。自分には発想することはむずかしいかもしれません。経験値を増やして思い出す形にしたいです。