真面目に振り返るよ
ABC130に参加、5完41分で135位でした。pfは黄色でたけどまだまだやれた感。
問題の振り返り
A はい
B はい
C 急いでいて「小さい方を最大化する」という設定に気付くまで時間がかかったので、国語の勉強をした方がいいかもしれない (？) 今回は明らかな上限とその構成がすぐわかる。実装もかんたん。
D
長さNの正整数の列 a[i] があって、連続する区間で和が与えられたK以上になるものの個数を求めたい。N<=10^5 なので O(N^2) は通らない、どうする？という問題。愚直解は O(N^3), 累積和 sum[i] を用いると O(N^2) だがまだだめ、なので工夫が必要。
一つ目の方法が二分探索で O(N log N) にするもの。累積和の列は単調増加なので、左端のindex lをfixしたとき、それより右で sum[l]+K 以上の場所になる場所を二分探索で O(log N) で探せる。それを足せばよい。
二つ目の方法が尺取り法。これも [l, r) で条件を満たすならそれより広い区間で成立する、対偶をとれば [l, r) で条件を満たさないならそれより狭い区間で成立しない、ということを利用した方法。l が 0 のときからはじめて、l を 1 増やすごとに r の値を前から保持した上で増やしていって判定するというもの。r を保持するというのが無駄な区間を調べないための枝刈りになっていて、l, r は各indexを 1 回ずつ訪れるので O(N) になっている。
どちらも典型的な議論なので覚えておく、というか体に染みつかせておきたい。自分は後者でやったが、まあまあ時間がかかった。まだまだ身に付けられてはいないか...
E
2 本の整数列 S, T が与えられるので、(必ずしも連続していない) 部分列の組であって一致するようなものの個数 (のmod) を求めよ、という問題。長さは N, M としてどちらも 2*10^3 以下とする。
もちろん全探索は O(2^(N+M)) なのでだめで、当然DPすることになる。S, T の i, j 文字目までみたときの組の個数を dp[i][j] とおく。遷移を考えると、S, T のちょうど i 文字目と j 文字目を使うかどうかで包除原理が使え、S[i] != T[j] なら dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1], S[i] == T[j] なら dp[i-1][j-1] = dp[i-1][j-1]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1] = dp[i-1][j]+dp[i][j-1] となる。
包除原理がふつうに使えるね...本番では i 文字目と j 文字目を使うかどうかという定義でdpしたが、別に普通に包除原理でできるんじゃん...数え上げ力が足りないね。
F
本番ではゴミみたいに時間を溶かしてだめでした...
x, y 軸にわけるのはよい。xmax-xmin, ymax-ymin のグラフの形状は直線でつくった凸な形で、区間ごとに考察すると積が最小になるのは傾きが変わる場所になる。あとはxmax, xminを見るだけだが、これ実は注目する点を相当減らせるんですね...それに気づかず面倒な実装をしていた、悲しいなぁ。
この「端点だけ見ればいい」という考察ちゃんとやるべきでしたね。その上で、端点になる場所を出すのに必要な点が3個*4くらいでできるので全探索すればいいっすね... O(N) で出来そうだと思ってたけど、冷静な考察が大事だなぁ。
