Cまで三完。
D. Doremy's Pegging Game
「N/2個連続で消した時点で終了」だから、最後に消す頂点とその幅を固定して、残りの頂点から何個消すかを選べば、二項係数と階乗で計算できる。
「残りの頂点から何個消すかを選べば」というところでハマっていた。残りの頂点からも、N/2個連続で選んではいけないので、選び方を求めるのにDPが必要で、計算量三乗かかるんじゃないか、と。
しかし、最初に選んだ箇所がN/2以上なので、残りの頂点はN-(N/2+2)以下だから、そういう事態は起きない。だから、組み合わせで計算すれば良いと分かる。
普通はハマらないような箇所でハマって解けなかったのはおかしい。
E. Doremy's Number Line
ツイッターで解法を検索してAC。
どういう問題か理解するのが難しいが、整理すると、
・A[0]>=kならOK、A[0]+B[0]<kならダメ
・それ以外の場合、k-B[0]に色が塗れれば良い。そのためには、A[i]+B[i]>=kとなるようなiがあれば良い。
・一番最初に色を塗る際は、A[i]が大きいものを使いたいので、A[i]+B[i]>=kなるiのうち、A[i]が小さいものから使っていく。
という感じになる。
F. Doremy's Experimental Tree
解説ツイートを見てAC。
・Fを大きい順に見て、F[i][j]が繋がっていないなら、iとjは直接つながれている（Union-findで結ぶ）
・重さW[i][j]を知るためには、F[i][i]とF[i][j]を比較する
一点目がポイント。小さいループの方がFの値は大きくなるので、これが分かる。
ただ、PyPyだと時間の制約もメモリの制約も厳しく、ACまでは非常に苦労した。もうちょっと定数倍の良い解法がありそう？
0 件のコメント:
コメントを投稿