kurarrr's memooo

主に競プロ備忘録

SoundHound Programming Contest 2018 Masters Tournament Open B - Neutralize(400)

AtCoder DP 数列操作

解法

  • K個以上の区間は消せる
  • Greedyは厳しそう
  • dp[i] := (最後に[i,i+K) を消したときのmax ) とすると..?
  • dp[i+1] = max_{ j, [i,i+K) と [j,j+K) の区間が被っている } ( dp[j] + sum_b [j+K, i+K) ) と,
  • dp[i+1] = max_{ j, [j,j+K) の区間は [i,i+K) と被らない } ( dp[j] + sum_b[i,i+K) ) の漸化式が立つ

  • 愚直O(N2), 累積和+区間和とRMQのSeg木でO(NlogN)だが400点なのでさすがに...

  • 上の置き方は最後に消した場所を持っていて,まとめ方が良くなさそう

  • どの範囲が0か,ではなく末尾が0かだけを持っておこう
  • dp[i][j] := ( b[0,i) についての max, j は末尾が0かどうか ) とおく
  • dp[i+1][1] = max(dp[i-K+1][0] , dp[i][1] )
  • [i-K+1, i+1) を消す時,その範囲の j==0 の場合の更新はないものになる and 1個前が0の時はその数は好きに0にできるため
  • dp[i+1][0] = max(dp[i][0], dp[i][1]) + b[i] という漸化式が立つ

メモ

飛び地で更新する?系のDPに弱い

コード

Tenka1 Programmer Contest 2018 C - Align

AtCoder 必要条件の列挙

解法

1,..,N の順列を p1,..,pN として, 最大化したい関数は
|A_p1 - A_p2| + .. + |A_pN-1 - A_pN| になる.

目的関数の絶対値を外したい気持ちになるので,そのためには数列の順序付けが必要になる.
それを念頭に起きつつ最適解の必要条件を列挙してみる.
すると A_p1,.., A_pN が単調増加/減少になっていてはダメで, 凸凹のような形になっている必要があることがわかる.
例えば a < b < c であれば a c b と並んでいた方がいい.簡潔な証明は解説に載っている.
これを式で書くと
A_p1 >= A_p2 <= A_p3 >= .. or A_p1 <= A_p2 >= ..
となっている.
前者の時, N=evenとすると目的関数は
(A_p1 - A_p2)+(A_p3-A_p2) + .. + (A_p{N-1} - A_pN )
= 2(A_p1 + .. + A_p{N-1}) - A_p1 - 2(A_p2 + .. + A_pN) + A_pN
となる.
よって{A} を sortしてgreedyに当てはめていけばいい.
この場合だと奇数項が昇順sortしたときの後ろ半分(ただしA_p1がその中で最小のもの),
偶数項が前半分(ただしA_pNがその中で最大のもの) になる.

コード

AGC 008 B - Contiguous Repainting (400)

AtCoder 実験

解法

解説にある通り,上書きしていくような問題では操作列を逆に見ていって,そのマスで一番最初の操作で色が確定すると考えるのが良くて,そうするとそのマスに関してそれ以降の色の変化を考えなくて良くなる.

さて,逆順に見ていったときの最初(つまり元の操作で最後)の操作を固定する. これは2(N-K+1)通りある.
後は実験していって気づく必要があるが,それ以外のマスは自由に変えることができる(外側から1つずつずらして範囲を塗っていけばいい)

なので,これをループを回していけばいい. 1回の計算に数列の範囲の最大値が入っているので累積和を使って高速する.

コード

Mujin Programming Challenge 2018 C - 右折

AtCoder 累積和

解法

最初に右を向いていて,次に右折するパターンを考える.
各マスで上方向に累積和をとると下に何マス進めるかというのがO(NM)でわかる.
それを左方向に累積和をとっていくとその場所を始点として1マス以上進み,右に何マス進めるかというのがわかるのでこのパターンは解けた.

これを全方向実装するのはかなりめんどくさいので,迷路自体を回転してループを4回回せばいい.

メモ

公式解答は鮮やかすぎて思いつかないので...

コード

AtCoder Grand Contest 028 B - Removing Blocks (600)

AtCoder 数え上げ 確率

解法

解説の1つの解釈として.

解説/解説放送と同じように, iをremoveした時に A_j が足されるかどうかを考える.
ただし,確率ではなくそのような順列の場合の数を数え上げることにする.

事前準備として,n個の順列のうちで
そのうちの要素 x,y (x!=y) に関して x<y が成り立っているものは n!/2 になる.
これをもう少し考えると x_1 < .. < x_k+1 のk個の不等号があるものは n!/(k+1)! になることがわかる.
(n個の場所からx_iの場所k+1個を選ぶ) * (残りのN-k-1個は自由に並べる)
= nC(k+1) * (n-k-1)! = n!/(k+1)!
と考えても良い.

これを使って,上の順列が何通りあるかを数える.
簡単のため, i < j と仮定して
x_0 = i, x_1, ... , x_k, x(k+1) = j とする. (k = j-i-1)
ここで, 求めたい順列を束縛する不等式は i の後にx_1, x_2,.., x(k+1) が出るという条件のみを満たしていれば良いことを考えると
x_0 < ( x_1, x_2, .. , x(k+1) を好きに並べて不等号で繋いだもの ) であることがわかる.
これは, x_1,...,x(k+1) の順番が決まればk+1個の不等号が繋がっているので N!/(k+2)! 個ずつある.
このいずれかを満たす順列(つまり順列の和集合)を求めればよく,これらは全て排反であるため
合計で n!/(k+2)! * (k+1)! = n!/(k+2) = n!/(j-i+1) 個あることがわかる.

ここからは解説と一緒で,
A_j * sum_i{ n!/abs(j-i+1) } のjに関する和が答えになる.
調和級数を事前に計算しておけばO(N)

メモ

確率として典型処理するようにしたほうがいい気もする..

コード

「みんなのプロコン」2017 本選 A - YahooYahooYahoo

AtCoder DP 文字列 競プロ

解法

典型的な文字列AとBの編集距離を求める問題において, B = "yahoo" と固定したバージョンになる.
(は正規表現における閉包)

i=1,2,.. として 部分文字列S[0,i) を最終的な状態 "yahoo"* の前半と一致させることにしよう.
それまでの最小の編集距離に注目する上では, 末尾が "yahoo" の何番目になっているかということにだけ注目すれば良い.
よって, dp[i][j] := (S[0,i) を 末尾が"yahoo"のj番目(0-index)になるようにした,最小の編集距離 ) とする.

すると, 遷移は dp[i][j] からs[i] をそのまま足して 1<=k<=5 回末尾に insert, または末尾を 1回deleate したパターンを考えればわかる.
1<=k<=5 回でなく1回だけinsertすると考えて dp[i][j] から dp[i][j+1] に遷移させることもできるが, その場合解説にあるように2周しないといけない.
初期値と答えに注意.

コード

DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選 C - ロト2

AtCoder 競プロ 数列の組の数え上げ 最大公約数 分布

解法

a_i は K と共通の因数しか注目しなくて良いことがわかるので, a_i = gcd(a_i, K) とみなして良い.
Kの約数は高々 2sqrt(K) しかないので(エラトステネスの篩をやっていくとわかる), a_i として現れる数は O(sqrt(K)) しかない.

定跡としてこの分布をとると,(つまり cnt[a] := aの現れる回数 とする)
全ての a<=b (a,bはcntのkey) についての全探索がO(K)となって間に合う.

ただし a==bのときは abがKの倍数になるならば cnt[a](cnt[a]-1) を足すことに注意(自分自身とは組にできないため)

コード