2021/1/24 1:35 C問題の記載を若干修正
はじめに
キーエンス プログラミング コンテスト 2021 – AtCoder
A,B,Cの3完で663位でした。
レートは+26で1483になりました。調子がいいですね！
A – Two Sequences 2
A – Two Sequences 2 (atcoder.jp)
cnの値は、1<=i<=j<=nとなるような組み合わせのai*bjの最大値となります。
ここで、cn-1の値が何らか決まったとしてcnを求めることを考えます。
b1～bn-1はanとの組み合わせができないため、ここは考えなくて良さそうです。
a1～anはbnと組み合わせられるため、この組み合わせの最大値が答えの候補になりそうです。単純に積を行うため、a1～anの中で一番大きい値を選択する方がお得です。そのため、答えの候補としてa1～anの最大値*bnがあり得ます。
あとは、a1～an-1とb1～bn-1の中での組み合わせですが、この範囲での最大値はcn-1となっているはずです。
上記より、答えはmax(a1～anの最大値*bn,cn-1)となります。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
long long N;
cin>>N;
long long a[N],b[N];
for(int i=0;i<N;i++){
cin>>a[i];
}
for(int i=0;i<N;i++){
cin>>b[i];
}
long long amax=0;
long long ans=0;
for(int i=0;i<N;i++){
amax=max(amax,a[i]);
ans=max(ans,amax*b[i]);
cout<<ans<<endl;
}
}
B – Mex Boxes
最小の非負数が箱に書かれるため、なるだけ0,1,2,3…と連番となる様にボールを入れていきたいです。この考えがそのまま解法になります。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
long long N,K;
cin>>N>>K;
long long ans=0;
map<long long,long long> m;
for(int i=0;i<N;i++){
long long a;
cin>>a;
m[a]++;
}
long long c1=0,c2=0;
if(m.find(0)==m.end()) cout<<"0"<<endl;
else{
c2=min(K,m[0]);
c1++;
while(1){
if(m.find(c1)==m.end()){
ans+=c1*c2;
break;
}
long long c3=m[c1];
if(c3<c2){
ans+=(c2-c3)*c1;
c2=c3;
}
c1++;
}
cout<<ans<<endl;
}
}
注意点は箱がK個しかないので、0,1,2の連番が10個作れたとして、K=5の場合、0,1,2の連番は実質5個しか作れない(箱がないため)ことです。
私は、各数の個数をカウントしてそこから0～Nまでの連番が幾つ作れるかを計算しました。
C – Robot on Grid
C – Robot on Grid (atcoder.jp)
簡単なDPで解きたいですが、空白マスが厄介です。
空白マスにはR,D,Xと3つ書き込めるのですが、それぞれで移動経路のカウントをしなければならず、その分経路数が爆発します。
どうにかして空白をdpの遷移に組み込みたいところです。
遷移の整理
空白マスの影響を考えない、遷移の仕方を整理していきます。
文字ありマスのDPの遷移は
Rなら、dp[i][j+1]+=dp[i][j]
Dなら、dp[i+1][j]+=dp[i][j]
Xは上の二つを同時に行う、となります。
空白マスの遷移は、
dp[i][j+1]にはR,Xのどっちか書くと行けるのでdp[i][j+1]+=dp[i][j]*2です。
dp[i+1][j]も同様に+=dp[i][j]*2となります。
ただ、始めに述べたようにこれだけでは不完全です。
入力例 1のように、下右のルートが空白マスの影響を受けて経路数が3倍されています。これをどうにかして考えたいです。
空白を通った時をカウント
入力例 1のように、空白を通っていないときに経路数が増えてしまします。
そのため、dp[H][W]を、dp[空白を通った数][H][W]として、最後にpow(3,合計空白数-空白を通った数)とかすれば解けそう…と考えたのですが、H,Wの最大は5000、そうなると空白マスの合計は10000ほどになります。
メモリ的にも計算量的にもだめです。
空白を通っていないを、もっと賢くカウントする必要がありそうです。
距離で考える
空白が(1,4)にあると考えます。この位置はスタートの(1,1)から距離が3の場所です。
距離3の場所は他に(2,3),(3,2),(4,1)の3か所ありますが、これらの場所から空白マスの(1,4)に到達するのは不可能です。(移動するたびに距離が1増えるため、同じ距離のマスには絶対いけない)
なので、これら3マスは遷移のさいに空白マス分の影響…具体的にはpow(3,同じ距離の空白マス(自マス以外))を掛けます。
これにより、空白マスを通らない経路が受ける空白マスの影響をdpの遷移に丸め込むことができました。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
// https://algo-logic.info/calc-pow/
int MOD = 998244353;
long long mpow(long long x, long long n) {
long long ret = 1;
while (n > 0) {
if (n & 1) ret = ret * x % MOD; // n の最下位bitが 1 ならば x^(2^i) をかける
x = x * x % MOD;
n >>= 1; // n を1bit 左にずらす
}
return ret;
}
int main(){
long long H,W,K;
cin>>H>>W>>K;
map<pair<int,int>,char> m;
long long bl[20000]={0};
for(int i=0;i<K;i++){
int h,w;
char c;
cin>>h>>w>>c;
m[make_pair(h,w)]=c;
}
for(int i=1;i<=H;i++){
for(int j=1;j<=W;j++){
if(m.find(make_pair(i,j))==m.end()) {
//cout<<i<<","<<j<<endl;
bl[i-1+j-1]++;
}
}
}
modint998244353 dp[H+2][W+2];
for(int i=0;i<=H+1;i++){
for(int j=0;j<=W+1;j++){
dp[i][j]=0;
}
}
long long powdata[10000]={0};
for(int i=0;i<10000;i++){
powdata[i]=mpow(3,i);
}
dp[1][1]=1;
for(int i=1;i<=H;i++){
for(int j=1;j<=W;j++){
if(m.find(make_pair(i,j))==m.end()){
//long long p=mpow(3,bl[i-1+j-1]-1);
//cout<<"B"<<p<<" ";
dp[i][j]*=powdata[bl[i-1+j-1]-1];
dp[i][j+1]+=dp[i][j]*2;
dp[i+1][j]+=dp[i][j]*2;
}
else{
char c=m[make_pair(i,j)];
//long long p=mpow(3,bl[i-1+j-1]);
//cout<<"C"<<p<<" ";
dp[i][j]*=powdata[bl[i-1+j-1]];
if(c=='R'||c=='X') dp[i][j+1]+=dp[i][j];
if(c=='D'||c=='X') dp[i+1][j]+=dp[i][j];
}
}
//cout<<endl;
}
if(m.find(make_pair(H,W))==m.end()) dp[H][W]*=3;
cout<<dp[H][W].val()<<endl;
}
ただのpowだと計算量が怖いため、事前計算+繰り返し二乗法を使いました。
繰り返し二乗法は上記のサイトのものをお借りしました。
注意点はdp[H][W]が空白の場合、そこには何も書いていいため答えが*3になることです。あとはmodの取るタイミングも注意ですが、C++ならatcoderライブラリのmodint998244353を使えば安全です。
D – Choosing Up Sides
D – Choosing Up Sides (atcoder.jp)
Twitter見てACしました。
コンテスト中に考えたこと
K=2を手計算で考えた場合、
3 AABB ABAB ABBA
となり、K=1の時と考えると何となくpow(2,K)-1になりそうな気がします。
この考察は正解なのですが、ここから法則が掴めず時間切れでした…
アダマール行列
pow(2,K)ごとに増えて、各列のAとBの数が同じ…ということを考えると、ある有名な行列が連想されるそうです。
知ってますか？私は生まれて初めて聞きました。
“各行が互いに直行である”の性質が大事で、これはD問題の2つの条件を満たすことになります。
具体的には、任意の2行取り出した際の各値の積の和が0になる(多分)が直行になることのため、任意の2行にある1と1,-1と-1の同じ組み合わせと1,-1の違う組み合わせの数が等しいことになります。
今回はWikipediaにあるシルベスターの生成法を使いました。
再帰的な方法でアダマール行列を作ることができます。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
//https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%80%E3%83%9E%E3%83%BC%E3%83%AB%E8%A1%8C%E5%88%97#%E3%82%B7%E3%83%AB%E3%83%99%E3%82%B9%E3%82%BF%E3%83%BC%E3%81%AE%E7%94%9F%E6%88%90%E6%B3%95
int main(){
int N;
cin>>N;
int n=pow(2,N);
int m=pow(2,N)-1;
if(N==1){
cout<<"1"<<endl<<"AB"<<endl;
return 0;
}
int H[N+1][n][n];
for(int i=0;i<N+1;i++){
for(int j=0;j<n;j++){
for(int k=0;k<n;k++){
H[i][j][k]=0;
}
}
}
H[0][0][0]=1;
H[1][0][0]=1;
H[1][0][1]=1;
H[1][1][0]=1;
H[1][1][1]=-1;
for(int i=2;i<=N;i++){
for(int j=0;j<pow(2,i-1);j++){
for(int k=0;k<pow(2,i-1);k++){
for(int l=0;l<2;l++){
for(int q=0;q<2;q++){
H[i][j*2+l][k*2+q]=H[1][l][q]*H[i-1][j][k];
}
}
}
}
}
cout<<m<<endl;
for(int i=1;i<=m;i++){
for(int j=0;j<n;j++){
if(H[N][i][j]==1) cout<<"A";
else cout<<"B";
}
cout<<endl;
}
}
1列目は全て1のため、ここは出力しないようにします(そのため、答えがpow(2,K)-1になります)。
任意の2行は直行になりませんが、代わりに任意の2行の積が-1になるため問題ありません。(異なるチームが1回多い)
番外編：popcount解
D – Choosing Up Sidesの解説放送でpopcountという単語が出ました。
popcountとは何でしょう？
popcountは2進変換した際の1の数を言います。
7=111なら、popcount(7)=3
競プロではこれを高速に計算するアルゴリズムがあるそうです。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
//https://qiita.com/zawawahoge/items/8bbd4c2319e7f7746266
int popcount(long long x){
x = x - ((x >> 1) & 0x5555555555555555);
// 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f; // 8bitごと
x = x + (x >> 8); // 16bitごと
x = x + (x >> 16); // 32bitごと
x = x + (x >> 32); // 64bitごと = 全部の合計
return x & 0x0000007f;
}
int main(){
int N;
cin>>N;
int n=pow(2,N);
int m=pow(2,N)-1;
cout<<m<<endl;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(popcount(i&j)%2==0) cout<<"A";
else cout<<"B";
}
cout<<endl;
}
}
ビットカウントする高速アルゴリズムをPythonで実装しながら詳しく解説してみる – Qiita
こちらのコードをお借りしてACしました。
O(1)でpopcountが計算できます。
ちなみにですが、C++20ではstdにpopcountが入っているそうです。(Atcoderは現在C++17なので使えないです…多分)
こちらの解答、popcount(i&j)の偶奇でチームを分けていますが、pdf解見ても思考が書かれていなくて？？？となります。解説放送見てもイマイチなので、これは類題を解いてエスパー力付けろって問題な気がしますね…。
おわりに
今年までに青コーダーを目指していましたが、この調子なら今年度中に行けそうです！
このブログを書き始めてから特に伸びが良くなった気がします。
ブログを書くことの個人的なメリットとして
- 思考が整理できる
(ブログに載せるために、自分のコードを整理したり、もっときれいな別解でAC通したりする) - ブログに載せるために、解説ACを頑張ろうとする
など、誰が見ているか分からないブログですが、一応世界に発信するということで微かに気を使った部分が聞いている気がします。
ブログでの参加記を書くの、競プロ上達におススメです！
コメント