http://agc012.contest.atcoder.jp
B. Splatter Painting
http://agc012.contest.atcoder.jp/submissions/1197833
辺に着目して計算していくのは全く気づかなかった。頭いい。
部分点解法(partial関数)
各クエリについてdfsで塗っていく（木っぽくしてるけど、木っぽく探索しても大丈夫）。
想定解法(sol関数)
dp[v][d] := 頂点vから距離dで塗られる{クエリ番号, 色}
を更新していく。
まずクエリはdp[V[i]][D[i]] = {i + 1, C[i]}として入力していく。
dp[v][d]をdを10から1まで降順で処理していく。
各dについて以下の処理を行っていく
1. 全ての頂点について、既に塗られている色を距離d-1に伝搬する
2. 全ての辺について、隣接する頂点について距離dの色を距離d-1に伝搬する
dpにクエリ番号を含めることで塗られた時間を保存しておき、最新の色を塗る。
答えはdp[v][0]のsecond
C. Tautonym Puzzle
http://agc012.contest.atcoder.jp/submissions/1199007
こんな方法思いつくかよって感じだけど、傾向ってあるんだなぁ
説明は難しいので解説放送を見よう。
相変わらず、とても分かりやすい。
www.youtube.com1 2 3 4 ... 80 と数列を作っておく。
その後ろに順列を作るが、その順列の単調増加列の個数が、今回求めたい個数となる。
よって、問題が単調増加列がN個である順列を求める問題となる。
以下のように構成する
{} -> 1個(0個)
{1} -> 2個(1個)
{1 2} -> 4個(3個)
{3 1 2} -> 5個(4個)
{3 1 2 4} -> 10個(9個)
最初を1にすると、前に追加で+1, 後ろに追加で*2となる最初の空集合は0個ではなく1個にしておくと計算しやすいので、1から+1と*2をつかってN+1を作るように構成していく。
前に後ろに追加するのでdequeを使うとよい
D. Colorful Balls
http://agc012.contest.atcoder.jp/submissions/1199141
玉を頂点と考え、交換可能な玉の間に無向辺を貼る。
この辺で成分分解をして(merge関数)、成分分解毎に玉の組合せを計算して合わせる(count関数)と答え。
count関数ではmerge関数で連結成分でマージしてあるUnionFindを見ながら交換パターンを全て求める。
同じグループであればどんな形にでも変形できるので、「同じものを含む計算」(ぐぐると分かる)をする感じで計算していく。
以下、merge部分の愚直解と最適解。
愚直解
全ての2頂点間について同色・異色で辺が張れるかチェックする。
O(N^2)で当然間に合わない
最適解
まず、処理に移る前に色について玉をまとめて、重さで昇順ソートしておく
1. 同色の辺
最も軽い玉と他の玉の間の辺だけ考えれば良い。
2. 異色の辺
全ての色から最も軽い玉だけを集めた時に、その中でも最も軽い2つの玉だけ考える。
この2つの玉から任意の玉との間の辺だけ考えれば良い。
解説動画と合わせた解答なので、動画を見つつ、ソースを見つつ考えると分かるかと思います。
