ARC047 B. 同一円周上

問題

座標平面上にN個の点がある。
各点の座標は整数で、ある点Pとのマンハッタン距離が同じであることがわかっている。(点Pの座標も整数)
点Pとしてあり得る点を一つ出力せよ。

制約

1 <= N <= 10^5
-10^9 <= x,y <= 10^9

解説

arc047

平面座標で、点Pからのマンハッタン距離が同じ点というのは、点Pを中心とするひし形の線上に乗る。
しかし、ひし形のまま扱うのは大変なので、テクニックとして45度回転させた座標を考える。
(x,y)->(x+y,x-y)という変換を考えると、上記の「ひし形の線上」というのが「正方形の線上」になり、とても考えやすい。

また、平面座標のどこかの候補点を探す場合、かつ、単純な方法では候補点が多くなりすぎる場合は、候補点を絞ることを考える。
(x座標・y座標それぞれで、線分の端点や交点などだけ取り出してその組み合わせを考える、など)

今回の場合、正方形の1辺の長さDが決まれば、点Pの座標は各点から距離Dの点のどこかということになる。(これだけだとまだ候補点が多すぎる)
もし正方形の1辺が決まれば、その辺の端点から距離がD/2の点(辺に対して両側が考えれる)が候補点になる。
そこで、正方形の辺を探す。

変換後の平面座標において、各軸について独立に出現している点の座標を考える。
その座標で最小の点と最大の点を見つける。
このとき、これらの点を端点とする辺が「正方形の1辺」の候補になる。
(例外としてN=1の時は1辺が作れないので別処理する)

これより長い辺を考える必要があるかというと、もう片方の軸の方で同じことをして見つけた辺がより長い場合、そちらが1辺の長さとしてふさわしい。
言い換えると、各軸について辺の長さを求めて、その大きな方が正方形の1辺の長さDとしてふさわしい。
(Dも候補として各軸について求めた2つがあると考えてもよい)

そして、候補点はそれぞれの点からD/2だけずれた点となる。(最大点+D/2,最大点-D/2,最小点+D/2,最小点-D/2の4点 最大点-D/2,最小点+D/2の2つ)
あとは候補点すべてについて実際に成り立つ点Pを確認してあげればよい。
計算量は、候補点の組み合わせで4*4=16個2*2=4個(または、各軸のDの候補を別に考える場合は、8*8=64個 4*4=16個)についてO(N)でチェックすることになるので、間に合う。

反省

• 座標系で絶対値が出てきたら45度回転させてみる
• 候補点が無数に考えられる場合、端点や中点など候補点としてありえる部分に絞って探索する

AGC015 C. Nuske vs Phantom Thnook

問題

N*Mのグリッドの各マスに色が塗ってある。
ある色の塗ってあるマスから別の色の塗ってあるマスへ移動できる場合、同じマスを通らずに移動する経路は高々1通りである。

Q個のクエリが与えられる。
各クエリは「(x1,y1)から(x2,y2)の長方形範囲でグリッドを切り出したとき、色の塗ってあるマスの連結成分がいくつあるか？」の質問であるので、これに答えよ。

制約

1 <= N,M <= 2000
1 <= Q <= 200,000

解説

Editorial - AtCoder Grand Contest 015 | AtCoder
AtCoder Grand Contest 015 - YouTube

どこから考えるかが難しい。

問題の最初の条件は「森(グラフ理論)」のことを言っている。
任意のグラフで連結成分を求めるにはUnionFindなどが使えるが、森における連結成分は「頂点数 - 辺の数」で求められる。

頂点数は、単純に2次元累積和で求められる。
辺の数も、各頂点に対して下方向か右方向にしか伸びないので、同様に2次元累積和で求められる(縦方向の辺、横方向の辺で独立に累積和を計算すると見通しがよい)。

計算量は、構築がO(NM)でクエリ処理がO(Q)なので、全体でO(NM+Q)。

反省

• 「森における連結成分が"頂点数-辺の数"」というところに注目できないとほぼ無理そう
  • 連結成分をつないだり外したりみたいな方向で考えてしまうと余計無理そう
• 一般的な解き方ではなく、「問題の条件に合わせた効率的な解き方」を考察できるようにする必要がある

ARC074 E. RGB Sequence

問題

N個のマスが横一列に並んでおり、各マスを赤、緑、青のいずれかで塗りたい。
しかし、 M個の「マスlからマスrの色の種類数がx」という条件を満たすようにしたい。
条件を満たすような塗り方は何通りか？10^9+7の余りを答えよ。

