SRM600 Div1E/SRM 601 Div1E

電車の中でかんがえて帰ってきてから通した.以下かんがえたことメモ.

・SRM600 Div1E ORSolitaire

n個の数が与えられる.いくつかの数を消して,どんな選び方をしてもそれらのORがgoalにならないようにしたい.最小でいくつの数を消せばいい?という問題.

まず(x|goal)!=goalであるようなxは無視できることがわかる(これとORをとった時点でgoalにならないので).

k個選んで消せばいい,というのは上手くk個選ぶとのこりのn-k個全てのORをとってもgoalにならない(=立つべきビットが立たない)ということだとわかる.

goalのiビット目が立っているとき,iビット目が立っているような数を全て消すとのこりの数すべてのORをとってもiビット目は立たない.

各ビットについてそのビットが立たないようにするには何個の数を消せばいいかを計算し,その最小値が答え.

・SRM601 Div1E WinterAndPresents

n個の袋があり,i個目の袋にはりんごがx[i]個,オレンジがy[i]個入っている.各袋から同じ個数ずつ取り出すとき,(りんごの数,オレンジの数)のペアとしてあり得るのは何通りか,という問題.

まず各袋から取り出す個数が違えば合計の個数が異なるので当然ペアは異なる.各袋からk個ずつ取り出すとしてみる.りんごをx個,オレンジをy個取り出すことは出来るだろうか.できるだけ多くりんごを取り出そうとするとΣmin(x[i],k)個で,できるだけすくなくりんごを取り出そうとすると,これはできるだけ多くみかんを取り出そうとするのと同じだからn*k-Σmin(y[i],k)個.(n*k≦Σmin(x[i],k)+min(y[i],k)だからn*k-Σmin(y[i],k)≦Σmin(x[i],k)は保証される)その間の数は全て取れる気がするので各kについてりんごの個数が何種類あり得るか計算して和を求めればいい.