kurarrr's memooo

主に競プロ備忘録

第三回 アルゴリズム実技検定 (PAST) N - 入れ替えと並び替え

AtCoder

問題

解法

解説にもある通り、バブルソートを用いてソートすれば全体の計算量は O(Q * (1回の隣接swapにかかる計算量) ) に収まる。
swapはもちろん O(1) になるが、今回は候補を更新する & 次の候補を見つける必要がある。

swapごとに a[idx] > a[idx + 1] を満たす idx (これを転倒数と呼ぶ) を candsに入れ、満たさなくなったものは消していくことにすると、
cands に入ったり消えたりするような数は idx - 1, idx, idx + 1 のうちどれかになるのでこれらをチェックする。(update関数のところ)
このupdate操作を繰り返していけば区間を正しくソートすることができる。
どこをswapするかは [x[q], y[q]] から適当に選んでいけばいいが、今回はlower_boundを使っている。

全体の計算量は O(Q log N + N)。

コード

void solve(long long N, long long Q, std::vector<long long> t, std::vector<long long> x, std::vector<long long> y){
  set<Int> cands;
  vi a(N);
  iota(ALL(a), 1LL);
  auto update = [&](Int idx){
    swap(a[idx], a[idx + 1]);
    for(Int temp = idx - 1; temp <= idx + 1; temp++){
      if(temp < 0 || temp + 1 >= N) continue;
      if(a[temp] < a[temp + 1]) cands.erase(temp);
      else cands.insert(temp);
    }
  };
  rep(q, Q){
    x[q]--; y[q]--;
    if(t[q] == 1){
      update(x[q]);
      continue;
    }
    for(;;){
      auto itr = cands.lower_bound(x[q]);
      if(itr == cands.end() || *itr >= y[q]) break;
      // bubble sort
      update(*itr);
    }
  }
  rep(i, N) cout << a[i] << ( i == N-1 ? "\n" : " " );
}

template is here

setのlower_boundがO(NlogN)になるミス

競プロ

TL;DR

set<int> st;
lower_bound( st.begin(), st.end(), 0); // これは O(NlogN)
lower_bound( 0 ); // これはO(logN)

解説

この前のABCでハマってしまった.
上のコード
下のコード

異様に遅いしlower_boundあたりがもしかして O(N) になってないか?と思って書き直したらACした. (本当はO(NlogN))
なぜかというと, 上のコードをやるとsetのメンバ関数が呼ばれないため

template <class ForwardIterator, class T>
  ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
  ForwardIterator it;
  iterator_traits<ForwardIterator>::difference_type count, step;
  count = distance(first,last);
  while (count>0)
  {
    it = first; step=count/2; advance (it,step);
    if (*it<val) {                 // or: if (comp(*it,val)), for version (2)
      first=++it;
      count-=step+1;
    }
    else count=step;
  }
  return first;
}

lower_bound - C++ Reference

この lower_bound が呼ばれ, O(logN) 回だけ advance(it,step); が呼ばれる.
setのiteratorはRandomAccessIteratorでないのでこれは大体 O(N), 全体では O(NlogN) かかってしまう.
気をつけような

はてなブログで数式をなんとかする & mathjaxが表示されなくてややハマった

はてなブログで数式をなんとかする

  1. mathjaxを導入します 参考
  2. 完

これは30秒ぐらいで終わります

mathjaxが表示されなくてややハマった

$$
f(n)=\sum_{0\leq i \leq n} i^2
$$

これをmarkdownでプレビューすると f:id:kurarrr:20190811165749p:plain
こうなるので

$$
f(n)=\sum_{0\leq i \leq n} i^{2}
$$

こうすると
$$ f(n)=\sum_{0\leq i \leq n} i^{2} $$ こうなります

texならいけるけど mathjaxだと{}を省略できないみたい

日経コン 2019 E - Erasure (700)

AtCoder DP

解法

