典型90に感謝しましょう
2400Perfをだして、ここ数回の冷えを取り返す。
明日のARCで2300ぐらい出せれば。。。。
■A - AtCoder Quiz 2
if,else if,else if,else
■B - Maritozzo
rep(i, t.size()) cout << s[t[i] - '1'];
■C - Neo-lexicographic Ordering
pair<変換した文字列、与えられた文字列>
ともってsortする
■D - Strange Lunchbox
dp[i][j][k]:=i番目まで見た、たこ焼きj、たい焼きkを達成する最小の弁当の数
■E - Moat
これ割と難しいと思いますが
2^16を全探索すればいいのはすぐわかる。
全ての村を含む+選んだところが連結かどうか
これだけで考えるとサンプルが合わない。
####
#..#
#..#
####
のようなケースを想定できていないから。
これは周りをぐるっと増やし、
......
.####.
.#..#.
.#..#.
.####.
......
として全ての白は連結か、全ての黒が連結かを考えればいい。
■F - Cleaning Robot
実装が面倒。
一旦kを∞だと考えて、そのときに同じ場所を掃除するようなものをグループ分けする。
あとは適当に頑張る。
■G - Propagation
典型90の83問目。
past5にも類題がある。
次数が多すぎるものは、あとで貰いに来てもらう。
次数が小さいものは、直接更新する。
いわゆる平方分割
■H - Candles
解説を読んだ。割と素直なdpに思える。
[l,r]の範囲まで回収して、lかrにいる状態から
[l-1,r]か[l,r-1]の両端に移動するようなことをすればいいのはなんとなくわかる。
問題は、時間と、今のポイントの情報を持っていないと駄目なこと。
ここをうまいことやりたい。
回収する蝋燭の本数を固定し、移動先では回収する、しないの選択をできるようにする。
また、時間で蝋燭の長さが減るのではなく、移動中に自分のライフが減少し
蝋燭を回収すうるとライフが回復するような問題に読み替えることができる。
サンプルを用いて解説すると
2本回収することを目的として
0から-2に移動してライフが2*2減り、蝋燭を回収することで、ライフが10増える(0->6)
-2から3に移動してライフが1*5減り、蝋燭を回収することで、ライフが10増える(6->11)
これを区間dpぽく扱えばいい。
