■A - POSTal Code
s[3]とそれ以外で=='-' か!='-'
■B - PASTal Code
s[i * 4 + 1 ] == 'o'
■C - 携帯電話の購入
Bをsetで管理
■D - K項足し算
頭を削って、お尻を加える。
■E - 前から3番目
std::deque
■F - 安全装置
3ペナ
途中で安全装置に止められて、更に終わった瞬間にも安全装置に止められるケースを忘れていた。
■G - 一日一歩
Gにしては難しくない？
毎日毎日、到達したことのない頂点に到達できそうなら動く
使える辺の候補は、通行時間をkeyにしてpriority_queueで管理しておけば良い
priority_queueをwhileで回しながらpushをしてしまうと
一日に二歩動いてしまうのでwhileの外にvectorを保持しておき
whileを抜けたらしたらまとめてpush。
■H - カンカンマート
Gよりよっぽど簡単ですよね
同じ系統の缶詰なら安い方から買えばいいので
type0をi個、type1をm-i個を全てのiについて試せば良い。
缶切りのことも考慮した累積和を先に求めておく。
■I - 魚釣り
単純なdp
dp[i][j][k] :=(i,j)に来るまでにk匹魚を釣ったときの最大値
■J - ポイントとコストと
よく見るとただの２次方程式なので平方完成なり微分するなり。
■K - 共通クーポン
dp
少し難しい？
どの状態をまとめて持つかを考える。
購入金額をmod100でまとめ、その状態での最大値を考える
dp[i][j] := i個目まで見た、購入金額がmod100でjな購入金額の最大値。
■L - 都市計画
最小全域木
Mの制約が小さいから、全てのNと特定のMを使う2^M通り全てに対して最小全域木を行う。
■M - 等しい数
一番難しい。
嘘解放っぽいけど
{{l,r},x}で連続区間と要素を管理しておき必要な箇所のみ更新していく。
最悪ケースの計算量がこれで成立する理由がよくわからない。
■N - 活動
取る順番によって結果が変わる
しかし、不等式を作って整理するとa/bが大きいものから撮っていくのが最適だと言うことがわかる
なのでsortしてdp。
■O - 最短距離クエリ
実装が重い
M <= N+10なのでほとんど木
グラフから一部の辺を取り除いて木を作る
木の上での最短距離はLCAを使えば簡単に求まる。
問題は木に含まれない辺を経由するとき。
頂点u,vと辺の両端に含まれる頂点全てを取りだしダイクストラを行えば答えが出る。
