ABC #042,ARC #058
ARC#058に参加しました.
ABC#042はA問題からD問題,ARC#058はC問題からF問題です.
- AtCoder Beginner Contest 042 - AtCoder Beginner Contest 042 | AtCoder
- AtCoder Regular Contest 058 - AtCoder Regular Contest 058 | AtCoder
- 公式解説:http://arc058.contest.atcoder.jp/data/arc/058/editorial.pdf
[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円から始めて各桁にを含まなくなるまで1円づつ増やし確認する.Kは9以下かつなのでこの手続きはいつか停止する.また,支払う金額は高々100Nである(各桁に使える数がD'とするとNより1桁大きくて各桁がD'の数は条件を満たす).したがって,計算時間は.
ソースコード
#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'マスの場合はとなる.後は,同様に赤色の枠の部分の各々に対して経路数を計算した総和が答えになる.
ただし,H-A通りに対して組合せ数を計算するとTLEになるので前もって計算する.したがって,計算時間は である.
ソースコード
#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; }
まとめ
EとFは後でまとめる.
問題は面白かった.