気ままに実装する機械学習

機械学習に興味のある大学院生によるブログです. 機械学習以外のトピック多めです.

MENU

AtCoder Beginner Contest 110に参加しました

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

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

A. Maximize the Formula

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

3つの整数で2つの整数XYを作ることを考える. 例えば1, 4, 6と与えられたら、X = 64Y = 1としたとき65となり最大値をとる. またX = 61Y = 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があり、それぞれ座標XYに位置している.
  • 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とし、このZmin(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_1c_2に、c_2c1に置き換える.
  • 0回以上の操作で、SをTに一致させられるか?
解法

入力例にもある通り、'azzel' は、 c_1 = ec_2 = lとすると'azzle'になり、c_1 = zc_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で等しいとき(順不同)一致させることができ、それ以外は一致させることができないということになります.

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

#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);
    string S, T;
    cin >> S >> T;
    map<char, int> m1, m2;
    rep(i, 0, S.size()) {
        m1[S[i]]++;
    }

    rep(i, 0, T.size()) {
        m2[T[i]]++;
    }

    vector<int> v1, v2;
    for(map<char, int>::iterator itr = m1.begin(); itr != m1.end(); itr++) {
        v1.push_back(itr->second);
    }
    for(map<char, int>::iterator itr = m2.begin(); itr != m2.end(); itr++) {
        v2.push_back(itr->second);
    }

    vsort(v1);
    vsort(v2);

    rep(i, 0, v1.size()) {
        if(v1[i] != v2[i]) {
            cout << "No" << endl;
            return 0;
        }
    }

    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問題の出力する文字列を確認せずに提出してしまうというケアレスミスがあったのが非常に悔しいです...)

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

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