解答：https://atcoder.jp/contests/abc339/submissions/49982630
解法：解説AC。dp[i][x]を「数列をi番目まで見たとき、①そのi番目の数がxであればi番目まででできる題意を満たす部分列の最大長、②そのi番目の数が0でなければ0」というdp配列を考える。 このとき、dpの遷移は以下となる。
dp[i][x] = max(dp[j][x]) (x = , j < i, x - D ≦
≦ x + D)
よって、dp配列を最大値取得のセグ木で持たせ、各について、その
の±Dに存在する
の最大値をセグ木で取得しつつ、セグ木を更新してゆけばよい。
（こういうの何度か見ている気がするが、苦手…）
解答：https://atcoder.jp/contests/abc302/submissions/41636421
解法：解説AC。
頂点1からNの後に、1からMまでの整数に対応する超頂点を導入する。どちらも0-indexに変換して、0~N-1を頂点に、N~N+M-1を超頂点に対応させる。また、集合Siが整数jを有する場合に、頂点i-1と超頂点N+j-1の間に無向辺を張る。すると当問題は、この拡張グラフの上でBFSを行い、超頂点Nから超頂点N+M-1に到達する最短距離を求める問題に変換することができる。
個人的に最短距離とマージ回数の関係が少し悩ましく感じた。仮にN→0→N+M-1と行けるのであれば、最短距離は2であり、マージ回数は0（集合S1が1とMとをどちらも有している）である。N→0→N+1→1→N+M-1であれば、最短距離は4であり、マージ回数は1（集合S1が1と2を有し、集合S2が2とMを有するため、集合S1と集合S2をマージ）である。
この考察（もう少し経路を増やしてもよい）より次のことが分かる。最短距離は超頂点→頂点→超頂点→頂点→超頂点…と、超頂点と頂点を繰り返しているが、最初の超頂点→頂点と最後の頂点→超頂点からの移動はマージ回数に影響せず、その間の移動はマージ回数のちょうど2倍となっている。よって、最短距離をdistとすると、(dist - 2) / 2がマージ回数となる。
解答：https://atcoder.jp/contests/abc295/submissions/40056127
解法：l, r間で各数字が偶数個出ていればOK。数字の個数を累積和で管理すると、l, rで各数字の個数の偶奇がそろっていればよい。
とすると、各数字の個数は偶奇の情報を持てばよく、さらにそれをビットの情報としてとらえれば、0~1023(2047?)以下の1つの整数に置き換えることができる。
あとは同じ数字ごとに個数をカウントしてゆき、l, rの組み合わせとしてどのように取り出せるかを考えらればよい。これは、個数カウントをnとするとnC2となる。ただし、l＝1のケースは数字が0の場合に該当するため、数字が0の時のカウントをさらに足してあげる必要がある。
解答：Submission #27305078 - KEYENCE Programming Contest 2021 (AtCoder Beginner Contest 227)
解法：何となく部署の人数が多い方から一人ずつ集めるとよさそうだが、a[i]を減らしていって新たにタイが発生するところからわかりにくくなる。
実はプロジェクトの数を決め打つにぶたんが使える。プロジェクト数をxとすると、最低限必要な人数はK * xである。各部署から集められる人数について、1つの部署からx+1人を集めてしまうとかならずその部署のひとがかぶるプロジェクトが出てくるため、上限はx人となる。よって、各部署から集められる人数の合計はΣmin(a[i], x)である。したがって、Σmin(a[i], x) ≧ K * xでなければ、そもそもプロジェクトの人数を集めることができない。
実は、Σmin(a[i], x) ≧ K * xであれば、かならず部署がかぶらずに人を割り当てることが出来る。プロジェクト1, 2, ..., xに対し、部署1からmin(a[1], x)人、部署2からmin(a[2], x)人、...と順番に割り当ててゆく。すると、仮に一つの部署から最大x人集まったとして、最初の人の割当プロジェクトをkとすると、各人の割当プロジェクトk, k+1, ..., x, 1, 2, ..., k-1となり、重なることはない。
解答：Submission #25886274 - AtCoder Beginner Contest 218
解法：各辺を除いて逐一最短経路の算出をやると、辺の数がN2のオーダーなので、例えばダイクストラならO(N3logN)で間に合わないっぽい。
ここで一つ最短経路が見つかったとする。すると最短経路以外の辺は除いても最短経路を通れるのでその最短経路の長さを返せばよい。最短経路上の辺は愚直に最短経路の算出をやることになるが、最短経路は最長でN-1であるため、O(NlogN + N2logN)で間に合う。
解答：Submission #24919698 - AtCoder Beginner Contest 212
解法：DP。
dp[i][j]：i日目に都市jにいるときの場合の数とする。答えはdp[K][0]である。
Eを使える道の集合とする。
dp[i][j]
= Σdp[i-1][k] ( (k, j) in E)
= Σdp[i-1][k] (all k) - Σdp[i-1][k] ( (k, j) NOT in E)
ここで、「all k」は各j間で使いまわし可能、「(k, j) NOT in E」は問題で与えられる辺の集合で全てのjを計算しても高々5000である。よって最終的な計算量はO(K * (N + M))となり、間に合う。
解答：Submission #24895895 - AtCoder Beginner Contest 213
解法：01BFSが使える。
移動先をdequeに格納する。通常の移動はpush_front、パンチ後の移動をpush_backするとよい。
