2024-02-21

競プロ典型90問　★4

競プロ典型90問：https://atcoder.jp/contests/typical90

001 - Yokan Party

問題：https://atcoder.jp/contests/typical90/tasks/typical90_a

解答：https://atcoder.jp/contests/typical90/submissions/27846976

解法：「K+1個のピースにしたとき、最も小さいピースをx以上に出来るか」という判定問題を考える。これはようかんを前から見てゆき、ピースの長さがx以上となったら切れ目を入れてゆき、最終的にK個の切れ目を入れられれば出来る。本問ではこの判定問題を利用して二分探索を用いて、この判定問題が可能となる最大のxを求めればよい。

003 - Longest Circular Road

問題：https://atcoder.jp/contests/typical90/tasks/typical90_c

解答：https://atcoder.jp/contests/typical90/submissions/21919448

解法：その2頂点を結ぶ辺が木の直径となっている2頂点について辺を追加するのが最大となる。よって求める値は「木の直径+1」である。

008 - AtCounter

問題：https://atcoder.jp/contests/typical90/tasks/typical90_h

解答：https://atcoder.jp/contests/typical90/submissions/21919499

解法：Tを"atcoder"とする。dp[i][j]を「文字列Sのi文字目まで見たとき、そのi文字目で文字列Tのj文字目までを作成するときの通り数」と定義する。
このdp配列はS[i] = T[j]のときdp[i][j] += dp[i-1][j-1]と遷移する。このdpについてdp[N][7]が最終的な答えとなる。（提出コードでは添字iに関しdp配列を使いまわしている）

012 - Red Painting

問題：https://atcoder.jp/contests/typical90/tasks/typical90_l

解答：https://atcoder.jp/contests/typical90/submissions/25164513

解法：Union-Find木を用いる。クエリ1の実行時、赤色マスの上下左右4マスについて、赤色マスがあれば自マスとそのマスを併合する。クエリ2では対象の2マスが両方赤マスかつ同じグループであればYesを返し、そうでなければNoを返せばよい。

026 - Independent Set on a Tree

問題：https://atcoder.jp/contests/typical90/tasks/typical90_z

解答：https://atcoder.jp/contests/typical90/submissions/25164643

解法：重要な事実として、木は二部グラフである。そのため、二部グラフの頂点の塗り分けを行い、多い方の色の頂点を返せばよい。

028 - Cluttered Paper

問題：https://atcoder.jp/contests/typical90/tasks/typical90_ab

解答：https://atcoder.jp/contests/typical90/submissions/27850578

解法：2次元いもす法を用いる。具体的には以下の手順となる。

2次元配列imos2dを準備する
各長方形lx[i], ly[i], rx[i], ry[i]に対し
imos2d[lx[i]][ly[i]], imos2d[rx[i]][ry[i]]に1を加算し
imos2d[lx[i]][ry[i]], imos2d[rx[i]][ly[i]]に1を減算する
imos2dについて、行ごとに列方向の累積和を取る
imos2dについて、列ごとに行方向の累積和を取る

034 - There are few types of elements

問題：https://atcoder.jp/contests/typical90/tasks/typical90_ah

解答：https://atcoder.jp/contests/typical90/submissions/27855603

解法：区間[l, r]内にある整数の種類がK以下であるようなl, rをしゃくとり法を用いて走査してゆく。主に以下のような実装方針とした。

lをforループとし、各lに対するrの最大値を求めてゆく(rは広義単調増加)。
各lに対し、rがn未満かつ[l, r]内の整数の種類数がKである限りrを増加させる。種類数の計算はmapを使用する。
rを増加させきったら、次のループに備え種類数管理のmapを更新する。

2021-02-06

第四回アルゴリズム実技検定（A～L）

A - 中央値

解答：Submission #17975213 - 第四回アルゴリズム実技検定

解法：ソートして2番目のものを答える。解答はA, B, Cで出力する必要があるため、元の添え字を覚えておき、charとして出力する。

B - 電卓

解答：Submission #17976377 - 第四回アルゴリズム実技検定

解法：y = 0 ならERRORを先に出力してしまう。そうでない場合、100倍してintの切捨除算を行った後、double型で小数表示すればよい。計算誤差も大丈夫そう。

C - 隣接カウント

解答：Submission #17978357 - 第四回アルゴリズム実技検定

解法：#の数を愚直に数える。外側に1マスずつ.のマスを追加しておくと境界条件を減らすことができる。

D - 分身

解答：Submission #19195860 - 第四回アルゴリズム実技検定

