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か所について逐一確認してゆけばよい。
