Codeforces Round #229 (Div 2) - 不定期プログラミング覚え書き

10分延長してくれたお陰で色々バグが取れて４問解けた回。当時Div 1だったのでレート変動無くて助かったか？
Eがなかなか勉強になりそうなので、最近のCF参加記そっちのけでここのログ書きます。

Problem A Inna and Alarm Clock

格子状に目覚まし時計が配置されてる。Innaは縦に並んだor横に並んだ目覚まし時計は一変にスイッチオフにできる
最小なんステップで目覚まし時計はスイッチオフにできるか答えよ。

考える事

やるだけ

コード

int main(){
  int n;
  cin >> n;
  int x[n];
  int y[n];
  for( int i = 0 ; i < n ; i++ ){
    cin >> x[i] >> y[i];
  }
  sort( x, x+n );
  sort( y, y+n );
  int sizex = unique( x, x+n )-x;
  int sizey = unique( y, y+n )-y;
 // cout << sizex << " " <<sizey << endl;
  cout << min( sizex, sizey ) << endl;
  return 0;
}

Problem B Inna, Dima and Song

２人の演奏者が居て、i番目の音はどちらも最大a[i]の音量を出すことができる。
２人の音量がピッタリb[i]だった時、聴講者は2つの音量の積だけの幸福度を得る。そうでなければ幸福度が１下がる。
得られる最大の幸福度を答えよ。なお、音量は整数のみ認めるとする。

考えたこと

b[i]/2とb[i]-b[i]/2の音量を可能な限り出し続ければOK
ということでさっくり書いたが、b[i]=1の時を弾かないと幸福度0を得る、と算出されることに気が付かず、終了ギリギリまでドはまりした。

コード

int main(){
  int n;
  cin >> n;
  long long a[n];
  long long b[n];
  long long ans =0;
  for( int i = 0 ; i < n ; i++ ) cin >> a[i];
  for( int i = 0 ; i < n ; i++ ) cin >> b[i];
  for( int i = 0 ; i < n;  i++ ){
    if( b[i]==1 || a[i]+a[i] < b[i] ) ans--;
    else{
      long long x = b[i]/2;
      long long y = b[i]-x;
      ans += x*y;
    }
  }
  cout << ans << endl;
  return 0;
}

Problem C Inna and Candy Boxes

キャンディが一直線上に並べられている。また、入力としてk,wを与える。
その後、l,rをw回与えるので、それぞれに対し、
[l,r]の区間のうちl+k-1,l+2k-1,...,rにしかキャンディが存在しないようにするための操作（飴を取り払うor飴を入れる）数を答えよ

考えたこと

基本的にk距離離れたところの飴の有無しか気にならないので、
sum[N]にN,N-k,N-2k,...のうちに含まれるキャンディ数を保管しておくことにした。
そうすると、l+k-1,l+2k-1,...,rに含まれるキャンディの数はsum[r]-sum[l-1]で、
l+k-1-s,l+2k-1-s,...r-sに含まれるキャンディの数はsum[r-s]-sum[l-1-s]で(s=1〜k-1)ある。
後者の値はそのまま操作数に直結し、前者の値は本来あるべき1の数に足りない分を補完すればよい。
…まで考えたけど、l=rの時の処理方法があんまりよくわからなくて何度かミスった。

コード

