2021/01/24 8:00 F問題を解説ACしたので追記
はじめに
AtCoder Beginner Contest 189 – AtCoder
A,B,C,Dの4完で1111位でした。ゾロ目！
レートは-1で1482になりました。何とか耐えた感じです。
A – Slot
入力された3文字が同じかどうか判定するだけです。
C++ではA==B==Cみたいには書けない(正確には、A==Bの結果True or FalseとCが==で評価されるので、期待した結果にならない)ため、A==B && B==Cのように書きます。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
string S;
cin>>S;
if(S[0]==S[1]&&S[1]==S[2]) cout<<"Won"<<endl;
else cout<<"Lost"<<endl;
}
AtcoderはYes or Noに出力を統一するとかって話だと思っていたのに、Won or Lostでうぇぇってなってました。
B – Alcoholic
単純に足していけばいい…感じがしますが、誤差に注意です。(1WA、誤差死しました)
回避策として、Xを100倍し、V*Pへの100割りを消すことにより整数で計算するようにします。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N;
int X;
cin>>N>>X;
X*=100;
int sum=0;
int ans=-1;
for(int i=0;i<N;i++){
double V,P;
cin>>V>>P;
double al=V*P;
sum+=al;
if(ans==-1&&sum>X){
ans=i+1;
}
}
cout<<ans<<endl;
}
C – Mandarin Orange
C – Mandarin Orange (atcoder.jp)
ややこしそうですが、N<=10^4であるためO(N^2)が許されます。
全てのAi,Aj(i<=j)を見ていけばOKです。xの値は、jをi,i+1,i+2….と見ていく際に、最小値で更新していけば良いです。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N;
cin>>N;
int A[N];
for(int i=0;i<N;i++){
cin>>A[i];
}
int ans=0;
for(int i=0;i<N;i++){
int mx=A[i];
for(int j=i;j<N;j++){
mx=min(A[j],mx);
ans=max(ans,mx*(j-i+1));
}
}
cout<<ans<<endl;
}
D – Logical Expression
D – Logical Expression (atcoder.jp)
状態がTrue or Falseしかないため、dp[2(True or False)]=パターン数 として、N個目の演算子終了時点のTrueとFalseのパターン数をdpで数えていけば良いです。
2^60=(1024)^6≒10^18とかなので、intだと死にます。(1WA)
64bitで構えましょう。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N;
cin>>N;
long long dp[2];
dp[0]=1;
dp[1]=1;
for(int i=0;i<N;i++){
long long nx[2]={0};
string S;
cin>>S;
if(S=="AND"){
nx[0]+=dp[1]+dp[0]+dp[0];
nx[1]+=dp[1];
}
else{
nx[0]+=dp[0];
nx[1]+=dp[1]+dp[1]+dp[0];
}
dp[0]=nx[0];
dp[1]=nx[1];
}
cout<<dp[1]<<endl;
}
E – Rotate and Flip
E – Rotate and Flip (atcoder.jp)
このような回転や対象移動を行うアルゴリズムとしてアフィン変換というものがあるそうです。
アフィン変換（平行移動、拡大縮小、回転、スキュー行列） | イメージングソリューション (imagingsolution.net)
アフィン変換の良いところは、各操作を3*3の行列で表すことにより纏められるところです。
そのため、m回目の操作終了後の操作行列を持っていると、m回後の各点の座標を行列計算よりO(1)で求めることができます。
各操作をアフィン変換に直す
回転は以下のように定義されています。
cosΘ -sinΘ 0 sinΘ cosΘ 0 0 0 1
時計回りはΘ=270
反時計回りはΘ=90であるため
op=1 0 1 0 -1 0 0 0 0 1
op=2 0 -1 0 1 0 0 0 0 1
となります。
x軸,y軸に対称な移動は、拡大の際に-1倍することで可能です。
今回対象とする軸が自由に決められますが、x軸,y軸に対称な移動を行った際に平行移動すればOKです。
絵に書くと分かりやすいですが、x=pに対称な移動の際は、xに2*p平行移動すれば良いです。
op=3 -1 0 p*2 0 1 0 0 0 1
op=4 1 0 0 0 -1 p*2 0 0 1
行列の計算
行列の積は以下の式で求められます。
A(n*m)B(m*l)=C(n*l)の時、 Cij(1<=i<=n,1<=j<=l)=∑(k=1→m)(Aik*Bkj)
気を付ける点は、AB≠BAであることです。
行列の積は交換法則が成り立ちません。
アフィン変換の場合、前に付けていく(A→B→Cと処理する場合、CBAとなる)ことで纏められます。
さいごに
上記で解くための材料は揃いました。
今回、クエリをAの小さい順にソートし、アフィン変換しながらAiの小さい順に変換後の座標を求めるようにしました。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
long long N;
cin>>N;
long long X[N],Y[N];
for(long long i=0;i<N;i++){
cin>>X[i]>>Y[i];
}
long long M;
cin>>M;
long long op[M],opp[M];
for(long long i=0;i<M;i++){
cin>>op[i];
if(op[i]==3||op[i]==4){
cin>>opp[i];
}
}
long long Q;
cin>>Q;
//A B idx ansx,ansy
vector<pair<pair<long long,long long>,pair<long long,pair<long long,long long>>>> v;
for(long long i=0;i<Q;i++){
pair<long long,long long> AB;
pair<long long,pair<long long,long long>> ia;
long long A,B;
cin>>A>>B;
AB=make_pair(A,B);
ia=make_pair(i,make_pair(0,0));
v.push_back(make_pair(AB,ia));
}
sort(v.begin(),v.end());
//アフィン変換
long long afin[3][3];
afin[0][0]=1;
afin[0][1]=0;
afin[0][2]=0;
afin[1][0]=0;
afin[1][1]=1;
afin[1][2]=0;
afin[2][0]=0;
afin[2][1]=0;
afin[2][2]=1;
long long vi=0;
for(long long i=0;i<M+1;i++){
while(vi<Q&&v[vi].first.first==i){
long long xy[3];
xy[0]=X[v[vi].first.second-1];
xy[1]=Y[v[vi].first.second-1];
xy[2]=1;
for(long long k=0;k<2;k++){
for(long long l=0;l<3;l++){
if(k==0) v[vi].second.second.first+=xy[l]*afin[k][l];
if(k==1) v[vi].second.second.second+=xy[l]*afin[k][l];
}
}
vi++;
}
if(i==M) break;
long long afin2[3][3];
if(op[i]==1){
afin2[0][0]=0;
afin2[0][1]=1;
afin2[0][2]=0;
afin2[1][0]=-1;
afin2[1][1]=0;
afin2[1][2]=0;
afin2[2][0]=0;
afin2[2][1]=0;
afin2[2][2]=1;
}
if(op[i]==2){
afin2[0][0]=0;
afin2[0][1]=-1;
afin2[0][2]=0;
afin2[1][0]=1;
afin2[1][1]=0;
afin2[1][2]=0;
afin2[2][0]=0;
afin2[2][1]=0;
afin2[2][2]=1;
}
if(op[i]==3){
afin2[0][0]=-1;
afin2[0][1]=0;
afin2[0][2]=opp[i]*2;
afin2[1][0]=0;
afin2[1][1]=1;
afin2[1][2]=0;
afin2[2][0]=0;
afin2[2][1]=0;
afin2[2][2]=1;
}
if(op[i]==4){
afin2[0][0]=1;
afin2[0][1]=0;
afin2[0][2]=0;
afin2[1][0]=0;
afin2[1][1]=-1;
afin2[1][2]=opp[i]*2;
afin2[2][0]=0;
afin2[2][1]=0;
afin2[2][2]=1;
}
long long afin3[3][3]={{0}};
for(long long j=0;j<3;j++){
for(long long k=0;k<3;k++){
for(long long l=0;l<3;l++){
afin3[j][k]+=afin[l][k]*afin2[j][l];
}
}
}
for(long long j=0;j<3;j++){
for(long long k=0;k<3;k++){
afin[j][k]=afin3[j][k];
//cout<<afin[j][k]<<",";
}
//cout<<endl;
}
}
for(long long i=0;i<Q;i++){
v[i].first.first=v[i].second.first;
}
sort(v.begin(),v.end());
for(long long i=0;i<Q;i++){
cout<<v[i].second.second.first<<" "<<v[i].second.second.second<<endl;
}
}
めちゃくちゃ汚い＼(^o^)／
sedでint→long longに一斉置換したのもアレだし、pair<pair<long long,long long>,pair<long long,pair<long long,long long>>>みたいなpairの多重入れ子を作ったのもアレ。
行列の計算やアフィン変換はライブラリとして持っておきたいですね…。
F – Sugoroku2
振り出しに戻るがある双六の期待値を求める問題。
まず、振り出しに戻るがなければどう求めていくかを考えます。
振り出しに戻るがない場合
nマスに辿り着くまでの期待値を考えます。
n=Nの時は明らかに0で、n=N-1の時は1です。
n=N-2の時はどうなるでしょうか？
M面サイコロを振って、1が出た場合は期待値1必要 2～Mの場合はそのままゴール 1/M(1が出た場合は期待値1でゴール)+1(N-2でサイコロを振るため)
同様にN-3の場合
M面サイコロを振って、1が出た場合は1/M+1の期待値が必要 2が出た場合は期待値1が必要 3～Mの場合はそのままゴール (1/M+1)/M+1/M+1
ここまで書くと何となく法則が見えてきそうです。
具体的には、以下のようになります。
nマスからNマスに辿り着く期待値は (n+1～n+Mマスの期待値の和)/M+1
です。
ここで、期待値の和を累積和で取ることを考えると逆順から見ていくことでO(N)で0マスからの期待値が分かります。
振り出しに戻るを考える
振り出しに戻る場合、再び0マスからの期待値が発生すると考えます。
そのため、以下のように纏められます。
nマスからNマスに辿り着く期待値は nマスが振り出しに戻るでないなら：(n+1～n+Mマスの期待値の和)/M+1 nマスが振り出しに戻るなら ：0マスの期待値
0マスからの期待値を求めたいのに、0マスからの期待値が計算に出てきてしまいます。
答えを決め打つ
0マスからの期待値をK(定数)とすれば、計算は可能です。
このとき0からの実際の期待値がKより大きければKを小さく、小さければKを大きくして調節すればいいです。
また、線形探索すると地球が滅亡しても計算が終わらないので、二分探索により高速化します。
さいごに
これで答えのための材料は揃いました。
“-1″を出力するケースですが、振り出しに戻るがM個続く場合は明らかに辿り着けないため”-1″とします。それ以外なら、何とかゴールできます。
(上での話は、M個続かないことを前提にしてたりします)
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N,M,K;
cin>>N>>M>>K;
set<int> A;
int Aa[N];
for(int i=0;i<N;i++) Aa[i]=0;
for(int i=0;i<K;i++){
int Ain;
cin>>Ain;
Aa[Ain]=1;
A.insert(Ain);
}
if(N>M){
int c=0;
for(int i=0;i<M;i++){
c+=Aa[i];
}
if(c>=M){
cout<<"-1"<<endl;
return 0;
}
for(int i=M;i<N;i++){
c+=Aa[i];
c-=Aa[i-M];
if(c>=M){
cout<<"-1"<<endl;
return 0;
}
}
}
double l=0;
double r=DBL_MAX/N-1;
int c=0;
while(1){
double m=(l+r)/2;
double dp[N+1];
for(int i=0;i<N+1;i++) dp[i]=0;
double wa=0;
for(int i=N-1;i>=0;i--){
if(A.find(i)==A.end()) dp[i]=wa/M+1;
else dp[i]=m;
wa+=dp[i];
if(i+M<=N) wa-=dp[i+M];
//cout<<i<<","<<wa<<endl;
}
//cout<<m<<","<<dp[0]<<endl;
if(dp[0]<m) r=m;
else l=m;
c++;
if(c>=2000) break;
}
printf("%.12f\n",(l+r)/2);
}
二分探索のrの右端は、オーバーフローしない範囲で最大の数字にしました。
終了条件は、TLEにならない程度計算したら抜けるようにしました。
少し不確定ですが、1674msで何とかAC取れました。
おわりに(あんまり関係ない話)
私がやっているDJMAXというゲームですが、近々アップデートで
Dareharuのkarmaが追加されます！
なんだよって話ですが、Dareharuは僕が一番好きだといえるアーティストさんです。
その曲が入ってきたということでゲームの方のやる気がかなり上がってきました。
ということで、来週以降コンテストに出ない可能性があります＞＜
最近平日の勉強もできていないので、上手くゲームとのバランスを取りたいですね…。(特に、最近勉強できないのもSteamで週1くらいのペースでゲームを買って潰しているから…でもあります)
コメント