プログラミング初心者の勉強日記

情報科学専攻です. 機械学習と競技プログラミングについて日々勉強しています.

MENU

AtCoder Beginner Contest 110に参加しました

競技プログラミング

AtCoder Beginner Contest 110に参加したので記録を残しておきたいと思います.

問題のタイトルは以下のようになっています.

A. Maximize the Formula

問題の概要
  • 1以上9以下の整数1つが書かれた整数パネル3枚と'+'が書かれた演算子パネル1枚がある
  • これら4枚を横一列に並べてX + Yの形を作る.
  • 作れる数式から得られる値のうち最大となるものを出力
解法

3つの整数で2つの整数XとYを作ることを考える. 例えば1, 4, 6と与えられたら、X = 64、Y = 1としたとき65となり最大値をとる. またX = 61、Y = 4としてもよい.

要は2桁の数字の10の位に与えられた3つの整数の最大値を割り当ててあげればよい.

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

#define MAX_V 1000000

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    vector<int> a;
    int A, B, C;
    cin >> A >> B >> C;
    a.push_back(A);
    a.push_back(B);
    a.push_back(C);
    vsort(a);
    int tmp = a[2] * 10 + a[1];
    int rsl = tmp + a[0];
    cout << rsl << endl;
}

B. 1 Dimensional World's Tale

問題の概要

(テストケースに不具合があった問題です.)

  • 一次元世界の中に帝国Aと帝国Bがあり、それぞれ座標X、Yに位置している.
  • A帝国は座標x_1, x_2, \cdots, x_N、B帝国は座標y_1, y_2, \cdots y_Mに支配下を置きたい.
  • 以下の3つの条件をすべて満たすZが存在すれば、合意が成立して戦争は起きないが、存在しない場合には戦争が起こる.
    • X < Z \leq Y
    • x_1, x_2, \cdots x_N < Z
    • y_1, y_2, \cdots y_M \geq Z
解法

2つ目の制約と3つ目の制約からmax(x_1, x_2, \cdots, c_N)はZ未満、min(y_1, y_2, \cdots y_M)はZ以上であるという制約を満たせばよい.

したがって、もし3つの制約を満たすZが存在するならば、Z=max(x_1, x_2, \cdots, x_N) + 1とし、このZがmin(y_1, y_2, \cdots y_M)より小さいことが必要である.

最後に、この選んだZが1つ目の制約を満たしているかを確認し、満たしていれば戦争が起きず、満たさないとき戦争が起きてしまう.

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

#define MAX_V 1000000

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M, X, Y;
    cin >> N >> M >> X >> Y;
    vector<int> x, y;
    rep(i, 0, N) {
        int tmp;
        cin >> tmp;
        x.push_back(tmp);
    }
    rep(i, 0, M) {
        int tmp;
        cin >> tmp;
        y.push_back(tmp);
    }

    vsort(x);
    vsort(y);
    int rsl = x[N - 1] + 1;
    if(X < rsl and rsl <= Y) {

        if(y[0] < rsl) {
            cout << "War" << endl;
            return 0;
        }

        cout << "No War" << endl;
        return 0;
    }

    cout << "War" << endl;
}

余談ではありますが、'No War'と出力しなければいけないところ'Not War'として提出してしまい一度WAになってしまいました...

C. String Transformation

問題の概要
  • 英小文字のみからなる文字列S, Tが与えられる.
  • Sに対して次の操作を何度でも行うことができる.
    • 操作：2つの異なるc_1, c_2を選び、Sに含まれるすべてのc_1をc_2に、c_2をc1に置き換える.
  • 0回以上の操作で、SをTに一致させられるか？
解法

入力例にもある通り、'azzel' は、 c_1 = e、c_2 = lとすると'azzle'になり、c_1 = z、c_2 = pとすると、'apple'になるので、'apple'と一致させることができるということになります.

ここで、各文字列に含まれる英小文字の出現回数に着目してみます.

上の例でいうと、Sは「a =1回、z = 2回、e = 1回、l = 1回」であり、Tは「a = 1回、p = 2 回、l = 1回、e = 1回」です.

このときSの'z'をpに、'e'を'l'に、'l'を'e'に対応付けしてあげれば一致させることができます.

このように各英小文字の出現回数を数え、その出現回数がSとTで等しいとき（順不同）一致させることができ、それ以外は一致させることができないということになります.

