A – Maximize the Formula
A – Maximize the Formula (atcoder.jp)
Aにしては微妙にややこしい。
X+Yの形を作った際、2桁+1桁になります。
数式で言い換えると、(X*10+X)+(X)の形になるため、*10がかかっている所に最大値を置くことで最大化できそうです。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
int A,B,C;
cin>>A>>B>>C;
cout<<max(A,max(B,C))*10+A+B+C-max(A,max(B,C))<<endl;
}
B – 1 Dimensional World’s Tale
B – 1 Dimensional World’s Tale (atcoder.jp)
xi,yiのminmaxとX,Yの範囲が重なっているかどうかを判定すれば良さそうですが、私は範囲の重なりのコードを書くのが苦手です…。
制約が弱いためゴリゴリ書いても行けそうです。
Zを-100～100の全パターン試してみて、”No War”の条件に適しているかを確認しました。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
int N,M,X,Y;
cin>>N>>M>>X>>Y;
int x[N];
int y[M];
for(int i=0;i<N;i++){
cin>>x[i];
}
for(int i=0;i<M;i++){
cin>>y[i];
}
for(int Z=-101;Z<=101;Z++){
if(X>=Z||Z>Y) continue;
bool f=true;
for(int i=0;i<N;i++){
if(x[i]>=Z) f=false;
}
for(int i=0;i<M;i++){
if(y[i]<Z) f=false;
}
if(f){
cout<<"No War"<<endl;
return 0;
}
}
cout<<"War"<<endl;
}
C – String Transformation
C – String Transformation (atcoder.jp)
難問。分からなくて一回寝てました。(緑問ってマジですか？)
入力例2のようなパターンである場合NGです。具体的に
S="aa" T="ab" のようになっていると、aを変えようとすると両方変わるため、どっちかに合わせられなくてNG。
これだけだと不十分です。もう一つT側から見て以下のパターンもNGです。
S="ab" T="aa" のようになっていると、bをaに合わせに行こうとした時にSのaがbに代わってしまうため両方が合わなくなる。
上記2つであるよな場合はNG、そうでない場合はOKとすれば大丈夫です。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
string S,T;
cin>>S>>T;
set<char> c[300];
for(int i=0;i<(int)S.size();i++){
c[(int)S[i]].insert(T[i]);
if(c[(int)S[i]].size()>=2){
cout<<"No"<<endl;
return 0;
}
}
set<char> c2[300];
for(int i=0;i<(int)T.size();i++){
c2[(int)T[i]].insert(S[i]);
if(c2[(int)T[i]].size()>=2){
cout<<"No"<<endl;
return 0;
}
}
cout<<"Yes"<<endl;
}
これ、ダメなパターンを幾つか列挙しただけで、これ以外がOKという証明ができていません。(まだ、この考察だけでは未証明ACです。多分。)
ABCの場合、1WA5分なのでどこまで証明を詰めるかは難しい問題な気がします。(すぐさま証明できる知識が付ければ1番だとは思いますが…)
ちなみに、私は今回くらい詰めたら提出しちゃう派です。WAしたら更に詰め直します。
D – Factorization
D – Factorization (atcoder.jp)
a1～aNにMの約数が過不足なく入っていれば良さそうです。
入力例1：2 6 の場合 6の約数は2と3 (2,3)と() (2)と(3) (3)と(2) ()と(2,3) の4パターンと割り当てていく問題と言えます。 ※(2,3)なら2*3=6、()は何もないので1となっています。
こう考えると(約数の数)^Nっぽさそうですが、入力例2で破綻します。
入力例1：3 12 の場合 12の約数は2と2と3 2が二つあるので、これらは区別されないため、計算方法を考える必要がある。
ここまではすぐ分かったのですが、ここから数え上げの計算式に持っていくのに苦戦しました。
こういった場合は以下のように考えます。
約数ごとに考える(2が2個、3が1個) 2つを3つの箱に振り分けるパターン*1つを3つの箱に振り分けるパターン 区別のつかないものを区別のつく箱に入れる場合、区切り線で考える。 2||2 と、区別がつかないものと区切り線2つを並べる。 (2)|()|(2) 区切り線ごとにグループ化した場合、これが3つの箱に振り分けたことになる。 →求めたい通りは(区切り線の数+振り分けるものの数)C区切り線の数 区切り線の数は箱-1本
競プロでたまによく出てきますよね。
上記数え上げの式を実装します。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
long long mod=1000000007;
vector<long long> fac(300001); //n!(mod M)
vector<long long> ifac(300001); //k!^{M-2} (mod M)
//https://qiita.com/ofutonfuton/items/92b1a6f4a7775f00b6ae
long long comb(long long a, long long b){ //aCbをmod計算
if(a == 0 && b == 0)return 1;
if(a < b || a < 0)return 0;
long long tmp = ifac[a-b]* ifac[b] % mod;
return tmp * fac[a] % mod;
}
long long mpow(long long x, long long n){ //x^n(mod M) ←普通にpow(x,n)では溢れてしまうため，随時mod計算
long long ans = 1;
while(n != 0){
if(n&1) ans = ans*x % mod;
x = x*x % mod;
n = n >> 1;
}
return ans;
}
void combini(){
fac[0] = 1;
ifac[0] = 1;
for(long long i = 0; i<300000; i++){
fac[i+1] = fac[i]*(i+1) % mod; // n!(mod M)
ifac[i+1] = ifac[i]*mpow(i+1, mod-2) % mod; // k!^{M-2} (mod M) ←累乗にmpowを採用
}
}
int main(){
int N,M;
cin>>N>>M;
map<int,int> s;
for(int i=2;i<sqrt(M)+2;i++){
while(M%i==0){
s[i]++;
M/=i;
}
}
if(M!=1) s[M]++;
modint1000000007 ans=1;
combini();
auto it=s.begin();
while(it!=s.end()){
ans*=comb(N-1+it->second,it->second);
it++;
}
cout<<ans.val()<<endl;
}
コンビネーションの計算に以下のqiitaのものを使いました。
というのも、modの計算は割り算が入っているときにおかしくなるため、フェルマーの小定理を使った変換を行う必要があります。(上記のコードはコンビネーションの計算の高速化も入っている？)
雑談
ライブラリ整備があんまりできていない…と最近思っています。(コンビネーションでさえ他人のパクッて使ってますね)
落ち着いたころに一度ライブラリ整備をしたいですね。(前々から言っているマクロ整備も)
コメント