参加していましたがブログの記載が遅れました。
ちなみにですが、4完早解きで800位でした。
A – Difference Max
A – Difference Max (atcoder.jp)
x-yの最大値なので、xは大きくyは小さくするのがBESTです。
xもyもある範囲内で変化する値なので、その範囲での最大最小を選択すればいいです。
具体的にはxの範囲の最大であるbと、yの範囲の最小であるcを選択し、b-cを出力すればOKです。
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b,c,d;
cin>>a>>b>>c>>d;
cout<<b-c<<endl;
}B – Round Down
制約が10^100と大きいのでdoubleなんかで受け取るのは現実的ではありません。
出力する答えがが小数点以下切り捨てです。これは言い換えると、整数部だけ出力すると言えます。
なので、文字列で受け取って整数部(“.”が出るまで)を出力すればOKです。
#include<bits/stdc++.h>
using namespace std;
int main(){
string X;
cin>>X;
for(int i=0;i<X.size();i++){
if(X[i]=='.') break;
cout<<X[i];
}
cout<<endl;
}C – Doubled
Nの最大が10^12なので、全探索はTLEです。
“前半と後半は文字列として等しい”を上手いこと使います。
これは、10^12の場合abcdefabcdefのような数字であるといえます。
この中に出てくる文字の種類は6種類しかありません。なので、この6種類を全探索すればOKです。
#include<bits/stdc++.h>
using namespace std;
int main(){
long long N;
cin>>N;
int ans=0;
for(long long i=1;i<=1000000;i++){
int keta=0;
int ii=i;
while(ii!=0){
ii/=10;
keta++;
}
long long n=i+i*pow(10,keta);
if(n<=N) ans++;
}
cout<<ans<<endl;
}コードとしては1～10^6までを全探索して、2個くっ付けた数字がN以下であるものをカウントするようにしています。
D – Hanjo
atcoderっぽくない問題です。
1マスの畳を置く、2マスの畳を横向きに置く、2マスの畳を縦向きに置くと3パターンを全マスにすると考えます。(正確ではないですが、計算量を求めて間に合うか確認したいだけなので大きく出る分には良しとします。)
HWの最大が16であるため、3^16≒4.3*10^7です。
雑に全探索して十分間に合います。
#include<bits/stdc++.h>
using namespace std;
int H,W,A,B;
int tatami[16][16];
int dfs(int y,int x){
//cout<<x<<","<<y<<endl;
if(y>=H){
if(A==0&&B==0) return 1;
return 0;
}
int nx=x+1;
int ny=y;
if(nx>=W){
nx=0;
ny++;
}
int ans=0;
if(tatami[y][x]==1){
return dfs(ny,nx);
}
tatami[y][x]=1;
B--;
if(B>=0) ans+=dfs(ny,nx);
B++;
A--;
if(A>=0&&y!=H-1&&tatami[y+1][x]==0){
tatami[y+1][x]=1;
ans+=dfs(ny,nx);
tatami[y+1][x]=0;
}
if(A>=0&&x!=W-1&&tatami[y][x+1]==0){
tatami[y][x+1]=1;
ans+=dfs(ny,nx);
tatami[y][x+1]=0;
}
A++;
tatami[y][x]=0;
return ans;
}
int main(){
cin>>H>>W>>A>>B;
cout<<dfs(0,0)<<endl;
}左上から見ていっているため、右に伸ばして畳Aを置くか、下に伸ばして畳Bを置くか、その場に畳Aを置くかの3通りだけでOKです。
※上に伸ばすパターンは、上のマスで下に伸ばすことと同義。左に伸ばすパターンも、その左のマスで右に伸ばすことと同義なので必要なし。
置かない(畳がないのにあえて置かない)パターンは、そのマスがどうやっても拾えなくなるので必要なし。
E – Filters
mapとかで管理してゴリゴリやっていましたが諦めて解説見ました…。賢い。
最終的に、minで均された値、maxで均された値、min～maxにある値の3種類に分かれます。
min値、max値、t1のときのaiの合計値の3つを更新することで解くことができます。
入力例1の場合 -10 2 →max=-10 min=INF aiの合計=0 (maxで均される値が-10になる。) 10 1 →max=0 min=INF aiの合計=10 (aiの合計が増える。maxで均された値も増える) 10 3 →max=0 min=10 aiの合計=10 (minで均された値が10になる)
と更新し、まずQの各値にaiを足して均されるかを判定します。
-15 -10 -5 0 5 aiの合計である10を足す →-5 0 5 10 15 max以下は0に、min以上は10に均す →0 0 5 10 10
aiを足すことによって、Qの各点とminmaxで均された値が上下に平行移動することを考えると分かりやすいです。
説明がやや雑めですが、エデュ解が分かりやすいのでそちらを見てください＞＜
(合成関数を使った数学的な解説が載っています)
#include<bits/stdc++.h>
using namespace std;
int H,W,A,B;
int tatami[16][16];
int main(){
long long N;
cin>>N;
long long a[N],t[N];
for(int i=0;i<N;i++){
cin>>a[i]>>t[i];
}
long long mx=LLONG_MIN/2,mn=LLONG_MAX/2,add=0;
for(int i=0;i<N;i++){
if(t[i]==1){
mx+=a[i];
mn+=a[i];
add+=a[i];
}
else if(t[i]==2){
mx=max(mx,a[i]);
mn=max(mn,a[i]);
}
else{
mx=min(mx,a[i]);
mn=min(mn,a[i]);
}
}
//cout<<add<<","<<mx<<","<<mn<<endl;
int Q;
cin>>Q;
for(int i=0;i<Q;i++){
long long x;
cin>>x;
x+=add;
x=min(x,mn);
x=max(x,mx);
cout<<x<<endl;
}
}F – Substring 2
一晩考えても分からなかったので答え見ました。
FFT(高速フーリエ変換)の畳み込みを使うそうです。
※Beginnerコンテストです。
入力例1を例にすると 0001 101 0001 101 101 とTを先頭から末尾までずらしたときのハミング距離の最小が答えになる。 (この場合、1つ後ろにずらすとハミング距離が1になって最小になる) ここでTを反転することを考える 1000 101 ここで、Sの先頭とTの末尾...のように元々の位置関係でハミング距離を取ることを考えると、クロスするような取り方になる。 →この取り方こそがFFTの畳み込みになる。
…らしいです。
私はHAHAHAHAという感じでエデュ解を読んでました。
ちなみに、畳み込みって掛け算の和じゃん？今回とは違うくない？と思いそうですが、
1000 101 のハミング距離を Si xor Ti (i=a～a+Tsize)の和と考える。 ※a=Tの先頭位置 このとき、Si xor Tiは Si(1-Ti)+Ti(1-Si) と言い換えられるので、ハミング距離を求めるということは Si(1-Ti)の和+Ti(1-Si)の和 (i=a～a+Tsize) と言い換えられる。
なので、Siと1-Tiの畳み込み、Tiと1-Siの畳み込みを行ったものの和を求めればOKです。
Si xor Ti→Si(1-Ti)+Ti(1-Si)の変換。私は知らなかったですが、真理値表書いてびっくりしました。
#include<bits/stdc++.h>
//#include<boost/multiprecision/cpp_int.hpp>
#include<atcoder/all>
using namespace std;
//using namespace boost::multiprecision;
using namespace atcoder;
int main(){
//FFT atcoder::convolution
//a^b = a(1-b)+b(1-a)
//...a=0 b=0 0*1+0*1=0
// a=0 b=1 0*0+1*1=1
// a=1 b=0 1*1+0*0=1
// a=1 b=1 1*0+1*0=0
string S,T;
cin>>S>>T;
reverse(T.begin(),T.end());
string S1=S,T1=T;
for(int i=0;i<S1.size();i++){
int n=S1[i]-'0';
n=1-n;
S1[i]=n+'0';
}
for(int i=0;i<T1.size();i++){
int n=T1[i]-'0';
n=1-n;
T1[i]=n+'0';
}
vector<int> s1,s2,t1,t2;
for(int i=0;i<S.size();i++){
s1.push_back(S[i]-'0');
s2.push_back(S1[i]-'0');
//cout<<s1[i]<<","<<s2[i]<<" ";
}
//cout<<endl;
for(int i=0;i<T.size();i++){
t1.push_back(T[i]-'0');
t2.push_back(T1[i]-'0');
//cout<<t1[i]<<","<<t2[i]<<" ";
}
//cout<<endl;
vector<int> ans1=convolution(s1,t2);
vector<int> ans2=convolution(s2,t1);
int ans=INT_MAX;
for(int i=T.size()-1;i<S.size();i++){
//cout<<i<<","<<ans1[i]<<","<<ans2[i]<<endl;
ans=min(ans,ans1[i]+ans2[i]);
}
cout<<ans<<endl;
}
C++だとatcoder library、pythonだとnumpyなんかを使えばOKです。
AtCoder Typical Contest 001 – AtCoder
FFTは全く知らないので、この辺りで勉強したいですね…。
(せめて競プロ範囲だけでもマスターしたい…)
コメント