A – 豆まき
A,B,Cの順位付けは3*2*1=6パターンしかないので、全パターンの判定式を書きました。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int A,B,C;
cin>>A>>B>>C;
if(A>B&&B>C&&A>C) cout<<"1\n2\n3\n";
if(A>B&&B<C&&A>C) cout<<"1\n3\n2\n";
if(A<B&&B>C&&A>C) cout<<"2\n1\n3\n";
if(A>B&&B<C&&A<C) cout<<"2\n3\n1\n";
if(A<B&&B>C&&A<C) cout<<"3\n1\n2\n";
if(A<B&&B<C&&A<C) cout<<"3\n2\n1\n";
}
よくよく考えれば、順位は1位から始まって他人より何らか負けると下がっていきます。
今回の場合、他人の点数が高ければ1下がっていくため、1+(自分より点数の高い点数の人数)となりそうです。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int A,B,C;
cin>>A>>B>>C;
cout<<((A<B)+(A<C)+1)<<endl<<((B<A)+(B<C)+1)<<endl<<((C<A)+(C<B)+1)<<endl;
}
C++では、true=1,false=0なので、こんな感じにまとめて書けます。
B – 文字列の反転
文字反転の基礎問題です。
頭から始まるindexと、尻尾から始まるindexの2つ用意し、それぞれのindexが指す文字をswapすることで反転できます。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
string s;
cin>>s;
int N;
cin>>N;
for(int i=0;i<N;i++){
int l,r;
cin>>l>>r;
for(int j=0;j<(r-l+1)/2;j++){
swap(s[l-1+j],s[r-1-j]);
}
}
cout<<s<<endl;
}
C – 菱型カウント
愚直に数えると、R=500,C=500,K=250のときにO(250^3=3*10^9)くらいでTLEします。
何か上手いこと高速化する必要がありそうです。
ひし形が置ける場所=距離がK-1である場所に”x”がないといえます。なので、最も近い”x”の位置が分かれば高速に計算できそうです。
最も近い”x”の場所ですが、横縦別に考えることによってO(RC)で求めることができます。
具体的には、まず横だけで最も近い”x”の場所を計算し、その値を利用しながら縦も考慮して計算します。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int R,C,K;
cin>>R>>C>>K;
string s[R];
for(int i=0;i<R;i++){
cin>>s[i];
}
int dis[R][C];
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
dis[i][j]=R*C;
}
}
for(int i=0;i<R;i++){
int c=R*C;
for(int j=0;j<C;j++){
if(s[i][j]=='x') c=0;
dis[i][j]=min(dis[i][j],c);
c++;
}
}
for(int i=0;i<R;i++){
int c=R*C;
for(int j=C-1;j>=0;j--){
if(s[i][j]=='x') c=0;
dis[i][j]=min(dis[i][j],c);
c++;
}
}
for(int j=0;j<C;j++){
int c=R*C;
for(int i=0;i<R;i++){
c=min(c,dis[i][j]);
dis[i][j]=c;
c++;
}
}
for(int j=0;j<C;j++){
int c=R*C;
for(int i=R-1;i>=0;i--){
c=min(c,dis[i][j]);
dis[i][j]=c;
c++;
}
}
/*
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
cout<<dis[i][j]<<" ";
}
cout<<endl;
}
*/
int ans=0;
for(int i=K-1;i<R-(K-1);i++){
for(int j=K-1;j<C-(K-1);j++){
if(dis[i][j]>=K) ans++;
}
}
cout<<ans<<endl;
}
動き的にはこんな感じです。
3 3 oxo xoo ooo の場合、 010 012 000 まず、横だけを考慮して計算 110 012 100 縦の左は真ん中が"x"なので、そこから波及する 100 012 120 縦の真ん中の一番上は1だけど、縦で見たときに"x"があるので0で更新 そのまま、下に波及させていく 103 012 123 縦の右は、横だけ考慮の2が真ん中にあるため、それを波及させていく
D – バレンタインデー
N,Mの制約的にbit全探索をしてほしそうな問題です。
仮に、女子の参加メンバーが決まった際の最適解がどうなるのか考えます。
入力例1 3 4 2 3 7 1 1 9 1 2 7 1 3 15 1 4 6 2 2 3 2 4 6 3 3 6 で、女子は1,3が参加する場合 x=1 or 3であるチョコレートに関する情報だけを取り出し、 yとzだけで以下のようになる 1 9 2 7 3 15 4 6 3 6 この時、同じyはまとめて 1 9 2 7 3 21 4 6 とでき、zが大きいyを選択するのが明らか最適である
と、貪欲の簡単な問題にすることができます。
女子の人数は最大18なので、全通りbit全探索で試すことができます。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N,M,P,Q,R;
cin>>N>>M>>P>>Q>>R;
int x[R],y[R],z[R];
for(int i=0;i<R;i++){
cin>>x[i]>>y[i]>>z[i];
}
int ans=0;
for(int i=0;i<(1<<N);i++){
int nf[18]={0};
int c=0;
int ii=i;
for(int j=0;j<N;j++){
if(ii%2==1){
nf[j]=1;
c++;
//cout<<j<<" ";
}
ii/=2;
}
//cout<<endl;
if(c!=P) continue;
int ysum[18]={0};
for(int j=0;j<R;j++){
if(nf[x[j]-1]) ysum[y[j]-1]-=z[j];
}
sort(ysum,ysum+18);
int zsum=0;
for(int j=0;j<Q;j++){
zsum-=ysum[j];
}
//cout<<i<<","<<zsum<<endl;
ans=max(ans,zsum);
}
cout<<ans<<endl;
}
余談ですが、atcoder problem上では青diffらしいですが、今の環境だと緑diffっぽい問題ですよね。
コメント