dp[ i ][ j ] := #( [0,j) のみ消されていて, i-1 開始の区間を列挙し終えた )
として, i 開始の区間を考える.
半開区間で考えているので消す区間 [l,r) の満たす条件は r-l >= K+1.

新しく [0,x) から [0,j) ( x < j ) まで消す場合
[ i, j ) は必ず選ばなければならず, (よって j - i >= K+1 )
残りの [ i, i+K+1 ), ..., [ i, j-1 ) の j-i-K-1 は自由に決められるので
dp[ i+1 ][ j ] += ( sum _ { i <= x < j } dp[ i ][ x ] ) * 2j-i-K-1

一方, dp[ i ][ j ] から dp[ i+1 ][ j ] に遷移する場合は
i から始まる区間が j を超えてしまう場合( j < i+K+1 )は
dp[ i+1 ][ j ] += dp[ i ][ j ]
超えない場合は [ i, i+K+1 ), ... , [ i, j ) を自由に選べるので
dp[ i+1 ][ j ] += dp[ i ][ j ] * 2j-i-K

これを単に累積和で処理してやればいい.

メモ

簡単なはずなんだけどこんがらがってしまった..

コード

ARC 094 F - Normalization (700)

AtCoder DP 文字列 必要条件の列挙 文字列のmod

解法

n文字からなる文字列の変換の典型として,
'a' -> 0, 'b' -> 1, 'c' -> 2 に変換して総和のmod3に注目する

この場合でも総和のmod3は保存されることがわかる.

この非自明な必要条件が本質.
更に実験すればわかるが,1回以上の操作によって a[i] == a[i+1] なる i ができる.

ここまで得た必要条件を列挙すると,できうる文字列は
(1) mod3 の総和が s と等しい (2) 1回以上の操作を経由すると a[i]==a[i+1] なる i がある
となる.
後は 必要条件を列挙が実は必要十分条件になっている というAtCoderの典型パターン.
実は (1) (2) を満たす文字列は N>=4で全部作ることができるらしい(証明してない)

