秘密の本棚

気になることをなんでも書きます

AtCoder Beginner Contest 105

AtCoder Beginner Contest 105 - AtCoder

A - AtCoder Crackers

考察

N個のものをK人で分けるときの個数の差の最小値。ちょうど割り切れれば0、割り切れなければ1…?(証明せず)

コード

int main(){
  ll n,k;
  cin >> n >> k;
  if(n%k==0){
    cout << 0 << endl;
  }else{
    cout << 1<< endl;
  }
  return 0;
}

B - Cakes and Donuts

考察

 4a+7b=Nをみたす0以上の整数の組(a,b)が存在するかどうかの判定。Nが大きければ4と7が互いに素であることを利用してうにゃうにゃしそうだが、今回はNが小さいので考えうる a,bの範囲で全探索。

コード

int main(){
  ll n;
  cin >> n;
  bool ans = false;
  REP(i,26){
    REP(j,16){
      if(i*4+j*7==n){
        ans = true;
      }
    }
  }
  if(ans){
    cout << "Yes" << endl;
  }else{
    cout << "No"  << endl;
  }
  return 0;
}

C - Base -2 Number

考察

与えられた整数の -2進数表現を求める。 -2進数表現の桁をどのように求めればよいかを考える。分かれ道は上の桁から決めていくか、下の桁から決めていくかのいずれかだが、少し考えると下の桁からのほうが容易であることがわかる。例えば、一番下の位は2で割り切れるかどうかで決まり、下か2番目の位は一番下の位を差し引いたあと、4で割り切れるかどうかで決まる。これを繰り返していけば、順次桁が求まりそうだ。

コード

int main(){
  ll n;
  cin >> n;
  str s;
  ll pw = 1;
  if(n==0){
    cout << 0 << endl;
    return 0;
  }
  ll power = 2;
  while(n!=0){
    if(n%power==0){
      s += '0';
    }else{
      s += '1';
      n -= (power/2)*((pw%2)?1:-1);
    }
    pw++;
    power *= 2;
    //cout << n << endl;
  }
  reverse(s.begin(),s.end());
  cout << s << endl;
  return 0;
}

疑問

最初にシフトビットを利用したコードを書いたが、TLEになってしまった。なぜこうなったのかが未だに不明(コメントください)。

D - Candy Distribution

考察

サイズ Nの数列 Aに対して、 \sum_{k=l}^rA_k Mの倍数となるような整数の組 (l,r)の個数を求める。数列の要素の和という時点で、累積和を使いそうな予感がする。
 B_i = \sum_{k=1}^i A_kによって数列 Bを定めると、結局 Mで割ったあまりが等しいような2つの要素 B_x, B_yを取ってくれば B_y-B_x = \sum_{k=x+1}^y A_k Mの倍数となる。したがって、 Bの要素を Mで割ったあまりによって分類し、 Mで割って j余る Bの個数を C_jとしたとき、2つの数の選び方を考えて C_j*(C_j-1)/2の和を取ればよい。
ただし、 M 10^9まで大きくなりうるので Cを配列として保持することができない。そこで連想配列を使用してオーダを抑えればよさそう。

コード

const ll max_n = 100000;
ll a[max_n];
ll sum[max_n+1];

int main(){
  ll n,m;
  cin >> n >> m;
  map<ll,ll> count;
  fill(sum,sum+n+1,0);
  count[0]++;
  REP(i,n){
    cin >> a[i];
    sum[i+1] += sum[i]+a[i];
    count[sum[i+1]%m]++;
  }
  ll ans = 0;
  for(pair<ll,ll> cnt :count){
    ans += cnt.second*(cnt.second-1)/2;
  }
  cout << ans << endl;
  return 0;
}

雑感

C問題に結構苦戦させられましたが、なんとか時間内に全完できました。不具合でUnratedになってしまったのが残念(笑)。
あと、以前の記事
nexusuica.hatenablog.jp
に掲載していた、蟻本初級編の部分をほぼ終わらせることができました。その結果だいぶ考え方になれることができたように思います。中級編の方も進めていきたいです。