CODE THANKS FESTIVAL 2018 G - Sum of Cards (500)
解法
最初maxの方を選択していって差分が小さい順に種類を増やしていくgreedyが思いつく
-> なんかgreedyはやばそうなのでDPかな?
(やばそうと言いつつも反例は思いつかなかった,教えて欲しい)
-> key: i 番目まで見た, j 種類出た として1枚ずつ表裏を決めていくDPが思いつく
-> が, あるカードを決める時, それが既出の数字かもしれない
-> {a}, {b} に数字 x は合計で高々2回しか出ないので依存関係は2個まで. この順番にDPしたい
-> 依存関係( a_i - b_i )に辺を貼る(典型)
-> 全て次数2なので自己辺を含むサイクルの集合になる(要出典)
-> 各辺について向きをつけていくと #(出現する数字) = #(入次数>0である頂点) となる.
よってサイクル上でDPしていきたい.
適当に視点を x_0 として x_0 -- x_1 -- .. -- x{n-1} -- x_n = x_0 の順番でDPすることを考える.
x_i -- x{i+1} の向きを決める時, 出現した数字の種類は次の
- x_{i-1} -- x_i の向きはどちらか
- x_{i+1} は終点か(i+1=nか)どうか,またi+1=nの時は x_0 -- x_1はどちらの向きか
公式の解説のDPの意味はこういう意味.
ただ x_0--x_1 の向きを決めた後,各々のDPは独立に更新できるので,
DPのキーは前に決めた辺の向きはどちらだったかを持っておけば良い.
tdp[ i ][ j ][ k ] :=
( 合計のmax s.t. (i+1) 番目の辺( x_i -- x{i+1} )の向きを決めて, j 種類の数字が出て, kはx{i+1}の入次数 )
と置いて,各連結成分ごとにDPしていく.
tdpの結果から各連結成分で ary[ j ] := (j種類出現するときの合計のmax) を求め,
dp[ i ][ j ] := ( i 番目の連結成分をみて全体で j 種類出現するときの合計max) として
dp[ i+1 ][ j ] = max_{ 0 <= k <= j } ( dp[ i ][ j - k ] + ary[ k ] ) を更新していく.
計算量は それまでみた頂点の合計 a, 新しく見るサイクルの頂点数 b とすると,
f(a+b) = f(a) + O(b2) + O((a+b)b) で,
f(x) = x2 とすると f(a+b) - f(a) = 2ab + b2 = O(ab) + O(b2) から f(N) = N2 が確かめられる.
(厳密な証明はわからない)
メモ
いくつか知ったこと
- 順列でグラフを貼るとサイクルの集合になる
- vector<vector<vector
>> hoge; みたいなのめっちゃ遅い(これだけでTLE&MLEした) - サイクル上のDPは最初の点,それまで見た点の状態をもつ
コード
DDCC 2019 予選 D - チップ・ストーリー ～黄金編～ (700)
解法
全力で必要条件を列挙していく.
Nのk進数表記が下の桁から n_0, n_1, n_2, .. であったとすると,
N = n_0 + n_1 r1 + + n_2 r2 + ..
a_k = n_0 + n_1 + n_2 + ..
N - a_k = n_1 (r - 1) + n_2 (r2 - 1) + n_3 (r3 - 1) で,
rx - 1 は r-1 で割り切れるので N = a_k (mod k-1) となる.
よって拡張Euclidの互除法を用いてmod lcm(2,3,..,30) の元でこれを求めてやり,
明らかに lcm(2,..,30) > 1e12 なので この解が条件を満たしてやるかを確かめてやれば良い.
拡張Euclidの互除法については下を参照.
メモ
思いつかなかったけど,n進数の各桁の和で割と一般的に使えそうな気がした.
後CRT(中国人剰余定理)はそもそも知らなかったので...
コード
数列操作に関する手筋まとめ
とりあえず考えること
- 要素/総和のmod/パリティに注目する
- 操作回数を求めることができるか(特に総和を用いて)
- 逆操作が可能か
操作が単純な操作に分解できるか
階差数列を考える
数列2つを一致させるなら差を取る
操作の縮約ができないか/周期を持たないか
- 上の典型的な場合として,単純な一連の操作を考える(最初から順番に操作していくなど)
- 数列を自分で用意することができる場合は,数列も単純なものを用意する({1,2,..}, {n,n,...})
例題 (順次追加)
2つの数列の差を取る & 操作回数が決まる
逆操作
D - Decrease (Contestant ver.)
操作できる数に制約があるので逆操作を考えるのは難しい.
単純な数列で単純な一連の操作を考えると縮約ができる
ARC 086 D - Non-decreasing (600) - 主食は米
単純な操作を考えよう
総和に注目する -> 逆操作を考える -> 階差数列を見る -> 逆操作を分解する
SoundHound Programming Contest 2018 Masters Tournament Open B - Neutralize(400)
解法
- 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
解法
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)
解法
解説にある通り,上書きしていくような問題では操作列を逆に見ていって,そのマスで一番最初の操作で色が確定すると考えるのが良くて,そうするとそのマスに関してそれ以降の色の変化を考えなくて良くなる.
さて,逆順に見ていったときの最初(つまり元の操作で最後)の操作を固定する. これは2(N-K+1)通りある.
後は実験していって気づく必要があるが,それ以外のマスは自由に変えることができる(外側から1つずつずらして範囲を塗っていけばいい)
なので,これをループを回していけばいい. 1回の計算に数列の範囲の最大値が入っているので累積和を使って高速する.
コード
Mujin Programming Challenge 2018 C - 右折
解法
最初に右を向いていて,次に右折するパターンを考える.
各マスで上方向に累積和をとると下に何マス進めるかというのがO(NM)でわかる.
それを左方向に累積和をとっていくとその場所を始点として1マス以上進み,右に何マス進めるかというのがわかるのでこのパターンは解けた.
これを全方向実装するのはかなりめんどくさいので,迷路自体を回転してループを4回回せばいい.
メモ
公式解答は鮮やかすぎて思いつかないので...