実装では、出現回数を連想配列で求め、それをソートしたあとに等しいかどうか調べています.

すみません、嘘解法です.

例えば、S=aab、T=bccのときにYesと出力してしまいますが、SをTにすることは無理です.

実は、S中の同じ文字が違う文字に変換されることはありません. またT中の同じ文字に対しても同じことが言えます.

したがって、SやTの文字を先頭から見ていき、対応関係を確認していきます.

一致していればそのまま次の文字を確認し、異なる文字に変換されていることが確認できた時点でNoを出力するようにします.

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

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

    string S, T;
    cin >> S >> T;

    int used1[26], used2[26];
    rep(i, 0, 26) {
        used1[i] = -1;
        used2[i] = -1;
    }

    rep(i, 0, S.size()) {
        int tmp1 = int(S[i]) - 'a';
        int tmp2 = int(T[i]) - 'a';

        if(used1[tmp1] >= 0) {
            if(used1[tmp1] != tmp2) {
                cout << "No" << endl;
                return 0;
            }
        } else used1[tmp1] = tmp2;
        if(used2[tmp2] >= 0) {
            if(used2[tmp2] != tmp1) {
                cout << "No" << endl;
                return 0;
            }
        } else used2[tmp2] = tmp1;
    }

    cout << "Yes" << endl;
}

D. Factorization

問題の概要

a_1 \times a_2 \times \cdots a_N = Mとなる長さNの数列aあ何通りあるか、10^{9} + 7で割った余りを求める.

解法

Mを素因数分解するところで思考停止してしまい、時間内に解くことができませんでした...

それはさておき、やはりまずは、Mを素因数分解します.

そうすると、 $$ p_1^{b_i} \times p_2^{b_2} \times \cdots \times p_m^{b_m} = M $$

となります. ただし、ここでp_i (i = 1, 2, \cdots m)は素数です.

さらに、問題で与えられている数列aの各項に対しても素因数分解します.

そうすると、 $$ p_{i, 1}^{c_{i, 1}} \times p_{i, 2}^{c_{i, 2}} \cdots \times p_{i, m}^{c_{i, m}} = a_{i} $$

と表すことができます.

したがって、 $$ b_i = \sum_{k = 1}^{N} c_{k, i} $$ を満たすような選び方の場合の数を考える問題に帰着できます.

各iに関しては重複組み合わせの公式を用いて、{}_{N} H_{b_{i}} = {}_{N + b_i - 1} C_{b_{i}}で計算することができます.

これらの場合の数を、すべてのiについてかけ合わせてあげれば答えが求まります.

この組み合わせを求める方法については以下の記事がものすごく参考になりますのでリンクを貼っておきます. qiita.com

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

const ll mod = 1e9 + 7;

#define MAX_V 1000000
const int MAX = 510000;

ll fac[MAX], finv[MAX], inv[MAX];

void comInit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    rep(i, 2, MAX) {
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}

ll comb(ll n, ll k) {
    if(n < k) return 0;
    if(n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}


map<ll, ll> prime_factor(ll n) {
    map<ll, ll> res;
    for(ll i = 2; i * i <= n; i++) {
        while(n % i == 0) {
            ++res[i];
            n /= i;
        }
    }
    if(n != 1) res[n] = 1;
    return res;
}

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

    comInit();
    ll N, M;
    cin >> N >> M;
    map<ll, ll> m = prime_factor(M);
    ll rsl = 1;
    for(map<ll, ll>::iterator itr = m.begin(); itr != m.end(); itr++) {
        rsl *= (comb(itr->second + N - 1, N - 1) % mod);
        rsl %= mod;
    }

    cout << rsl << endl;
}

感想

今回C問題までを17分で解くことができました (ペナルティ抜きで). (B問題の出力する文字列を確認せずに提出してしまうというケアレスミスがあったのが非常に悔しいです...)

たまたま相性の良かった問題だったのかもしれませんが、少しばかり成長を確認することができたコンテストだったと思います.

C問題は嘘解法でのACだったので実質2完ですね... 精進します.

D問題は今回も時間内に解くことができませんでしたので、とりあえずD問題埋めを頑張ろうと思います. それに加えて、整数論をからめた問題をいつも落としているイメージなので、整数論についても学習しなおそうと思います.