beet's soil

競プロのことなど

Codeforces Round #394 (Div. 2)

div1に上がるつもりでいたんですよ

【開始直後】

圧倒的codeforces(サーバーがコドフォって問題が見れない

【A. Dasha and Stairs】

絶対値の差が1以下ならYES
ただし閉区間なので0 0はNO
初Hack成功してうぇいwってなった。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int a,b;
  cin>>a>>b;
  if(a==0&&b==0) cout<<"NO"<<endl;
  else cout<<(abs(a-b)<=1?"YES":"NO")<<endl;
  return 0;
}
【B. Dasha and friends】

N^2が余裕で回るので愚直に全部試す。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int n,l;
  cin>>n>>l;
  vector<int> a(n),b(n),c,d;
  for(int i=0;i<n;i++) cin>>a[i];
  for(int i=0;i<n;i++) cin>>b[i];
  bool f=0;
  for(int i=0;i<n-1;i++){
    c.push_back(a[i+1]-a[i]);
    d.push_back(b[i+1]-b[i]);
  }
  c.push_back(l+a[0]-a[n-1]);
  d.push_back(l+b[0]-b[n-1]);
  for(int i=0;i<n;i++){
    bool ff=1;
    for(int j=0;j<n;j++) ff&=c[j]==d[(i+j)%n];    
    f|=ff;
  }
  cout<<(f?"YES":"NO")<<endl;
  return 0;
}
【C. Dasha and Password】

桁DPみたいにやる。
dp[数字あるか][英字あるか][記号あるか][index]でやる。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int dp[2][2][2][100];
int main(){
  int n,m;
  cin>>n>>m;
  string s[n];
  for(int i=0;i<n;i++) cin>>s[i];
  for(int i=0;i<=n;i++)
    for(int a=0;a<2;a++)
      for(int b=0;b<2;b++)
	for(int c=0;c<2;c++)
	  dp[a][b][c][i]=1<<25;
  dp[0][0][0][0]=0;
  for(int i=0;i<n;i++)
    for(int a=0;a<2;a++)
      for(int b=0;b<2;b++)
	for(int c=0;c<2;c++)
	  for(int j=0;j<m;j++){
	    bool d=isdigit(s[i][j]);
	    bool e=isalpha(s[i][j]);
	    bool f=(!d)&&(!e);
	    dp[a|d][b|e][c|f][i+1]=
	      min(dp[a|d][b|e][c|f][i+1],dp[a][b][c][i]+min(j,m-j));
	    
	    //cout<<(a|d)<<" "<<(b|e)<<" "<<(c|f)<<" "<<(i+1)<<":";
	    //cout<<dp[a|d][b|e][c|f][i+1]<<endl;
	  }
  cout<<dp[1][1][1][n]<<endl;
  return 0;
}
【D. Dasha and Very Difficult Problem】

なんかよくわかんないんだけどできた。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
int main(){
  ll n,l,r;
  cin>>n>>l>>r;
  vector<ll> a(n),b(n),p(n);
  vector<P> c(n);
  for(ll i=0;i<n;i++) cin>>a[i];
  for(ll i=0;i<n;i++) cin>>p[i];
  for(ll i=0;i<n;i++){
    c[i].first=p[i];
    c[i].second=i;
  }
  sort(c.rbegin(),c.rend());
  ll m=r;
  for(ll i=0;i<n;i++){
    ll v=c[i].second;
    if(m<l){
      cout<<-1<<endl;
      return 0;
    }
    b[v]=m;
    if(i<n-1){
      ll u=c[i+1].second;
      m=min(r+1,m-a[v]+a[u])-1;
    }
  }
  //for(ll i=0;i<n;i++) cout<<b[i]-a[i]<<" \n"[i==n-1];
  for(ll i=0;i<n;i++) cout<<b[i]<<" \n"[i==n-1];
  return 0;
}
【E. Dasha and Puzzle】

AtCoderで既出。フラクタルを構築しておしまい。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX 50
ll len[MAX];
typedef pair<ll,ll> P;
P pos[MAX];
vector<ll> G[MAX];
ll ax[]={1,-1,0,0};
ll ay[]={0,0,1,-1};
ll an[]={1,0,3,2};
void dfs(ll v,ll u,P p,ll d,ll l){
  if(G[v].size()>4){
    cout<<"NO"<<endl;
    exit(0);
  }
  pos[v]=p;
  int k=0;
  for(int i=0;i<(int)G[v].size();i++){
    if(G[v][i]==u) continue;
    if(k==d) k++;
    P np=p;
    np.first+=ax[k]*len[l];
    np.second+=ay[k]*len[l];
    dfs(G[v][i],v,np,an[k],l-1);
    k++;
  }
}
int main(){
  len[0]=1LL;
  for(ll i=1;i<MAX;i++) len[i]=len[i-1]*2LL;
  ll n;
  cin>>n;
  for(ll i=0;i<n-1;i++){
    ll u,v;
    cin>>u>>v;
    u--;v--;
    G[u].push_back(v);
    G[v].push_back(u);    
  }
  dfs(0,-1,P(0,0),-1,n+1);
  cout<<"YES"<<endl;
  for(ll i=0;i<n;i++) cout<<pos[i].first<<" "<<pos[i].second<<endl;
  return 0;
}
【全体】

ooooo- +1 105th

かなり調子が良くてレート上がるだろうなあと思っていたら、
I'm sorry to announce that the round will be unrated due to technical problems with standings page. Sorry again.
とのことでunrated かなしい。
朝見たときは99thで初2桁だとおもったのになんか落ちてた。謎。
明日またあるので次こそ上がりたい。
まあ初Hackが成功したのでよかった(ぽじてぃぶ。