※今までnoteでメモしていた参加記を個人ブログで書くことにしました。(ブログネタがないため)
001～019はnoteに書いていますので、そちらも是非見てください。
↓019のnote記事
2020/11/01 1:39 D問題を解説ACしたため追記しました。
2020/11/01 2:35 E問題を解説ACしたため追記しました。
はじめに
このブログを触っていたり、JavaScriptで遊んでいたりして参加がなかなかできていませんでしたが、久々に参加しました。
A,B,Cの3完でした。500点問題解けたので及第点といった感じです。
A – Simple Math
3つのシグマからなるabcを求める問題。
単純にやればO(N^3)なのでしんどいです。
2つのシグマで考える
問題を簡略化して2つのシグマで考えます。
#include<bits/stdc++.h>
using namespace std;
long long mod=998244353;
int main(){
long long a,b;
cin>>a>>b;
long long ans=0;
for(int i=1;i<=a;i++){
for(int j=1;j<=b;j++){
cout<<i<<"*"<<j<<"="<<i*j<<endl;
ans+=i*j;
}
}
cout<<ans<<endl;
}O(N^2)のコードですが、これにa=2,b=3を入れて出力を観察します。
2 3 1*1=1 1*2=2 1*3=3 2*1=2 2*2=4 2*3=6 18
1+2+3+2+4+6=18ですが、これを1～b(今回の入力の場合1,2,3)の和でくくると、
(1+2+3)(1)+(1+2+3)(2)=18となります。
ここから、2つのシグマの場合は、1～bの和と1～aの和を掛け合わせたものが答えになりそうだなと予想できます。
3つのシグマに拡張
2つのシグマの答えをabとした場合、問題文の式は
ab*c1+ab*c2+ab*c3+…ab*cmax
となります。なので、3つのシグマには先ほどの2つのシグマの答えに1～cの和を掛け合わせれば良さそうです。
最終的な解法
上記の考えを纏めると、
1～aの和*1～bの和*1～cの和
をすれば求まりそうです。
和の計算には除算が入るためmodがややこしそうですが、除算前でオーバーフローはしない制約になっているため、modの場所にさえ気をつければ問題ありません。
#include<bits/stdc++.h>
using namespace std;
long long mod=998244353;
int main(){
long long a,b,c;
cin>>a>>b>>c;
long long bb=b*(b+1)/2%mod;
long long aa=a*(a+1)/2%mod;
long long cc=c*(c+1)/2%mod;
cout<<(aa*bb)%mod*cc%mod<<endl;
}
B – Quadruple
条件を満たす、a,b,c,dの組み合わせを考える問題。
a+b-c-d=Kを式変形し、
a+b-(c+d)=Kと考えた場合、2値の和-2値の和=Kと考えられます。
2値の和-2値の和=Kを考える
a+b=ab
c+d=cd
とすると、条件の式は
ab-cd=K
となります。これを満たす、ab,cdの組み合わせを考えます。
2<=ab,cd<=2*Nであるため、単純な全探索はO(N^2)です。
ただ、ab=K-cdと考えた場合、abが決まればcdは一意に決まることが分かります。
そのため、ab,cdの組み合わせはabを2～2*Nの間で回して、K-cdが範囲内である場合を考えればいいことが分かります。
ab,cdの組み合わせを考える
ab=pとなるような、a+bの組み合わせの個数を考えていきます。
単純にa+bの全パターンを列挙しようとすると、O(N^2)かかります。
あるaに対してb=1～Nの全パターンを考えた場合、a+1～a+Nの範囲のパターンが1個ずつ増えるはずです。
そのため、範囲に対するアルゴリズムを何か適用して高速に計算することができます。
今回、私はimos法を使って求めました。
最終的な解法
ab,cd=p(2<=p<=2*N)となるようなab,cdの組み合わせの個数を事前計算し、それを使ってab-cd=Kの組み合わせ数を求めました。
#include<bits/stdc++.h>
using namespace std;
long long mod=998244353;
int main(){
long long N,K;
cin>>N>>K;
long long cnt[200010]={0};
for(int i=1;i<=N;i++){
cnt[i+1]++;
cnt[i+N+1]--;
}
for(int i=2;i<=2*N;i++){
cnt[i]+=cnt[i-1];
}
long long ans=0;
for(long long i=2*N;i>=2;i--){
long long ab=i;
long long cd=ab-K;
if(ab<0||ab>2*N||cd<0||cd>2*N) continue;
ans+=cnt[ab]*cnt[cd];
}
cout<<ans<<endl;
}C – Shuffle Permutation
この手の問題の行列の性質として、
- 操作の順番は関係ない
(1,3)列の交換→(1,3)行の交換 = (1,3)行の交換→(1,3)列の交換 - 2回操作すればなかったことになる
(1,3)列の交換→(1,3)行の交換→(1,3)列の交換 = (1,3)列の交換
みたいな事があります。
また、
(1,3)行が交換できる、(2,3)行が交換できる
が満たせる場合、1,2,3の行にある数字たちは1,2,3行のそれぞれの好きな位置に配置できます。つまり、3!(3*2*1=6)パターンどの並びも操作によって並べられるということです。
上記の行列の性質から、この問題は並び替えられるグループごとに分け、それぞれのグループの個数の階乗をかけ合わせればいいことになります。(考えが飛んだ気がしますが、書くのに疲れました＞ ＜)
グループごとに分ける実装法は何個かあると思います。
今回はそれぞれの行と列を頂点、並び替え可能を辺に持つ無向グラフを作成し、そこからBFSでグループの個数を求めました。
#include<bits/stdc++.h>
using namespace std;
long long mod=998244353;
int main(){
int N,K;
cin>>N>>K;
int a[N][N];
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
cin>>a[i][j];
}
}
vector<int> vt[N],vy[K];
for(int x=0;x<N;x++){
for(int y=0;y<N;y++){
if(x==y) continue;
bool f1=true,f2=true;;
for(int k=0;k<N;k++){
if(a[x][k]+a[y][k]>K) f1=false;
if(a[k][x]+a[k][y]>K) f2=false;
}
if(f1) {
vt[x].push_back(y);
vt[y].push_back(x);
}if(f2){
vy[x].push_back(y);
vy[y].push_back(x);
}
}
}
long long ans=1;
long long ok[50]={0};
long long mod=998244353;
for(int i=0;i<N;i++){
if(ok[i]==0){
queue<int> q;
q.push(i);
long long c=0;
while(!q.empty()){
int ni=q.front();
q.pop();
if(ok[ni]==1) continue;
//cout<<ni<<endl;
ok[ni]=1;
c++;
for(int j=0;j<vt[ni].size();j++){
if(ok[vt[ni][j]]==0){
q.push(vt[ni][j]);
}
}
}
//cout<<i<<","<<c<<endl;
for(int j=1;j<=c;j++){
ans*=j;
ans%=mod;
}
}
}
//cout<<"--------------"<<endl;
long long ok2[50]={0};
for(int i=0;i<N;i++){
if(ok2[i]==0){
queue<int> q;
q.push(i);
long long c=0;
while(!q.empty()){
int ni=q.front();
q.pop();
if(ok2[ni]==1) continue;
//cout<<ni<<endl;
ok2[ni]=1;
c++;
for(int j=0;j<vy[ni].size();j++){
if(ok2[vy[ni][j]]==0){
q.push(vy[ni][j]);
}
}
}
//cout<<i<<","<<c<<endl;
for(int j=1;j<=c;j++){
ans*=j;
ans%=mod;
}
}
}
cout<<ans<<endl;
}
今回は時間がなくてゴリゴリ書きましたが、UnionFindなんかを使うとスッキリすると思います。
D – Number of Multisets
1,1/2,1/4,1/8…をN個使って総和をKにする問題。
解説を見て通しました。
1を1個以上使う場合、使わない場合を考えるとスッキリします。
1を1個以上使う場合
1を1つ取り除くことにより、
1,1/2,1/4,1/8…をN-1個使って総和をK-1にする問題。
と同値になることが分かります。
1を1個以上使わない場合
1を使わないため、
1/2,1/4,1/8,1/16…をN個使って総和をKにする問題。
と言い換えることができます。この時、総和と要素を2倍にすることで
1,1/2,1/4,1/8…をN個使って総和を2Kにする問題。
と言い換えることができ、要素が元の問題となるため同値になると言えることができます。
最終的な解法
dp[N][K]とdpテーブルを持ち、これを更新することを考えます。
上で考えた2パターンを足し合わせ、
dp[N][K]=dp[N-1][K-1]+dp[N][2*N] (dp[0][0]=1)
と更新していきます。(※0個使って0にするは、あらかじめ1通りを初期値としておく)
#include<bits/stdc++.h>
using namespace std;
int main(){
//1を使わない N個の1/2,1/4...を使ってKにする
// ->*2する N個の1,1/2...を使って2Kにする
//1を使う N-1個の1,1/2,1/4を使ってK-1にする
//1を使うかに関係なく、 N個の1,1/2...を使って2K + N-1個の1,1/2,1/4を使ってK-1 が答え
//dp[N][K]=dp[N][2K]+dp[N-1][K-1]といえる。
long long mod=998244353;
long long N,K;
cin>>N>>K;
long long dp[N+10][2*N+10];
for(int i=0;i<N+10;i++){
for(int j=0;j<2*N+10;j++){
dp[i][j]=0;
}
}
dp[0][0]=1;
for(int i=1;i<=N;i++){
for(int j=2*i;j>=0;j--){
long long a=0;
if(i>=0&&i<=N&&2*j>=0&&2*j<=2*N) a=dp[i][2*j];
long long b=0;
if(i-1>=0&&i-1<=N&&j-1>=0&&j-1<=2*N) b=dp[i-1][j-1];
dp[i][j]=a+b;
dp[i][j]%=mod;
//cout<<dp[i][j]<<",";
}
//cout<<endl;
}
cout<<dp[N][K]<<endl;
}
E – Mex Mat
a11～a1Nとa21～aN1が与えられので、mexで表を埋めた際に0,1,2が幾つになるか求める問題。
解説ACしました。
実験してみる
愚直解で、解がどうなるか観察してみます。
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
cin>>N;
int a1[N],a2[N];
for(int i=0;i<N;i++){
cin>>a1[i];
}
a2[0]=a1[0];
for(int i=1;i<N;i++){
cin>>a2[i];
}
for(int i=0;i<N;i++){
cout<<a1[i];
}
cout<<endl;
for(int i=1;i<N;i++){
cout<<a2[i];
for(int j=1;j<N;j++){
int mex=0;
if(a2[i]==0&&a1[j]==0) mex=1;
if(a2[i]==0&&a1[j]==1) mex=2;
if(a2[i]==0&&a1[j]==2) mex=1;
if(a2[i]==1&&a1[j]==0) mex=2;
if(a2[i]==1&&a1[j]==1) mex=0;
if(a2[i]==1&&a1[j]==2) mex=0;
if(a2[i]==2&&a1[j]==0) mex=1;
if(a2[i]==2&&a1[j]==1) mex=0;
if(a2[i]==2&&a1[j]==2) mex=0;
cout<<mex;
a2[i]=mex;
a1[j]=mex;
}
cout<<endl;
}
}15 0 1 2 0 1 2 1 1 1 2 2 2 0 0 0 1 2 0 0 0 2 1 0 1 1 1 2 0 1 012012111222000 101201020101212 210120101010101 021012010101010 010101201010101 021010120101010 202101012010101 120210101201010 012021010120101 101202101012010 120120210101201 101012021010120 210101202101012 021010120210101 102101012021010
i,jが大きいときの数字を見てみると、同じ数字が右下に伸びていることが分かります。
この実験結果を元にコーディングしていきます。
コーディング
今回、x=10までy=10までは愚直に求め、x=11,y=11からは右下に伸びる法則を使って計算で求めるようにしました。
注意点として、答えの数字がintではオーバーフローする可能性があります。long longで答えを持つようにしましょう。
#include<bits/stdc++.h>
using namespace std;
int mex(int x,int y){
int mexi=0;
if(x==0&&y==0) mexi=1;
if(x==0&&y==1) mexi=2;
if(x==0&&y==2) mexi=1;
if(x==1&&y==0) mexi=2;
if(x==1&&y==1) mexi=0;
if(x==1&&y==2) mexi=0;
if(x==2&&y==0) mexi=1;
if(x==2&&y==1) mexi=0;
if(x==2&&y==2) mexi=0;
return mexi;
}
int main(){
int N;
cin>>N;
int a1[N],a2[N];
long long c[3]={0};
for(int i=0;i<N;i++){
cin>>a1[i];
c[a1[i]]++;
}
a2[0]=a1[0];
for(int i=1;i<N;i++){
cin>>a2[i];
c[a2[i]]++;
}
for(int i=1;i<min(N,10);i++){
for(int j=1;j<N;j++){
int m=mex(a2[i],a1[j]);
c[m]++;
a2[i]=m;
a1[j]=m;
}
}
if(N>=10){
for(int j=1;j<10;j++){
for(int i=10;i<N;i++){
int m=mex(a2[i],a1[j]);
c[m]++;
a2[i]=m;
a1[j]=m;
}
}
for(int i=10;i<N;i++){
int m=mex(a2[i],a1[10]);
c[m]+=(N-i);
a2[i]=m;
a1[10]=m;
}
for(int j=11;j<N;j++){
int m=mex(a2[10],a1[j]);
c[m]+=(N-j);
a1[j]=m;
a2[10]=m;
}
}
cout<<c[0]<<" "<<c[1]<<" "<<c[2]<<endl;
}
数学問が続いた後の実験問題は中々厳しいですね…。
おわりに
書いている途中にレートが更新されましたが、パフォーマンス1325でレートは1334(-1)になりました。
一先ず、ほぼ実力通りの力を出せたということで安心しました。
明日のABCも出る予定のため、この調子で頑張りたいです。
今回の問題は数学的要素が多く、受験問題を解いているような感じでした…。
個人的にはこういう問題の方が好きですが、対策はしにくいですね…。
コメント