phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

AGC017 C. Snuke and Spells

問題

N個のボールが一列に並んでおり、各ボールには数字が書かれている。
魔法を使うと、今あるボール個数と同じ数字が書かれたボールを消すことができる。また、魔法は連続的に行うことができる。
例えば、{1,3,3}だった場合、魔法を2回連続で行うと、{1,3,3}->3個あるので3が書かれたものが消える->{1}->1個あるので1が書かれたものが消える->{}となる。

各ボールは単位時間ごとに、ボール1個だけ数字が変化することがわかっており、変化する回数はM回であることもわかっている。
ここで、各単位時間ごとのボールの状態に対して、いくつか数字を書き換えて連続魔法で全消しができるようにする最小書き換え回数を求めたい。

制約

1 <= N,M <= 2*10^5
1 <= ボールの数字 <= N
1 <= 変化するボールの場所 <= N
1 <= 変化した後の数字 <= N

解法

まずは、あるボールの状態に対して、ボールの最小の書き換え回数を求める問題を考える。


魔法を発動するときのボールの位置は無関係なので、あるボールの状態をソートしたものを考える。
例えば、{1,3,3,5,5}のような場合、魔法を連続発動することで、全消しができる。
どういうときに全消しができるか考えると、

i 1 2 3 4 5
x 1 3 3 5 5

インデクスが5から5が2個、3から3が2個、1から1が1個、、、と、NからNがa個、N-aからN-aがb個、、、と続けられればよいことがわかる。
また、例えば、

i 1 2 3 4 5
x 1 3 3 4 4

の場合は、インデクスが5のとき値が4なので、全消しすることができないことがわかる。
たとえば、この4を5に書き換えると、インデクスが5から5が1個、4から4が1個、、、となり全消しができる。


ここで、全消しができる条件を考えると、各インデクスの部分について、ボールの数字で、すべてのインデクスをボールの数字の連続でカバーできるかどうか?になっている。(上だと、各数字のインデクスのところから各数字の連続ですべてのインデクスをカバーできている)


(難しいが)、これを扱うのに、数字aについて、[a-数字aの個数,a]という範囲を考える。
上の全消しができない場合の例{1,3,3,4,4}を考えると、カバーしている範囲の数を各インデクスで考えると、

i 1 2 3 4 5
r 1 1 2 1 0

のようになる。
5のときカバーできていないので、他の2以上になっているところから5のところに数字を書き換えてあげれば全面カバーができることがわかる。

ここで、書き換えてあげる必要がある数字の個数というのは、カバーされていないインデクス==0になっているところの数なので、これを求めてあげればよい。


数字が変化した場合は、各数字の個数から上のカバーしている範囲の数のところが1か所減って1か所増える、という変化を起こすので、各単位時間での変化はO(1)で更新できる。
前の状態で0の個数がわかっていればこの更新時に0になるかどうかみれば、こちらもO(1)で更新できる。

AGC017 B. Moderate Differences

問題

N個のマスの一番左にA、一番右にBが書かれており、それ以外は空白になっている。
いま、空白のマスに、以下の条件を満たすように数字を入れることができる。

  • 隣接するどの2マスについてもその差はC以上D以下

このとき、条件を満たすように数字を入れることができるかどうか判定せよ。

制約

3 <= N <= 5*10^5
0 <= A,B <= 10^9
0 <= C <= D <= 10^9
変数はすべて整数

解法

Aの右隣の空白に何を入れられるか考える。
条件から、減らす方向に[A-D,A-C]と増やす方向に[A+C,A+D]の範囲の数字を入れることができる。
続けて、その隣には、ひとつ前の範囲[x,y]に対して、[x-D,y+D]の範囲が該当する。
最終的に、Bのマスまで来たとき、範囲にBが含まれているものが存在すればYESと答えられる。
しかし、この方法では、マスを進めるにつれ、範囲の数が2倍になっていくので、指数関数的に大きくなっていってしまう。


また、各マスで範囲が重なるような部分をマージするような方法をとったとしても、C==Dの時を考えればわかるように、範囲の数が多くなり、計算量が線形ではなくなるのでTLEしてしまう。