解法：タイプAとタイプBの操作はそれぞれ結果が順番によらず回数のみによる。そのため(タイプAの操作回数, タイプBの操作回数)の操作回数の和の小さい順にBFSで実際に操作をシミュレーションすればよい。

E - アナグラム

解答：Submission #18024607 - 第四回アルゴリズム実技検定

解法：next_permutationを使い、文字列の並べ替え全てで条件に合致するかを確認する。

F - 構文解析

解答：Submission #18024607 - 第四回アルゴリズム実技検定

解法：mapを使って文字列ごとの出現回数を調査し、Ｋ番目に大きいものを解答すればよい。ただし、タイがある場合にはAMBIGUOUSを出力する。タイの判定方法は、K-1番目とK番目の文字列の出現回数が同じ、もしくはK番目とK+1番目の文字列の出現回数が同じ場合、かつその時に限りタイになるとすればよい。

G - 村整備

解答：Submission #18041579 - 第四回アルゴリズム実技検定

解法：#のマスごとに、そのマスを.に変えた場合に「全てのマスから全てのマスに行き来できるか」を確認し、行き来できたマスの数をカウントする。「」部分の確認は、.であるマスからDFSを開始し、1回の探索で全てのマスに行けることを確認すればよい。

H - マス目のカット

解答：Submission #18163458 - 第四回アルゴリズム実技検定

解法：先に正方形として抽出する範囲を決め、「その正方形の数字を同じ数字にするために変えるべき数字の最小値」がK以下である場合に、そのときの正方形の1辺の長さを出力すればよい。

解法：取りうる（連続した）添字集合を $S$ 、a[i]の合計を $Sum$ とすると、 $|2 \sum_{i \in S} ai - Sum |$ を最小化すればよい。これは連続した添え字のうち左端を固定すると右端はざっくり $\sum ai$ が $Sum/2$ 以下となるもの、または $\sum ai$ が $Sum/2$ より大きくなるものの2種類を調べればよく、これはしゃくとり法で実装できる。

J - ワープ

解答：Submission #18635507 - 第四回アルゴリズム実技検定

解法：ワープも考慮してダイクストラ法を使いたいが、ワープの各頂点を愚直に結ぶと辺の数がN²のオーダーになってしまう。ain, bin, cin, aout, bout, coutの6つの頂点を別に用意し、以下の辺を追加してダイクストラ法を行えばよい。

タイプAの頂点とainをコスト0で結ぶ(B, Cも同様)
ainとboutをコストX_ABで結ぶ(他のin, out頂点も同様)
aoutとタイプAの頂点をコスト0で結ぶ(B, Cも同様)

K - 転倒数

解答：Submission #18649815 - 第四回アルゴリズム実技検定

解法：作成中です。公式解説はコチラ

L - マンションの改築

解答：Submission #18663672 - 第四回アルゴリズム実技検定

解法：mapに(隣接項の差, 偶奇)ごとの個数を記憶しておく。また、t=1による増減分をev, t=2による増減分をodという変数に持たせることとする。

t=1, 2の時ev, odをそれぞれ更新する。mapで取得すべき項目は変化するが、map自体は変化しない。t=3の時はmapを更新する。

2020-12-27

Educational DP Contest / DP まとめコンテスト（A～U）

A - Frog 1

問題：https://atcoder.jp/contests/dp/tasks/dp_a

解答：https://atcoder.jp/contests/dp/submissions/3938370

解法：dp[i]を「カエルが足場iに辿り着くまでに支払うコストの最小値」とする。dp[i] = min(dp[i-2] + abs(h[i-2] - h[i]), dp[i-1] + abs(h[i-1] - h[i]))であり、これを順番に求めてゆけばよい。

B - Frog 2

問題：https://atcoder.jp/contests/dp/tasks/dp_b

解答：https://atcoder.jp/contests/dp/submissions/3939065

解法：前問と同様に、dp[i]を「カエルが足場iに辿り着くまでに支払うコストの最小値」とする。dp[i] = min(dp[i-k] + abs(h[i-k] - h[i]), dp[i-k+1] + abs(h[i-k+1] - h[i]), ..., dp[i-1] + abs(h[i-1] - h[i]))である。min部分をループにして計算するとよい。

C - Vacation

問題：https://atcoder.jp/contests/dp/tasks/dp_c

解答：https://atcoder.jp/contests/dp/submissions/3939799

