ABC191F - GCD or MIN
解答：Submission #20060874 - AtCoder Beginner Contest 191
解法：
「最終的に残る数」の構成
gcd(a, b) ≦ min(a, b) より、最終的に残る数はmin(A)以下である（以降min(A)をAminと呼ぶ）。また、あるAi1, Ai2, ..., Aixに対し、gcd(Ai1, Ai2, ..., Aix)はAmin以下であれば最終的に残る数の候補となりそうである。
実は最終的に残る数はAmin以下のgcd(Ai1, Ai2, ..., Aix)で構成される。X：最終的に残る数、Y：{gcd(Ai1, Ai2, ..., Aix), Amin以下}とし、X = Yであることを示す。
X⊂Yを示す。x∊Xに対し、A1, ..., ANの順列と、gcd or minの操作のN-1個の操作の選択が対応する。このときAisとAis+1に対し、gcdの操作が行われる場合はAisとAis+1をどちらも残し、minの操作が行われる場合は小さい方を残す作業を考える。この作業で最終的に残ったものにgcdの操作を行うと、その結果はxになり、かつx∊Yが言える。
Y⊂Xを示す。y∊Yに対し、以下の場合分けを考える。
なお、gcd(Ai1, Ai2, ..., Aix)は単項のgcdをgcd(Ai) = Aiとして定義する。本問で最終的に残る数はAmin以下であり、単項gcdとしてはAminしか採用されない。
gcd(Ai1, Ai2, ..., Aix)の全探索
gcd(Ai1, Ai2, ..., Aix)の全探索は愚直にやると指数時間のオーダーが必要となる。実は次のような効率のよいアルゴリズムが存在する。
- 各Aiの約数jに対し、変数tjを定義し、tj = Aiとする。既にtjが定義されている場合はtjをgcd(tj, Ai)に置き換える
- i = 1, 2, ..., Nに対し上記の操作を行い、最終的にtj = jとなっているものがgcd(Ai1, Ai2, ..., Aix)によってあらわされる数となる
X：上記アルゴリズムで生成される数の集合、Y：gcd(Ai1, Ai2, ..., Aix)の集合とし、X = Yを示す。
X⊂Yを示す。x∊Xとする。最初にtxが定義されるときのAの項をAiとすると、xはAiの約数である。このときx=Aiであれば、x=gcd(Ai)でありx∊Yである。x<Aiのときはxの定義より、Aiとは別の項のAj1, ..., Ajtが存在し、x = gcd(Ai, Aj1, ..., Ajt)となっているはずである。よってこの場合もx∊Yである。
Y⊂Xを示す。y∊Yとする。
- yがAの1つの項のAiのgcdであるとき
y = gcd(Ai) = Aiである。このとき、tAiに対する上記アルゴリズムの操作と、それに対するtAiの挙動を確認する。- Aiより前の項の操作
y | AgなるAgが存在したとすると、tAi = Agとして定義される。ただし、Ag以降にy | AhなるAhが1つでもあれば、tAi = gcd(Ag, Ah)となる。このとき、y' = gcd(Ag, Ah)とすると、gcdの性質よりy | y'である。 - Aiの操作
y | AgなるAgが存在したとき、tAiはy | y''なるy''を用いてtAi = y''と表せる。AiではtAi = gcd(y'', y) = yとなる。存在しなかったとき、tAi = yとして定義される。いずれの場合もtAi = yとなる。 - Aiより後の項の操作
y | AjなるAjではtAi = gcd(y, Aj) = yのままであるし、y | AjでないAjはtAiに影響を与えない。よって最終的にtAi = y = Aiとなる。
- Aiより前の項の操作
- yが複数の項のgcdであるとき
gcdに現れる項Aiに対してはy | y'なるy'が存在し、tAi = y'となる。また、gcdに現れる項の操作がすべて完了するとtAi = yとなる。gcdに現れない項Ajの操作については、y | AjであるAjではy | y'なるy'が存在し、tAj = y'となるし、y | AjでないAjはtAiに影響を与えない。よってこれも最終的にtAi = yとなる。
ABC189 F - Sugoroku2
解答：Submission #19664058 - AtCoder Beginner Contest 189
解法：M個以上の連続した「スタートに戻る」マスがあればゴールに到達不可能であり、その場合は-1を出力する。それ以外はゴールに到達可能となる。
期待値の独立性より、ある状態xの期待値dp[x]は、その一つ先の状態yiとその状態への遷移確率piを用いて下記のように表現される（多分）。
dp[x] = Σ (dp[yi]+1) * pi
仮に「スタートに戻る」というマスがない場合は、上記のdp遷移式により、dp配列を添字の大きい方（後ろの方）から埋めてゆくとよい。
「スタートに戻る」とはdp[0]の状態になることであるので、「スタートに戻る」マスはyi = 0と置くことにより立式は可能である。dp配列を添字の大きい方から求めてゆくと、dp[0]の立式では左辺と右辺にdp[0]が登場することになる。dp[0]の係数は1でなく（※）、dp[0]の一次方程式として解答を算出できる。 ※要証明だが、おそらく「M以上の連続する「スタートに戻る」マスがない」がまさに必要十分条件と思われる。
また、x > 0なるdp[x]の立式ではdp[0]の値を適当に仮置きし、最終的にdp[0]の計算結果と仮置き値の誤差を図り、その誤差を0にするように三分探索してもよい（誤差が非負となる最小の仮置き値を求める）。提出解答では誤差を差の絶対値としたため、三分探索で求めている。
ABC189 E - Rotate and Flip
解答：Submission #19699054 - AtCoder Beginner Contest 189
解法：与えられた4種類の座標変換は、tT = [x, y, 1]に対し、3×3の行列Aを左から乗じることで計算することが出来る。具体的には下記の通りである。
- [[0, 1, 0], [-1, 0, 0], [0, 0, 1]]
- [[0, -1, 0], [1, 0, 0], [0, 0, 1]]
- [[1, 0, 0], [0, -1, 2p], [0, 0, 1]]
- [[-1, 0, 2p], [0, 1, 0], [0, 0, 1]]
あとは、各回までの変換をO(1)で行うために、その回までの変換行列を累積積のような形で蓄えておき、各クエリにO(1)で答えてゆけばよい。
ABC168 E - ∙ (Bullet)
解答：Submission #19557514 - AtCoder Beginner Contest 168
解法：美味しさA、香り高さBのイワシを(A, B)と表記する。
(0, 0)のイワシはどのイワシとも一緒にクーラーボックスに入れない。よって(0, 0)のイワシは別に考え、最終的な答えに(0, 0)のイワシの匹数を足せばよい。
Ai * Aj +Bi * Bj = 0の等式が成り立つ(Ai, Bi), (Aj, Bj)に対して、(Ai, Bi)の（同符号の）倍数・約数、(Aj, Bj)の（同符号の）倍数・約数に変えても等式が成り立つことは変わらない。よって、di = gcd(Ai, Bi)とし(Ai, Bi)を(Ai / d, Bi / d)に置き換えてグループ化して考えてよい。また、Ai = 0かつBi ≠ 0のイワシはAj ≠ 0 かつBj = 0のイワシとのみ仲が悪い。よって前者を(1, 0)、後者を(0, 1)としてグループ化する。
クーラーボックスに一緒に入れることができるイワシの組み合わせを考える。このとき仲が悪い同士のグループをペアにして考える。異なるペア間では入れ方は独立して決めることができ、組み合わせの数は掛け算となる。同じペア同士では、片方のグループのイワシが入るともう片方のイワシが入らないという関係性がある。グループAとグループBがペアになっている（仲が悪い同士）とすると、このペアのイワシの組み合わせ数は2 ^ |A| + 2 ^ |B| - 1となる。
なお、各ペアの組み合わせを考えるときにはイワシが全く入らないケースも考慮し、最後にその場合を取り除くことに注意する。
ABC178 F - Contrast
問題：F - Contrast
解答：Submission #19529927 - AtCoder Beginner Contest 178
解法：AとB合わせてN+1個以上含まれる数字がある場合は、どのように並べ替えてもAとBとでかぶる場所が生じてしまうためNoを出力する。実はそれ以外の場合はBを適切に並べ替えることにより、Aとかぶる数字をなくすことが出来る。さらにいうと、そのようなBの並べ方はシフトのみで実現できる。
C[i]を「Aの要素でi以下のものの個数」、D[i]を「Bの要素でi以下のものの個数」とする。このとき半区間(C[i-1], C[i]]はAの中でiが現れる場所を表現する。Bを右にx個シフトすることによりAとBがかぶらない状態にできるとするとき、全てのiについてC[i] ≦ x + D[i-1] かつ x + D[i] ≦ C[i-1] + Nが成り立つ（要素iがかぶらない条件）。これを整理すると、すべてのiに対し C[i] - D[i-1] ≦ x ≦ C[i-1] - D[i] + N という条件になる。このようなxが1つ存在することは証明できる（解説参考）ため、C[i] - D[i-1]の最大値をxとおけばよい。これは直感的には、「かぶらないようにするために最も右に動かさなくてはならない数字」に合わせてB全体を右シフトするようなイメージである。
キーエンス プログラミング コンテスト 2021 C - Robot on Grid
解答：Submission #19484879 - KEYENCE Programming Contest 2021
解法：空白マスの取扱いが難しい。(1, 1)から(r, c)までの1つのパスを考える。通常このパスは1通りであるが、パス中に空白マスがある場合、この空白マスはXまたは(RもしくはD)の2通りに置き換えることが出来る。また、このパスで通らなかった空白マスについてはX, R, Dの3通りに置き換えることができる。
よって、dp[r][c]を「(1, 1) から(r, c)までのパスの総数」とすると、dp[r][c]はdp[r-1][c] or dp[r][c-1]から遷移するが、空白マスの遷移からは2倍して遷移させ、一方でlを「(1, 1) - (r, c)内空白マスの総数 」、xを「各パスにおける空白マスの数」とし、 各パスごとに3^(l-x)を乗ずる。これは遷移の際に2/3を乗じ、最後に3^lを乗ずるのと同値である。
ABC186 F - Rook on Grid
解答：Submission #19457973 - Panasonic Programming Contest (AtCoder Beginner Contest 186)
解法：右→下と動く場合と下→右と動く場合に分けて考える。
①右→下と動く場合：各列ごとに最初に当たる障害物の行座標を覚えておき、その障害物までのマスを1列目の障害物に当たるまで足してゆけばよい。
②下→右と動く場合：同様に各行ごとに最初に当たる障害物の列座標を覚えておき、その障害物までのマスを1行目の障害物に当たるまで足してゆけばよい。ただし、①で既に足したマスが足される可能性があるのに注意。既に足されたマスを除くためには、segtreeなどで各列ごとに「まだ障害物に当たっていなければ1、そうでなければ0」という情報を保持し、各行ごとに1列目から障害物に当たるまでのsegtree上の1の数を合計して全体の答えから引けばよい。
