CODE FESTIVAL 2014 予選B D - 登山家
問題：D - 登山家
解答①：Submission #10974270 - CODE FESTIVAL 2014 予選B
解答②：Submission #10977004 - CODE FESTIVAL 2014 予選B
解答③：Submission #10993670 - CODE FESTIVAL 2014 予選B
解法：i番目の山小屋について、その山小屋より左側、右側でそれぞれどこで突き当たるかを調べてゆく。
①DP
右側の場合を考える。dpr[i]：i番目の山小屋が右側で突き当たる山小屋の番目 とすると、右側に見える山小屋の数はdpr[i] - i - 1個である。dprは次の手順で高速に算出できる。
- 最初はdpr[i] = i + 1 と設定
- dpr[i] < n かつ h[dpr[i]] ≦ h[i]のとき、dpr[i] = dpr[dpr[i]] と更新
これは、i番目の山小屋より右の突き当たる山小屋を次々と辿ってゆくイメージである。山小屋を辿る回数は、n個の山小屋を通して合計n回までであるため、全体としてはO(N)である。
左側も同様。
②Stackを使う
右側の場合を考える。dpr[i]：i番目の山小屋が右側で突き当たる山小屋の番目 とするのは①と同じ。
山小屋の番目を保持するStackを準備し、i番目の山小屋の調査に対し、Stackを次のように更新していく。
- h[Stack.top()] ≦ h[i]である限り、Stack.pop()
- Stackが空なら突き当たる山小屋はなく、そうでないならStack.top()が突き当たる山小屋
- Stack.push(i)
i番目の山小屋より小さい山小屋がそれ以降に調査対象とはならないため、Stackから落としてゆくイメージ。
左側も同様。
③二分探索
山小屋の高い順に山小屋の個数を調べてゆけばよい。山小屋の番目をsetに格納し、upper_boundとその1つ手前の要素が突き当たる両端の山小屋である。調べ終わったらその山小屋の番目をsetに格納する。
注意点として、同じ高さの山小屋がある場合は、各山小屋について先に全て調査し、その後各山小屋の番目をsetに格納する必要がある。
Code Formula 2014 予選B C - 仲良し文字列
問題：C - 仲良し文字列
解答：Submission #10929382 - Code Formula 2014 予選B
解法：1回のスワップでab間の異なる文字が同じになるのは高々2文字なので、7文字以上異なる場合はその時点でNO。6文字であれば3回スワップしても計算量は66=46636で間に合う。なのでスワップ位置で全探索する。
ここで仮にaとbが最初から同じだったとしても、3回はスワップをしないといけないので、スワップ後が必ずしも同じ文字列になるとは限らない。（例：サンプル3）ただし、aの中で同じ文字があると、その文字同士をスワップすることで実質的なスワップ回数を減らすことができる。
よって、aの中に同じ文字があるかないかで何回スワップできるかを変えて全探索すればよい。
Indeedなう（予選B） C - 木
問題：C - 木
解答：Submission #10920720 - Indeedなう（予選B）
解法：dfsで各頂点を探索していく。いったん隣接頂点を全て確認した後、それをpriority_queueに格納しておき、次に探索するのはpriory_queueの中の最小の頂点とする。
天下一プログラマーコンテスト2014予選B B - エターナルスタティックファイナル
解答：Submission #10902648 - 天下一プログラマーコンテスト2014予選B
解法：dp[i]をi文字目までを作るときの作り方の通り数とする。
元の文字列sのi文字目について、全ての文字列の候補でマッチするかどうかを確認する。文字列tがマッチする場合、dp[i+t.size()]にdp[i]を加算する。（配るDP）
Codeforces Round #627 (Div. 3) E. Sleeping Schedule
解答：Submission #73178165 - Codeforces
解法：dp[i][j]をi回目の睡眠で睡眠開始がjであるときのgood睡眠の最大値とする。
このときi回目で睡眠開始がj であるとき、i+1回目の睡眠開始はj + a[i]もしくはj + a[i] - 1なので、これがgood睡眠の範囲であるかどうかでdpに加算を行う。（いわゆる配るdp）
Codeforces Round #627 (Div. 3) D. Pair of Topics
解答：Submission #73177810 - Codeforces
解法：ai + aj > bi + bj ⇔ ai - bi > aj - bj よりci = ai - bi とし、ci > cjとなる(i, j)の個数を探す。
cを昇順ソートする。iとjを逆にし、ci < cj (i < j)を探す。
ci > 0 であればj >i なる全てのjでci < cjがなりたつ。 ci ≦ 0 のとき、 cj ≧ - ci + 1 であればよいので、そのようなcjの個数を数える。(lower_bound)
ARC091 E - LISDL (700)
問題：E - LISDL
解答１（通常座圧）：Submission #10767274 - AtCoder Regular Contest 091
解答２（自前計算座圧）：Submission #10767259 - AtCoder Regular Contest 091
解法：次のような2次元マトリクスを考える。
このマトリクスから次のようにN個の数を取得する。
- B, B-1, B-2, ..., 1を取得
- 2B, 2B-1, ... , B+1を取得してゆくが、2Bと3.以降の3B, 4B, ... , ABのBの倍数部分は必ず取得するようにしたい。2B-1以降の数で、その数を取得すると最終的な取得数がN個より多くなる場合は数の取得をやめる。
- 3B, 3B-1, ..., 2B+1についても同様。これをAB, AB-1, ..., (A-1)B+1の列まで繰り返す
このとき取得した数列は長さがN、最長増加列の長さがA、最長減少列の長さがBである。この数列を座標圧縮することで、1からNの数列とすることができる。数の取り方から、A+B-1 ≦ N, AB ≧ Nである場合は必要な数列が取得できることが分かる。
逆に、N, A, Bの設定を満たす数列を取得するためにはA+B-1 ≦ N, AB ≧ Nが必要であることを満たす。
A+B-1 ≦ N については、最長増加列と最長減少列が高々1つの数を共有することから示される。
AB ≧ Nについては、f(i)をi番目の数を増加列の最終項としてもつ増加列の長さの最大値とすると、f(i)の値で数列をグルーピングできる。同じf(i)を持つ数を数列中の順番に並べると、減少列をなす。よって、グループ数は最長の増加列の長さであるA以下、各グループの個数は最長の減少列の長さであるB以下であるため、示される。
