はい。
Educational Codeforces Round 18
A. New Bus Route
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define sc1(a) scanf("%d",&a)
int main(){
int n,m,ans=2e9+7,cnt=0;
sc1(n);
vector <int> a(n);
rep(i,n) sc1(a[i]);
sort(a.begin(),a.end());
rep(i,n-1) {
int x=abs(a[i+1]-a[i]);
if (ans==x) cnt++;
else if (ans>x) {ans=x; cnt=1;};
}
printf("%d %d\n",ans,cnt);
return 0;
}
移動距離の短いバスを調べるのでソートしてよしなに。
B. Counting-out Rhyme
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define sc1(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d %d",&a,&b)
bool w[117];
int ans[117];
int main(){
int n,k,p=0,mod;
sc2(n,k);
mod=n;
vector <int> a(k);
rep(i,k) sc1(a[i]);
rep(i,k) {
int l=a[i]%mod;
for(;;) {
if(l==0) {
ans[i]=p+1;
w[p]=1;
mod--;
for(;;){
if (w[p]==0) break;
p=(p+1)%n;
}
break;
}
p=(p+1)%n;
if (w[p]==0) l--;
}
}
rep(i,k-1) printf("%d ",ans[i]);
printf("%d\n",ans[k-1]);
return 0;
}
時計回りするのはmodを取って回らないとTLEします、多分。消える、消えた人、次は隣がリーダーを丁寧に書けばなんとかなります、多分。
C. Divide by Three
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define sc1(a) scanf("%d",&a)
int cl[5],cr[5];
bool sl[100005];
int main(){
int total=0;
char s[100005];
scanf("%s",s);
long t=strlen(s),kugiri=t-1l;
bool sentou=0;
for (long i=0;i<t;i++){
int x=s[i]-'0';
total=(total+x)%3;
if (x==0 && kugiri==t-1l) kugiri=i;
if (x==0) sentou=1;
if (sentou) cr[x%3]++;
else cl[x%3]++;
}
if (total==0) {
true;
} else if (total==1 && cl[1]==1 && cl[0]+cl[2]+cr[0]+cr[1]+cr[2]==0) {
printf("-1\n"); return 0;
} else if (total==1 && cl[2]==2 && cl[0]+cl[1]+cr[0]+cr[1]+cr[2]==0) {
printf("-1\n"); return 0;
} else if (total==2 && cl[2]==1 && cl[0]+cl[1]+cr[0]+cr[1]+cr[2]==0) {
printf("-1\n"); return 0;
} else if (total==2 && cl[1]==2 && cl[0]+cl[2]+cr[0]+cr[1]+cr[2]==0) {
printf("-1\n"); return 0;
} else if ((total==1 && (s[0]-'0')%3==1 && s[1]-'0'==0 && s[2]-'0'==0 && cl[2]+cr[2]>1)){
int chk0=0;
for (long i=t-1;i>=0;i--) {
if ((s[i]-'0')%3==2 && chk0==0) {sl[i]=1; chk0++;}
else if ((s[i]-'0')%3==2 && chk0==1) {sl[i]=1; break;}
}
} else if (total==1 && cr[1]+cl[1]>0){
for (long i=t-1;i>=0;i--) if ((s[i]-'0')%3==1) {sl[i]=1; break;}
} else if (total==1 && cr[1]+cl[1]==0 && cl[2]+cr[2]>1){
int chk1=0;
for (long i=t-1;i>=0;i--) {
if ((s[i]-'0')%3==2 && chk1==0) {sl[i]=1; chk1++;}
else if ((s[i]-'0')%3==2 && chk1==1) {sl[i]=1; break;}
}
} else if (total==2 && cr[2]>0){
for (long i=t-1;i>=0;i--) if ((s[i]-'0')%3==2) {sl[i]=1; break;}
} else if (total==2 && cr[2]+cl[2]==0 && cr[1]+cl[1]>1){
int chk1=0;
for (long i=t-1;i>=0;i--) {
if ((s[i]-'0')%3==1 && chk1==0) {sl[i]=1; chk1++;}
else if ((s[i]-'0')%3==1 && chk1==1) {sl[i]=1; break;}
}
} else if ((total==2 && cr[2]+cl[2]>0 && cr[1]+cl[1]<2)||(total==2 && cr[2]+cl[2]>1)){
for (long i=t-1;i>=0;i--) if ((s[i]-'0')%3==2) {sl[i]=1; break;}
} else if ((total==2 && (s[0]-'0')%3==2 && s[1]-'0'==0 && cr[1]>1)){
int chk2=0;
for (long i=t-1;i>=0;i--) {
if ((s[i]-'0')%3==1 && chk2==0) {sl[i]=1; chk2++;}
else if ((s[i]-'0')%3==1 && chk2==1) {sl[i]=1; break;}
}
} else if (total==2 && cr[2]+cl[2]>0){
for (long i=t-1;i>=0;i--) if ((s[i]-'0')%3==2) {sl[i]=1; break;}
}
for (long i=0;i<t-1;i++) {
int xxx=s[i]-'0';
if (xxx>0 && sl[i]==0) break;
else sl[i]=1;
}
for (long i=t-1;i>=0;i--) {
int xxx=s[i]-'0';
if (xxx>0 && sl[i]==0) break;
if (xxx==0 && sl[i]==1) {sl[i]=0; break;}
}
bool taisaku=0;
for(long i=0;i<t;i++){
if (sl[i]==0) {
if (taisaku==1 || s[i]-'0'>0) {
taisaku=1;
printf("%c",s[i]);
}else if (s[i]-'0'==0 && taisaku==0) {
printf("%c",s[i]);
break;
}
}
}
puts("");
return 0;
}
各桁の総和が3の倍数で先頭に余分な0が付かない数を最小手で完成させる。場合分けがとても大変でした。
先頭の数の剰余が1,2で後ろに0が連続しているときは先頭を取ってしまうと巻き込み?で0をたくさん消すことになるのでダメな場合あり。総和の剰余1をどこかの桁の剰余2を2つ消して解決する場合ありとかが要注意でしょうか。ひたすら場合分けです。
おそらくはこの提出コードよりももっとシンプルに分けられると思いますけどもまたそのうちに。
D. Paths in a Complete Binary Tree
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define sc1(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d %d",&a,&b)
#define sl1(a) scanf("%lld",&a)
#define sl2(a,b) scanf("%lld %lld",&a,&b)
long long w[65][3],mav=576460752303423488;
int main(){
long long a,b,n,q,tf1=0,tf2;
w[0][0]=1;
w[0][1]=mav;
w[59][0]=mav+1;
rep(i,58) {
w[i+1][0]=w[i][0]*2;
w[i+1][1]=w[i][1]-w[i][0];
}
sl2(n,q);
for (long long i=0;i<61;i++){
tf1=tf1*2+1;
if (tf1==n) { tf2=i; break; }
}
for (long long i=0ll;i<q;i++) {
char s[100005];
sl1(a);
scanf("%s",s);
long t=strlen(s);
if (a%2) {
b=0ll;
} else {
for(int j=58;j>0;j--){
if (a==w[j][0]) {
b=j;break;
} else if(a%w[j+1][0]==w[j][0]){
b=j;break;
}
}
}
for (long j=0;j<t;j++){
if ( (b==tf2 && s[j]=='U') || (a%2 && (s[j]=='L' || s[j]=='R')) ) {
} else if (s[j]=='U' && a%(w[b][0]*4ll)==w[b][0]%(w[b][0]*4ll)) {
a+=w[b][0];b++;
} else if (s[j]=='U') {
a-=w[b][0];b++;
} else if (s[j]=='L') {
a-=w[b-1][0];b--;
} else if (s[j]=='R') {
a+=w[b-1][0];b--;
}
}
cout<< a << endl;
}
return 0;
}
木の構造の法則?を使って頑張りました。一番左の番号の増え方、同じ深さでの隣?といくつ間隔で並ぶかなど。