2018-02-01から1日間の記事一覧

Falling Balls | CS Academy #67

dp[i][d]:= 「i番目の台からd∈{左, 右}に落ちたとき最後にボールが行き着くx座標」とする。 iをyの昇順に決定することでこのDPを解ける。よって、事前にソートしておくことでi<=j ⇔ y[i]<=y[j]とする。台iの端dからボールが落ちたとする。このとき、x[i][d]…

Suffix Flip | CS Academy #67

実験すると以下を得る最下位ビットが1のとき勝ち最下位ビットが0のとき負け 証明(1)最下位ビットが1のとき常に最下位の1を選ぶことで相手に最下位ビットが0の状態を押し付けられる。値の変化はDAGになっていて(つまり値が必ず減少する)相手のターンで最後に…