CSA #83 (Div. 2 only)
-
masashinakata
- 660
- 0
- 0
- 0
-
- いいね！0
Hideyuki Tanaka
@tanakh
CSA傾斜配点だけど、解いた人数（のみ？）によって問題のスコアが決まるシステムなの面白いな。Codeforcesとかもそんな感じな気がするけど、あれはデフォのスコアがあった気もするし
2018-07-05 02:06:59
やざてん
@Yazaten
E今更わかったかもしれない。 着火点と結び目と1つ余分な頂点からなるグラフ作って、余分な頂点からの最短経路木作って、(u,v)に後退辺あったら(d[u]+d[v]+cost)/2 が解候補 みたいな感じ？
2018-07-05 02:10:00
nmnmnmnmnmnmnm
@enuemuenuemuenu
Eはグラフに距離と時間の概念があって（速度は一定なので良かったが）さらにスタートがエッジの途中とかなので問題読んで即諦め。
2018-07-05 02:10:27
てんぷら
@tempura_cpp
A *26or*25、*10or*9 B m*(m+1)/2から引いて足して C 大正義priority_queue D わからんって言いながらセグ木で殴ったらできた E ダイクストラで各頂点が燃える時間がわかるんだけど辺で考えなきゃいけなくてほげって感じだった
2018-07-05 02:10:33
nmnmnmnmnmnmnm
@enuemuenuemuenu
Bは300000くらいまでやれば良いか・・・という発想で違う答えを書いてしまったので大きくタイムロス。
2018-07-05 02:12:47
Hideyuki Tanaka
@tanakh
CS Academy Round #83 License Plates：同書くのが早いか悩ましいけど、36^4でやることにした。 Smallest Missing Numbers：ソートして、前から舐めて、直前の数との間の区間の和を足していく。
2018-07-05 02:15:44
Hideyuki Tanaka
@tanakh
Hill Skateboarding：前から舐めて、-1なら+2、0なら-1、+1なら-2して、連続して正だった区間の長さを、負の数になったらリセット、正の数なら+1して、その最大値をとる。カッコのバランス問題的な。-1なら((, 0なら)、+1なら))的な。
2018-07-05 02:15:45
Hideyuki Tanaka
@tanakh
Rectangle Fit：縦線を引くx座標を決めたら、横線は面積がA以下になる最大をとるのが最善なので、座標をx座標でソートして、順に舐めながらy座標を集合に突っ込んで、都度最高のy座標以下の数を数えれば良い。そういうことができるバランス2分木がC++にない？気がするのでFenwickTree使った
2018-07-05 02:15:45
Hideyuki Tanaka
@tanakh
Firestarter：発火地点に新しいノードを作って、その枝を分割すれば、着火地点は全て頂点と考えていい。そのグラフに対してマルチ始点でダイクストラをして、全ての頂点の発火時刻のmax、それから枝の両端の発火時刻から枝だが燃え尽きる時間が求まるのでそれもmaxとる。実装が長くなって楽しかった。
2018-07-05 02:15:45
satanic@研究💪
@satanic0258
CSA A:s[i]==d?10:26を掛ける(前の文字と同じときはこの-1を掛ける) B:x以下の個数をにぶたんして個数がm以上かを判定するにぶたん C:現在の速度で累積和取って同じ高さのもの(ただしサンプル2みたいなのは飛ばす)のうち最大のもの (→)
2018-07-05 02:18:36
satanic@研究💪
@satanic0258
(→) D:yを固定すればxが特定できて,このyを大きいものから調べれば内包判定を楽に出来る.今内包している頂点の座標をpriority_queueで持って各yでの最大キューサイズが答え (→)
2018-07-05 02:18:54
satanic@研究💪
@satanic0258
(→) E:頂点として,元の頂点(N個),発火頂点(1個),クエリ頂点(Q個)を用意しておき,各クエリiについて発火頂点からクエリ頂点へ長さt[i]の辺を張るようにする.このグラフで発火頂点から最短経路を求めて,各辺で最後に燃える部分を(dist(u)+dist(v)+cost(u,v))/2で求めてこれらのmaxを取る
2018-07-05 02:18:58