解法：dp[i][j]を「i日目に行動jを行った場合に、i日目までに得る幸福度の最大値」として計算してゆく。前日に同じ行動をとらないようにdp計算を行う。

D - Knapsack 1

問題：https://atcoder.jp/contests/dp/tasks/dp_d

解答：https://atcoder.jp/contests/dp/submissions/3940486

解法：dp[i][j]を「i番目までの商品を用いて重さがjとなるときの価値の最大値」として計算してゆく。

E - Knapsack 2

問題：https://atcoder.jp/contests/dp/tasks/dp_e

解答：https://atcoder.jp/contests/dp/submissions/3939799

解法：dp[i][j]を「i番目までの商品を用いて価値がjとなるときの重さの最小値」として計算してゆく。

F - LCS

問題：https://atcoder.jp/contests/dp/tasks/dp_f

解答：https://atcoder.jp/contests/dp/submissions/3952280

解法：dp[i][j]を「sをi文字目、tをj文字まで用いたときの共通文字列の長さの最大値」とする。sのi文字目とtのj文字目が同じとき、かつその時に限りchmax(dp[i][j], dp[i-1][j-1] + 1)の遷移をすればよい。復元は逆にdp[|s|][|t|]から"逆順に"dpを辿ってゆき、dp[i][j] = dp[i'][j'] + 1となるときに(i, j)のひとつ前として(i', j')を取得してゆく。

G - Longest Path

問題：https://atcoder.jp/contests/dp/tasks/dp_g

方針：dp[u]を「頂点uを始点するパス長の最大値」とすると、dp[u] = max{dp[v] + 1 | vはuの子頂点}となる。またuの出次数が0である場合、dp[u] = 0とする。遷移の方法のさせ方で複数解法がある。また、連結成分が1つとは限らないところに注意が必要。

解答①：https://atcoder.jp/contests/dp/submissions/19009152

解法①：メモ化再帰。どの頂点から始めてもその頂点から出る辺を辿ってゆき、最終的に出次数0の頂点に辿り着き、その頂点からuまでの頂点のdp配列値が決まってゆく。いったん計算されてしまえばあとはそのdp配列値を使いまわすことができる。ちなみにメモ化再帰なので配列名はmemoにしています（趣味です）。

解答②：https://atcoder.jp/contests/dp/submissions/3959327

解法②：頂点番号が小さい頂点からトポロジカルソートを行う。トポロジカルソートの逆順に頂点を辿ると必ず出次数0の頂点からその頂点に入る頂点を辿ってゆくことができる。この順にdpを更新してゆくとよい。

H - Grid 1

問題：https://atcoder.jp/contests/dp/tasks/dp_h

解答：https://atcoder.jp/contests/dp/submissions/3943239

解法：dp[i][j]を「マス(i, j)までの経路の通り数」とする。マス(i, j)はマス(i-1, j)またはマス(i, j-1)から到達することができるので、その2マスからの遷移を考えればよい。

I - Coins

問題：https://atcoder.jp/contests/dp/tasks/dp_i

解答：https://atcoder.jp/contests/dp/submissions/3944117

解法：確率dp。dp[i][j]を「i番目までのコインを使い、表がj枚である確率」とする。dp[i][j]は「dp[i-1][j-1]から表がでる」「dp[i-1][j]から裏がでる」の2通りの出元がある。

J - Sushi

問題：https://atcoder.jp/contests/dp/tasks/dp_j

解答：https://atcoder.jp/contests/dp/submissions/3964795

解法：期待値dp。dp[{i, j, k}]を「寿司1個の皿がi枚、寿司2個の皿がj枚、寿司3個の皿がk枚のときに、全ての寿司がなくなるまでの操作回数の期待値」とする。状態の持たせ方の工夫として、寿司の個数さえわかれば皿の番号は不要である点、寿司0個の皿の枚数は自動的に分かる点に注意が必要である。

遷移が難しい。{i, j, k}の状況から次にどうなるかというと、下記の遷移がありえる。

確率i / nで{i-1, j, k}の状態になる
確率j / nで{i+1, j-1, k}の状態になる
確率k / nで{i, j+1, k-1}の状態になる
確率(n - i - j - k) / nで{i, j, k}の状態のまま

これらの状態は{i, j, k}から試行回数が1回多い状態であるため、期待値ベースで下記の式が成立する。（要証明）

dp[{i, j, k} ] = i / n * dp[{i-1, j, k}] + j / n * dp[{i+1, j, k}] + k / n * dp[{i, j+1, k-1}] + (n - i - j - k) / n * dp[{i, j, k}] + 1

