■A - アトラクション
if
■B - 穴の開いた硬貨
やるだけ
■C - 最速正解者
逆から見るかminを使うか
■D - 試験
operator<
■E - キーボード
0の扱いが面倒ですがやるだけ
■F - 将棋のように
bfs
■G - 連結
bfsをQ回やっても問題ない
O(q*n^2)が間に合うため
■H - 最長非共通部分列
dp
LCAの要領
■I - 直通エレベーター
終点、始点、エレベーターの設置位置だけ取り出してダイクストラ
/*ここまで１時間64点中級*/
■J - 回転と反転
90分かかった
状態は8パターンあるので上手にやる
■K - ガソリンスタンド
ガソリンスタンドからsへの距離+ガソリンスタンドからtへの距離の最小値
ガソリンスタンドの数は少ないのでbfsで前計算
■L - 嘘つきな生徒たち
難しくないですか？
配列はとりあえずreverseする
配列aが単調増加⇔配列b(bi=ai-i)が広義単調増加列
なのであとはbitなりセグ木に乗せる。
座標圧縮する必要がある。
/*ここまで３時間82点上級*/
■M - 名前の変更
setでは削除、挿入ができても、n番目は求められない
だがa~zと0~9しか出てこないのでtrie木に任せれば解ける
trie木を使うと上に書いたことができる。
■N - 共通部分
共通部分の多角形は
１：sの頂点かつtの内部
２：tの頂点かつsの内部
３：sの辺とtの辺の交点
により作られる。
あとはライブラリに押し付ける。
■O - ペアスコア
ボス問にしては簡単
FFTに少しテクニックを足すだけ。
x = Bj-Biとなるi,jの組み合わせをそれぞれのxに対して高速に求めたい。
これは配列を反転させれば良い。
