Codeforces Round #556 (Div. 2)

バチャした。紫なんですけど、Div2でしました。

問題：株を買ってから売って現金を最大化せよ

考察：

もっとも安いときに買って、高いときに売ればよいです。

なぜか最適かわからんくなって5分

問題：十字のブロックを使って敷き詰めろ

考察：

上のブロックを基準に貪欲する。

結構実装が典型っぽくて5分でかけた、自己評価〇

問題：1と2が与えられる。好きなように並べて、接頭辞の合計を並べる。素数の数を最大化せよ

考察：

素数は2以外奇数である。

なので、2を出した後3にして、そこから2ずつ増やすようにすればよい。

2の数と1の数が0のときは別で考えると、2，1，２２２２，１１１１とすればよい

問題：文字列sが与えられる。文字列1~3をクエリで更新する。この1~3がそれぞれ重複しないように文字列sの部分文字列にすることができるか判定せよ

考察：

DPをする。

dp[i][j][k]：1のi文字目、2のj文字目、3のk文字目が出るような、sの最前index

もし1にi文字目を追加するときは、i-1=>iの更新と、ｊ、ｋについてすべて探索する。

したがってO(QM^2）である。

ここであるindex以降の最前のアルファベットが知りたい。

二分探索でもよいが、26*nの配列すべてで前計算したほうがはやい。

二分探索は意外と効く