Codeforces Round #424 Div.2 A,B,C,D

所感

考察力足りない...

本番A,Bを20分くらいで通して後は唸ってました。

 

Problem - A - Codeforces

与えられた数列が単調増加、同値、単調減少の順になっているかを判定する。

愚直にやったのであんまり綺麗なコードじゃありません...。

単調増加のbreak判定で同値かどうかだけ気をつければいいですかね。

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long

using namespace std;

int main(){
int N;
cin>>N;

int cnt=0;
int before=0;
int next;

bool isPossible=true;
bool same=false;
while(cnt<N){
cin>>next;
cnt++;
if(next<=before){
if(next==before)same=true;
break;
}
before=next;
}

before=next;
if(same){
while(cnt<N){
cin>>next;
cnt++;
if(next>before)isPossible=false;
if(next<before)break;
before=next;
}
}

before=next;
while(cnt<N){
cin>>next;
cnt++;
if(next>=before)isPossible=false;
before=next;
}

if(isPossible){
cout<<"YES"<<endl;
}else{
cout<<"NO"<<endl;
}

return 0;
}

 

Problem - B - Codeforces

大文字・小文字両方のアルファベットを対応するものに変換する。

charの知識があれば一瞬だと思います。大文字も変換しないといけないので

変換元のローマ字 -'a' +'A' で大文字にしています。

char型が整数を表しており、連続するアルファベットは数値も連続していることを利用していますね。ちなみにアルファベット以外(数字)はそのまま出力するので

最初に compile[i] = i (変換しない)を代入しています。

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long

using namespace std;

int main(){

char compile[256];
REP(i,256){
compile[i]=i;
}

string from,to,input;
string output="";
cin>>from>>to>>input;

REP(i,26){
compile[from[i]]=to[i];
compile[from[i]-'a'+'A']=to[i]-'a'+'A';
}

REP(i,input.size()){
output+=compile[input[i]];
}
cout<<output<<endl;

return 0;
}

 

Problem - C - Codeforces

未知のある得点に対し、与えられた数列の順に得点が加算されていく。得点の過程の集合(最初の得点は含まない、また加算された順番通りとは限らない)が与えられるので、最初の得点としてありうる個数を求める。

終わった後にシャワー浴びてたら解けました(よくある)。

最初の得点に対する変化をsetで持っておきます。

例えば、得点の変化が (-5 , -5 , 10 , 12 , 13) なら、最初の数を x とすると、得点は

(x -5, x -10, x, x +12, x +25) と変化するので、(-5, -10, 0, 12, 25)というようなsetを作ります。覚えている得点は最初の得点を含まないので、覚えている内の一つの得点(コードではremember[0]としています)が、最初の得点からの変化が -5なら、-10なら...と列挙していきます。他の点数がset内に含まれていれば有りうる、そうでなければ有り得ません。例えば 7, 2,24 という値を覚えていたとして、7 が最初の得点からの変化が -5 (最初の得点が12 ) だとすると、2は最初の得点からの変化が -10 , 24は +12 なので、先ほどのset内に含まれるので有り得ます。二重ループとset.countでO(nk log k)。

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long

using namespace std;

int main(){

int k,n;
cin>>k>>n;
set<int> point;
int sum=0;
REP(i,k){
int p;
cin>>p;
sum+=p;
point.insert(sum);
}

vector<int> remember;
REP(i,n){
int p;
cin>>p;
remember.push_back(p);
}

int cnt=0;
for(auto p : point){
bool isPossible=true;
REP(i,n-1){
if(point.count(remember[i+1]-(remember[0]-p))==0)isPossible=false;
}
if(isPossible)cnt++;
}

cout<<cnt<<endl;
return 0;
}

 

Problem - D - Codeforces

直線上にn人がa[i]の場所いて、k個の鍵( k >=n )がb[j]の場所にある。n人全員がいずれかの鍵を持って(あるb[j]に辿り着いて) pの位置にあるオフィスに着くときの最短時間を求める。

まず最初に、鍵がn個ちょうどだけあったときのことを考えます。このとき、オフィスから見て左右両方の一番外側の人、鍵を考えると、一番外側の人が一番外側の鍵を持って行くのが最短であるとわかります。順番に外側から考えると、結局端の人から順に、端の方から鍵を持って行くのが最短であると分かります。

次に、k個の鍵についてn個の鍵を選びます。ここで、選んだ鍵がとびとびだとします。もし空白が一番外側にいる人より外側にあるならば、より内側にあるものを選んだ方が近いことが分かります。また、内側にあるならば、オフィスに向けて空白を埋めるように取る鍵をシフトしても、オフィスに行く途中で拾うので、問題ないことが分かります。

以上の考察により、k個の中から連続するn個について、n人で順番に持って行った時間の最小値が答えになります。

こういう特殊なデータ構造とかアルゴリズムとかを使わない考察系の問題をスラッと解けるようになりたい...

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long

using namespace std;

int main(){

int n,k;
LL p;
cin>>n>>k>>p;
LL a[n];
REP(i,n)cin>>a[i];
LL b[k];
REP(i,k)cin>>b[i];

sort(a,a+n);
sort(b,b+k);

LL ans=2*1000000000;
REP(i,k-n+1){
LL time=0;
REP(j,n)time=max(time, abs(a[j]-b[j+i])+abs(b[j+i]-p));
ans = min(ans,time);
}

cout<<ans<<endl;

return 0;
}