ARC074 D. 3N Numbers

問題

長さが3*Nの数列vが与えられる。この数列からちょうどN個の要素を取り除き、「前からN個の配列a」と「後ろからN個の配列b」を考える。
「aの総和-bの総和」の最大値を求めよ。

制約

1 <= N <= 10^5
1 <= 要素の値 <= 10^9

解説

数列vにおいて適当に1か所場所を決めると、そこより前からの要素が配列a、それ以降の要素が配列bと割り当てて考えることができる。
最大値がほしいので、配列aの方は大きい値からN個、配列bの方は小さい値からN個を取ればよい。

愚直に計算してしまうとO(N^2)でTLEしてしまうので、高速に計算できないかを考える。

欲しいのは「集合Sに要素xを追加したとき値の大きいor小さい上位N個の和」が高速に求められるようなもの。
上位N個を保持するのに使えるデータ構造はheap(priority_queue)で、これを使って、

• 和と上位N個の要素を保持しておく
• 要素xを追加したら和とheapに入れ、heapから1つ要素を取り出し、和から引いて捨てる

のようにする。
値の追加はO(logN)、上位N個の和の取得はO(1)で求められ、十分に速い。

配列bの方は、小さい方からN個＆後ろから前に向かって考えると配列aと同様に高速に求められる。
別途配列などに配列aと配列bの上位N件の和の値を入れておくなどして、最後に線形に「位置iより前の大きい上位N個-位置i以降の小さい上位N個」の最大値を求めればO(NlogN)で答えが求まる。

反省

最初、何も考えずに、位置に対して最大値は"上に凸"になるのでは？と思って確かめずに投げてWAやTLEを出しまくってしまった。
ランダムに生成させてみると、

3
10 5 2 4 2 18 10 10 7

のとき、最大値は各位置で「x,x,4,0,-8,6,x,x,x」のように簡単にそうならないケースが見つかる。

ちゃんと確かめてからコードを書き始めること。

ポリオミノの列挙

ポリオミノは、複数の正方形を辺でつなげた多角形のこと。(ドミノやテトリスででてくるブロック)
グリッド上の接するn個のグループの形としてもみなせるので、簡単に列挙できると便利かもしれない。

Redelmeierのアルゴリズム

向きを考慮したNオミノ(fixed n-ominoes)を生成するアルゴリズム。

図のようなy>=0かつ、y==0のときx>=0だけのマスを考え、(0,0)のマスに1番の番号を割り当てる。
ここではN=4を生成することを考える。

番号のついている空のマスから1つ選び(最初は(0,0)を選ぶことになる)、正方形を設置する。
設置したタイミングで、下、左、右、上の順にもし空いているマスがあったら番号をインクリメントしながら割り振る。
(下も考慮しないと、N=5のときのn字型が生成されない)

あとは再帰的に繰り返す。ただし、設置した番号より小さい番号は選ばない。(図の真ん中の状態でいうと、5番に設置したので、以降3番と4番は設置場所に選ばない)
設置したマスの個数が目的のN個になったら終了する。

コード

雑だけど、生成するコード。

#include <bits/stdc++.h>

//ポリオミノの状態
struct PolyominoState {
  std::vector<std::vector<int>> number, field; //number: 番号を管理、field: 設置済みかを管理
  PolyominoState(int n, int m):number(n, std::vector<int>(m,-1)),field(n, std::vector<int>(m,0)){}

  //フィールドの余白を削る
  void minimize(){
    if(field.size() == 0) return;
    if(field[0].size() == 0) return;
    std::vector<int> w(field[0].size(), 0), h(field.size(), 0);
    
    for(int i=0; i<field.size(); i++){
      for(int j=0; j<field[i].size(); j++){
        if(field[i][j] == 1){
          w[j] = 1;
          h[i] = 1;
        }
      }
    }

    int width = 0, height = 0;
    for(int i=0; i<w.size(); i++) if(w[i]==1) width++;
    for(int i=0; i<h.size(); i++) if(h[i]==1) height++;
    
    std::vector<std::vector<int>> new_field(height,std::vector<int>(width,0));
    for(int i=0,ii=0; i<field.size(); i++){
      if(h[i] == 0) continue;
      for(int j=0,jj=0; j<field[i].size(); j++){
        if(w[j] == 0) continue;
        new_field[ii][jj] = field[i][j];
        jj++;
      }
      ii++;
    }

    number.clear();
    field = new_field;
  }
};
class GeneratePolyomino {
  int N;
  
