コンテストページです。
解法です。
A - 2 倍チェック / Is It a Number?
激ムズで笑いました。C++ なら char でイテレート をして、0 から 9 でなかったら早期リターンです。
B - 増減管理 / Up and Down
std::adjacent_difference で隣接差を取って、先頭を消せばよいです。
C - 3 番目 / The Third
vector に入れてソートをすると良いです。
D - 重複検査 / Duplicated?
各番号の登場回数を調べて、2 のものと 0 のものを報告すると良いです。なければ Correct です。いいですか？ 大文字ですからね？（泣）
E - SNS のログ / Restore
実行時間には余裕があるので愚直で OK です。ただし 3 番目のクエリで自分を入れないように注意でしましょう！（泣）
F - DoubleCamelCase Sort
前から順番に見ていって string の vector を作ってソートです。いいですか？ 大文字小文字を無視した辞書順ですからね！！（泣）
G - 組分け / Division 2
各部分集合について、それを 1 グループにしたときのスコアを前計算です。3 グループですから、集合分割を全探索すればよいです。いいですか？ 任意個ではありませんよ！？（泣）
H - まとめ売り / Bulk Selling
基本的には在庫をそのまま管理するのですが、奇数番目と偶数番目を一括で減らすのは、普通にやると時間がかかりすぎてしまいますから、別で管理しましょう。
I - 部品調達 / Procurement
各部分集合について、それを購入するための最小コストを管理しながら、セット販売を前から順に見ていく DP です。
J - 地ならし / Leveling
中継地点から左下、右下、右上に最短で舗装すればよいです。ダイクストラを 3 回です。
K - 巨大企業 / Conglomerate
突然のライブラリです。LCA(a,b) = b と同値なので、貼りましょう！
L - グラデーション / Gradation
中継に使う小さな塔の集合を全探索です。それを決めたらそれらを結ぶ橋としてあり得るものを全列挙してクラスカルです。
M - おまかせ / Auto Choice
お ま か せ
い つ も の
実 家 の よいえ、なんでもありません。 答えを決め打ちする二分探索です。コストを答え×質量−魔力として最小化するように選んで、コストが負になってる最小の答えを探します。
N - 整地 / Land Clearing
整地する場所を[X,Y] を全探索です。X はなんらかの区間の終端で、Y は X + C としてよいです。 すると、[0,X], [Y,W] にすっぽり含まれる区間のコストの合計を求めれば良くて、これは前計算ができます。
O - 持久戦 / Endurance
いいですか？ 「はすべて異なる」ですよ ！？（泣）
目の大きい順に見ていって、各サイコロを強制的にふらされる場合の期待値をセグツリーで管理です。
目 X が出た後での期待値 e を求めます。 場合分けは 2 つです。
- X のあるサイコロ i をまた振った法が良い場合
- 別のサイコロに浮気したほうが良い場合
です。 1 つ目の場合には、期待値は5/6 * ( seg[i] + 1) です。 2 つ目の場合には、期待値は seg.query(all) + 1 です。 大きい方を採用しましょう。
これがわかったら、セグツリーの方に反映させましょう。 seg[i] += 1/6 * e でよいです。