両辺にdp[{i, j, k} ] があるため整理すると、numer = x + y + zとして
dp[{i, j, k} ] = i / numer * dp[{i-1, j, k}] + j / numer * dp[{i+1, j, k}] + k / numer * dp[{i, j+1, k-1}] + n / numer
が成り立つ。この式に従い、メモ化再帰すればよい。

K - Stones

問題：https://atcoder.jp/contests/dp/tasks/dp_k

解答：https://atcoder.jp/contests/dp/submissions/3969759

解法：ゲームdp。dp[i]を「残りの石の個数がi個のときに先手が勝てるか」を表すbool型の配列とする。このとき、dp[i]はdp[i-a[j]] (i - a[j] ≧ 0)に遷移することができるが、dp[i-a[j]]に一つでも先手負けのものがあればその手を用いて（先手になった）相手を負かせることが出来る。一方そのようなa[j]がなければ先手負けになる。よってiが小さい方からdp[i]を決めてゆけばよい。

L - Deque

問題：https://atcoder.jp/contests/dp/tasks/dp_l

解答：https://atcoder.jp/contests/dp/submissions/3969759

解法：dp[i][j]を「i+1からj番目までの数字でゲームをするときのX-Yの最大値」とする。ただし手番は1～nまでのカードを使用してその局面になった時の手番で考えるものとする。

(i, j)は(i-1, j)と(i, j+1)に遷移する。また手番ごとに最小値を取るか最大値を取るかが変わるため、それに注意して計算してゆく。

M - Candies

問題：https://atcoder.jp/contests/dp/tasks/dp_m

解答：https://atcoder.jp/contests/dp/submissions/19011906

解法：dp[i][j]を「i番目までの子供まで見たときに、残りの飴の数がj個のときの通り数」とする。N * K が大きいのでdp配列は前回のもののみを保持する(bef)。

i-1番目からi番目への遷移を考える。i番目の子供は0個以上a[i]個の飴を受け取ることができる。よってdp[j] = bef[j] + bef[j+1] + ... + bef[j+a[i]]である。また、dp[j-1] = bef[j-1] + bef[j] + ... + bef[j+a[i]-1]である。よって、両者の違いは+bef[j-1] - bef[j+a[i]]であり、jごとにこの差分を調整してdp[j]を計算してゆけばよい。

N - Slimes

問題：https://atcoder.jp/contests/dp/tasks/dp_n

解答：https://atcoder.jp/contests/dp/submissions/19024098

解法：dp[l][r]を「l番目からr番目のスライムを合体させるのにかかるコストの最小値」とすると、dp[l][r] = min{dp[l][l] + dp[l+1][r], dp[l][l+1] + dp[l+2][r], ..., dp[l][r-1] + dp[r][r]} + (a[l] + a[l+1] + ... + a[r])である。N≦400なので3乗が間に合うため、この計算を愚直にやるとよい。なお、メモ化再帰にすると計算順序を明示する必要がない。また、スライムが1体でいるときにコストはかかっていないため、dp[i][i] = 0であることに注意。

O - Matching

問題：https://atcoder.jp/contests/dp/tasks/dp_o

解答：https://atcoder.jp/contests/dp/submissions/19037739

解法：2^21 = 2097152なのでビットDPができる。dp[S]を「すでにペアが決まった女性の添字集合をSとしたときのペアの通り数」とする。このとき男性は先頭から決めてゆくすると男性の添字を記憶する必要がなくなる。貰うDPとすると計算量が測りやすい。配るDPは枝刈りにより計算量を落とせるらしい。公式解説で少し触れられている。

P - Independent Set

問題：https://atcoder.jp/contests/dp/tasks/dp_p

解答：https://atcoder.jp/contests/dp/submissions/19038900

解法：根付き木と考え、葉から順番に色を決めてゆくことを考える。ある頂点はその子の色に関わらず白色になる。また、その子が全て白の場合のみ黒色となる。よって、dp[i][j]を「頂点iの部分木の塗り方の総数。ただしj=0の時頂点iは白色、j=1のとき頂点iは黒色に塗られる。」とし、葉から値を決めてゆく。葉からの値の決め方はdfsの帰りがけに値を親に反映する。

別の視点としては、トポロジカルソートを行い、トポロジカルソートの逆順に頂点を見ていくと必ず子⇒親の順に頂点を見てゆくことが出来る。

トポロジカルソートを使った解法⇒https://atcoder.jp/contests/dp/submissions/19038640

Q - Flowers