  //設置可能かどうかを確認
  bool check(const PolyominoState& s, int y, int x){
    int n = s.number.size();
    int m = s.number[0].size();
    if(y<0 || n<=y || x<0 || m<=x) return false;
    if(y==0){
      if(m/2 <= x && s.number[y][x] == -1) return true;
      return false;
    }else{
      if(s.number[y][x] == -1) return true;
      return false;
    }
  }
public:
  GeneratePolyomino(int N):N(N){}
  
  //Nオミノをすべて生成
  std::vector<PolyominoState> generate(){
    std::vector<PolyominoState> ret;

    //初期状態
    PolyominoState st(N, 2*N-1);
    st.number[0][N-1] = 1;
    if(N>1) st.number[0][N] = 2;
    if(N>1) st.number[1][N-1] = 3;
    st.field[0][N-1] = 1;

    if(N == 1){
      ret.push_back(st);
      return ret;
    }
    
    std::queue<PolyominoState> que;
    que.push(st);

    while(!que.empty()){
      st = que.front(); que.pop();

      //フィールドの状態から設置個数、設置された番号の最大値、空マスの番号の最大値を取得
      int n_last = -1;
      int f_last = -1;
      int f_num = 0;
      for(int i=0; i<st.number.size(); i++){
        for(int j=0; j<st.number[i].size(); j++){
          if(st.field[i][j] == 0) n_last = std::max(n_last, st.number[i][j]);
          if(st.field[i][j] == 1){
            f_last = std::max(f_last, st.number[i][j]);
            f_num++;
          }
        }
      }

      //Nオミノだったら、フィールドの余白を消して返り値ベクトルに入れておく
      if(f_num==N){
        st.minimize();
        ret.push_back(st);
        continue;
      }
      
      //空マスから1つ選んで状態を更新する
      for(int i=0; i<st.number.size(); i++){
        for(int j=0; j<st.number[i].size(); j++){
          if(st.number[i][j] == -1) continue; //番号がなければスキップ
          if(st.field[i][j] == 1) continue;  //設置済みならスキップ
          if(st.number[i][j] < f_last) continue; //設置番号より小さい番号ならスキップ
          
          PolyominoState tmp = st;
          tmp.field[i][j] = 1; //設置

          //下、左、右、上の順に空マス番号を割り当てる
          int number = n_last+1;
          if(check(tmp, i-1, j)) tmp.number[i-1][j] = number++;
          if(check(tmp, i, j-1)) tmp.number[i][j-1] = number++;
          if(check(tmp, i, j+1)) tmp.number[i][j+1] = number++;
          if(check(tmp, i+1, j)) tmp.number[i+1][j] = number++;

          que.push(tmp);
        }
      }
    }
    return ret;
  }
};

N=5の時、列挙。

N=1～12までのfixedの個数を表示。(wikipediaの個数と一致することは確認)

1       1
2       2
3       6
4       19
5       63
6       216
7       760
8       2725
9       9910
10      36446
11      135268
12      505861

参考

Polyomino - Wikipedia

http://www.csun.edu/~ctoth/Handbook/chap14.pdf

AGC013 C. Ants on a Circle

問題

周の長さがLの円上にN匹の蟻がいる。
それぞれの蟻は番号がついていて、座標X_iと向きW_iが与えられ、毎秒1単位距離の速度で動く。
各蟻は衝突するとそれぞれ進む向きを変える。
T秒後にそれぞれの蟻がいる位置を求めよ。

制約

1 <= N <= 10^5
1 <= L,T <= 10^9
0 <= X_1 < X_2 < ... < X_N <= L-1
W_i = {1,2}

解説

いくつか気づかないといけないことがある。

• 1. 番号を無視したときのT秒後の蟻の位置

番号を無視したT秒後の蟻の位置座標の集合は、蟻本で紹介されている通り、素通りするように考えると求められる。
各蟻について、求めた座標をソートすると、番号はわからないが、答えの座標になっている。

• 2. 衝突で跳ね返る場合、T秒後の番号の並びは1,2,3,...をずらしたものとなる

