A - エレベーター
解答：Submission #12827083 - 第二回 アルゴリズム実技検定
解法：1F, 2F, ...⇒ Fを取る、B1, B2, ... ⇒ Bをとり－をつけ+1する。すると2つのフロアを表す数字ができるので、この差を取ればよい。自分の解答だと、9F, 8F, ..., 1F, B1, ..., B9の順番に配列に入れ、そのインデックスを取得し、インデックスの差を取った。
B - 多数決
解答：Submission #12827302 - 第二回 アルゴリズム実技検定
解法：a, b, cごとの票数を集計し、最大得票のものを出力する。
C - 山崩し
解答：Submission #12828061 - 第二回 アルゴリズム実技検定
解法：下の段から順に、与えられた条件のもと山を書き換えてゆく。
D - パターンマッチ
解答：Submission #12828851 - 第二回 アルゴリズム実技検定
解法：文字列Tの候補は高々28^3 = 21952。一つの候補について、愚直なマッチング判定は3 * |S|程度。よって全ての文字列の候補Tに対しSがマッチするかを愚直に試せばよい。
E - 順列
解答：Submission #12829110 - 第二回 アルゴリズム実技検定
解法：順列を巡回置換で分解する作業に相当する。あるx(1≦x≦n)についてxをa[x]で置き換えてゆくが、その際に経由する数字をsetに保管しておく。置き換えを続けてふたたび同じxが現れた場合（setで判定可能）、その時のsetの要素の個数がそこまで現れた数字について出力が必要な数になる。setに入っている他の要素についても、このとき一緒に個数を記憶しておくと計算量が小さくなる。
F - タスクの消化
解答：Submission #12829325 - 第二回 アルゴリズム実技検定
解法：タスクをあらかじめ日付がキー・消化ポイントの配列が値のmapに格納しておく。1日目から順に実行可能となったタスクをプライオリティーキューに格納し、最大のものを毎日1つずつ取り出し合計して出力してゆく。
G - ストリング・クエリ
解答：Submission #12844499 - 第二回 アルゴリズム実技検定
解法：文字と文字数をペアにしてdequeで管理する。また、あらかじめ文字ごとに削除数を記憶する配列を保持しておく。文字の追加は文字と文字数のペアをdequeに追加する(push_back)。文字の削除は文字ごとにまとめて削除し(push_front)、同時に文字ごとの削除数を更新する。出力は文字ごとの削除数より逐一計算する。
H - 1-9 Grid
解答：Submission #12845242 - 第二回 アルゴリズム実技検定
解法：dist[r][c][d]を「dまでの数字にすでに到達している状態でr行c列目のマスに到達するときの最短時間」とする。これをBFSで計算する。
I - トーナメント
解答：Submission #12845732 - 第二回 アルゴリズム実技検定
解法：実際にトーナメントをシミュレーションすればよい。具体的には、各人の添字と強さをペアにして管理し、人iと人i+1の対戦を行っていく。勝った人を配列に追加し、負けた人はその時点で結果を格納する配列に結果を記入してゆく。
J - 文字列解析
解答：Submission #12846967 - 第二回 アルゴリズム実技検定
解法：作成する文字列を配列で管理する。具体的には下記の手順を行う。
- s[i] = '('のとき
- 配列の階層を一つ進める
- s[i] = ')'のとき
- 現在の配列の階層の文字列aとそれを逆順にした文字列rev(a)を連結したものを一つ上の配列の階層の文字列に連結する。
- 配列の階層を一つ戻す
- 上記以外
- 現在の配列の階層の文字列にs[i]を連結する
問題：K - 括弧
解答：Submission #12875879 - 第二回 アルゴリズム実技検定
解法：dp[i][j]を「i文字目まで見たときに「(の個数 - )の個数」がjであるときの操作コスト合計の最小値」としてdpする。正しい括弧列は各文字目までの「(の個数 - )の個数」が常に0以上であることに注意する。
L - 辞書順最小
解答：Submission #12875879 - 第二回 アルゴリズム実技検定
解法：先頭から詰めて要素を選ぶ場合と末尾から詰めて要素を選ぶ場合を考える。例えばN = 7, K=2, D= 2, A = {3, 1, 4, 1, 5, 9, 2}の場合、先頭から詰めると3, 4, 5を取得し、末尾から詰めると4, 5, 2となる。このとき、第１項の候補は3, 1, 4、第2項の候補は4, 1, 5、第3項の候補は5, 9 , 2である（要証明）。また、辞書順最小を選ぶので、後ろの項よりも前の項で小さいものを選ぶ必要があり、前から貪欲に小さい項を選んでゆけばよい。
具体的には以下の手順となる。先頭から詰めて要素を選んでもK個の要素を取得できない場合は-1を取得する。取得できる場合は、「Aの添字と値をペアとし、値昇順⇒添字昇順で取り出せるプライオリティーキュー」を用いて次の手順で先頭から要素を選んでゆく。
- 各項でとりうる最も遅い後ろの項までをプライオリティーキューに格納する。
- 添字が「前回取得した要素の添字+D」以上となるまでプライオリティーからペアを取り出す
- 取り出したペアのうち、値を解答出力用の配列に格納し、添字を覚えておく。
M - 食堂
解答：（未回答）
N - ビルの建設
解答：Submission #19574324 - 第二回 アルゴリズム実技検定
解法：平面走査を行う。
作業の順番が重要で、x座標の小さい方から物事を考えることにする。すると、各敷地に該当するx座標になった場合(x[i]とする)、[y[i], y[i]+d[i]]にc[i]を加算、x[i] + d[i]になった場合、[y[i], y[i]+d[i]]からc[i]を減算すれば、(x, y)の敷地のコストを効率よく管理できる。これは区間加算の(遅延評価）セグ木を用いればよい。あとは、x座標がクエリのa[i]座標になった場合、その時点のb[i]の値を取得する。
なお、座標が10^9の大きさであるため、座標圧縮を行う必要がある。