問題：https://atcoder.jp/contests/dp/tasks/dp_q

解答：https://atcoder.jp/contests/dp/submissions/19039171

解法：dp[i]を「1番目からi番目までの花を使った時の美しさの最大値（i番目は必ず使う）」とする。このときdp[i] = max(dp[j] | j < i, h[j] < h[i]) + a[i]である。maxを取る際にi未満のjを走査しなければならず高速化が必要。ここでは1点更新最大値取得のセグメント木を用いる。

h[i]が1からnまでの順列となっているため、h[i]自体を添字に見立てるとよい。すなわちj番目の花の時には、セグメント木の前からh[j]番目にdp[j]を格納すれば、その後i > jなるiに対しては最初の項からh[i]番目未満までのdpの最大値を取得できる。

R - Walk

問題：https://atcoder.jp/contests/dp/tasks/dp_r

解答：https://atcoder.jp/contests/dp/submissions/19039600

解法：取得すべきパス長がかなり長く、愚直にはできそうにない。一旦次のようなdpを考える。dp[x][i][j]：「i番目の頂点からj番目の頂点に行くパス長xのパスの総数」とする。このとき遷移としては長さx-1のパス長に長さ1のパスをつなげればよいため、dp[x][i][j] = Σ dp[x-1][i][k] * a[k][j] である（k = 1～nの和）。この式をよく眺めると、実は行列の積の構造と同じである。初期状態は各頂点上からパスを考えることより、dp[0][i][j] = 1 (i = j)、dp[0][i][j] = 0 (i ≠ j)である。すなわちdp[0]は単位行列であり、dp[x] = A^xという行列累乗で求められることになる。

S - Digit Sum

問題：https://atcoder.jp/contests/dp/tasks/dp_s

解答：https://atcoder.jp/contests/dp/submissions/19040063

解法：桁DPを用いる。dp[i][j][e]を「先頭からi番目の数字までを使い、先頭からi番目までの数字の和がj (mod d)のである数の種類数。ただし、e = 1のときはもともと与えられたkと同じ数の種類数を表し、e = 0であればもともと与えられたkより小さい数の種類数を表す。」とする。（長いですね。。）

eの遷移が肝である。i-1桁目からi桁目への遷移について以下のことが言える。

eが1から1に遷移する場合、i桁目の数字はsiである
eが1から0に遷移する場合、i桁目の数字は0～s[i]-1である
eが0から0に遷移する場合、i桁目の数字は0～9である

このようにeの場合分けにより遷移先の数字が決まり、それに伴い保持すべき数(mod d)も計算・更新できることとなる。

T - Permutation

問題：https://atcoder.jp/contests/dp/tasks/dp_t

解答：https://atcoder.jp/contests/dp/submissions/19041461

解法：すでに使用した番号の添字集合(bit)を持ちたくなるが、N≦3000なのでできない。i番目の数字のときに「その数字より大きい数がいくつ残っているか」を状態にするのが肝であり、遷移が少し複雑だがこれでうまくいく。

U - Grouping

問題：https://atcoder.jp/contests/dp/tasks/dp_u

解答：https://atcoder.jp/contests/dp/submissions/19042811

解法：dp[x]を「添字集合xに含まれるウサギについてのグループ分けによる得点の最大値」とする。dp[x]は以下のうちいずれかで最大値を取る。

xに含まれる全てのウサギを同じグループにする
y ⊂ x なる全てのyについて、xをyとx-yに分割してdp[y] + dp[x-y]に帰着させる（ただし、y ≠ ∅かつy ≠ x）

実装はメモ化再帰だとdp[y]とdp[x-y]が求めやすい。また、y ⊂ xなるyを走査する部分はy = (y-1) & xでyを更新してゆくと無駄なく計算できる。

2020-12-27

第三回アルゴリズム実技検定（A～N）

A - ケース・センシティブ

問題：https://atcoder.jp/contests/past202005-open/tasks/past202005_a

解答：https://atcoder.jp/contests/past202005-open/submissions/19493993

解法：まず文字列としての比較を行い、一致していればsameを出力する。そうでない場合、s, tともに大文字に変換し、一致すればcase-insensitiveを出力する。いずれにも当てはまらない場合、differentを出力する。

B - ダイナミック・スコアリング

問題：https://atcoder.jp/contests/past202005-open/tasks/past202005_b

解答：https://atcoder.jp/contests/past202005-open/submissions/19494010