衝突で蟻は跳ね返るので番号の大小関係は変わらない。
なので、ある蟻の番号と位置がわかればそこから他の蟻の番号が一意に決まる。

• 3. 最初、番号1だった蟻のT秒後の座標と番号は衝突回数から求められる

最初番号1だった蟻が時計回りだった場合を考える。
座標は1の方法で求められる。
番号については、衝突がx回だった場合、+xになる。

衝突回数は、進行方向が異なる蟻に対して、
1回目は、(2匹の蟻の距離の半分)秒
2回目は、(2匹の蟻の距離の半分+L*1/2)秒
3回目は、(2匹の蟻の距離の半分+L*2/2)秒
...
となっているので、以下のような感じで衝突回数がO(1)で求められるので、すべての進行方向が異なる蟻について求めるとO(N)。

ll calc_count(ll x, ll y, ll L, ll T){
  if(T*2 < abs(x-y)) return 0;
  ll remain = T*2 - abs(x-y);
  return 1+remain/L;
}

反時計回りだった場合は、衝突回数がx回だった場合、-xになる。
2つの蟻の距離も「最初の蟻の座標+L」との距離を求めればよい。

1で求めた座標の中からこの座標を持つ座標を見つければ、それが求めた番号であることがわかる。
なので、2の事実によって求められる。

• 4. 同じ座標になる場合

3で求めてたT秒後の座標が同じ座標になる場合がある。(入力例2)
ただし、同じ座標になるのは、最初の座標がすべて異なり、同じ速度で動いているため2匹しかありえない。
このような場合、衝突直後なので、進行方向に対して後ろ側になる。

これらを事実を合わせてれば答えが得られる。
計算量は、ソートする部分が一番重く、O(NlogN)。

反省

• 負の数のmoduloには気を付ける
  • 型にも気を付ける

int a = -5;
int b1 = 3;
unsigned int b2 = 3;

cout << (a%b1) << endl; //-2
cout << (a%b2) << endl; //2

AGC013 B. Hamiltonish Path

問題

N頂点M辺の連結で単純な無向グラフが与えられる。
このグラフにおける以下の条件を満たすパスを1つ出力せよ。

• 2頂点以上
• 同じ頂点を通らない
• パスの少なくとも一方の端点と直接辺で結ばれている頂点は必ずパスに含まれる

制約

2 <= N <= 10^5
1 <= M <= 10^5

解説

直感的に、できるだけ長いパスを作った場合、パスの端点の近傍がパスの頂点集合に含まれる可能性が高そうなことがわかる。
ある頂点vから、条件を満たす端点wを見つけるまで、パスを伸ばしていくことを考える。

伸ばしていったら端点wが見つかると仮定する。
もし近傍N(v)が1個の場合、そこを端点とすればすぐに条件を満たせるので問題ない。
もし近傍N(v)が2個以上の場合、とりあえず1つを選んで伸ばしていき、端点wを見つける。
パスを伸ばしていったとき、近傍の頂点N(v)がすべて含まれれば条件を満たす端点となり得ることがわかるし、近傍の頂点でパスに含まれない頂点がある場合は、頂点vは端点として条件を満たせない頂点とわかる。
満たしていない頂点の場合にも、パスを伸ばしていくことができるので、条件を満たす端点v'を見つけるまで伸ばしていけばよい。

端点wが見つからないことがあるかどうかが問題だが、伸ばしているパスの端点xの近傍は伸ばせば伸ばすほどすでに訪れている可能性が増えていき、最終的に「動けなくなる＝すべての近傍にすでに訪れている状態」になるので、端点wは見つかる。

反省

最初、A-B-C-Dみたいなグラフがあったときに、「A-B」も「パスの少なくとも一方である端点Aと直接結ばれている頂点Bがパスに含まれている状態」なので、条件を満たすかと思ったらサンプルでWAして混乱してた。
(「パスの両方の端点A,Bの近傍N(A)とN(B)の和集合N(A)∪N(B)がパスに含まれている」ことだった)

GCJ2017 Round1A A. Alphabet Cake

問題

R*Cのグリッドに大文字アルファベットまたは「?」が書かれている。
各アルファベットは高々1回しか出現しない。
「?」は出現したアルファベットのどれかを割り当てることができる。
各アルファベットを長方形を維持した状態で拡張し、すべての「?」をどれかのアルファベットに割り当てたい。
割りあてた後の「?」のない状態を1つ出力せよ。