int main(){
  int n,k,w;
  cin >> n >> k >> w;
  string candies;
  cin >> candies;
  int sum[n+1];
  memset( sum, 0 , sizeof(sum) );
  for( int i = 0 ; i < n ; i++ ){
    if( i >= k ){
      sum[i+1] += sum[i+1-k];
    }
    sum[i+1] += (candies[i]-'0');
  }
#ifdef DEBUG
  for( int i = 0 ; i < n+1 ; i++ ){
    cout << sum[i] << ", " ;
  }
  cout << endl;
#endif
  for( int i = 0 ; i < w; i++ ){
    int l,r;
    cin >> l >> r;
    if( l == r ){ 
      cout << 1-(candies[r-1]-'0')<< endl;
      continue;
    }
    int n_one = (r-l+1)/k;
    int cur_one = (sum[r]-sum[l-1]);
#ifdef DEBUG
    cout << "need:" << n_one <<" cur:" << cur_one << endl;
#endif
    int task_to_add = n_one-cur_one;
    int task_to_erase = 0;
    for( int j = 1 ; j < k ; j++ ){
      int n_extra_one = sum[r-j];
      if( l-1-j >= 0 ) n_extra_one -= sum[l-1-j];
      task_to_erase += n_extra_one;
#ifdef DEBUG
      cout << "offset:" << j << "..." << n_extra_one << endl;
#endif
    }
    cout << task_to_erase + task_to_add  << endl;
  }
  return 0;
}

Problem D Inna and Sweet Matrix

n*mの格子状にkこのキャンディを置くこととする。
キャンディを置く時は毎回左上点(1,1)から1マスずつ縦or横に移動して置くこととし、すでにキャンディが置かれた場所は通ることができない。
この時、移動距離がペナルティとして加算される。
最小のペナルティ値とその時のキャンディの運び方を答えよ。

考えたこと

マンハッタン距離が大きい順にk子並べれば良い、以上。
何故か盤面を常に縦長になるように調整したら経路を出すところでミスったり、経路出力でそもそもケアレスミスをしてたりで2WA食らった。

コード

void printpath( pair<int,int> p ,bool swaped ){
  int x = p.first;
  int y = p.second;
  if(swaped) swap(x,y);
  cout << "(1,1)";
  for( int i = 2 ; i <= x ; i++ ){
    cout <<" ("<<i<<",1)";
  }
  for( int i = 2; i <= y ; i++ ){
    cout <<" ("<<x<<","<<i<<")";
  }
  cout << endl;
}

int main(){
  int n,m,k;
  cin >> n >> m >> k;
  bool swaped= false;
  if( n < m ){
    swaped= true;
    swap(n,m);
  }
  int cnt[101];
  memset( cnt, 0, sizeof(cnt) );
  int total = 0;
  int point = 0;
  vector<pair<int,int> > list[101];
  for( int i = 1 ; i <= n ; i++ ){
    for( int j = 1 ; j<=m ; j++ ){
      list[i+j-1].push_back( make_pair(i,j));
    }
  }
  for( int i = 1 ; i <= n+m-1 ; i++ ){
    int curnum = list[i].size();
    if( total+curnum >= k ){
      cnt[i]=k-total;
      point += cnt[i]*i;
      break;
    }
    cnt[i] = curnum;
    total += curnum;
    point += cnt[i]*i;
  }
  cout << point<<endl;
  for( int i = 100; i >= 0 ; i-- ){
    for( int j = 0 ; j < cnt[i]; j++ ){
      printpath( list[i][j],swaped );
    }
  }
  return 0;
}

Problem E Inna and Large Sweet Matrix

n*mの盤面に対し、クエリをw個実行せよ
クエリは以下のフォーマットで与えられる。

