2020年 9月 4日
まえがき
ｹﾞﾗｹﾞﾗﾎﾟｰのうた
健康管理
何した
競プロが今俺の中であつい。
具体的に
今日解いた問題
ABC176 E-Bomber
- [最大化,1変数ずつ考える]
似たような問題としてABC129 D- Lampがありますが、リンク先の問題はO(H * W)が通る。
今回の問題は,爆破対象が最も多い行と爆破対象が最も多い列の交差点に爆弾を置くのが良いです。
そのような行の候補をa1, a2, a3, ..., an, 列の候補をb1,b2,b3, ..., bmとします。
また、マス目を(行,列)で(5,2)のように表記します。
上のように候補が上げられたとき、マス(ai,bj) (1 <= i <= n, 1 <= j <= m) に爆弾が無いようなi,jの組があれば、そのようなマス(ai,bj)に爆弾を置くのが最適です。
マス(ai,bj)に爆破対象が存在する場合、爆破出来る対象の個数は、ai行にある爆破対象の個数 + bj列にある爆破対象の個数 - 1 となります。
しかし、存在しない場合は ai行にある爆破対象の個数 + bj列にある爆破対象の個数 だけ爆破できるにゃん。
さて、本文での計算量は、恐らく行や列の候補の数がもっとも多くなる場合を考えればよく、そのような場合というのは、全てのマスに爆破対象があるときです(多分)。
(だって、全てのマスに爆破対象があったら全ての行と列が候補になるもん）
制約で 1 <= M <= min(H * W, 3 * 105)とあって、H = 3.0 * 10 ^ 5, W = 3.0 * 10 ^5 のときに全てのマスに爆破対象があるようなことはなくて、なんかうまいこと行の候補数 * 列の候補数の計算量て間に合うように鳴ってます（もう知らん）
ABC174 E- Logs
- [二分探索,木を切る,達成可否判定]
とりあえず無理な解法として、「常に一番長いものを半分に切る」が浮かびます。
しかし、これはO(K)でKが10の9乗で攻めてくると泣きたくなります。泣きたいほどに貴女が恋しくなります。
はあ、困ったなぁ…
うーん、合計K回切った後に最小の長さをxにすることが出来るかの判定って出来ないかな…？あ、二分探索いけんじゃね？
ってことで二分探索解法が浮かびました。
さて、そこから、長さAiの木を全てx以下にするときの切る回数をどうやって求めるんだ？
木を切る時、『ちょうど半分に切る』,『長さ/2 (切り捨て) と (長さ+1) / 2(切り上げ）
になるように切る』の2つを考えてみました。
なんとなく後者の方がいいんじゃないかな〜っておもって、でもそのときの回数が分からなくて困りました。
で、分からん分からん分からんぞ〜っていいながら、x==1のとき,Aiを3〜7あたりで書いてみて、でも分からんな〜ってなった。
ふと、Aiがxのm倍ならm回ぐらい切ればいいんじゃね？って思って、その次に「あ、m-1か」って思ってやってみました。そしたら行けた。
、ACした後に考えてみたら、確かにAiがxのm倍の時,m-1回切ればいいっていうのが分かりました。
あとがき
Anything goes to zero 明日解きます。
解説読んで動画もみた。解ける。間違い無い。
以下は毎回記事に貼っているテンプレート
基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます - 瑞々しぃにぼしの自己紹介(自己紹介の記事です)
