beet's soil

競プロのことなど

yukicoder contest 157

出るつもりなかったんですけど気づいてたら出てた(は?)

【No.485 方程式のお勉強】

はい。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int a,b;
  cin>>a>>b;
  if(abs(b)%abs(a)) cout<<"NO"<<endl;
  else cout<<b/a<<endl;
  return 0;
}
【No.486 3 Straight Win(3連勝)】

やる。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  string s;
  cin>>s;
  for(int i=0;i<(int)s.size()-2;i++){
    if(s[i]==s[i+1]&&s[i]==s[i+2]){
      if(s[i]=='O') cout<<"East"<<endl;
      else cout<<"West"<<endl;
      return 0;
    }
  }
  cout<<"NA"<<endl;
  return 0;
}
【No.487 2017 Calculation(2017の計算)】

mod_pow()する。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod_pow(ll x,ll n,ll mod){
  ll res=1;
  while(n>0){
    if(n&1) res=res*x%mod;
    x=x*x%mod;
    n>>=1;
  }
  return res;
}
int main(){
  ll n,m;
  cin>>m;
  n=mod_pow(2017,4034,m);
  cout<<(n+2017)%m<<endl;
  return 0;
}
【No.488 四角関係】

4重ループを書く。
もっと綺麗に書けそうだけどめんどくさかった(ア。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n,m;
  cin>>n>>m;
  int e[n][n];
  memset(e,0,sizeof(e));
  for(int i=0;i<m;i++){
    int a,b;
    cin>>a>>b;
    e[a][b]=e[b][a]=1;
  }
  int ans=0;
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      for(int k=j+1;k<n;k++){
	for(int l=k+1;l<n;l++){
	  int tmp=0,d[4];
	  if(e[i][j]) d[tmp++]=j;
	  if(e[i][k]) d[tmp++]=k;
	  if(e[i][l]) d[tmp++]=l;
	  if(tmp!=2) continue;
	  tmp=0;
	  if(e[j][i]) d[tmp++]=i;
	  if(e[j][k]) d[tmp++]=k;
	  if(e[j][l]) d[tmp++]=l;
	  if(tmp!=2) continue;
	  tmp=0;
	  if(e[k][i]) d[tmp++]=i;
	  if(e[k][j]) d[tmp++]=j;
	  if(e[k][l]) d[tmp++]=l;
	  if(tmp!=2) continue;
	  tmp=0;
	  if(e[l][i]) d[tmp++]=i;
	  if(e[l][j]) d[tmp++]=j;
	  if(e[l][k]) d[tmp++]=k;
	  if(tmp!=2) continue;
	  
	  if(!e[d[0]][d[1]]) ans++;
	}
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}
【No.489 株に挑戦】

RMQする。
復元パートはなんかいい感じにやる。

signed main(){
  int n,d,k;
  cin>>n>>d>>k;
  int ans=0,idx=0,idy=0;
  RMQ rmq(n);
  map<int,vector<int> > m;
  int a[n];
  for(int i=0;i<n;i++){
    cin>>a[i];
    m[a[i]].push_back(i);
    rmq.update(i,a[i]);
  }
  for(int i=0;i<n;i++){
    int p=min(i+d+1,n);
    int x=rmq.query(i,p);
    if(ans<x-a[i]){
      ans=x-a[i];
      idx=i;
    }
  }
  cout<<ans*k<<endl;
  int p=min(idx+d+1,n);
  int x=rmq.query(idx,p);
  vector<int> v=m[x];
  idy=*upper_bound(v.begin(),v.end(),idx);
  if(ans) cout<<idx<<" "<<idy<<endl;
  return 0;
}
【全体】

ooooo 562points 18th
ABCのペナルティで時間勝ってるのに負けたのなんか悔しい。
なんかABCやってるみたいで安心した。