ここで気づきたいのは、各マスでは、「減らす方向への範囲更新」と「増やす方向への範囲更新」の2つの変化をさせられるが、これを行う順番はマスの位置に依存せず、それぞれを何回行ったか?だけでBのマスでの範囲が決まる。


増やす方向の回数をX回、減らす方向の回数をY回とすると、Y=N-1-Xとなる。
このとき、Bマスでの範囲は、[A+X*C-Y*D,A+X*D-Y*C]になる。
Xは、0回~N-1回まで考えられるが、それはループを回せばよいので、範囲内にBが入るかどうかを試せば、O(N)で求められる。

反省

変なコード書いてメモリ使い切ってPC再起動とかやらかしてしまっていた。
(さらに強制終了したせいでPC調子悪くなってダメ)
ちゃんと、計算量的使用メモリ的に問題ないアルゴリズムを考えてから書き始めること。

ARC076 E. Connected?

問題

x,y座標の(0,0)から(R,C)までの長方形を考える。
N個の長方形内の点のペアが与えられる。(各点はすべて異なる)
ペアの点同士を曲線で結びたい。ただし、長方形の外に出たり、交わってはいけない。
可能かどうか判定せよ。

制約

1 <= R,C <= 10^8
1 <= N <= 10^5

解説

Editorial - AtCoder Regular Contest 076 | AtCoder

いくつかサンプルを図で書いてみると、「ペアの点がどちらも長方形の周上にある場合、領域を2分割してしまって、それぞれ異なる領域にある点はどうやっても交差してしまう」というのがわかる。
そうでない場合は、曲線をうまく調整することで交差しないように書くことができることがわかる。


周上を1直線として見て、領域がoverlapしていないかを判定すればよい。


これは、「対応のある括弧の整合性判定(「((()()())((()()())))」みたいなの)」ともみなせるので、stackを使って判定すればよい。

反省

領域のoverlapの判定で、普通にミスってしまった。


領域を周上の座標にマッピングしたとき(l,r)とすると、l側でソートしておき、rをstackに入れながら処理していて、
今(l,r)を考えていて、直前のスタックにあるのがprとすると、

  • l < prの場合、かつ、pr < rの場合、オーバーラップしている
  • l < prの場合、かつ、r < prの場合、領域内にいるので、prとrをスタックに積んで次へ
  • pr < lの場合、新しい領域に入っているので、rだけスタックに積んで次へ

というやり方をしてしまった。
これだと処理が一つ抜けていて、例えば(1,5)、(2,3)、(4,6)のような場合、(2,3)の処理をした後、5と3がスタックに積まれているが、(4,6)を処理するとき、prで考えるべきは5と3両方なのに、3だけ確認して処理して、スタックに5と6みたいな処理をしてしまう。
なので、pr < lの時は、スタックからl < prになるまで全部取り出してあげる必要がある。

  stack<ll> st;
  st.push(R+R+C+C);
  int i=0;
  while(i<v.size()){
    ll l = v[i].l;
    ll r = v[i].r;
    ll pr = st.top(); st.pop();
    if(pr < l) continue;
    if(r<pr){
      st.push(pr);
      st.push(r);
    }
    else if(pr<r){
      cout << "NO" << endl;
      return 0;
    }
    i++;
  }
  cout << "YES" << endl;

ARC075 E. Meaningful Mean

問題

長さNの整数列aに対して、空でない連続する部分列の算術平均がK以上であるものの個数を答えよ。

制限

2 <= N <= 2*10^5
1 <= K <= 10^9, Kは整数
1 <= a[i] <= 10^9

解説

https://atcoder.jp/img/arc075/editorial.pdf
AtCoder Regular Contest 075 / Beginner Contest 063 解説放送 - YouTube


愚直に計算するとO(N^3)や、すぐ思いつく方法ではO(N^2)で、TLE。


ある範囲[l,r)について、条件は「(Σ_{i=l}^{r-1} a[i]) / (r-l) >= K」と書ける。
これを変形すると、

<=> Σ_{i=l}^{r-1} a[i] >= (r-l)*K
<=> Σ_{i=0}^{r-1} a[i] - Σ_{i=0}^{l-1} a[i] >= (r-l)*K
<=> Σ_{i=0}^{r-1} a[i] - r*K >= Σ_{i=0}^{l-1} a[i] -l*K

