■A - Odd vs Even
愚直にやって一回TLEしました。
奇数なら、約数も全て奇数
偶数のときに４の倍数でないなら、奇数と偶数が半分半分
そうでないなら偶数のほうが多くなる
■B - Products of Min-Max
とりあえずソートします。
minを大きいものから小さいものに下げながら前の状態を保持しておいて計算量を減らす
例
A = {1,2,3,4}
min = 4 -> 4*4
min = 3 -> 3*(3+4)
min = 2 -> 2*(2+3+2*4)
min = 1 -> 1*(1+2+2*(3+2*4))
■C - Multiple Sequences
最後尾のA[N-1]を決め打ちする
A[N-1]を素因数分解すると出来る
例
A[N] = 6 N=3として
2は{1,1,2},{2,2,2},{1,2,2}となるが(3も同様)
これの場合の数は、前計算しておけばいいので求められる
説明適当。
■D - I Wanna Win The Game
形式的べき級数風に考えて、畳み込み
それぞれのbitごとに、何個選ぶかで考えればいい。
普通にdpで良かったみたいですけど
■E - Spread of Information
JOIに同じ問題があるらしい
木＋分割とかで検索すればいいらしい。
二分探索だろうというのはコンテスト中に思いついていたが
貪欲パートがわからず。
各頂点ごとに{置いた都市への最短距離、届いてない都市の最長距離}を返すdfsをする。
マージした結果、"置いた都市への最短距離＋届いてない都市の最長距離"がc以下なら
全て覆うことが出来るので"届いてない都市の最長距離"を-INFで初期化
"届いてない都市の最長距離" = cなら置いて初期化{0,-INF}
