CSA Round #83 (Div. 2 only)

https://csacademy.com/contest/round-83

License Plates

dがn文字連続していたらそこに当てはまる数字列は10*9^(n-1)通りあり,cがn文字連続していたらそこに当てはまる英字列は26*25^(n-1)通りある.

Smallest Missing Numbers

数列Aに含まれない小さい方からM番目の正整数nがわかれば,(1からnまでの和)-(数列Aに含まれるn以下の整数の和)で答えが求まる.nはAをソートしておけば簡単に計算できる.

Hill Skateboarding

ある区間を滑りきれるかどうかは,その区間内で常に速度が0以上であるかで判定できる.つまり上り坂を-2,平地を-1,下り坂を+2に対応させたとき,ある区間の累積和が常に0以上ならその区間を滑りきれる.

よって始点を固定して区間を伸ばせるだけ伸ばし,累積和が負になったら今の終点を始点とする,ということを繰り返せばよい.

ただし,上り坂の真ん中で止まるということもあり得るので,上り坂を[-1,-1],平地を[0,-1],下り坂を[+1,+1]と2個にわけてあつかうと便利.

Rectangle Fit

いくつかの点を含む長方形を,含む点の数をかえず縮小していくことをかんがえると,長方形の横の長さとしては点のx座標に現れるものだけを試せばいいことがわかる.また横の長さを固定したら,出来るだけ縦を長くした方がいいので縦の長さもfloor(A/横の長さ)と決まる.あとは今長方形に含まれている点のy座標をプライオリティーキューで管理し,y座標がfloor(A/横の長さ)より大きい点を消していけばいい(横に長くなると縦は短くなるので,今長方形に入らない点があとで入ることはない).

Firestarter

燃え始める場所が頂点だけであれば,ある辺が燃え尽きるのにかかる時間は,両端点に火が到達する時間を計算することで簡単に求まる.今回の問題では辺の真ん中から燃え始めたりするのでややこしいが,燃え始める場所も頂点と見なしてグラフを作ればok.また燃え始めるイベントを表す点を作り,燃え始める場所を表す頂点との間に辺を張ってやるとT分後に燃え始めるということが表現できる.