解法：各問の現在の得点を保持する1次元配列probと各参加者が各問を解いたかどうかの2次元配列solvedを準備しておく。クエリの処理は以下の通り。

クエリ1
- 参加者xが問題iを解いているかをsolved[x][i]より判断し、solved[x][i]がTrueなら現在の配点であるprob[i]を参加者の得点に加算し、合計得点を出力する。
クエリ2
- 参加者xが問題yを解いたというクエリに対し、prob[y]を1減らし、solved[x][y]をTrueにする。

C - 等比数列

問題：https://atcoder.jp/contests/past202005-open/tasks/past202005_C

解答：https://atcoder.jp/contests/past202005-open/submissions/19494023

解法：第n項を求めようとするとオーバーフローする可能性がある。aにn-1回rを掛けていき、10^9を超えた時点でlargeを出力し、largeが出力されなかったものについて最終値を出力すればよい。

D - 電光掲示板

問題：https://atcoder.jp/contests/past202005-open/tasks/past202005_D

解答：https://atcoder.jp/contests/past202005-open/submissions/19494041

解法：0-9までの数字は5行の3文字配列で表現される。これらをすべて配列に格納し、与えられた文字列を先頭からみてゆき、0-9のどれかの数字に合致することを調べ、その数字の列を出力すればよい。

E - スプリンクラー

問題：https://atcoder.jp/contests/past202005-open/tasks/past202005_E

解答：https://atcoder.jp/contests/past202005-open/submissions/19494056

解法：愚直にやればよい。具体的には、各頂点の現在の色をを配列に保持し、以下のようにクエリに対応してゆく。

クエリ1
- 現在の色を出力する
- 自分と隣接頂点の色を変更する
クエリ2
- 現在の色を出力する
- 自分の色を変更する

F - 回文行列

問題：https://atcoder.jp/contests/past202005-open/tasks/past202005_F

解答：https://atcoder.jp/contests/past202005-open/submissions/19494090

解法：aを先頭(i)及び末尾(n-1-i)から見てゆく。i行目をすべてsetに格納し、n-1-i行目にsetに含まれている文字があればそれを回文の要素にすればよく、そうでない場合はその時点で回文ができないので-1を出力する。

G - グリッド金移動

問題：https://atcoder.jp/contests/past202005-open/tasks/past202005_G

解答：https://atcoder.jp/contests/past202005-open/submissions/19494108

解法：与えられた6通りの移動方法でBFSを行う。座標を配列で処理する場合は、マイナスが最も大きい座標である(-200, -200)がどちらも正となるように平行移動させて考えるとよい。

H - ハードル走

問題：https://atcoder.jp/contests/past202005-open/tasks/past202005_H

解答：https://atcoder.jp/contests/past202005-open/submissions/19494126

解法：dp[x]を「距離x進んだ際にかかる時間の最小値」とする。各地点xから、行動1・2・3それぞれを実施して到達する地点について、各行動でかかった時間を加味してdpを遷移させる（いわゆる配るdp）。各行動ともに到達地点にハードルがあるとT3がかかることに注意。また、ゴールを過ぎるような移動ではゴールまでの移動時間とすることにも注意が必要。

I - 行列操作

問題：https://atcoder.jp/contests/past202005-open/tasks/past202005_I

解答：https://atcoder.jp/contests/past202005-open/submissions/19007860

解法：Nが大きいので愚直に操作するとTLE。配列aの値は添字から計算で求めることができるため、配列行添字の配列(r)、列添字の配列(c)、転置の有無を表すbool型変数(flg)を準備し、クエリに効率的に対応する。

J - 回転寿司

問題：https://atcoder.jp/contests/past202005-open/tasks/past202005_J

解答：https://atcoder.jp/contests/past202005-open/submissions/19494142

解法：各子供が最後に食べたお寿司の美味しさを配列で保持すると、この配列は単調減少となる。この減少列に対し、各お寿司がどの子供に食べられるかを二分探索で探し、美味しさの配列を更新しながら答えを記録してゆく。なお、お寿司の美味しさにマイナスをかけると配列が単調増加となり、実装しやすくなる。

K - コンテナの移動

問題：https://atcoder.jp/contests/past202005-open/tasks/past202005_K

解答：https://atcoder.jp/contests/past202005-open/submissions/19494173

解法：fir[i]を「机iに乗っている一番下のコンテナ番号」、las[i]を「机iに乗っている一番上のコンテナ番号」、par[i]を「コンテナiの下のコンテナ番号」とし、これらを移動のたびに適切に更新することで移動を再現できるようにする。最終的な各コンテナの机番号の取得もfir, parの情報から復元する。

