CODE THANKS FESTIVAL 2018 H - Median Game (500)
解法
スコアは中央値なので,そのままやるとこれまで書いた和を全て持っておく必要がある(どれも中央値になり得る)
=> これは当然全探索に近いので不可能
=> 中央値は2ぶたんがやりやすい(X以上がY個の条件が判定しやすい) という典型もあり,判定関数を作って2ぶたんをしようという気持ちになる
すると判定をO(N2)ぐらいのDPでやろうというのが自然な流れになる.
注意としては,ゲームでDPをやるときは後ろから(そうしないと最終的にmax/minに持っていけない)
x以上のスコアを取れるか？という判定をすることを考える.
dp[ i ][ j ] := ( i ターン経過, a[j,N) でゲームをした時の x 以上の個数 ) とやると, O(N3) かかってしまう.
かといって遷移で x 以上でなるべく遠くをとったほうがいい みたいなのは成り立たない.(間違った)
ここで削れる要素は i ターンで, 先手/後手を持てば良さそうだが, x 以上が半分以上か?というのが判定できなくて困る.
こういうときは 値として #(x 以上) - #(x 未満) を持てば良い (半分以上か？を判定する典型)
( #(x以上)/ターン数 を最大化するようにこの2つの数を持ってもいいのか.. ? )
後は公式解説と同じ.
コードでは
dp1[ i ] := (先手番で,#(x以上) - #(x未満) の max )
dp2[ i ] := (後手番で #(x以上) - #(x未満) の min )
としている.
メモ
500ではない
コード
CADDi 2018 D - Harlequin (500)
解法
公式動画&解説で基本的にわかるので個人的な備忘録にとどめておく.
ゲームの問題の基本的な戦略として,手で書いて実験をする.
N個の数のケースで実験すると1回の遷移が O(2N) になるので, N=2で実験する.
公式解説のようなグラフを書いて実験をすると良い.
これは結構定番で
ARC 072 D - Alice&Brown - 主食は米
とかもこれを使って解ける.
2個で大体のパターンがわかると一般化できそうだという気がしてくる.
この際に用いるのが相手がどのような手をとっても同じ状態に戻せるということで,
この問題であれば 全て偶数/それ以外 の状態に全ての状態をまとめることができ,
全て偶数という状態が最終的に相手の負けになるので,解説の答えが出る.
メモ
N=2 の状態で実験をしてグラフを書くのはマストな気がする.
最初からNが大きい状態で考えてしまって解けなかった.
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がその中で最大のもの) になる.