1行に5個の整数 x,y,x2,y2,vが与えられた時は、x<=i<=x2, y<=j<=y2が成立するすべてのセルにキャンディをv個置く
1行に4個の整数x,y,x2,y2が与えられた時は、x<=i<=x2,y<=j<=y2が成立する全セル(i,j)のキャンディ総和と、(i

考えたこと

あーこれなんとかツリーを使うやつじゃなかったっけ？
そのくらいの漠然としたイメージはあるけどいざ問題として出されるととけんな。。。

復習

kmjpさん(http://kmjp.hatenablog.jp/entry/2014/02/12/1000)の記事を読んでそうだBITだーとは思ったけどそもそもBITを使うための考察等色々足らなかったなあと反省。
まず、2番めのクエリをこなすには、x<=i<=x2のキャンディ位数 + y<=j<=y2のキャンディ数 - 全キャンディ数をすれば良い。
そのため、

x行目からx2行目までのキャンディ数の計算
x行目からx2行目間の各行にキャンディc個追加

とかを高速に計算できると良い。クエリ数wが10^5くらいあるので、10^3くらいで計算できると良い。
普通のBITだと前者は高速に計算できるが、後者ができなくて困る。
しかし、1行目からx行目までのキャンディ数を b1*x+b0と求めるようにすると、そこにBITが使える。

b1(x2)*x2+b0(x2)-b1(x1-1)*(x1-1)+b0(x1-1)を計算するだけ。
b1(x1,c) b0(x1,-(x1-1)*c), b1(x2+1,-c), b0(x2+1,y2*c)を計算

蟻本をガン見しながら現時点で理解した気になってるけど言葉で説明すると難しい…何度か蟻本を見て復習したい所。

コード

void bit_add( long long* bit, int pos, long long val,int size ){
  // pos番目にvalを足した時のbitの総和の値を更新する
  while( pos < size ){
    *(bit+pos) += val;
    pos += pos-(pos &(pos-1));
  }
}

long long bit_get( long long* bit, int pos ){
  long long ret = 0;
  while( pos != 0 ){
    ret += *(bit+pos);
    pos = pos & (pos-1);
  }
  return ret;
}

int main(){
  int n,m,w;
  cin >> n >> m >> w;
  long long n_bit_1[n+1];
  long long n_bit_0[n+1];
  long long m_bit_1[m+1];
  long long m_bit_0[m+1];
  memset( n_bit_1,0,sizeof(n_bit_1));
  memset( n_bit_0,0,sizeof(n_bit_0));
  memset( m_bit_1,0,sizeof(m_bit_1));
  memset( m_bit_0,0,sizeof(m_bit_0));
  long long sum = 0;
  for( int i = 0 ; i < w ; i++ ){
    int type;
    cin >> type;
    if( type == 0 ){
      int x1,y1,x2,y2,v;
      cin >> x1 >> y1 >> x2 >> y2 >> v;
      // add v*(y2-y1+1) to all x such that x1 <= x <= x2
      long long addval = v*(y2-y1+1LL);
      bit_add( n_bit_1, x1, addval,n+1);
      bit_add( n_bit_0, x1, -addval*(x1-1),n+1 );
      bit_add( n_bit_1, x2+1, -addval,n+1);
      bit_add( n_bit_0, x2+1, addval*x2,n+1 );
      
      // add v*(x2-x1+1) to all y such that y1 <= y <= y2
      addval = v*(x2-x1+1LL);
      bit_add( m_bit_1, y1, addval,m+1 );
      bit_add( m_bit_0, y1, -addval*(y1-1),m+1 );
      bit_add( m_bit_1, y2+1, -addval,m+1);
      bit_add( m_bit_0, y2+1, addval*y2,m+1 );

      sum += v*(x2-x1+1LL)*(y2-y1+1LL);
    }
    else{
      int x1,y1,x2,y2;
      cin >> x1 >> y1 >> x2 >> y2;
      // x1 to x2
      long long xsum = x2*bit_get(n_bit_1,x2)+bit_get(n_bit_0,x2);
      //cout << xsum <<", ";
      xsum -= (x1-1)*bit_get(n_bit_1,x1-1)+bit_get(n_bit_0,x1-1);
      //cout << (x1-1)*bit_get(n_bit_1,x1-1)+bit_get(n_bit_0,x1-1)<<endl;


      // y1 to y2
      long long ysum = y2*bit_get(m_bit_1,y2)+bit_get(m_bit_0,y2);
      //cout << ysum <<", ";
      ysum -= (y1-1)*bit_get(m_bit_1,y1-1)+bit_get(m_bit_0,y1-1);
      //cout <<  (y1-1)*bit_get(m_bit_1,y1-1)+bit_get(m_bit_0,y1-1)<<endl;
    
      //cout << xsum << "+"<< ysum <<"-"<< sum << endl;
      cout << xsum + ysum - sum<<endl;
    }
  }
  return 0;
}