後はDPで数え上げる. dp[ i ][ j ][ k ][ l ]
:= ( i 文字からなる文字列で, j=1なら(2)を満たすi'が存在し, 末尾の文字がk, 総和mod3がl ) として, 次の文字によって遷移する. O(N).

メモ

これすごい.

DPでやろうとしたら無理なのには気づいた. 例えば両端の文字を持っておいて区間dpをやろうとしても [l,x) と [x,r) -> [l,r) と遷移した後でも, s[x],s[x+1] を変化させたら再び [l,x) の範囲で操作ができるようになる可能性がある.
なのでこの方針は諦めてできる文字列の必要条件を列挙するべきだった.

コード

KEYENCE Programming Contest 2019 D - Double Landscape

AtCoder 順列 数え上げ

反省

解法は解説見ればわかるのでなんで反省点のみ.

  • {a}, {b} をsortして右下から入れていこうとしていた

-> 明らかに煩雑. 典型要素として perm を考えるときには挿入/数字が入る場所から決めていく
-> 上の数字から入れていくのを

  • a_i = b_j = x なる i, j があるならば (i, j) は一意に定まる

-> これは実験でわかった.

  • 上から入れていく

-> これは考察できていたけどふわっとしていた.
x が入ることができるマスは y (<x) も入ることができる単調性があることを考えるとこれしかなさそう
ただし, y が一意に定まる a_i = b_j = y なる i, jが存在しないケースに限る(これのせいで混乱した)

まとめ

順列は数字の入る場所から考えていく
ただし単調性があるような順番に入れていくのが良い.
今回のような入ることのできる場所を掛けていくような場合には,
入れる候補が今まで入れた場所を含んでいるという性質が重要.

Educational DP Contest / DP まとめコンテスト 復習

AtCoder DP DPのkeyの変換

メモ

17完. 解けない問題いっぱいあるなあ
集めるDPの方がバグらせにくくて(当社比),メモ化にもしやすいのでほぼそっちで書いた.
簡潔なまとめはプロのツイッターを見るのが良い.

A

dp[ i ] := min( dp[i-1] + cost(i-1,i), dp[i-2] + cost(i-2,i) )
cost(i,j) = abs( h_i - h_j )
O(N).

Submission #3936500 - Educational DP Contest

B

dp[ i ] := min_{ i-K <= j < i } ( dp[ j ] + cost(j,i) )
cost(i,j) = abs( h_i - h_j )
O(NK).

Submission #3937040 - Educational DP Contest

C

dp[ i ][ j ] := max( 現在 i-1 日目 で 前日に j 番目の活動をした時の幸福度 )
dp[ i ][ j ] = max_{ k != j }( dp[ i-1 ][ k ] + h[ i ][ k ] )
h[ i ] = { a_i, b_i, c_i }
O(N).

Submission #3937463 - Educational DP Contest

D

dp[ i ][ j ] := max( i-1 番目まで入れるか決めて重さ j の時の価値の総和) dp[ i ][ j ] = max( dp[ i-1 ][ j ], ( j - w_i >= 0 ? dp[ i-1 ][ j - w_i ] : -INF) )
O(NW).

Submission #3937463 - Educational DP Contest

E

dp[ i ][ j ] := min( i-1 番目まで入れるか決めて価値 j の時の重さ)
dp[ i ][ j ] = min( dp[ i-1 ][ j ], ( j -v_i >= 0 ? dp[ i-1 ][ j -v_i ]: INF ) )
O(N sum(v_i )).

Submission #3938707 - Educational DP Contest

F

N = |s|, M = |t|
dp[ i ][ j ] := max( s[0,i) , t[0,j) の LCS(最長共通部分列) )
dp[ i ][ j ] = max( dp[ i-1 ][ j ], dp[ i ][ j-1 ], dp[ i-1 ][ j-1 ]+ (s[ i-1 ] == t[ j-1 ] ? 1 : 0) )

復元は dp[ N ][ M ] からスタートして ans = (空文字列)とし,
今 dp[ i ][ j ] を見ているとして
if s[ i-1 ] == t[ j-1 ] ans += s[ i-1 ]
else ( i-1, j-1 ), ( i-1, j ), ( i, j-1 ) のうち dpが等しい所に遷移.
i-1 < 0 or j-1 < 0 になったら ans を reverseして終了.
dp[ i-1 ][ j-1 ] + 1 == dp[ i ][ j ] でも s[ i-1 ] == t[ j-1 ] とは限らないので注意 (他の所から遷移してきたかもしれない)
O(NM).

Submission #3940676 - Educational DP Contest

G

dp[ u ] := max( uに至るパスの総長 )
トポロジカルソートをしてその順に
dp[ u ] = max( dp[ u ], dp[ v ] + 1 ) if v->u のパスが存在
さすがに配るDPの方が自然な気がする.
O(N).

Submission #3941322 - Educational DP Contest

H

dp[ i ][ j ] := sum( ( i, j ) に至る経路 ) dp[ 1 ][ 1 ] = 1, ans は dp[ H ][ W ]
if ( i, j ) が壁でない dp[ i ][ j ] = dp[ i-1 ][ j ] + dp[ i ][ j-1 ]
else dp[ i ][ j ] = 0
O(HW).

Submission #3941908 - Educational DP Contest

I

dp[ i ][ j ] := prob( i 枚目まで投げて j 回表)
dp[ i ][ j ] = p * dp[ i-1 ][ j-1 ] + (1-p) * dp[ i-1 ][ j ]
dp[ 0 ][ 0 ] = 1
ans = sum{ i > floor(N/2) } ( dp[ N ][ i ] )
テストケース,結構誤差とかに気を使いそう.(こどふぉだとmodでやるよね)
O(N2).

Submission #3942299 - Educational DP Contest

J

dp( i, j, k ) := ( 寿司が1,2,3個乗った皿が i, j, k 枚あるまでの期待値 )
次に1,2,3,0個乗った皿をとる確率をp,q,r,sとすると
p = i / N, q = j / N, r = k / N, s = 1 - ( p + q + r )
p,q,r,s それぞれの確率で,その後に何回かかるかの期待値は
dp( i-1,j,k ), dp( i+1,j-1,k ), dp( i,j+1,k-1 ), dp( i,j,k ) になり,
それぞれで必ず1回は試行が増加するので
dp( i, j, k ) = p * dp( i-1,j,k ) + q * dp( i+1,j-1,k ) + r * dp( i,j+1,k-1 ) + s * dp( i,j,k ) + 1
の式が成り立つ.
dp( i, j, k ) の項を移行してメモ化再帰で解く
一瞬ループがないか気になってしまうが, まあよく考えればないことがわかる
期待値漸化式は けんちょんさんのブログ

Submission #4704505 - Educational DP Contest

K

a_i は1回しか使えないのかと誤読していた.
dp[ i ][ j ] := ( i 個石が残っている, j = (先手番 ?) の時、値が1なら先手勝ち )
として再帰してやればいい.
O(K).

Submission #4095737 - Educational DP Contest

L

dp[ i ][ j ] := ( a[ i, j ) からゲームを始めた時の得点. j - i = N mod 2 なら先手番なのでmax, 後手番ならmin )

if 先手番 dp[ i ][ j ] = max( dp[ i-1 ][ j ] + a_i, dp[ i ][ j-1 ] + a_j )
else dp[ i ][ j ] = max( dp[ i-1 ][ j ] - a_i, dp[ i ][ j-1 ] - a_j )

O(N2).

区間DP/ゲームはメモ化がやりやすいね

Submission #3945707 - Educational DP Contest

M

dp[ i ][ j ] := sum( i 人までに j 個を配る )
dp[ i+1 ][ j + k ] += dp[ i ][ j ] ( 0 <= k <= a_i )
そのままやると O(NK2) でTLEなので imos法を使う.
(集めるDPなら累積和)
O(NK).

Submission #3946111 - Educational DP Contest

N

dp[ l ][ r ] := min( [ l, r ) スライムを合体させるコスト )
最後に [ l, x ) と [ x, r ) から各々できるスライムを合体させるとしたら,
各々は a[ l, x ) , a[ x, r ) なので
dp[ l ][ r ] = min_{ l < x < r} ( dp[ l ][ x ] + dp[ x ][ r ] + a[ l, x ) + a[ x, r ) )
aは累積和をとっておこう.
O(N3).

Submission #3947535 - Educational DP Contest

アルゴリズムイントロダクションに乗ってる連鎖行列積とほとんど一緒だなあと思った.
このスライドの44ページ目から.

O

dp[ i ][ s ] := ( i 人目までの男性をマッチングさせて, 女性集合 s が残っている )
dp[ i ][ s ] = sum_{ j in s } ( dp[ i-1 ][ s \ j ] )
O( N2 2N ).

Submission #3947997 - Educational DP Contest

P

0を勝手に根として,
dp[ u ][ i ] := sum( u 以下を塗り, u は i==1 ? 黒 : 白 とする塗り方 )
dp[ u ][ 0 ] = prod _ { v in child( u ) } ( dp[ v ][ 0 ] + dp[ v ][ 1 ] )
dp[ u ][ 1 ] = prod _ { v in child( u ) } ( dp[ v ][ 0 ] )
どちらも子がない場合は 1.
ans = dp[ 0 ][ 0 ] + dp[ 0 ][ 1 ]
O(N).

Submission #3948387 - Educational DP Contest

和と積がこっちゃになる人は和集合(Or),積集合(And)を考えるとわかりやすいかも

Q

そのまま式を立てると
dp[ i ][ j ] := max( 左から i 本目まで見て一番高い花が j 本目の時の美しさの総和 )
dp[ i+1 ][ i+1 ] = max _ { h j < h_i } ( dp[ i ][ j ] ) + a_i
dp[ i ]の列は1つの値しか更新しなくて良いことに気づくので1次元にしよう.
( ( i, k) -> ( i+1, l) , ( i, l ) -> ( i+1, m) のような更新があると1次元では困る )
すると dp[ i ] := max( 一番高い花が i 本目である時の美しさの総和 ) となる.
遷移は
dp[ i ] = max{ j < i, h _ j < h _ i }( dp[ j ] ) + a_i
左から更新していくと j < i は常に満たされるので h_j < h_i なるものの中から max をとってやれば良い.
これは h_i をDPのキーとして持ってやればSegmentTreeでできる.
h_i が大きいと座圧してやる必要があるけど,これは順列になっているのでそのままできる.
よってDPテーブルをSegmentTreeで作って,
dp[ k ] := max( 一番高い花の高さがk の美しさ )
dp[ k ] = max_{0 <= j < k} ( dp[ j ] )

O(N logN).

Submission #3948747 - Educational DP Contest

R

これ数理情報学の院試で見たやつだ
A = (隣接行列) として Ak _{i, j} = ( i -> j の総長 k のパスの本数 ) になる.
これ自体知ってても良さそうだけど
dp[ k ][ i ][ j ] := ( i -> j の総長 k のパスの本数 ) とすると制約見て行列積しかないねってなりそう.
O(N3 log K).

Submission #3948940 - Educational DP Contest

S

桁DP.
dp[ i ][ j ][ k ] := sum( 上から i 桁まで決めて数字の総和 mod D が j , k == 1 ならその桁まで K と等しい )
dp[ 0 ][ 0 ][ 1 ] = 1 から
dp[ i+1 ][ ( j + K[ i ] ) % D ][ 1 ] += dp[ i ][ j ][ 1 ]
for 0 <= d < K[ i ] : dp[ i+1 ][ ( j + d ) % D ][ 0 ] += dp[ i ][ j ][ 1 ]
for 0 <= d <= 9 : dp[ i+1 ][ ( j + d ) % D ][ 0 ] += dp[ i ][ j ][ 0 ]
と配っていく.
O( |K| D).

Submission #3949252 - Educational DP Contest

T

小さい順に挿入していくことを考えすぎてできなかった.

dp[ i ][ j ] := #( [0,i) の位置まで配って末尾より大きいものが j 個残っている状態 )
i + j <= N を満たす.
この時, 状態 ( i , j ) からの遷移を考える.
s[ i-1 ] = '<' の時,
j 個の置く数の候補があり dp[ i ][ j ] を dp[ i+1 ][ k ] ( 0 <= k < j ) に足し込めばいい.

'>' の時,
N-i-j 個の候補があり(末尾より小さい数), dp[ i ][ j ] を dp[ i+1 ][ k ] (j <= k < N-i )に足しこむ.

愚直 O(N3) 、 imos法を使うと O(N2) になる.

Submission #4385313 - Educational DP Contest

U

p[ s ] := ( 集合 s を全員同じグループにした時に得られる得点 ) を前計算し,
dp[ s ] = max( 集合 s を使った時の合計得点 )
漸化式は
dp[ s ] := max_{ t = subset( s ) } dp[ s \ t ] + p[ t ]

各 s に対して 2N 列挙して部分集合なら遷移みたいな実装をすると O(4N) になるが,
正しく部分集合を列挙すると s で立っているビット数を b として
sum_ { 0 <= b <= N } comb(N, b) 2b = 3N となる.
詳しくは こことか

Submission #3970446 - Educational DP Contest

V

いわゆる全方位木DPというやつ.
dp[ u ] := ( u以下の部分木で u を黒で塗る塗り方) として,
dfsで0を根として dpテーブルを埋める.
その後もう一回 dfsをしていく, この際呼び出し元 u から子 v を呼んだ際に
pval := ( 木全体からvを根とする部分木を除いた木で u を黒に塗る塗り方 ) を持っていく.
すると頂点 u に関する答えは PI( dp[ vの子 ] + 1 ) * ( pval + 1) になる (PIは積)
後は v から その子に pvalを持って伝播させていけばいい.
これは累積和の要領で [ 0,i ) の積, [ i, sz(vの子) ) の積を持っておけば,
i 番目の子に関して pval = PI _ [ 0, i ) * PI _ [i+1, sz) で計算できる.

木と計算量 後編 〜全方位木DP〜 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

Submission #4387140 - Educational DP Contest

W

やっと解説ACした. 要復習.

区間の操作関連でDPするときに,区間が含まれたときではなくその終点で操作を行う,みたいなやつ.
この解説がわかりやすすぎて書くことない.

Submission #5033754 - Educational DP Contest

X

まず荷物の置き方について, 上から Xの荷物, (w_1,s_1) , (w_2,s_2) と置くことを考える.
この時満たすべき条件は
X <= s_1 and X + w_1 <= s_2
<=> X <= min(s_1 , s_2 - w_1 )
これを swapすると X <= min( s_2 , s_1 - w_2) .
これが上における荷物の上限ということになる.
w_1 を上に置きたい時 min( s_1 , s_2 - w_1 ) >= min( s_2 , s_1 - w_2) .. (1) であればいい.
(1) <=> s_1 >= min( s_2, s_1 - w_2 ) (2) かつ s_2 - w_1 >= min( s_2, s_1 - w_2) (3) となる.
(2) は s_1 >= s_1 - w_2 から必ず満たす.
(3)は s_2 - w_1 >= s_2 が成り立つことはないため s_2 - w_1 >= s_1 - w_2 と同値.
よって s_1 + w_1 <= s_2 + w_2 を得る. つまり { s_i + w_i } で並べていけばいい.

dp[ i ][ x ] := max( i 番目のブロックまでを考え,合計の重さ x の時の価値)
とすれば
dp[ i+1 ][ x ] = max( dp[ i ][ x ], ( x-w_i <= s_i ? dp[ i ][ x - w_i ] + v_i : -INF) )

重さは最悪ケースの max( w ) + max( s ) 程度を考えればOK.
( max( w ) の上に max( s ) が乗っている )

Submission #4386153 - Educational DP Contest

Y

数学でもそうだけど,こういうの大体余事象を数える.
この際 i 番目の点を初めて通ったという条件を入れると独立に数えられる.
{ (r_i, c_i) } に (H-1,W-1) を加えて pair の昇順sortし,
dp[ i ] := ( i 番目の点を初めて通るような ( r_i, c_i ) へのパスの数 ) とすれば,
dp[ i ] = f( r_i, c_i ) - sum _ { j, r_j <= r_i かつ c_j <= c_i } ( dp[ j ] * f(r_i - r_j, c_i - c_j ) )
ただし f( r , c) = {r+c} C {r} これ身に付けたい.

Submission #4384588 - Educational DP Contest

Z

dp[ i ] = min{0 <= j < i } (dp[ j ] + (h[ i ] - h[ j ])2 + C )
愚直O(N2)だがConvexHullTrickを使うとO(N)になる.
(右辺) = min{ 0 <= j < i }( -2 h[ j ] * h[ i ] + ( dp[ j ] + h[ j ]^2 ) )+ ( h[ i ]^2 + C )
で左の min の部分が求められればいいが, これは h[ i ] を x とみなして CHTを適用すれば求められる.
dp[ i ] を求めた後は 直線 -2 h[ i ] * x + ( dp[ i ] + h[ i ]^2 ) をCHTの直線群に追加する.
-2h[ i ] は単調増加するのでこれは可能である.

Submission #4707883 - Educational DP Contest