2019/12/9

ABC147 D - Xor Sum 4

愚直に数え上げては間に合わない

xorは桁ごとに独立なので各桁について考える

→各桁ごとに立っているbitの数を数えてえい

 

ABC147 E - Balanced Path

最小値

全探索は間に合わない(全経路を見れない)

頂点倍加して最短経路?→絶対値の最小化なので無理そう

a,b<=80を使いたい→各頂点ごとに可能な値を持っておく?

→全経路を見ることと実質同じ?

→よく考えると取りうる値は80*(80+80)ぐらい

dp[行][列][取りうる絶対値]で間に合う

 

10^8は2秒なら間に合う

制約にもっと注目して考えるべきだった(a,b<=80だけでdpテーブルにコストを持たせる方針は見えそう)

 

ABC16 D - 一刀両断

幾何 線分交差判定

二回交わると+1個

 

Codeforces 257 B

最適操作→貪欲を考える

置ける限り、先攻は同じ色、後攻は違う色を貪欲に置くのがよさそう(敢えてこの戦略を外れるメリットがない)

 

操作によるパラメータの変化に注目するといいかも?

 

 

Codeforces 257 D

数列構築

式変形をしていじる→部分和を総和の半分に近づけたい→部分和問題はO(N^2)必要だね

明らかに怪しい制約がある

制約の不等式をいじると、数列の適当な隣接2項を取り出したとき、それらが条件を満たすようにできることがわかる

→後ろから符号を漸次決定 A1が負になったら全ての符号を反転

漸次決定法の証明は帰納法