制約

1 <= N <= 300
1 <= M <= 300
1 <= l_i <= r_i <= N
1 <= x_i <= 3

解説

Editorial - AtCoder Regular Contest 074 | AtCoder
AtCoder Regular Contest 074/ Beginner Contest 062 解説放送 - YouTube
以下、だいぶ自分の解釈が入っているので、間違っているかもしれないことに注意。

種類数を数えたいので、DPが適用できないか考える。

• 条件がない場合の数え上げ

まず、M個の条件がない場合を考える。
左から順番に塗っていって、i番目までの計算結果があるとする。
このとき、
dp[i][...]:=i番目まで塗ったときの塗り方の総数
を考える。
このとき「赤を最後に塗った場所がr」「緑を最後に塗った場所がg」「青を最後に塗った場所がb」というのがわかっていれば、
i+1に赤を使った場合は、dp[i+1][i+1][g][b] += dp[i][r][g][b]、
i+1に緑を使った場合は、dp[i+1][r][i+1][b] += dp[i][r][g][b]、
i+1に青を使った場合は、dp[i+1][r][g][i+1] += dp[i][r][g][b]、
と更新することができる。
しかし、O(N^4)になってしまっている。が、これはだいぶ無駄で、i番目のとき、rまたはgまたはbのどれか一つはiになっているところだけ考えればよいはずなので、iは必要ない。

dp[r][g][b]のとき、i=max(r,g,b)と計算できるので、
i+1に赤を使った場合は、dp[i+1][g][b] += dp[r][g][b]
i+1に緑を使った場合は、dp[r][i+1][b] += dp[r][g][b]
i+1に青を使った場合は、dp[r][g][i+1] += dp[r][g][b]
と更新できる。
これはO(N^3)なので、間に合う。

• 条件を満たさないとき、数え上げない

条件を満たすときだけの数え上げをしたいので、dpの更新中にこの判定をいれたい。

(r,g,b)が決まっているとき、i=max(r,g,b)とすると、M個の各条件(l_i,r_i,x_i)について、「l_i<=r<=r_i」「l_i<=g<=r_i」「l_i<=b<=r_i」であるか確認して使われている色の種類数を確認して、x_iと一致するかどうか見ればよい。
そして、条件を満たさない場合はdp[r][g][b]=0としてしまえばよい。

しかし、r,g,bの三重ループの中で単純にM個のループを回してしまうとO(M*N^3)となる。
そこで、「vector < pair < int,int > > v」として、v[r_i][j] = pair(l_i,x_i)のように持たせて、各iでv[i]だけをチェックする。
iは0～Nの範囲で動くが、v[i]のようにM個の条件をiで分割して持たせると、O(N+M)になる。
全体ではO(M*N^3)はO(N^2*(N+M))=O(N^3 + M*N^2)となり、間に合う。

コード

#define MOD 1000000007

int dp[305][305][305];
vector<pair<int,int>> v[305];

int main(){
  int N, M;
  cin >> N >> M;
  rep(i,M){
    int l, r, x;
    cin >> l >> r >> x;
    v[r].push_back(make_pair(l,x));
  }

  ll ret = 0;
  dp[0][0][0] = 1;

  rep(i,N+1){
    rep(j,N+1){
      rep(k,N+1){
        int m = max(i,max(j,k));

        rep(ii,v[m].size()){
          int r = m;
          int l = v[r][ii].first;
          int x = v[r][ii].second;

          int cnt = 0;
          if(l<=i && i<=r) cnt++;
          if(l<=j && j<=r) cnt++;
          if(l<=k && k<=r) cnt++;
          if(cnt != x){
            dp[i][j][k] = 0;
          }
        }

        if(m == N){
          ret += dp[i][j][k];
          ret %= MOD;
          continue;
        }

        dp[m+1][j][k] += dp[i][j][k];
        dp[m+1][j][k] %= MOD;
        dp[i][m+1][k] += dp[i][j][k];
        dp[i][m+1][k] %= MOD;
        dp[i][j][m+1] += dp[i][j][k];
        dp[i][j][m+1] %= MOD;
      }
    }
  }
  
  cout << ret << endl;

  return 0;
}

反省

• 条件を持つ数え上げとかは、桁DPとかでもよく見る
• 無駄な状態を減らす
• O(N)でM個の条件のチェックをする場合、位置に依存するならばO(NM)ではなくO(N+M)に落とせる

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|」ペアが最大マッチングになる。