AtCoder Beginner Contest 110
AtCoder Beginner Contest 110 - AtCoder
A - Maximize the Formula
考察
与えられた3つの1桁の数字を順不同にとするとき、
の最大値を求める。結局
に何が入るかを場合分けすれば、取りうる値はたかだか3通りなのですべて調べればよい。
コード
int main(){ int a,b,c; cin >> a >> b >> c; int ans = max(max(a*10+b+c,a+b*10+c),a+b+c*10); cout << ans << endl; return 0; }
B - 1 Dimensional World's Tale
考察
A帝国の首都とその支配に置きたい都市、およびB帝国の首都とその支配に置きたい都市が数直線上でオーバーラップしていないかどうかを判定すればよい。前者の座標の最大値と後者の座標の最小値を比較することで判定ができる。
コード
int main(){ int n,m,x,y; cin >> n >> m >> x >> y; int x_max = x; REP(i,n){ int xi; cin >> xi; x_max = max(x_max,xi); } int y_min = y; REP(i,m){ int yi; cin >> yi; y_min = min(y_min,yi); } if(x_max<y_min){ cout << "No War" << endl; }else{ cout << "War" << endl; } return 0; }
C - String Transformation
考察
長さが等しい2つの文字列と
が、文字の入れ替え（「いっぱい」を「おっぱお」にするような入れ替え）によって変換できるかどうかを答える。これは、
の中で同じ文字は
で同じ文字に対応し、
の中で違う文字は
で違う文字になっているかどうかと同値である。よって、2つの文字列の各文字について「その文字が最初に出てくるその文字列内の場所」を計算しておき、比較すれば、判定ができる。
コード
int main(){ str s,t; cin >> s >> t; int n = s.length(); map<char,int> mp_s; int group_s[n]; REP(i,n){ if(mp_s[s[i]]==0){ mp_s[s[i]]=i+1; } group_s[i]=mp_s[s[i]]; } map<char,int> mp_t; int group_t[n]; REP(i,n){ if(mp_t[t[i]]==0){ mp_t[t[i]]=i+1; } group_t[i] = mp_t[t[i]]; } REP(i,n){ if(group_s[i]!=group_t[i]){ cout << "No" << endl; return 0; } } cout << "Yes" << endl; return 0; }
D - Factorization
考察
かけてになるような
個の数のパターンの数を求める（ただし
で割った余り）。とりあえず
を素因数分解し、ある素数
について
乗となっているとき、この
個の
を
個のグループに分割する方法は
通りある。これをすべての素数に関して計算して積を取ればよい。
ただし、組み合わせを計算するときはオーバーフローに注意する必要がある。より、
はlong long型でも容易にオーバーフローすることがわかるので、組み合わせを
で割ったあまりを工夫して求める必要がある。まず、
と変形し、分子と分母をで割った余りを計算しておく。そして、「分母で割る」ことと「ある整数をかける」ことが等価となる整数（
における逆元）を求め、分子にその整数をかけることによって組み合わせを
で割った余りを求める。
逆元の求め方は蟻本の4-1章に記載があるほか、Web上にも資料がある。
http://hos.ac/slides/20130319_enumeration.pdf
コード
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;
}
const ll p = 1000000007;
ll extgcd(ll a, ll b, ll& x, ll& y){
int d = a;
if(b!=0){
d = extgcd(b,a%b, y, x);
y -= (a/b)*x;
}else{
x = 1; y = 0;
}
return d;
}
ll mod_inv(ll n){
ll x,y;
extgcd(n,p,x,y);
return (p+x%p)%p;
}
int main(){
ll n,m;
cin >> n >> m;
map<ll,ll> factor = prime_factor(m);
ll ans = 1;
for(auto b : factor){
int x = b.second;
ll num = 1, den = 1;
REP(i,x){
num = num * (x+n-1-i) % p;
den = den * (x-i) % p;
}
ans *= num*mod_inv(den)%p;
ans = ans % p;
}
cout << ans << endl;
return 0;
}
雑感
今週も用事で参加できず。休日の夜は参加しづらいです。
Dは逆元やらなにやら調べていたらかなり時間がかかりました。