L - スーパーマーケット

問題：https://atcoder.jp/contests/past202005-open/tasks/past202005_l

解答：https://atcoder.jp/contests/past202005-open/submissions/19210008

解法：各客は1番目の棚（N列）、もしくは1・2番目の棚（2N列）から最大の値を見つけることを繰り返すので、この作業の高速化がネックとなる。1番目の棚、2番目の棚をmultisetにすると最大値をO(logN)で取得できるようにする。

あとは商品を取った後に棚の商品が移動する部分の実装が必要となる。multisetの要素を{値、棚の添字}とすることで、最大値を取得した上でその商品の棚がどれかを判別できる。またmultisetから要素を削除するところもO(logN)で実行可能。

棚の商品の移動だが、1番目の棚・2番目の棚とは別に、全ての棚の商品をdeque（の配列）で管理し、1番目の棚から商品がとられる場合・2番目の棚から商品がとられる場合をそれぞれ注意深く実装すればよい。

M - 行商計画問題

問題：https://atcoder.jp/contests/past202005-open/tasks/past202005_m

解答：https://atcoder.jp/contests/past202005-open/submissions/19745933

解法：巡回セールスマン問題の亜種。巡回セールスマン問題は頂点数をnとするとO(n * 2^n)のbitDP解法がある。本問はトータルの頂点数NはN≦10^5であるが、訪れる候補の頂点数KはK≦16であるため、訪れる候補の頂点数KのみのグラフでbitDPを行えるとよさそう。これは訪れる候補の頂点それぞれを始点とするダイクストラで各頂点間の最短距離を求め、訪れる候補の頂点間にその最短距離の辺を張りなおしたグラフで考えればよい。

N - 入れ替えと並び替え

問題：https://atcoder.jp/contests/past202005-open/tasks/past202005_n

解答：https://atcoder.jp/contests/past202005-open/submissions/19889329

解法：愚直にやるとクエリ1でO(1)、クエリ2でO((y - x) log (y - x))かかりそうで、クエリ2が間に合わない。

仮にクエリ2を全てスワップで処理するとする。実はこのときスワップ回数はクエリ全てを通してO(Q)となる。これは転倒数を考えるとよく、クエリ1の1回のスワップで増加する転倒数は高々1であり、クエリ2で戻すべき転倒数が高々クエリ1の回数であるためである。ただしクエリ2のスワップ処理は確実に転倒数を減少させるように行う必要がある。

すなわち、クエリ2のスワップ処理はa[i] > a[i+1]となっている箇所のみを行う必要がある。そのためにはクエリ1のスワップの時点でa[i] > a[i+1]となった箇所を記憶しておき、クエリ2ではx ≦ i ≦ yである箇所を順番にスワップしてゆく。一回のスワップでa[i] > a[i+1]となりうるのは、(i, i+1)のスワップについては(i-1, i), (i, i+1), (i+1, i+2)であるため、スワップのたびに左記3か所について逐一確認してゆけばよい。

2020-12-16

第二回アルゴリズム実技検定（A～L, N）

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の大きさであるため、座標圧縮を行う必要がある。

2020-12-12

第一回アルゴリズム実技検定

A - 2 倍チェック

解答：https://atcoder.jp/contests/past201912-open/submissions/19493518

解法：一文字目からチェックし英小文字ならerrorを出力。全て数字ならstoiして2倍する。

B - 増減管理

解答：https://atcoder.jp/contests/past201912-open/submissions/19493538

解法：前日からの増減分に応じて文字列を出力する。

C - 3 番目

解答：https://atcoder.jp/contests/past201912-open/submissions/19493555

解法：降順にソートし、a[2]を出力する。

D - 重複検査

解答：https://atcoder.jp/contests/past201912/submissions/8943992

解法：各数字が何回aに登場するかをカウントする。カウントが全て1ならば、書き換えは起きていない。そうでないならば、カウント0の数字がカウント2の数字に書き換えられている。

E - SNS のログ

解答：https://atcoder.jp/contests/past201912-open/submissions/19493617

解法：bool型の2次元配列follow[x][y]を準備する。follow[x][y] = true ⇔ xはyをフォローしているとする。
1, 2のクエリは愚直に実装する。3のクエリについて、一旦フォロー対象を別の配列に格納し、全てのフォロワーについてのチェックが終わった後にフォロー反映を行う必要がある。

F - DoubleCamelCase Sort