制約

1 <= R,C <= 25

解説

まずすべての行について、アルファベットを適当に横方向(左右)に全部を伸ばす。
これで「?」が残っている場合は、その行すべてが「?」になっているはずである。
この「?」のみの行は上か下で埋まっているアルファベットを行ごと伸ばせは長方形を維持して埋められる。

反省

大切な気づきは、「行と列が独立に計算できる」こと。
最初単純な左右に伸ばす方法を考えてたのに、考えてるうちに、上下方向も同時に考える方向に進んでしまってハマった。
(左右上下で長方形を考えると、考えるべきパターンがかなり多くなってしまう)
結局本番は「考える長方形候補を減らす＆「?」が残らないようにするルール」みたいなのを書いてしまった。。。

二項演算が非可換な場合のセグメント木のクエリ処理

気になったのでメモ。

モノイド

セグメント木は、完全二分木の各ノードがその子孫の範囲の情報を管理しているようなデータ構造。

図は、配列(緑)に対して対応するセグメント木(青)を表す。
青の2番は、緑の0番から3番までの範囲に演算した結果を保持する。

セグメント木は、和やmax/minなんかの演算結果を持たせるだけでなく、一般にモノイドであればよいらしい。

モノイドは、集合Sと二項演算*:S×S→Sに対して、

• 結合律：(a*b)*c = a*(b*c)
• 単位元の存在：Sの元eが存在して、Sの任意の元aに対して、a*e = e*a = a

を満たすようなものをいう。

二項演算が可換の場合の範囲クエリ処理

ある範囲[l,r)に対して二項演算を行った結果を得たい。

二項演算がsumやmax/minの場合は、蟻本にあるように

• 完全に範囲外
• 完全に範囲内
• 部分的に範囲内

で場合分けして、「部分的に範囲内」の場合再帰するような関数で求められる。

二項演算が非可換の場合の範囲クエリ処理

sumやmax/minは可換なので、上のように実装できているが、非可換な二項演算の場合はどうなるかよくわからなかったので、調べたところ、
http://codeforces.com/blog/entry/18051
このエントリで紹介されていた。(「Non-commutative combiner functions」のところ)

基本的に、演算の左右を明示的に区別して処理すればよいっぽい。(combine(lhs, rhs)関数を用意して処理)

ちなみに上記のエントリだと、query(l,r)関数はlとrに対応する葉ノードから親方向に向かって処理していた。

赤のノードが演算対象。
範囲内の一番端から該当するノードをうまく選んでめぐって演算を繰り返す(l < rの間)。

AGC012 B. Splatter Painting

問題

連結とは限らない、N頂点、M本の辺を持つ無向グラフが与えられる。
頂点には1～Nの番号が振られている。
Q回「頂点v_jから距離d_jの頂点を色c_jで塗る」という操作をした後の各頂点の色が何色か答えよ。

制約

1 <= N,M,Q <= 10^5
0 <= d <= 10
1 <= c_j <= 10^5
自己ループや多重辺は存在しない

解説

https://atcoder.jp/img/agc012/editorial.pdf
AtCoder Grand Contest 012 解説放送 - YouTube

愚直な方法を考える。
操作をそのまま実行して、頂点vから深さdまで実際にたどって色cで塗ることを繰り返す。
ただ、この方法だと色を塗る頂点が全頂点になる可能性があり、O(Q*N)だと間に合わない。

そこで、無駄なことをしているところを考える。