<=> b[r] >= b[l]
   ただし、b[x] = Σ_{i=0}^{x-1} a[i] - x*K

となる。
この変換によって、配列bの要素の大小関係の問題(転置数)になる。


この問題は、値を座圧っぽく変換して、BITを使って0~i-1まででb[i]以下の個数を求めればO(NlogN)で計算できる。

反省

  • 数式で書き出せるものは書いて、変形してみる

yukicoder No.519 アイドルユニット

問題

N人(2の倍数)のアイドルがいる。
全員ペアを組ませて売り出したい。
しかし、ペアには相性度が決まっており、すべてのペアの相性度の合計値が最大になるようにしたい。
相性度の合計の最大値を返せ。

制約

1 <= N <= 24
0 <= 各ペアの相性度 <= 1000

解説

一般的には、グラフの重み付きマッチングの問題らしい。
ここでは、各アイドルがペアを組んでいるかどうかを状態として持つbitDPを考える。

単純に考えると、「各状態でペアを組んでいないアイドル2人を選んで、状態を更新」するように計算する。

int N;
int cost[30][30];

int dp[1<<25];

int main(){
  cin >> N;
  rep(i,N){
    rep(j,N){
      cin >> cost[i][j];
    }
  }

  rep(i,1<<25) dp[i] = -1;
  dp[0] = 0;

  rep(i,1<<N){
    if(dp[i] < 0) continue;
    rep(j,N) if(((i>>j)&1) == 0){
      REP(k,j+1,N) if(((i>>k)&1) == 0){
        int ii = i | (1<<j) | (1<<k);
        dp[ii] = max(dp[ii], cost[j][k] + dp[i]);
      }
    }
  }
  cout << dp[(1<<N)-1] << endl;
  return 0;
}

これだとO(2^N * N^2)でTLEしてしまう。


実は上記のループは無駄なところがある。
状態が「100100」の場合を考える。
(この状態でjとkのループでは、「1**100」「1*01*0」「1*010*」「10*1*0」「10*10*」「1001**」を列挙して状態を更新している。)
ここで、
「100100」から「110110」と遷移して「111111」に至るケースと、
「100100」から「101101」と遷移して「111111」に至るケースでは、
同じペアの組み方なのに、2回計算してしまっている。

ペアの推移的には、
(0,3)->(0,3)(1,4)->(0,3)(1,4)(2,5)
(0,3)->(0,3)(2,5)->(0,3)(1,4)(2,5)
のような感じ。

このような場合、同じペアの組み方をするのは1通りだけ考えればよいので、状態の中でまだペアを組んでいないアイドル(状態が0のところ)を一人選んで、そのアイドルを必ず取る場合を考えて、そのペア候補だけ(kのループ)を考えればよい。

  rep(i,1<<N){
    if(dp[i] < 0) continue;
    rep(j,N) if(((i>>j)&1) == 0){
      REP(k,j+1,N) if(((i>>k)&1) == 0){
        int ii = i | (1<<j) | (1<<k);
        dp[ii] = max(dp[ii], cost[j][k] + dp[i]);
      }
      break; //これを入れるだけ
    }
  }

計算量は、O(2^N * N)になり、間に合う。

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)を生成するアルゴリズム

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


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


f:id:phyllo_algo:20170521015825p:plain
あとは再帰的に繰り返す。ただし、設置した番号より小さい番号は選ばない。(図の真ん中の状態でいうと、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の時、列挙。
f:id:phyllo_algo:20170521020857p:plain


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

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

解説

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

反省

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

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

気になったのでメモ。

モノイド

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

f:id:phyllo_algo:20170406004009p:plain
図は、配列(緑)に対して対応するセグメント木(青)を表す。
青の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」のところ)


query(l,r)関数はlとrに対応する葉ノードから親方向に向かって処理している。
f:id:phyllo_algo:20170406004014p:plain
赤のノードが演算対象。
範囲内の一番端から該当するノードをうまく選んでめぐって演算を繰り返す(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を減らしながら辿るのも考える。