はじめに
鹿島建設プログラミングコンテスト2020（AtCoder Regular Contest 110） – AtCoder
出張や新作ゲームの発売があり、競プロが少しできていませんでしたが、コンテストには何とか参加しました。
結果はA,B,Cの三完でした。
A – Redundant Redundancy
A – Redundant Redundancy (atcoder.jp)
2～Nを掛けた値は、2～Nの約数を持っているため2～Nで割り切ることができます。
さらに、この2～Nを掛けた値に1を加えることで、2～Nで割った際に余りを1にすることができます。(N%k=0のとき、(N+1)%k=1になります)
これでOKとしたいのですが、Nの制約が最大30で、出力の許容範囲が10^13以下です。2～Nを単純に掛けると越えてしまします。
ここで、最小公倍数を使います。最小公倍数とは、ある集合Aの値全て割り切れるものの中で最小の値です。
最小公倍数を求めて、そこに1加えることで題意の数が求まります。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
long long gdb(long long a,long long b){
if(a<b) return gdb(b,a);
if(b==0) return a;
return gdb(b,a%b);
}
int main(){
long long N;
cin>>N;
long long ans=2;
for(long long i=3;i<=N;i++){
ans=ans*i/gdb(ans,i);
}
cout<<ans+1<<endl;
}
最小公倍数は最大公約数(gdb)を用いて計算します。
2つの値を掛けて、共通の素因数をgdbで割ることで消している感じです。
B – Many 110
Tが1101101….か1011011011….か0110110110…である場合、部分文字列が存在します。それ以外の場合は存在しません。
それぞれの場合でいくつ含まれるか考えてみます(考えやすくするためS=110110110とします)。
110
110の場合、Sには3つ含まれています。
110110と1つ110が増えた場合、Sの最後の110が含まれなくなるため2つになります。
このように、110の繰り返しが1増えるごとに、Sの部分文字列の数が1減っていきそうです。
また、繰り返しが途中の場合(1101など)も、Sの最後の部分が対応できなくなるため1つ減ってしまいます。よってS=110110110の場合
3-((N/3)-1)-(N%3!=0)
となりそうです。
101
110の場合と考え方は同じですが、101と最小の場合でも110110110には2つしか含まれません。
101101と繰り返しが増えるごとに、最後が対応できなくなり1つ減っていくのは同様です。
また、1011や10110といった途中でも101の場合は最後が対応できます。
よって、S=110110110の場合、
3-(N/3);
`となりそうです。
011
101の場合と同じですが、途中の場合が違います。
0110と1つ途中の場合は最後が対応できますが、01101と2つ途中の場合は対応できません。
よって、S=110110110の場合、
-(N/3)-(N%3==2)
となりそうです。
結果
Tから3つのどのパターンかに場合分けし、それぞれの場合で計算すればOKです。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N;
string T;
cin>>N;
cin>>T;
bool f1=true;
for(int i=0;i<N;i++){
if(i%3==0&&T[i]!='1') f1=false;
if(i%3==1&&T[i]!='1') f1=false;
if(i%3==2&&T[i]!='0') f1=false;
}
bool f2=true;
for(int i=0;i<N;i++){
if(i%3==0&&T[i]!='1') f2=false;
if(i%3==1&&T[i]!='0') f2=false;
if(i%3==2&&T[i]!='1') f2=false;
}
bool f3=true;
for(int i=0;i<N;i++){
if(i%3==0&&T[i]!='0') f3=false;
if(i%3==1&&T[i]!='1') f3=false;
if(i%3==2&&T[i]!='1') f3=false;
}
long long ans=0;
if(f1){
ans+=10000000000ll-((N/3)-1)-(N%3!=0);
}
if(f2){
ans+=10000000000ll-(N/3);
}
if(f3){
ans+=10000000000ll-(N/3)-(N%3==2);
}
cout<<ans<<endl;
}
(入力例に101のパターンしかなく、意地悪だなぁと思いました。1発ACできて良かったですが、ハマると大変そうです。)
C – Exoswap
1回しか交換できないため、2 4 1 5 3のように1が3番目にある場合、操作2→操作1と2回操作し1を端にする必要があります。先に操作1をして2を確定させようとしたりすると、1の経路がなくなるため悪手です。
…と、このように端から決めていくようなパターンがあるかを見ていくのが最適だと言えます。(今回の操作の場合、1を端に送る手順が1通りしかないため、端から決めて出来なさそうなら、どうやってもできないといえる)
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N;
cin>>N;
int P[N];
for(int i=0;i<N;i++){
cin>>P[i];
}
set<int> s;
int ans[N],ansc=0;
for(int i=0;i<N;i++){
//cout<<"==="<<P[i]<<endl;
if(P[i]!=i+1){
int idx;
// cout<<"---"<<i<<endl;
for(idx=i+1;idx<N;idx++){
if(P[idx]==i+1) break;
}
if(idx==N){
cout<<"-1"<<endl;
return 0;
}
for(int j=idx;j>=i+1;j--){
if(s.find(j)!=s.end()){
cout<<"-1"<<endl;
return 0;
}
//cout<<j<<endl;
s.insert(j);
ans[ansc++]=j;
swap(P[j],P[j-1]);
}
}
}
for(int i=0;i<N;i++){
if(P[i]!=i+1){
cout<<"-1"<<endl;
return 0;
}
}
if(ansc!=N-1){
cout<<"-1"<<endl;
return 0;
}
for(int i=0;i<ansc;i++){
cout<<ans[i]<<endl;
}
}
太字で書かれていますが、”ちょうど1回ずつ”という制約があります。なので、1 2 3 4みたいに、元々昇順になっているような数列は-1になります。(これのせいで2WAしたx x)
おわりに
過去最高パフォーマンス(1917)が出ました！
この調子で青に突入していきたいですね:)
コメント