こんばんは。生活リズムが完全に崩壊したとーです。
解くに至った問題
ABC:006D/035D
AGC:009A/013A/018A/021A
ABC006D
解説AC
LIS(Longest Increasing Subsequence)の問題
カードを挿入することで位置を変化させる必要がない部分は「前から見ていって増加している」ような部分である
カードを挿入する回数を最小にしたいので、その「増加する」列（飛び飛びでもよい）で、最も長いところを求めればよい（その長さを数字の個数から引けば終わり）
[例]
1,3,5,2,4,6
のLISは1,2,4,6
さて、その部分列の求め方を説明する といってもあんまり難しくない
1からNまでのN個の数字で構成された部分列を考える
まず、N個の∞をもったリストdpを用意する
ここでは、簡単に1,3,5,2,4,6という数列で説明を進める
dp = [float('inf')]*6
さて、dpの値を更新することを考える
dp[i]には（iは0インデックス）、部分列の長さがi+1になるような列で、その列の最後の数字で最も小さい数字が入る
例えば、上の例で言えば、
dp = [1,2,4,6,inf,inf]
となる
数列を前から見ていき、今見ている数列の要素がdpのどこに入るかを二分探索で調べる
こうすることで、例えば1,3,5まで見た時点ではdp = [1,3,5,inf,inf,inf]となっていたのが、次に2を見たら3の前に入ることが分かるので、その値を更新してdp = [1,2,5,inf,inf,inf]
→4を見たら5の前に入ることが分かるので、dp = [1,2,4,inf,inf,inf]
→6を見たら4の後ろに入るので、dp = [1,2,4,6,inf,inf]
となるようにアルゴリズムを組めばよい
以下はpython3による答えのコード
import bisect N = int(input()) L = [] for i in range(N): L.append(int(input())) dp = [float('inf')]*N for i in range(N): k = bisect.bisect_left(dp,L[i]) dp[k] = L[i] endnum = bisect.bisect_left(dp,N+1) #N+1は必ず、リストdpの「無限でない最小の要素」になる print(N-endnum)
ABC035D
島を訪れるのは一つだけでよい（二つ以上滞在するのは時間食うし、それだったらポイントが多くなる方により長く滞在すればよい）ということを念頭に置き、島1から各頂点への最短経路をダイクストラで求める
今回注意すべきなのは「往復するコストが同じではない」ということ
なので、辺を格納するときは片道に限るということを念頭に置いておき、行きと帰りでダイクストラを二回やってそこまでの往復にかかる時間を計算し、各島の滞在時間を求め、ポイントが最大になるような島を選べばよい
AGC031
失敗 0完 2つTLEが取れなかった 反省します
