ABC-D 79-86 - cmat日記(競技プログラミングその他)

実装する段階になって読み間違いに気づくことがしばしば。

それでも一応86以外は自力で解けたので良い傾向。

79
各数字について、最小コストの遷移を決めてやればいい。
ワーシャルフロイドでok.

80
si-0.5 -tiが最も多く重複する区間の重複度。
imos[10^5][30]

81
値が正なら、左の数字を右に足していけばいい。
負の時は？
左をより小さくすればいいので、右を左に足す。
後者によって前者で作った関係が壊れうる。
うるのでもう一周で2N回

最初のN回で符号を揃えてしまえばいい。
負に揃ったら右から、正に揃ったら左から処理でok

82
TとTの間のFを数える。
0回目と1回目の間、2回目と3回目の間、、、、を数えると、x方向に進めるパターンはそれらの和or差の組み合わせで全て生成される。setで管理。

最後の移動を処理するために、末尾に'T'を追加しておく。

83
n-1回でできるのは、一番左、一番右を好きな数にすること。
Kの場合、左右からn-K番目までは自由にできる。
よって問題は、それらの中間がどうなっているか。

数列の中心から見ていって、異なる数字が出るまでどれだけ広げられるか。
.....011111.....の場合、 ...0 1111 1...と分割。n-K=(n-4)/2
...0111111...で...0 11111 1....の場合も、n-K=(n-5)/2

84
10^5以下の奇数全てについてあらかじめ調べておいて、条件を満たすものをソートして格納した配列を作る。あとは各クエリに対して二分探索していくつ含まれるか計算。

85
振るのは最大のaiのもののみでいい。
そのaiをどのタイミングで投げるか。
bj>aiは投げて良い。ただし、biを投げることで回数が減るなら処理が必要。

bj全て投げで終わるなら、大きいものから。
終わらないなら、aiで適正回数殴ってから投げる。
ai殴りでHがbjの総和以下になったら投げに移行する。投げる順番はbjの大きい方から。

N 3^2だから全部試せばいいと思って書いている途中にN K^2と気づく。

O(N K^2)から落とす方法がいまいちわからず断念。