解答：https://atcoder.jp/contests/past201912-open/submissions/19493632

解法：まずは単語ごとに分割し、全ての単語をvectorに格納する。格納する際は全て英小文字にする。その後ソートし、最初の文字と最後の文字を大文字にして出力する。最初の格納方法に少し工夫が必要。

G - 組分け

解答：https://atcoder.jp/contests/past201912-open/submissions/19493647

解法：全ての組分けを試し、幸福度の最大値を求める。より具体的には、0, 1, 2から成る長さＮの文字列を組分けと対応させ、この文字列を全て生成し、各文字列について幸福度を計算する。

H - まとめ売り

解答：https://atcoder.jp/contests/past201912-open/submissions/9963675

解法：セット販売、全種類販売では、カード数が購入数に満たないカードが一種類でもあれば販売しないのがミソ。セット販売の購入数、セット販売対象カードの最小枚数、全種類販売の購入数、全種類カードの最小枚数を記憶しておき、各クエリ時に適切に更新してゆく。

I - 部品調達

解答：https://atcoder.jp/contests/past201912-open/submissions/19493660

解法：すでに持っている部品のインデックスの集合をビット列と見なして、ビットDPを行う。具体的には、dp[i][S]：i番目のセット販売まで見たときに、持っている部品のインデックスの集合がSである場合の購入金額の最小値を表す。

J - 地ならし

解答：https://atcoder.jp/contests/past201912-open/submissions/10035553

解法：最小コストを実現する経路はあるマス(s, t)が存在して次が成り立つ。

最小コストはdist[((H-1, 0), (s, t)] + dist[(s, t), (H-1, W-1)]+ dist[(s, t), (0, W-1)]
パス(H-1, 0)→(s, t)、(s, t)→(H-1, W-1) 、(s, t)→(0, W-1)が共通して通るマスは(s, t)のみである。

これより、全てのマス(s, t)に対して上記distを計算し、その最小値を求めればよい。ただし、(s, t)には1度入ればそれ以降のコストがかからないため、2A[s][t]を除く必要があることに注意する。

K - 巨大企業

解答：https://atcoder.jp/contests/past201912-open/submissions/19493681

解法：aとbのLCAがbであればYesを出力し、そうでなければNoを出力する。LCAはライブラリを使用した。

L - グラデーション

解答：https://atcoder.jp/contests/past201912-open/submissions/10039677

解法：小さい塔のうち連結するものをあらかじめ決めておき、大きな塔すべてと決めておいた小さい塔の最小全域木の構成コストをクラスカル法で求める。小さい塔の組み合わせを全て試せばＯＫ。

M - おまかせ

解答：https://atcoder.jp/contests/past201912-open/submissions/10040347

解法：蟻本P.132の平均最大化の応用。

平均（1質量あたりの価値）最大化は二分探索の応用で、「C(x)：平均をx以上にできるか」という条件について「 Σ(v[i] - x * w[i]) ≧ 0 」をチェックする。

この問題では通常カード5枚、通常カード4枚+お助けカード1枚のそれぞれについて「 Σ(v[i] - x * w[i]) ≧ 0」をチェックすればよい。

N - 整地

解答：https://atcoder.jp/contests/past201912-open/submissions/10067145

解法：車が通る場所を決めると、各石について取り除く必要があるかどうかが一意に決まる。石が[li, ri]にある場合、車が通る場所の左端点が(li - c, ri)となる場合にその石を取り除かなければならない。このとき石を取り除くためにはコストがpiかかるので、車が通る場所の左端点を設定して取り除く石のコストを合計すればよい。

石の合計コストが変化するのは各石についてli - c(減少)とri(増加)であるため、これらの座標とコスト増減を配列に格納し、座標の小さい方からコストを変化させてゆき、コストの最小値を求める。

コスト増減時に重要な点として、(li - c, ri)は開区間として処理する必要がある。すなわち、石が[li, ri]にある場合、車が通る場所の左端点をli - c, riにそれぞれ設定することが可能であることに注意が必要である。

O - 持久戦

解答：https://atcoder.jp/contests/past201912-open/submissions/10095653

解法：各試行で現れるサイコロの目を数列にすると、狭義単調増加になる。特に、全てのサイコロの中で最も大きい目を出すと、その時点で操作終了となる。

サイコロを区別せずに、xをサイコロの目としたときdp[x]を「そのサイコロの目が出た後にサイコロが何回振れるか」という値とする。このとき dp[x]の値はy>xなるyについてのdp[y]が分かれば算出できる。