ABC194

5完。たまにABクソムズがあるけどやめてほしい。

A - I Scream

乳固形分と乳脂肪分の包含関係が最初のころ気になってたけど実装してから思い出して問題文を読み直す。無脂乳固形分の意味がコンテスト中にはとれなくて、ハードウェアアクセラレータを切って機械的に(それがあるべき姿だとは思うが)処理したので時間がかかった。

B - Job Assignment

Clarにあるように問題文が間違っていたのでなかなか頭に入ってこなかった。修正されても、仕事AにA_i分というのはなんか(間違った問題文を読んでいた影響もあるのか)不自然に感じて時間がかかる。問題文が読めてみると、1人でやる場合と2人でやる場合があって難しいとわかる。1人の場合は簡単。2人のときは楽なやり方が思い浮かばない。仕方ないので入力を保存して二重ループ。B問題までで10分かかった。

C - Squared Error

N*Nの表を書いてそのイメージで。答えの2倍を計算する。対角線部分は0なのでそこも足してしまっていい。式は展開してしまう。2乗部分はN個とN個、N^2通りの積の和は、A_iたちの和の2乗。こういうの、なんか瞬殺できない。Bより時間かかってる。

D - Journey

どこにいるかは関係なくて、新しい頂点を選ぶ確率の逆数が、高橋君がいる連結成分のサイズが1増えるまでの回数の期待値。足していく。

E - Mex Min

Nが異様に大きい。いつもなら3*10^5くらいなのに、15*10^5だ。iを1つずつずらしながらmexを計算していけばよさそう。何が何個あるかを管理しておいて、0が現れたり消えたりしたらその場所を記録しておく?いや、0が消えたときに隣の0がどこかわからない。セグ木でいけそう。個数の最小とその位置がわかればいい(セグ木のサイズをN+1にしておけば必ず0個の場所がありそこが最小になる)。pairを使う(最小値とるのが簡単)。std::setでもいけそうだと思う。実装はそっちのが軽いか。しかし、4秒あるからlogは許されるといっても、10^6超えてるのにsetは気が進まない。セグ木のが好きだしそっちでいいだろう。更新部分がけっこうややこしく、時間がかかってしまった。

F - Digits Paradise in Hexadecimal

ちょうどKなので包除原理か。使う数字を固定して2^16通りとかも考えたけど。0の扱いがあまりにも厄介。やりたくない。頑張って整理して考えていく。十進法でも同じことなので十進で考える。1から9、10から99というように区切ればいけるか。例えば3456なら、さっきの区切り方で1000未満はわかって、1000から1999と2000から2999もわかりそうだし、3000から3399、3400から3449、3450から3456というのもどうにかわかりそう。ということで一応雑に書いたがサンプル通らず。かなり時間かかりそう。