AtCoder Beginner Contest 347(C問題・D問題)【AtCoder】

C – Ideal Holidays
D – Popcount and XOR

C – Ideal Holidays

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

D₁ ～ D_N の各曜日が収まる最小日数を求め、それが 1 ～ A の範囲に収まっていればよい。
とはいえ、各 D_i とその他の D の距離を求めるやり方では、O(n²) かかるので、間に合わない。
次のやり方により、1回の探索 O(n) で解ける。

D₁ , D₂ , D₃ の曜日の範囲が最小となるパターンを見つける。
各曜日は D_i から一週間の日数(A + B)を割った余りで求められる。
例えば一週間が7日で、D₁ ～ D₃ 曜日1, 曜日3, 曜日7のパターンだった場合、曜日7 ～曜日3の4日分が全ての曜日が収まる最小範囲である。
これを求めるためには、-6 ~ 13 の範囲内で各曜日全てに対して、最小パターンを見つける必要がある。
-6とは 0 – (1週間の日数7 – 1)、13とは 1週間の日数7 + (1週間の日数7 – 1)である。

D₁ (曜日1) ・・・ -6 (1 – 7) / 1 / 8 (1 + 8)
D₂ (曜日3) ・・・ -4 (3 – 7) / 3 / 11 (3 + 8)
D₃ (曜日7) ・・・ 0 (7 – 7) / 7

この中で、全曜日が最小日数に収まる範囲は、0 ～ 3 となる。
D₄ 以降も同様のやり方で、最小日数範囲を更新していけばよい。
最終的にこの範囲が 1 ～ A に収まっていれば”Yes”、収まっていなければ”No”である。

#include <bits/stdc++.h>
using namespace std;

int main(){
  int N, A, B, min = 0, max = 0;
  
  cin >> N >> A >> B;
  
  for (int i = 0; i < N; i++) {
    int D;
    cin >> D;
    D = D % (A + B);
    
    if (i==0) {
      min = D;
      max = D;
      continue;
    }
    
    if (D == 0) D = A + B;
    
    if (min <= D && D <= max) continue;
    int minusD = D - (A + B);
    if (min <= minusD && minusD <= max) continue;
    int plusD = D + (A + B);
    if (min <= plusD && plusD <= max) continue;
    
    int diff1 = 0x7fffffff, diff2 = 0x7fffffff, diff3 = 0x7fffffff, diff4 = 0x7fffffff;
    if (max <= D) diff1 = D - min;
    else diff2 = max - D;
    if (minusD <= min) diff3 = max - minusD;
    if (plusD >= max) diff4 = plusD - min;
    
    if (diff1 <= diff2 && diff1 <= diff3 && diff1 <= diff4) max = D;
    else if (diff2 <= diff1 && diff2 <= diff3 && diff2 <= diff4) min = D;
    else if (diff3 <= diff1 && diff3 <= diff2 && diff3 <= diff4) min = minusD;
    else max = plusD;
  }
  
  if (A < max -min + 1) cout << "No" << endl;
  else cout << "Yes" << endl;
  
  return 0;
}

D – Popcount and XOR

D - Popcount and XOR

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

O(n) で求めることができる。
以下の操作を行えばよい。

C の2進数表記において、1の個数を調べる。
⇒ この個数は、排他的論理和が1となる個数、つまり X と Y のあるビットについて、片方が 0、片方が 1 となっている個数である。
(a + b – (1で求めた個数)) / 2 を求める。割り切れなければ存在しない。
⇒ この個数は、排他的論理和が0となる個数、つまり X と Y のあるビットについて、両方とも 1 となっている個数である。
X, Y それぞれについて、a – (2で求めた個数)、b – (2で求めた個数) を求める。
⇒ この個数は X, Y それぞれについて、C と同じいずれかのビットに 1 をつけなければならない個数である。
これまで求めた個数に従って、X と Y のビットに1を付けていけばよい。

#include <bits/stdc++.h>
using namespace std;

int main(){
  int a, b;
  unsigned long long C;
  
  cin >> a >> b >> C;
  
  long long mask = 0x0000000000000001;
  
  int num = 0;
  
  for(int i=0; i < 60; i++) {
    num += (C & mask) != 0;
    mask <<= 1;
  }
  
  int result = 0;
  int ab = a + b;
  
  if (ab < num) result = -1;
  else if ((ab - num) %2 != 0) result = -1;
  
  if (result < 0) {
    cout << result << endl;
    return 0;
  }
  
  int diff = (ab - num) / 2;
  
  int a_num = a - diff;
  int b_num = b - diff;
  
  mask = 0x0000000000000001;
  
  unsigned long long X = 0, Y = 0;
  result = 0;
  for (int i = 0; i < 60; i++) {
        if ((C & mask) != 0) {
          if (a_num > 0) {
            X += mask;
            a_num--;
          } else if (b_num > 0) {
            Y += mask;
            b_num--;
          } else {
            result = -1;
            break;
          }
        } else if (diff > 0) {
          X += mask;
          Y += mask;
          diff--;
        }
        mask <<= 1;
  }
  
  if (diff > 0 || a_num > 0 || b_num > 0) result = -1;
  
  if (result < 0) cout << result << endl;
  else cout << X << " " << Y << endl;
  
  return 0;
}