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

ichirin2501's diary

いっちりーん。

Problem C. Candy Splitting

問題概要
最初に、Seanの所持してる飴を2つに分割し、どちらかをPatrickに分ける
次に、Patrickは各々の飴の値の和を計算します
Patrickは山が等しくならないと泣き始めます?
残念なことに、Patrickは幼く、正しく足し算することができない
彼は二進数の足し算ならほとんど知っています、は?w
しかし、繰り上がりができません。なるほど
例えば、12(1100)+5(101)なら、9(1001) になります
繰り上がりしないだけ、っぽい。1+1のところはちゃんと0になる
把握した。
まず、与えられた整数を二つに分割する
2つの分割して、グループごとに値の和を求める。
ただし、ここでの和は繰り上がりを考慮しない値である。
このとき、どうやっても等しくならない場合は NO
等しくなる場合があるなら、等しくなるケースのうち、Seanが所持できる最大の値の和(普通の和)を返す

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <climits>
using namespace std;

#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define DEB 0
#define all(x) x.begin(), x.end()

int main(){
  int T;
  scanf("%d",&T);

  rep(x,T){
    int n,c,ok=0;
    long long sum=0;
    int mi = INT_MAX;
    
    scanf("%d",&n);
    rep(i,n){
      scanf("%d",&c);
      sum += (long long)c;
      ok ^= c;
      mi = min(mi, c);
    }
    if( ok!=0 ){
      printf("Case #%d: NO\n",x+1);
    }else{
      printf("Case #%d: %lld\n",x+1,sum-(long long)mi);
    }
  }
  return 0;
}


・試行錯誤のめも
ビット処理でごにょごにょすればいいかな
テストケースが100個
飴が持つ値が10^6まで、飴の個数がLargeだと1000個、つまり10^6 * 10^3 = 10^9
和は32bitで収まるね。1000個の要素を任意の数で2分割すると…
あれ、連続してる飴を二つに分ける、とは書かれてない、pileは山…だし、任意の飴でいいんだよね
ということは、Σ_{i=1,999}1000_C_iの組み合わせがあるわけだが…
とても無理だ
ほんとに任意の要素で二分割するのか?
各ビットごとに考えると、二つに分けたときに
1の個数の偶奇が一致してなければ絶対に等しくならない
下位ビットが束になろうと上位ビットには値で勝ることはないので、上位ビットだけ考慮すればいい?
いやそんなことない、最後は和だから、一部の上位ビットだけでは判定できない
なんかXORくせー
XOR取って0になれば可能、素の場合は最小値を引いた値になるよ!とかそんなことないかな…
集合のイメージで考えると、うまくいってるぞ?
とりあえず、smallで全探索で書いて、XOR手法と等しくなるかどうかを確かめよう
さっそく実装、確かめるまでもなくsmallは何度でも挑戦できるのでいきなりXOR手法で試す
small通る、じゃあlargeも問題ねえや、たぶん。投げる。おわり