競プロ参加日記011 Codeforces Round #669 (Div. 2)
ぬるからです。
3回目のcodeforces参加となりました。
https://codeforces.com/contest/1407
・はじめに
A,Bの2完で2982位でした。
レートは+251で1262へ。何とか色が付きました。
・A. Ahahahahahahahaha
1と0で構成される数列からn/2個まで要素を削除し、奇数番目の要素の和-偶数番目の要素の和が0になるようにする。
1と0の2パターンしかないため、どちらか(または両方)の個数がn/2個以下になるはずです。つまり、数が少ないほうの要素を消せば全て1または、全て0にできます。
全て0にできる場合、和は0になるため題意を満たします。
全て1にできる場合、要素の個数が偶数個であれば、奇数番目の和と偶数番目の和が等しくなるため0になります。(0=n/2個,1=n/2個のパターンを0残しにするようにすると、1が奇数個であっても必ず1つは消せる操作が残っているはずです。なので、奇数個の場合は1を余分に1つ消し、偶数個にすれば問題ありません。)
上記の考えで実装していきます。
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<climits>
/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/
using namespace std;
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007
//0001010110
int main(){
int t;
cin>>t;
for(int i=0;i<t;i++){
int n;
cin>>n;
int a;
int o=0,z=0;
for(int j=0;j<n;j++){
cin>>a;
if(a==0) z++;
else o++;
}
if(z>=n/2){
cout<<n/2<<endl;
for(int j=0;j<n/2;j++){
cout<<"0";
if(j!=n/2-1) cout<<" ";
else cout<<endl;
}
}
else{
int n2=n/2;
if(n/2%2==1) n2++;
cout<<n2<<endl;
for(int j=0;j<n2;j++){
cout<<"1";
if(j!=n2-1) cout<<" ";
else cout<<endl;
}
}
}
}・B. Big Vova
a[]を並び替えてb[]を作る。この時、ciの各要素はb0～biのgcdになる。c[]が辞書順で最も大きくなるようなb[]を求めよ。
b0=c0になるので、b0はa[]のmaxを入れるのが適切です。残りのb1～ですが、この問題はn<=10^3と制約が弱く、gcdが最大になるものを全探索で求めていっても余裕で間に合います。
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<climits>
/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/
using namespace std;
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007
//0001010110
int gcd(int a,int b){
if(b>a) return gcd(b,a);
if(b==0) return a;
return gcd(b,a%b);
}
int main(){
int t;
cin>>t;
for(int i=0;i<t;i++){
int n;
cin>>n;
int a[n];
for(int j=0;j<n;j++){
cin>>a[j];
}
sort(a,a+n);
int gd=a[n-1];
cout<<a[n-1]<<" ";
a[n-1]=-1;
for(int j=0;j<n-1;j++){
int mxi=-1;
int mx=-1;
for(int k=0;k<n;k++){
if(a[k]!=-1){
if(mx==-1){
mx=gcd(gd,a[k]);
mxi=k;
}
else{
int g=gcd(gd,a[k]);
if(g>mx){
mx=g;
mxi=k;
}
}
}
}
cout<<a[mxi];
if(j==n-1-1) cout<<endl;
else cout<<" ";
gd=gcd(gd,a[mxi]);
a[mxi]=-1;
}
}
}・C. Chocolate Bunny
珍しい形式の問題です。Atcoderの過去問とかをやっていると、たまに見かけます。
長さnの数列p[]があります。? x yと出力することで、p[x]%p[y]を知ることができるため、2n回までの質問で数列を当ててください。
modについて少し考えると答えが出ます。
a<bのとき、
a%b=a
b%a<a (0～a-1)
になります。この時、答えの大きいほう(a%b)は必ず答えがaになり、l答えの小さいほう(b%a)は必ず答えがaになりません。つまり、a%b,b%aと2回質問を送ることでaかbが確定できます。
ex.a=6 b=13の場合
a%b=6
b%a=1
答えの大きいほうである、a%b=6よりa=6が確定する。
この操作は2クエリで1つ確定できるため、単純計算で2nのクエリで答えが求まります。問題の制約的にも大丈夫そうです。
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<climits>
/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/
using namespace std;
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007
//0001010110
int ans[10001];
int n;
void dfs(vector<int> v){
if(v.size()==1){
ans[v[0]]=n;
return;
}
vector<int> vmx;
int a,b;
for(int i=0;i<v.size();i+=2){
if(i+1>=v.size()){
vmx.push_back(v[i]);
break;
}
cout<<"? "<<v[i]<<" "<<v[i+1]<<endl;
cin>>a;
cout<<"? "<<v[i+1]<<" "<<v[i]<<endl;
cin>>b;
if(a>b){
vmx.push_back(v[i+1]);
ans[v[i]]=a;
}
else{
vmx.push_back(v[i]);
ans[v[i+1]]=b;
}
}
dfs(vmx);
}
int main(){
cin>>n;
vector<int> v;
for(int i=0;i<n;i++){
v.push_back(i+1);
}
dfs(v);
cout<<"! ";
for(int i=1;i<=n;i++){
cout<<ans[i];
if(i==n) cout<<endl;
else cout<<" ";
}
}※codeforcesは数学系の問題が少ないと聞いていたのですが、出ないってわけでは無いんですね...。
こんなの絶対コンテスト中に分かりません。
・D. Discrete Centrifugal Jumps
※完全、後から思い出すための自分用のメモです。
多分、他の方が見ても訳わからないことが書いてるかと思います。(うまく、纏められませんでした...)
3つの条件
・移動先が1つ先
・移動前と移動先より、間にある建物が全て大きい
・移動前と移動先より、間にある建物が全て小さい
のどれかを満たすとき移動できる。1->nに移動する最短手順は幾つか。
移動できる経路に辺を張り、BFSで最短経路を求めたいですが、全hiに関して調べているとO(n^2)かかってだめです。
移動できる条件を少し考えてみます。
x 8 5となった場合、xが7,6,5,4,3などの場合はx->5に移動できます。
x 7 8 5 となった場合、xが6,5,4,3などの場合はx->5に移動できます。
x 4 7 8 5 となった場合、xに何を入れてもx->5には移動できません。また、これより左は値に関係なく->5には移動できなさそうです。
つまり、移動先pj<pj-1のとき、インデックスを1減らしていってpj以下になるpj-nまでが移動元の可能性になりそうです。(※9 7 8 5みたいに、増えるケースは移動できません。ただ、6 9 7 8 5のように、左の値によっては->5へ移動できる可能性はあります。)
pj>pj-1の場合は、同様に考えてpj以上になるpj-nまで移動が可能です。
纏めると、
pj<pj-1のとき、i=pj-1として、pi未満の値の中で最も近いものから移動できる。また、その箇所をiとしてpiがpj以下になるまで再帰的に移動元が算出できる。
pj>pj-1のときも同じようなことがいえます。
各piに対して、左の区間の一番近いpi未満のindexとpiより大きいindexを保持できれば、有向グラフが作れそうです。
"左の区間の一番近い"は言い換えると。区間(0,i-1)の一番右の値と言えます。こういう操作はセグ木の二分探索で行えます。
纏めると、この問題は以下のステップで解けます。
・入力からminとmaxの二つのセグ木を構築
・セグ木の二分探索で、各piの区間(0,i-1)の一番右にあるpiより大きい値の場所と、pi未満の値の場所を記録
・記録した値をもとに、移動できる場所を算出。有向グラフを作成。
・有向グラフに対してBFSで最短経路を算出。
以下、コードです。
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<climits>
/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/
using namespace std;
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007
//0001010110
//0-index
vector<int> seqv,seqv2;
int seqv_n;
void seg_init(int N,int a){
seqv.clear();
seqv2.clear();
int n=1;
while(n<N) n*=2;
seqv_n=n-1;
n*=2;
n=n-1;
for(int i=0;i<n;i++){
seqv.push_back(a);
seqv2.push_back(a);
}
}
void seg_update2(int n,int a){
int k=n+seqv_n;
seqv2[k]=a;
while(k>0){
k=(k-1)/2;
seqv2[k]=max(seqv2[k*2+1],seqv2[k*2+2]);
}
}
int seg_find2(int x,int y){
struct segF{
static int segfind(int x,int y,int k,int l,int r){
//cout<<x<<","<<y<<","<<k<<","<<l<<","<<r<<endl;
if(r<x||l>y) return INT_MIN;
if(l>=x&&r<=y) return seqv2[k];
else{
int segl=segfind(x,y,k*2+1,l,(l+r)/2);
int segr=segfind(x,y,k*2+2,(l+r)/2+1,r);
return max(segl,segr);
}
}
};
return segF::segfind(x,y,0,0,seqv_n);
}
void seg_update(int n,int a){
int k=n+seqv_n;
seqv[k]=a;
while(k>0){
k=(k-1)/2;
seqv[k]=min(seqv[k*2+1],seqv[k*2+2]);
}
}
int seg_find(int x,int y){
struct segF{
static int segfind(int x,int y,int k,int l,int r){
//cout<<x<<","<<y<<","<<k<<","<<l<<","<<r<<endl;
if(r<x||l>y) return INT_MAX;
if(l>=x&&r<=y) return seqv[k];
else{
int segl=segfind(x,y,k*2+1,l,(l+r)/2);
int segr=segfind(x,y,k*2+2,(l+r)/2+1,r);
return min(segl,segr);
}
}
};
return segF::segfind(x,y,0,0,seqv_n);
}
int seg_rfind(int x,int y,int a){
struct segF{
static int segfind(int x,int y,int a,int k,int l,int r){
//cout<<x<<","<<y<<","<<k<<","<<l<<","<<r<<endl;
if(seqv[k]>a||r<x||l>y) return INT_MAX;
if(k>=seqv_n) return k-seqv_n;
int sgr=segfind(x,y,a,2*k+2,(l+r)/2+1,r);
if (sgr!=INT_MAX) {
return sgr;
} else {
return segfind(x,y,a,2*k+1,l,(l+r)/2);
}
}
};
return segF::segfind(x,y,a,0,0,seqv_n);
}
int seg_rfind2(int x,int y,int a){
struct segF{
static int segfind(int x,int y,int a,int k,int l,int r){
//cout<<x<<","<<y<<","<<k<<","<<l<<","<<r<<endl;
if(seqv2[k]<a||r<x||l>y) return INT_MIN;
if(k>=seqv_n) return k-seqv_n;
int sgr=segfind(x,y,a,2*k+2,(l+r)/2+1,r);
if (sgr!=INT_MIN) {
return sgr;
} else {
return segfind(x,y,a,2*k+1,l,(l+r)/2);
}
}
};
return segF::segfind(x,y,a,0,0,seqv_n);
}
int main(){
int n;
cin>>n;
seg_init(n,0);
int a[n];
for(int i=0;i<n;i++){
cin>>a[i];
seg_update(i,a[i]);
seg_update2(i,a[i]);
}
vector<int> v[n];
int nmx[n],nmi[n];
for(int i=n-1;i>=0;i--){
int nn=seg_find(i,i);
int mx=seg_rfind2(0,i-1,nn+1);
int mi=seg_rfind(0,i-1,nn-1);
nmx[i]=mx;
nmi[i]=mi;
//cout<<i<<","<<mx<<","<<mi<<endl;
}
for(int i=1;i<n;i++){
int f=i-1;
v[f].push_back(i);
if(a[i]<a[i-1]){
while(1){
if(nmi[f]==INT_MAX) break;
f=nmi[f];
v[f].push_back(i);
if(a[i]>=a[f]) break;
}
}
else if(a[i]>a[i-1]){
while(1){
if(nmx[f]==INT_MIN) break;
f=nmx[f];
v[f].push_back(i);
if(a[i]<=a[f]) break;
}
}
}
int dp[n];
for(int i=0;i<n;i++) dp[i]=-1;
queue<int> q;
q.push(0);
dp[0]=0;
while(!q.empty()){
int qn=q.front();
q.pop();
for(int i=0;i<v[qn].size();i++){
int tn=v[qn][i];
if(dp[tn]==-1||dp[tn]>dp[qn]+1){
dp[tn]=dp[qn]+1;
q.push(tn);
}
}
}
cout<<dp[n-1]<<endl;
}※セグ木の操作関数が多いですが、min用のセグ木とmax用のセグ木で分けているためです。
こういうの、抽象化でセグ木を作ればきれいに書けるっぽいのですが、ぬるからのセグ木は未対応です。
・終わりに
コンテスト後の解きなおしですが、
始めて整備したセグ木で、参加したコンテストの問題が解けました。
ちょっと、自分が分かりやすいように参考にしたコードから微妙に変えているので、ちゃんと動いているっぽくて良かったです。
この記事が気に入ったらサポートをしてみませんか？