読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

ARC008 メモ

ただのメモです
A:
10袋をいくつ買うかで全探索
AC
B:
各アルファベットについて必要な個数,1キットで手に入る個数をカウントしておく.
必要なアルファベットがキットになければ-1,あるならば必要個数/キットの個数の切り上げの値の最大値が答え.
AC
C:
投げる個数に制限がない(同じ時間に何個でも投げられる)とき,各頂点へのパスの最短時間を求めてそれの最大値が答えになる.
最小費用流っぽさはあるけどどのようにコストを設定すればいいかわからない
詰まったときは順に1秒ずつ吐く必要がある.
dpっぽさもある.
各たこ焼きの待ち時間をコストにすれば最小費用流でいける?
わかんね
スタート地点からは1秒おきにしかたこ焼き発射できない
ダイクストラで求めた最短パスにそれぞれ投げた時,最短経路木に沿うようにしか発射されないので二つ以上のたこ焼きが交差することはない
したがってたこやきの待ち時間はスタート地点でしか発生しない
あとはどの順番で投げるか
遠い順から貪欲で投げていくのが最適
各たこ焼きの到達時間を調べて最も長いのを取り出せばおっけー
AC
D:
せぐつりーというヒントはある
各ボックスで生まれる+bの部分はそれ以後のボックスのaの部分によって掛け算される
したがってセグツリーの各ノードにおいて,この範囲で生まれた+bの値は何倍になって出てくるかを保存しておけばよさそう
問題はaのところで0の乗算がありえること
これは0の個数をカウントしてやってその区間にかけられてる0が1個以上あるかどうか調べてやればよさそう
実装...この時点で辛そう
初期状態は[0,0].sum=1,i>0のとき[i,i].sum=0,任意の[i,j].mul=1にしておく
i a bが与えられたとき
まず[i,i].sum=bにして値を更新していく
次に[0,i-1].mulをa/mul[i]倍にする.値更新再び
a=0のときは[0,i-1].zero++;
ごにょごにょした
AC
あとで@camypaperさんにA=a_i*a_j,B=b_i*a_j+b_jとすると二つのボックスから一つのボックスに結合できてこれを使うと簡単に実装できることを聞く
天才
こっちでもAC