AGC 030 B - Tree Burning

• 問題

解法

お絵描きしたのでメモ.

部分点は O(N²) の区間DP.

それ以上に早くやるにはどうするか.
遷移が O(1) なので状態を減らすしかない.
しかし,DPテーブルは疎でもなく,あまりまとめられそうにもない.
よってある状態(操作)を禁止して状態を減らすことを考える.

ここ とかがわかりやすい.

(直進) - (往復) - (直進) みたいな操作列が存在するならば,
最後の直進の終点が往復の終点になるように(直進) - (往復) の操作列に替えることができて,
これは元の移動距離よりも大きくなる.
よって (直進) - (往復) の操作列だけを考えてよく,状態が減らせた.

あとは累積和を使えばO(N)で解ける.

Hello 2019 D. Makoto and a Blackboard

• 問題

問題概要

自然数Nに対し次の操作をK回繰り返す. K回後の期待値を求めよ.

• 自然数に対してその約数を等確率で1つ選び,その約数で置き換える.

1 <= N <= 10¹⁵ , 1 <= K <= 10⁴

解法

本番は愚直なDPを定数倍高速化しようとしたが無理だった.

これは約数を全列挙した後, dp[ i ][ j ] := ( i 回目の操作で j 番目の約数である確率,または期待値 ) とやるDP.
約数の数 S とすると, S 〜 2¹³ 〜 8 * 10³ 程度なので( 13番目の素数までの積〜 10¹⁵ より )
配るDPでやると複数区間に配ることになり,連続区間でなくimos法も使えないので O( S² * K ) で間に合わない.

Hello 2019 Editorial - Codeforces にもあるように,各素因数が独立であることを使って計算しよう.

X,Y が独立の時, E[XY] = E[X]E[Y] より, 操作後の値 X= 2^a 3^b 5^c ... とすれば
E[X] = E[ 2^a 3^b 5^c .. ] = E[2^a] E[3^b] E[5^c] .. となって各々DPで計算すれば良い.

a, b, c, .. = O( logN ) より, 全体での計算量は Q = |全体での素因数|と すると
愚直にやっても O( Q * log² N * K ) となって
さっき見たように Q〜 13程度なので十分間に合う.
imos法も簡単に使えるので O(Q * logN * K) となる.
ちなみに元の計算量は S = O( log^Q N) なので O( log^2Q N * K ) である.(最初よりも緩い見積もり)
状態を複数の独立な状態に分割することによって計算量を落としていることがわかる.
期待値の問題でよく使えそうなので覚えておきたい.

メモ

本番では 最後ありえる状態に対してその確率をなんとかして数えたい
↓ 6 ~(2回の操作)~> 1 に対して
6->6->1, 6->3->1, 6->2->1, 6->1->1 を数える?と思っていたが,
各パスが遷移の確率が等しくないので困っていた.

素因数独立に見るのは少し考えたが回答までたどり着かなかった.
状態数が落ちるのが明確にイメージできてなかったせいだと思う.

ちなみに愚直DPを行列累乗で高速化すると O( S² logK ) になるが間に合わないらしい.

コード

CODE THANKS FESTIVAL 2018 H - Median Game (500)

• 問題

解法

スコアは中央値なので,そのままやるとこれまで書いた和を全て持っておく必要がある(どれも中央値になり得る)
=> これは当然全探索に近いので不可能
=> 中央値は2ぶたんがやりやすい(X以上がY個の条件が判定しやすい) という典型もあり,判定関数を作って2ぶたんをしようという気持ちになる

すると判定をO(N²)ぐらいのDPでやろうというのが自然な流れになる.
注意としては,ゲームでDPをやるときは後ろから(そうしないと最終的にmax/minに持っていけない)
x以上のスコアを取れるか？という判定をすることを考える.
dp[ i ][ j ] := ( i ターン経過, a[j,N) でゲームをした時の x 以上の個数 ) とやると, O(N³) かかってしまう.
かといって遷移で 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(2^N) になるので, 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(b²) + O((a+b)b) で,
f(x) = x² とすると f(a+b) - f(a) = 2ab + b² = O(ab) + O(b²) から f(N) = N² が確かめられる.
(厳密な証明はわからない)

メモ

いくつか知ったこと

• 順列でグラフを貼るとサイクルの集合になる
• vector<vector<vector>> hoge; みたいなのめっちゃ遅い(これだけでTLE&MLEした)
• サイクル上のDPは最初の点,それまで見た点の状態をもつ

コード

DDCC 2019 予選 D - チップ・ストーリー ～黄金編～ (700)

• 問題

解法

全力で必要条件を列挙していく.
Nのk進数表記が下の桁から n_0, n_1, n_2, .. であったとすると,
N = n_0 + n_1 r¹ + + n_2 r² + ..
a_k = n_0 + n_1 + n_2 + ..
N - a_k = n_1 (r - 1) + n_2 (r² - 1) + n_3 (r³ - 1) で, r^x - 1 は r-1 で割り切れるので N = a_k (mod k-1) となる.

よって拡張Euclidの互除法を用いてmod lcm(2,3,..,30) の元でこれを求めてやり,
明らかに lcm(2,..,30) > 1e12 なので この解が条件を満たしてやるかを確かめてやれば良い.
拡張Euclidの互除法については下を参照.

qiita.com

メモ

思いつかなかったけど,n進数の各桁の和で割と一般的に使えそうな気がした.
後CRT(中国人剰余定理)はそもそも知らなかったので...

コード

数列操作に関する手筋まとめ

とりあえず考えること

• 要素/総和のmod/パリティに注目する
• 操作回数を求めることができるか(特に総和を用いて)
• 逆操作が可能か

• 操作が単純な操作に分解できるか

• 階差数列を考える

• 数列2つを一致させるなら差を取る

• 操作の縮約ができないか/周期を持たないか

• 上の典型的な場合として,単純な一連の操作を考える(最初から順番に操作していくなど)
• 数列を自分で用意することができる場合は,数列も単純なものを用意する({1,2,..}, {n,n,...})

例題 (順次追加)

B - Two Arrays

2つの数列の差を取る & 操作回数が決まる

A - Limited Insertion

逆操作

D - Decrease (Contestant ver.)

操作できる数に制約があるので逆操作を考えるのは難しい.
単純な数列で単純な一連の操作を考えると縮約ができる

ARC 086 D - Non-decreasing (600) - 主食は米
単純な操作を考えよう

AGC 010 B - Boxes - 主食は米

総和に注目する -> 逆操作を考える -> 階差数列を見る -> 逆操作を分解する