読者です 読者をやめる 読者になる 読者になる

beet's soil

競プロのことなど

Codeforces Round #392 (Div. 2)

ぞぞい

【A. Holiday Of Equality】

最大値探してそれとの差の和を求める。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int n;
  cin>>n;
  int a[n],m=0;
  for(int i=0;i<n;i++){
    cin>>a[i];
    m=max(m,a[i]);
  }
  int ans=0;
  for(int i=0;i<n;i++) ans+=m-a[i];
  cout<<ans<<endl;
  return 0;
}
【B. Blown Garland】

validな入力しか与えられないので位置を特定して周期4で数える

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  string s;
  cin>>s;
  int n=s.length();
  int p[4],a[4]={};
  for(int i=0;i<n;i++){
    if(s[i]=='R') p[0]=i%4;
    if(s[i]=='B') p[1]=i%4;
    if(s[i]=='Y') p[2]=i%4;
    if(s[i]=='G') p[3]=i%4;
  }
  for(int i=0;i<n;i++){
    if(s[i]=='!') a[i%4]++;
  }
  cout<<a[p[0]]<<" "<<a[p[1]]<<" "<<a[p[2]]<<" "<<a[p[3]]<<endl;
  return 0;
}
【C. Unfair Poll】

n=1,2のときは特別にやる。
それ以外は2m*(n-1)周期になるのでそこを削って余りを清算すればいい。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n,m,k,x,y;
  ll a1=0,a2=0,a3=0;
  cin>>n>>m>>k>>x>>y;
  if(n==1){
    a1+=k/m;
    a2+=k/m;
    a3+=k/m;
    k%=m;
    if(k) a1++;
    if(y<=k) a3++;
  }else if(n==2){
    a1+=k/(m*2);
    a2+=k/(m*2);
    a3+=k/(m*2);
    k%=m*2;
    if(k) a1++;
    if((x-1)*m+y<=k) a3++;
  }else{
    a1+=k/(2*m*(n-1))*2;
    a2+=k/(2*m*(n-1));
    if(x==1||x==n) a3+=k/(2*m*(n-1));
    else a3+=k/(2*m*(n-1))*2;
    k%=(2*m*(n-1));
    if(m<=k) a1++;
    if(m*n<k) a1++;
    if(!a1) a1++;
    if(m*n<=k) a2++;
    if(x==1){
      if(y<=k) a3++;
    }else if(x==n){
      if(m*(n-1)+y<=k) a3++;
    }else{
      if(m*(x-1)+y<=k) a3++;
      if(((n-1)+(n-x))*m+y<=k) a3++;
    }
  }
  cout<<a1<<" "<<a2<<" "<<a3<<endl;
  return 0;
}
【D. Ability To Convert】

C++だとオーバーフローする(実装が悪そう)。
多倍長書けるようにruby勉強してよかった、、!!
leading 0に気をつけてDP

n=gets.to_i
s=gets.to_s
p=s.chomp.split("")
x=1;
10000.times do
  x*=10;
end
dp = Array.new(100,x)
dp[0]=0;
y=p.size.to_i
for i in 0..y-1 do
  tmp=0
  j=i
  while j<y&&tmp*10+p[j].to_i<n do
    tmp=tmp*10+p[j].to_i
    dp[j+1]=[dp[j+1],dp[i]*n+tmp].min
    if p[i].to_i == 0
      break
    end
    j+=1
  end
end
puts dp[y]
【全体】

ooxo-- 2554points 458th
1863 -> 1869 (+6) highest

Cはifを一つ足したら通ってア。
こういうミスがあるからdiv1に上がれないんだろうなあ。
Dが通せたのは努力が役に立った感があってよかった。

【追記】

こんなイメージです。
f:id:beet_aizu:20170120145036g:plain
f:id:beet_aizu:20170120145040g:plain
f:id:beet_aizu:20170120145045g:plain