一つは、1度塗った頂点を別な色に塗り替えている部分が考えられる。
これは、与えられたクエリを逆順に実行すれば、すでに色が塗られているところは塗り返さなくてよくなる。
ただ、この方法でも、すでに塗った頂点を超えて塗らないといけないため計算量は変わらない。
(例：[1]-[2]-[3]というグラフで(「v=1,d=2,c=2」→「v=2,d=0,c=1」だと、逆順に頂点2から塗っても頂点1から塗るとき、すでに塗った頂点2を超えて頂点3を塗らないといけない)

さらに、無駄な移動がないかよく考えると、「ある頂点vに深さdで色cで塗りに来た」場合、すでに「頂点vに深さd'(>=d)で色c'で塗りに来ていた」場合は塗ることはないことがわかる。
なので、それを以下のようにメモって無駄な移動をしないようにする。
dp[v][d]:=頂点vに深さdですでに色を塗ったか
(coloring(v,d,c)で頂点vで来たら隣接ノードuにcoloring(u,d-1,c)で塗りに行けばよい)

反省

制約の中で異様なd<=10をうまく活用することを考えたほうがよい。
色を塗るとき、visited[v]をメモリながらbfsしていたけど、上みたいなメモ化しながらdfs(v,d)でdを減らしながら辿るのも考える。

yukicoder No.492 IOI数列

問題

IOI数列は、1,101,10101,1010101,...とa_1=1, a_i=100*a_{i-1}+1であるような数列である。
第N項について、1000000007で割ったあまりと101010101010101010101で割ったあまりを求めよ。

制約

1 <= N <= 10^18

解説

第N項を計算したい。
後者の10101...で割ったあまりは、64bit整数に収まらないが、パターンの繰り返しなので、それで答えればよい。
前者の1000000007で割ったあまりを考える。

特性方程式

「a_n = b*a_n + c」の形をしているので、特性方程式x=bx+cを解いてあげれば等比数列として考えられる。

x=100x+1 <=> x = -1/99

よって、「(a_{n+1}-x)=100*(a_{n}-x)」となるので、一般項は、「a_{n+1} = 100^n * (a_1 - x) + x」となる。
展開すると、a_{n+1}=(100^{n+1} - 1)/99なので、「a_n=(100^n - 1)/99」になる。

この計算を、MODでの累乗(繰り返し二乗法)や逆元(拡張ユークリッド互除法を使う方法)を使ってあげれば高速に求められる。

行列累乗

より一般に、m項間漸化式について、一つ次の項を求めるような行列計算を立てると、第N項を行列累乗で求められる。

v_{n+m} = (a_{n+m}, a_{n+m-1}, ..., a_{n+1})^Tとして、「v_{n+m} = X * v_{n+m-1}」となるような行列Xを作れれば、第n項は「v_{n+m-1} = X^n * v_{m}」のように書ける。

今回の漸化式は定数項があるので、

から

という式になる。行列の累乗は繰り返し二乗法を使ってO(m^3 log n)または高速にO(m^2 log n)の計算量で求められる。

反省

• 漸化式は行列累乗を検討

KUPC2016 E. 柵 / Fences

問題

H*Wのグリッドのいくつかのマスにヤギがいる。
ヤギは上下左右の隣接マスに移動できるが、移動先となるマスに柵がある場合は、その方向へは移動できない。
ヤギがグリッドの外に出ないようにするために必要な柵の最小個数を求めよ。

制約

1 <= H <= 100
1 <= W <= 100

解説

http://www.kupc.jp/editorial/2016/E.pdf

最小カットで求めることができる。

マスに柵を置くかどうかを扱うために、各マスをin頂点とout頂点に分解し、ヤギのいないマスの場合はinからoutを容量1でつなぎ、ヤギがいる場合は容量infでつなぐ。
ヤギのいないマスの場合は、さらに、out頂点から上下左右のマスのin頂点へ容量infでつなぐ。

最後に、s-tフローで扱うために、頂点sからグリッドの縁のマスのin頂点へ容量infでつなぎ、ヤギのいるマスのout頂点から頂点tへつないで、s-t最小カットを求めればよい。

AGC010 C. Cleaning

問題

Nノードからなる木が与えらえる。
各ノードにはA[i]個の石が置かれている。
「2つの(異なる)葉ノードを選び、そのパス上のノードすべてから1つずつ取り除く」という操作を繰り返して、すべての石を取り除けるか答えよ。
ただし、パス上に石のないノードがある場合は操作は行えない。

制約

2 <= N <= 10^5
0 <= A[i] <= 10^9

解説

https://atcoder.jp/img/agc010/editorial.pdf

適当にノードを選んで根にして、根付き木として考える。
あるノードvについて、親ノードがw、子ノードがc_1,c_2,...,c_kであるような場合を考える。

vとc_iの間の辺が何回パスとして通過するかをp[c_i]とすると、vとwの間の辺が何回パスとして通過するかp[w]は、ノードvの通過回数A[v]が決まっているので、
p[w] = 2*A[v] - Σp[c_i]
でなければならない。
このとき、条件として、

• p[w]は0以上A[v]以下の数でなければいけない
• もし、子ノードが1つの場合は、p[w]=A[v]=p[c_1]でなければならない
• vの周りの各辺の通過回数p[x]は、辺の通過回数合計/2回 = (p[w]+p[c_1]+...+p[c_k])/2以下でなけれなならない

を満たす必要がある。

これを再帰的に繰り返し(dfs)、根まで求め、

• 根が葉ノードの場合、根の疑似的な親ノードへの辺の通過回数=A[root]になっている
• 根が葉ノードでない場合、根の疑似的な親ノードへの辺の通過回数=0になっている

のどちらかになっていれば、すべての石を取り除くことができる。

反省

• 根付き木で考える
• 葉ノードから決定的に決まるものを見つける

ARC068 E. Snuke Line

問題

直線上の鉄道で、0～Mまでの番号が付いたM+1個の駅がある。
N種類の名産品が与えられ、名産品iは駅lから駅rまでの区間で売られている。
最初0番の駅にいるとして、d駅ごとに停車する電車の場合、購入可能な名産品の種類数を知りたい。
dが1～Mの場合それぞれについて、種類数を答えよ。

制約

1 <= N <= 3*10^5
1 <= M <= 10^5
1 <= l_i <= r_i <= M

解説

AtCoder Regular Contest 068/ Beginner Contest 053 解説放送 - YouTube
解説放送の方の方法で解いてみた。

よく知られた事実として、以下のループはO(M log M)程度であることが使える。

for(int d=1; d<=M; d++){
  for(int p=1; d*(long long)p<=M; p++){
    //d*pについて、何かする
  }
}

単純な方法だと、「l_i <= d*p <= r_i」であるかをN個の名産品でチェックする方法がある。
しかし、これだとTLEしてしまうし、気を付けないと、d*pもd*(p+1)も範囲内であるような「l_i <= d*(p+1) <= r_i」のケースでダブルカウントしてしまうかもしれない。

範囲l_i～r_iに対して、d*pが1回しかカウントしないようにするうまい方法として、「d*(p-1)は範囲外で、d*pが範囲内の場合カウント」することで、範囲内の停車駅のうち、一番左の駅を見つけることができる。
X=d*(p-1)、Y=d*pとおいて考えると、「X < l_i、かつ、l_i <= Y <= r_i」を満たすような特産品を高速に求められれば良いことになる。

範囲は扱いにくいので、「l～r」という情報を2次元平面の点p(l,r)として考える。
上のXとYの条件はこの2次元平面上でどのような条件になるか考えると、分解して、

• X < l
• l <= Y
• Y <= r

を満たす範囲の点の数を見つけることに相当する。
この3つの条件は、以下の*の部分のような平面上の長方形になっている。

M |-----+-------+
  |     |*******|
r |-----+***p***|
  |     |*******|
Y |-----+---+---|
  |     |   |   |
  +--------------
        X   l   Y

これを高速に処理することを考える。

今回、問い合わせクエリ(X,Y)と特産品の点(l,r)が先に求めておける。
そこで、問い合わせと特産品の点を合わせてl軸方向でソートしておき、r軸方向に対する1次元BITを使って、l軸の小さい方から点を置いたり、問い合わせに答えたりをすれば必要な(X,Y)の答えを求めておける。
あとは、X,Yの個数を使って該当する特産品数を求めて表示すればよい。

反省

(X,Y)の条件を満たす点の数を保存するのに、

map<pair<int,int>,int> memo;

としてしまったが、O(M log M)のループとはいえ、10^6個以上要素がある。
このままだと、memo[make_pair(X,Y)]などとアクセスした場合、木が深いため、時間が無視できない程度かかってしまう。
代わりに、

map<int,int> memo[100005];

などと木の深さが深くならないようにすることで、時間をかけずにアクセスできるようになる。

コード

#include <bits/stdc++.h>
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 FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

#define MAX 100005

class BIT{
  static const int MAX_N = 1 << 18;
  int n, bit[MAX_N+1];
public:
  BIT(int n_){
    n = n_;
    for(int i=0; i<n+1; i++) bit[i] = 0;
  }
  int sum(int i){
    int s = 0;
    while(i>0){
      s+=bit[i];
      i-=i&(-i);
    }
    return s;
  }
  void add(int i, int x){
    while(i<=n){
      bit[i]+=x;
      i+=i&(-i);
    }
  }
};
 
struct ST {
  int type;
  int l, r;
};
bool operator<(const ST& a, const ST& b){
  if(a.l == b.l) return a.type < b.type;
  return a.l < b.l;
}
 
map<int,int> query[MAX];
 
int main(){
  ios::sync_with_stdio(false);
 
  int N, M;
  cin >> N >> M;
 
  vector<ST> pts;
  rep(i,N){
    int l, r;
    cin >> l >> r;
    pts.push_back((ST){0,l,r});
  }

  for(int d=2; d<=M; d++){
    for(int p=1; d*(ll)p<=M; p++){
      int X = d*(p-1);
      int Y = d*p;
 
      if(query[X].count(Y-1)==0){
        query[X][Y-1] = 1;
        pts.push_back((ST){1,X,Y-1});
      }
      if(query[X].count(MAX)==0){
        query[X][MAX] = 1;
        pts.push_back((ST){1,X,MAX});
      }
      if(query[Y].count(Y-1)==0){
        query[Y][Y-1] = 1;
        pts.push_back((ST){1,Y,Y-1});
      }
      if(query[Y].count(MAX)==0){
        query[Y][MAX] = 1;
        pts.push_back((ST){1,Y,MAX});
      }
    }
  }

  sort(ALLOF(pts));
 
  BIT bit(1<<18);
 
  rep(i,pts.size()){
    if(pts[i].type == 0){
      bit.add(pts[i].r+1, 1);
    }else{
      query[pts[i].l][pts[i].r] = bit.sum(pts[i].r+1);
    }
  }

  for(int d=1; d<=M; d++){
    if(d==1){
      cout << N << endl;
    }else{
      int ret = 0;
      for(int p=1; d*(ll)p<=M; p++){
        int X = d*(p-1);
        int Y = d*p;
 
        ret += query[Y][MAX] - query[Y][Y-1] - query[X][MAX] + query[X][Y-1];
      }
      cout << ret << endl;
    }
  }
 
  return 0;
}

CodeFestival2016 Final D.Pair Cards

問題

N枚のカードがあり、カードiには整数X_iが書かれている。
今、「書かれた数字が同じ」または「和がMの倍数」になるような2枚のカードをペアにする。
最大で何ペア作れるか？

制約

2 <= N <= 10^5
1 <= M <= 10^5
1 <= X_i <= 10^5

解説

https://cf16-final.contest.atcoder.jp/data/other/cf16-final/editorial.pdf

「和がMの倍数」になるようなペアの処理は、X_i mod Mでグルーピングすると、余りがjのグループとM-jのグループのペアを取ればMの倍数になる。
(ただし、mod M == 0か、mod M == M/2(ただし、M mod 2==0)の場合は、同じグループ内でペアを取る)

こうすれば、グループAとグループBでの最大マッチングを求めて足し合わせればよくなる。

|A|==|B|の場合は、|A|個ペアが作れる。
|A|<|B|の場合、|A|個のペアは作れることがわかるが、|B|-|A|個のうち、「書かれた数字が同じ」場合はペアを取ることができる。
したがって、グループBの方で、|B|-|A|枚以下のカードを使って、書かれた数字が同じになるペアの最大ペア数をmとすると、「m+|A|」ペアが最大マッチングになる。

yukicoder No.374 コイン

問題

2人で以下のゲームを行う。
・半径Aの円の中に、半径Bの円を交互に置いていく
・置いていく円は、半径Aの円からはみ出したり、すでに置いた円とかさなったりしてはいけない
・先に置けなくなった方が負け
・置かれた円は動かせない
それぞれ最適に行動した場合、どちらが勝つか答える。

制約

1 <= A,B <= 2^32

解説

A < Bの場合、先手がすでにおけないので、後手の勝ち。
A >= Bの場合を考える。

2*A/3 < Bの場合は、真ん中に置くと、その後、どこにも置けなくなるので、先手の勝ちということがわかる。
2*A/3 >= Bの場合は、先手がどこに置いても後手に手番が回る。

最適な行動は、まず、真ん中に置いて、後手に手番をわたす。
後手がどこに置いたとしても、「円の中心の点対称の位置に円を置く」ということを繰り返すと、必ず先手はおくことができる。
したがって、先手がこの行動をとった場合、必ず勝てるので、先手の勝ちとなる。

AtCoder Regular Contest 055 C. ABCAC

問題

文字列Sが与えられる。
この文字列は、それぞれ長さ1以上の文字列A,B,Cを「ABCAC」のように連結してできている。
このような分割は何通りあるか？

制約

5<=Sの長さ<=200,000
(部分点：Sの長さ<=2,000)

解法

説明のために、「A B C A' C'」と置く。N=(Sの長さ)とする。

もし、A'が出現する位置がxだとわかったとして、A'の長さが決まれば、C'の長さが決まる。
なので、A=A'となる最大の長さa、C'=Cとなる最大の長さcが高速に求まれば、以下から判定できる。
・a+c<(N-x)ならば、作ることができないので、無し
・x<=(N-x)ならば、Bの部分を作ることができないので、無し
・候補となるA'とC'の最大の長さは、1文字以上である必要があるので、それぞれ、min(a,N-x-1)、min(c,N-x-1)
・このとき、組み合わせの数は、「min(a,N-x-1) + min(c,N-x-1) - (N-x) + 1」で求められる
　・min(a,N-x-1)+min(c,N-x-1)==N-xの場合は、1通り
　・min(a,N-x-1)+min(c,N-x-1)==N-x+1の場合は、2通り
　・、、、

ということで、位置xにおける「A=A'となる最大の長さa」と「C'=Cとなる最大の長さc」を高速に求める必要がある。
エディトリアルではいくつかの方法が紹介されているが、SuffixArrayと高さ配列を使っても解けるので、それを試してみる。

高さ配列は、SuffixArrayが構築されている場合、次の接尾辞とのprefixの一致数をO(N)で求められる。
SuffixArrayの中で、インデクスが0の部分が「Sの先頭からの文字列」を表すので、そこから前後に高さ配列の値が降順になるようにすれば、すべての位置に対する「A=A'となる最大の長さ」を求められる。

インデクス	接尾辞	高さ配列	高さ配列の値をインデクス0から降順になるようにしたもの
11		0	0
10	a	0	0
7	abra	1	1
0	abracadabra	4	4
3	acadabra	1	1
5	adabra	1	1
8	bra	0	0
1	bracadabra	3	0
4	cadabra	0	0
6	dabra	0	0
9	ra	0	0
2	racadabra	2	0

インデクスが0の部分から、高さ配列を前後にそれぞれ降順になるようにしたものが表の一番右。
これは、min()を取りながらO(N)で求められ、これは位置xに対する「A=A'となる最大の長さ」の情報になっている。(ので、O(1)で求められる)

「C'=Cとなる最大の長さc」については、文字列Sをreverseしたものについて同様に行えば、位置x-1で終わるようなCの最大の長さがO(1)で求められる。
したがって、
・SuffixArray構築にO(N)～O(N log^2 N)
・位置xを決めるためにO(N)
・aとcを求めるのにO(1)
・位置xでの組み合わせの数を求めるのにO(1)
なので、全体でO(N)～O(N log^2 N)程度で求められる。

解法2

Z algorithmは上のをO(N)で作ることができる。

//z[i]:=文字列sと、位置iから始まる部分文字列との共通接頭辞の長さ(ただしz[0]=0)
std::vector<int> Zalgorithm(const std::string& s){
  int n = s.length();
  std::vector<int> z(n, 0);

  int L = 0, R = 0;
  for(int i=1; i<n; i++){
    if(i>R){
      L = R = i;
      while(R<n && s[R-L] == s[R]) R++;
      z[i] = R-L;
      R--;
    }else{
      int k = i-L;
      if(z[k] < R-i+1){
        z[i] = z[k];
      }else{
        L = i;
        while(R<n && s[R-L] == s[R]) R++;
        z[i] = R-L;
        R--;
      }
    }
  }
  return z;
}

テンプレ

コードも残したいと思います。

使っているテンプレは以下です。

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <iostream>
#include <queue>
#include <list>
#include <stack>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
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 FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;