ABC #042,ARC #058

ARC#058に参加しました.
ABC#042はA問題からD問題,ARC#058はC問題からF問題です.

[Problem A. 和風いろはちゃんイージー]

方針

昇順にソートして小さい方から5,5,7と等しいかを調べる.

ソースコード
#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;

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

    vector<int> abc(3);
    for (int i = 0; i < 3; ++i)
        cin >> abc[i];
    sort(abc.begin(), abc.end());

    if (abc[0] == 5 && abc[1] == 5 && abc[2] == 7)
        cout << "YES\n";
    else
        cout << "NO\n";

    return 0;
}

[Problem B. 文字列大好きいろはちゃんイージー]

方針

N個の文字列を昇順にソートして小さい文字列から連結していく.

ソースコード
#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;

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

    int n, l;

    cin >> n >> l;
    vector<string> s(n);
    for (int i = 0; i < n; ++i)
        cin >> s[i];

    sort(s.begin(), s.end());

    for (auto x : s)
        cout << x;
    cout << endl;

    return 0;
}

[Problem C. こだわり者いろはちゃん]

方針

支払う金額をN円から始めて各桁に D_1, \ldots, D_kを含まなくなるまで1円づつ増やし確認する.Kは9以下かつ \{D_1, \ldots, D_k\} \neq \{1, 2, 3, 4, 5, 6, 7, 8, 9\}なのでこの手続きはいつか停止する.また,支払う金額は高々100Nである(各桁に使える数がD'とするとNより1桁大きくて各桁がD'の数は条件を満たす).したがって,計算時間は O(N \log N)

ソースコード
#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;

bool Check(int ans, const vector<int> &d) {
    while (ans) {
        int n = ans % 10;
        for (auto dd : d)
            if (dd == n)
                return true;
        ans /= 10;
    }

    return false;
}

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

    int n, k;

    cin >> n >> k;
    vector<int> d(k);
    for (int i = 0; i < k; ++i)
        cin >> d[i];

    int ans = n;
    while (Check(ans, d))
        ++ans;

    cout << ans << endl;

    return 0;
}

[Problem D. いろはちゃんとマス目]

方針

SからGへの単調な経路数で灰色の部分を通らない経路数はいくつかを考える.
SからGへの経路は赤枠のいづれかのマスを必ず通る.3行4列のマスから右に移動して3行5列のマスからGまで移動する経路数は,
 (Sから(3,4)までの経路数)×((3,5)からGまでの経路数)
となる.
障害物が無い場合の経路数は組合せ数を用いて計算することができる.横W'マス,縦H'マスの場合は {W'+H'-2 \choose W'-1}となる.後は,同様に赤色の枠の部分の各々に対して経路数を計算した総和が答えになる.
ただし,H-A通りに対して組合せ数を計算するとTLEになるので前もって計算する.したがって,計算時間は  O( (H + W) \log(H + W)) である.

f:id:tatanaideyo:20160724025429p:plain

ソースコード
#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;
const ll MOD = 1000000007;

// a, bの最大公約数と, ax+by=gcd(a, b)となるx,yを求める
ll Extgcd(ll a, ll b, ll &x, ll &y) {
    ll g = a;
    if(b != 0) {
        g = Extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    }
    else {
        x = 1;
        y = 0;
    }

    return g;
}

// ax = gcd(a, m) (mod m) となるxを求める
// a, m が互いに素ならば関数値はmod m でのaの逆数となる
ll ModInverse(ll a, ll m)
{
    ll x, y;
    Extgcd(a, m, x, y);
    return (x % m + m) % m;
}

const int MAX_N = 2 * 100010;
vector<ll> fact(MAX_N), rfact(MAX_N);
void Init() {
    fact[0] = rfact[0] = 1;
    for (int i = 1; i < MAX_N; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
        rfact[i] = (rfact[i - 1] * ModInverse(i, MOD)) % MOD;
    }
}

inline ll Combination(ll n, ll k) {
    return ((fact[n] * rfact[n - k]) % MOD) * rfact[k] % MOD;
}

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

    Init();

    ll h, w, a, b;

    cin >> h >> w >> a >> b;
    ll ans = 0;
    for (int i = 1; i <= h - a; ++i) {
        ll l1 = Combination(i + b - 2, min((ll)i - 1, b - 1));
        ll l2 = Combination(h - i + w - b - 1, min(w - b - 1, h - i));
        ans = (ans + (l1 * l2) % MOD) % MOD;
    }

    cout << ans << endl;

    return 0;
}

[Problem E. ]

方針

[Problem F. ]

方針

まとめ

EとFは後でまとめる.
問題は面白かった.