今日の精進 2020/06/01 - pitsuの精進日記

昨日のF

一か所から伸びる遷移は3本あって

1.部分集合に含めない

2.部分集合に含めるけど足さない

3.部分集合に含めるし足す

一つ目と二つ目はstartとgoalが一緒だからdp[i+1][j] += dp[i][j]*2でいいのか

HCPC個人戦バチャ

Aの1完....

A:スタート地点からいけるBFSで自分の位置より一番低いところに行くようにする

さっきのバチャのB

どっちで終わるか判定して各コマを除いたときゲームは終了しているか全探索

青~黄diffバチャ

Aの1完

A:dp[i][m][bit]で

i番目まで

最後に見た種類はm種類目

今まで見たものはbitが立ってるもの

復習

頂点を二部グラフに分けたとき、塗った結果は一意に定まる

2部グラフに分けた後に、間にある辺は全部塗っても奇数長の閉路はできない

なので絶対間の辺はオレンジに塗る

間の辺を繋げても連結になってないものは同じグループ内の辺を繋げても閉路は絶対できない

なので塗らなきゃいけなくなって二部グラフ崩壊

だから頂点を二部グラフに分けたときに連結になってるものを数え上げて最後に/2

これはNim数に帰着できるらしい

この記事がわかりやすかった