2022-03-10

ABC242D ABC Transform

ABC 二分木再帰

解説AC

問題へのリンク
 公式解説へのリンク

テキストとyoutubeの解説の自分用まとめです。特に新しいことはありません。公式を見た方が詳細です。

二分木として考える

各文字が2つの文字になることを順に図示すると、二分木の構成になります。

よって、この問題は、

$S^{(0)}_0,\ S^{(0)}_1,\ \cdots S^{(0)}_{N-1}$ を根とする二分木における、深さ $t$ で $k$ 番目の文字を求めよ

という問題と見ることができます。

$mod\ 3$ における0,1,2をA,B,Cに対応させます。
Aの左子ノードがB、右子ノードがCであるとします。
左子ノードに進むことは、 $mod\ 3$ において+1すること、右子ノードに降りることは+2することと同じです。B,Cにおいても同様に考えることができます。

よって、親の文字がわかれば子の文字を求めることができます。

以降、+xするという表現は $mod\ 3$ 上での操作を指します。

親と子の番号の関係

深さ $t$ において、 $k$ 番目である場合、その子は、深さ $t+1$ において、左子ノードが $2k$ 番目、右子ノードが $2k+1$ となります。

以下が理由です。
深さ $t$ において $k$ 番目である場合、自分より前には $0,...,k-1$ までの $k$ 個のノードが存在する。
深さ $t+1$ には、それらの子ノードが2個ずつ存在し、その数は $2k$ 個となる。それらの番号は、 $0,...,2k-1$ となるから。

これより、

親が $k$ 番目なら、子の番号は左が $2k$ 、右が $2k+1$
子の番号が $k$ なら親の番号は、 $\lfloor \frac{k}{2} \rfloor$

が言えます。
また、

子の番号が偶数なら親の左子ノード、奇数なら右子ノード

も言えます。

$t$ が小さい場合

解説にならって、 $S^{(t)}$ の $k$ 番目の文字を求める関数を $f(t,k)$ とおきます。

以下のように再帰的に求められます。

$f(t-1,\lfloor \frac{k}{2} \rfloor )$ を求め、 $k$ が偶数なら+1、奇数なら+2します。
$t$ が十分小さい場合、再帰の過程で $t=0$ となります。この時、 $f(0,k')$ を $S^{(0)}_{k'}$ として返せばよいです。

$t$ が大きい場合

深さが1増えると子の数は2倍になります。
深さ $d$ から、60回深いところに進むと、 $0,...,2_{60}-1$ 番目の文字は全て $S^{(d)}_0$ の子孫であることがわかります。

$k$ の最大値は $10^{18} \lt 2^{60}-1$ であることから、 $t$ から60回ほど親を遡ったところを $t'$ とすれば、深さ $t$ の $k$ 番目の文字は全て $S^{(t')_0}$ の子孫となります。

ある深さ $d$ における $S^{(d)}_0$ は、全て $S^{(0)}_0$ の左子ノードを $d$ 回進んだ文字であるので、 $S^{(0)}_0+d$ することで求められます。

以上より、再帰において $k$ を1/2していくと、高々60回ほどで、 $k=0$ となります。このとき、 $f(t',0)$ を $S^{(0)}_0+t'$ として返すようにすればよいです。
提出コード(公式とほぼ同じ)

2022-03-03

ABC241 参加記録

ABC 出次数1の有向グラフ双方向連結リスト Loop 鳩の巣原理

コンテスト中AC:A〜C,E
コンテスト後、Dは自力AC

2022/07/06追記
Eの実装に単射や同値類という記載がありますが、誤りです。無視してください。

D - Sequence Query
E - Putting Candies

D - Sequence Query

実装が複雑になりましたが、自作双方向連結リストでACしました。

出現した整数の昇順ソートされた順序集合 $S$ (set)
初めて出現した整数が双方向連結リストに何番目に挿入されたかを記録するハッシュマップ $M$ (unordered_map)
双方向連結リスト $D$

を準備します。
それぞれにあらかじめ、 $-\infty , \infty$ を入れておきます(番兵)。
$D$ には昇順に値が挿入されていくように処理します。

具体的には、 $i$ 番目のクエリは以下のように処理します。

クエリ1 x

$x$ が $D$ に初めて挿入される場合、 $M$ に $D$ の何番目に挿入されたかを記録する。
$x$ より大きい最小の整数 $y$ を $S$ から二分探索で得る。
$y$ が $D$ の何番目に挿入されたかを $M$ から得る。これを $j$ 番目とする。
$D$ において、 $j$ 番目に挿入された値( $y$ )の後ろに $x$ を挿入する。

クエリ2 x k

$x$ より大きい最小の整数 $y$ を $S$ から二分探索で得る。
$y$ が $D$ の何番目に挿入されたかを $M$ から得る。これを $j$ 番目とする。
$D$ において、 $j$ 番目に挿入された値( $y$ )から後ろに $k$ 回辿る。この時、途中または最後に $-\infty$ にたどり着いた場合、-1とする。そうでない場合、辿った先を答えとして出力する。

クエリ3 x k

$x$ より大きい最小の整数 $y$ を $S$ から二分探索で得る。
$y$ が $D$ の何番目に挿入されたかを $M$ から得る。これを $j$ 番目とする。
$D$ において、 $j$ 番目に挿入された値( $y$ )から前に $k-1$ 回辿る。この時、途中または最後に $\infty$ にたどり着いた場合、-1とする。そうでない場合、辿った先を答えとして出力する。

multisetを使うとイテレータの増減だけでいいようです。今更ながら勉強になりました。

提出コード

E - Putting Candies

$i\rightarrow (i+A_i)\ mod\ N$ に移動すると考えます。
常に移動先は同じなので、鳩の巣原理によって、多くとも $N$ 回くらい移動すると、同じ場所が2回現れ、その後ループします。

あとは、 $K$ 回の移動で何回iから移動するかをカウントすれば答えを計算できます。

それを自作ライブラリ化してあったので、よければ参考にしてください。
実装はコンテスト後に少し修正してあります。

なお、この問題は各頂点が有向辺を1つだけもつグラフとも捉えられます。
そのようなグラフは閉路を１つだけ持ち、すべての頂点は閉路に属するか、閉路へ向かうように向きづけられています。
(ここで一応証明してみてあります。AtCoderの過去問の記事なのでネタバレ注意)

提出コード

2022-03-02

ABC239F Construct Highway

ABC 木の構成マージテク

解説AC

問題へのリンク
 解説1へのリンク
 解説2へのリンク

web解説を見てよくわからなかったので、自分なりに証明してみました。
素人なので、間違っていたらすみません。

森と、森の各連結成分 $C_i$ について、他の連結成分と連結しなければならない次数の不足数 $D_i$ が与えられる(以下、不足数と表現します。)。これを満たすように連結させ、森を1つの木とすることを考えます。

$C=1$ のときは既に木が構成されているので、 $C\geq 2$ を仮定します。

これを達成するための必要十分条件は、連結成分数を $C$ 、与えられた不足数の合計を $D$ として、

$D=2C-2$ かつ $D_i\gt 0$

が成り立つことである。また、これを満たす時、その構成方法は、

$C\geq 3$ なら、少なくとも一方が不足数2以上である連結成分を選び、連結する
$C=2$ なら、不足数が1である2つの連結成分を連結にする

ことである。

まず、木を構成する上で、なぜ
$C=2C-2$ かつ $D_i\gt0$
という条件が出てくるのかメモしておきます。

木の構成可能条件が出てくる理由

木 $T$ の辺を1本ずつ切断していくことを考える。

任意の辺を1本切断した時、連結成分数は $C_1,C_2$ の2個になり、不足数は $D_1 = D_2 = 1$ で合計は2となる。これは、 $D=2C-2$ かつ $D_i\gt 0$ を満たす。

次に、 $k$ 本目の切断時に $D=2C-2$ かつ $D_i\gt 0$ が成り立っていると仮定し、 $k+1$ 本目の辺を切断した時を考える。
辺が1本以上存在する任意の連結成分 $C_x$ の辺を切断し、 $C_y,C_z$ に分割されたとする。

$C_y,C_z$ には次数の不足が+1ずつされることから $D_y,D_z\geq 1 \gt 0$ が成り立つ。

$k+1$ 本目の辺を切断した後の連結成分数を $C'$ 、不足数の合計を $D'$ とすると、連結成分数は1つ増え、次数の不足は2つ増える。

$k$ 本目切断時の $C,D$ から、 $C' = C + 1$ 、 $D' = D + 2$ となるので、 $D=2C-2$ に代入すると、
$D'-2=2(C'-1)-2\rightarrow D'=2C'-2$
となる。
従って、 $D=2C-2$ が成り立つ。

以上から、木から任意の辺を1本以上取り除くと、 $D=2C-2$ かつ $D_i\gt 0$ が常に成り立つことが示された。

このようにして条件が出てきます。

次に、 $D=2C-2$ かつ $D_i\gt 0$ ならば、木が構成できることを構成方法の正当性とともに示します。

$D=2C-2$ かつ $D_i\gt 0$ $\Rightarrow$ 木を構成できる

$C\geq 3$ である間、先程示した帰納法の逆を考えると、任意の連結成分を連結しても常に、 $D=2C-2$ が成り立つ。

連結する2つの連結成分の内、少なくとも一方について、連結前の不足数が2以上であれば、不足数が各々1減っても新たにできる連結成分の不足数は0とならないので、 $D_i \gt 0$ も保たれる。

よって、 $C=2$ となるまで、この操作を繰り返す。

$C=2$ となったとき、 $D=2C-2$ かつ $D\gt 0$ が成り立っていることから、2つの連結成分のそれぞれの不足数が1である。これを連結させることで1つの木とできる。

以上で証明は終了ですが、以下を示しておきます。

補足

$C\geq 3$ であり、 $D=2C-2$ かつ $D\gt 0$ ならば、

$D_i = 1$ しか存在しない
$D_i\geq 2$ しか存在しない

ことがあり得ないことを示す。
これが示されると、各段階で常に不足数が2以上の連結成分と1の連結成分が1個以上存在することになる。また、これが成り立たないと、構成の途中で木にできない状態を作り出してしまうことになる。

$D_i = 1$ しか存在しない状態にならない

この状態になったと仮定すると、 $D=C$ となり、 $D=2C-2$ が成立していることから、 $C=2C-2\rightarrow C=2$ が成り立つはずである。しかし、 $C\geq 3$ という仮定からこれは成り立たない。

$D_i \geq 2$ しか存在しない状態にならない

$D\geq 2C$ となるが、 $D=2C-2$ と矛盾する。

最後に、十分性を示しておきます。

木を構成できる $\Rightarrow$ $D=2C-2$ かつ $D_i\gt 0$

対偶

$D\neq 2C-2$ であるか、または、不足数0となる連結成分が1つでも存在するなら木を構成できない

を示す。

不足数0である連結成分が1つでも存在すると、その連結成分を連結できないため、1つの木とならない。よって、木を構成できない。

$i$ 回目の連結操作の終了時点で、 $D\neq 2C-2$ が成立し、 $i+1$ 回目の連結操作で $D=2C-2$ にできると仮定する。
しかし、先程示した帰納法と同様の議論で、 $i+1$ 回目に $D=2C-2$ が成立する場合、 $i$ 回目の操作終了時点に $D=2C-2$ が成り立つことが証明できる。
よって、仮定と矛盾するため、 $D\neq 2C-2$ から $D=2C-2$ が成立する状態にできない。
従って、 $D\neq 2C-2$ の状態から1つの木を構成することはできない。

以上で対偶が示された。

解法

これでweb解説の2つの構成方法

不足数2以上と不足数1を連結する
不足数が多い2つを連結する

がそれぞれ正しいことがわかりました。

ところで、次の構成方法も問題ないはずです。

初期状態( $M$ 個の辺を繋げた状態)において、不足数が最大のものを $C_x$ とおく。まず、不足数が2以上の連結成分を全て $C_x$ に連結させる。その後、不足数が1の連結成分を $C_x$ に連結させる。

この解法でACできました。
( $C_x$ として不足数最大を取らなくても不足数2以上であれば何でも良さそうです)

なお、構成前の前提として、以下の場合も解なしです。

頂点数と不足数の和が $D=2N-2$ を満たさない
$M$ 個の辺を繋いだ時に不足数が負となる連結成分が存在する

余談ですが、解説にあるような、個数の小さい方から大きい方にマージすることをマージテクと呼ぶのを初めて知りました。

提出コード

2022-02-24

ABC240 参加記録

ABC DFS 上界・下界を見積もる

コンテスト中AC:A〜E

E - Ranges on Tree

コンテスト中は確信が持てないまま通してしまいました。
解法に至った経緯をメモしておきます。

まず、問題文の意味がパッと見で理解できませんでした。そこで、入出力例を確認して、ざっくりと以下のような制約であると理解しました。

親の区間を、子に分配する。この時、子の区間は親の区間をはみ出してはならず、かつ、子同士の区間が重なってはならない。

ここまでで解法は思いつかなかったので、問題の例を全て確認してみました。すると、以下がわかりました。

根の区間は、葉の個数を $k$ として、 $[1,k]$
葉の区間は、ある正整数 $m=1,...,k$ をとって、 $[m,m]$ であり、 $m$ は葉同士で相異なる

ことがわかりました。
そこで、葉にそれぞれ $m=1,...,k$ まで割り振って、その葉の区間を $[m,m]$ とし、その後、親に向かうにつれて区間を併合していく解法を思いつきACできました。

公式解説によれば、この解法の正当性として、

葉には必ず異なる番号(区間)を振らなければならないので、k個の異なる整数が必要であり、答えはk以上になる。一方、先に示した方法なら、答えをkにできる。よって、この方法で得られる解は最小であり、解法の正当性が示された。

という感じでした。

提出コード

2022-02-20

ABC239 参加記録

ABC エラトステネスの篩ウェーブレット行列オイラーツアー床関数マージテク

コンテスト中AC:A〜E

B - Intenger Division

以前、このような自作関数を作っていました。

template<typename T> 
T Floor(T a, T b) {
    if ((a<0 && b<0) || (a>0 && b>0)) return a/b;
    else return (Abs(a)+Abs(b)-1)/Abs(b)*-1LL;
}

これを使うことで、Floor(X,10LL)で求められました。
提出コード

E - Subtree K-th Max

Kが小さいことから、公式解説の想定解を思いつきつつも、計算量の見積もりがよくわからなかったので、異なる解法で解きました。
オイラーツアーの部分木クエリと同じ考え方となります。

まず、一回のDFSで以下を記録しておきます。

頂点 $u_i$ のpre-order順。これを $Id_u$ とします。
$X_i$ を頂点のpre-order順に並べたもの。これを配列 $A$ とします。
部分木に属する頂点数。これを $dp_u$ とします。

このようにすると、 $i$ 番目のクエリは、

$Id_{V_i} \leq j \lt Id_{V_i}+dp_{V_i}$ を満たす $A_j$ のうち $K_i$ 番目に大きい数を求めよ

という問題となります。入力例1を例にします。以下はDFS実行後の一例です。

$A = \{1,4,2,5,3\}$
$Id = \{1,3,5,2,4\}$
$dp = \{5,3,1,1,1\}$

ここで、2個目のクエリ、頂点2を根とした時の1番目に大きい数を求めてみます。
対象となる $A_j$ の区間は、 $3\leq j \lt 3+3 \rightarrow 3\leq j \lt 6$ となるので、 $A_3,A_4,A_5$ から1番目に大きい値を計算します。
$2,3,5$ なので、答えは $5$ です。

ここで、 $K$ 番目に大きい値を高速に得る必要があります。
これはウェーブレット行列により可能となります。

$A$ のウェーブレット行列を求めておます。ウェーブレット行列には以下の関数があります。

$quantile(s,e,r)$ : 半開区間 $[s,e)$ のうち、 $r+1$ 番目に小さい値を返す。計算量は $O(logX_{max})$ 。(但し、 $X_{max}$ は $X_i$ の最大値)

これを用いると、区間のサイズが $dp_{V_i}$ であることから、 $quantile(Id_{V_i},\ Id_{V_i}+dp_{V_i},\ dp_{V_i} - K)$ として解を得られます。

計算量は、木なのでDFSに $O(N)$ かかります。また、ウェーブレット行列の構築に $O(NlogX_{max})$ 、
ウェーブレット行列で各クエリに答えるのに $O(QlogX_{max})$ かかります（多分）。

提出コード

2022-02-16

ARC135 参加記録

ARC XOR メモ化再帰

コンテスト中AC:A,C
Bはコンテスト後自力AC。もう少しで解けそうでした。

A - Floor, Ceil - Decomposition

実際に10まで、xとfloor(x/2)×ceil(x/2)のどちらが大きいか手計算しました。

すると、

x≦4なら、x≧floor(x/2)×ceil(x/2)
x≧5なら、x<floor(x/2)×ceil(x/2)

となりました。大きめの数で試してもx<floor(x/2)×ceil(x/2)となり、その差は大きくなっていくので、厳密でないものの一般のxでもこれが成り立つと考えました。
よって、

x≦4ならそのまま、そうでなければfloor(x/2)とceil(x/2)に置き換える。

という解法が成り立つと考えました。

実装ですが、この手の問題ではメモ化再帰を使える場合が多いです。
メモ化することで、xが偶数なら状態は1/2になりますし、厳密ではないものの、全状態数は十分に少ないと見積もりました。
実際に提出してみると、ACできました。
(最大の10¹⁸くらいは試しておけばよかったです。)

厳密でなかった部分は、前者は公式解説に証明がありました。後者も証明できるそうです。(具体的な証明はありませんでした。) 提出コード

B - Sum of Three Terms

$A_1,\ A_2$ 及び $S_i$ が決定すると、 $i\geq 3$ の $A_i$ を決定できます。
また、 $A_i \geq 0$ という制約があるので、 $A_1,\ A_2$ に関する何らかの制約が得られそうです。
$A_7$ まで、列挙してみます。
$A_1 = A_1$
$A_2 = A_2$
$A_3 = S_1 - A_1 - A_2$
$A_4 = S_2 - S_1 + A_1$
$A_5 = S_3 - S_2 + A_2$
$A_6 = S_4 - S_3 + S_1 - A_1 - A_2$
$A_7 = S_5 - S_4 + S_2 - S_1 + A_1$

$S_i$ のみからなる定数部分を $B_i$ としておきます。 $B_i$ は、

$i \leq 2$ のとき、 $B_i = 0$
$i \geq 3$ のとき、 $B_i \leftarrow S_{i-1} - B_{i-1} - B_{i-2}$

として、計算できます。

次に、 $A_1,\ A_2$ に関する制約式を得たいので、それぞれの $A_i$ での係数を $A_1 [i],\ A_2 [i]$ とします。
これも以下のように計算できます。

$i=1$ のとき、 $A_1 [1] = 1,\ A_2 [1] = 0$
$i=2$ のとき、 $A_1 [2] = 0,\ A_2 [1] = 1$
$i\geq 3$ のとき、
$A_1 [i] = -A_1 [i-1]- A_1 [i-2]$
$A_2 [i] = -A_2 [i-1]- A_2 [i-2]$

これを基に実際に実装して計算してみたところ、以下の事実に辿り着きました。

$i\ mod\ 3 = 0$ のとき、 $A_1 [i] = -1,\ A_2 [i] = -1$
$i\ mod\ 3 = 1$ のとき、 $A_1 [i] = 1,\ A_2 [i] = 0$
$i\ mod\ 3 = 2$ のとき、 $A_1 [i] = 0,\ A_2 [i] = 1$

そのため、 $A_i \geq 0$ という制約から、以下の3種類の制約式が得られます。

$i\ mod\ 3 = 0$ のとき、 $A_1 + A_2 \leq B_i$
$i\ mod\ 3 = 1$ のとき、 $A_1 \geq -B_i$
$i\ mod\ 3 = 2$ のとき、 $A_2\geq -B_i$

そこで、
$A_1+A_2$ の上限を $X$
$A_1$ の下限を $Y$
$A_2$ の下限を $Z$

とします。初め、 $X=S_1,\ Y=Z=0$ です。
これを $i=3,4,...,N+2$ について、以下のように更新していきます。

$i\ mod\ 3 = 0$ のとき、 $X\leftarrow min(X,\ B_i)$
$i\ mod\ 3 = 1$ のとき、 $Y \leftarrow max(Y,\ -B_i)$
$i\ mod\ 3 = 2$ のとき、 $Z \leftarrow max(Z,\ -B_i)$

これが終了したとき、
$0\leq A_1 + A_2 \leq X$
$Y\leq A_1 \leq S_1$
$Z\leq A_2 \leq S_1$
という制約式が得られ、これを満たすような $A_1,\ A_2$ を設定します。

まず、
$X\lt 0$
$Y\gt S_1$
$Z\gt S_1$
のいずれかを満たす時、解なしです。

そうでないとき、
$0\leq A_1 + A_2 \leq X$
を満たすようにするには、 $A_1,\ A_2$ は、それぞれの下限である $A_1=Y$ 、 $A_2 =Z$ にしておくのが最善です。
そのため、 $Y+Z\gt X$ であれば解なしです。

そうでなければ、 $A_1=Y$ 、 $A_2 =Z$ として $A$ を構築できます。
(下記実装はiが0-indexedなので、i mod 3の値が異なっています) 提出コード

C - XOR to All

$A=\{A_1,\ A_2,\ A_3,\ A_4,\ A_5\}$ として以下に一例を示します。

$A_1$ と全体のXORをとる。 $\{A_1\oplus A_1,\ A_2\oplus A_1,\ A_3\oplus A_1,\ A_4\oplus A_1,\ A_5\oplus A_1\}$
$A_5\oplus A_1$ と全体のXORをとる。
$\{A_1\oplus A_1\oplus A_5\oplus A_1,\ A_2\oplus A_1\oplus A_5\oplus A_1,\ A_3\oplus A_1 \oplus A_5\oplus A_1,\ A_4\oplus A_1\oplus A_5\oplus A_1,\ A_5\oplus A_1\oplus A_5\oplus A_1\}$
XORは交換法則が成り立ち、かつ、 $X\oplus Y\oplus Y = X\oplus 0 = X$ より、
$\{A_1\oplus A_5,\ A_2\oplus A_5,\ A_3\oplus A_5,\ A_4\oplus A_5,\ A_5\oplus A_5\}$

これより、任意に置き換えを行った場合でも最終的には、
$\{A_1\oplus A_i,\ A_2\oplus A_i,\ \cdots,\ A_N\oplus A_i\}$
という形になります。

そこで、 $i=1,2,...,N$ について、
$B_i=(A_1\oplus A_i)+(A_2\oplus A_i)+\cdots +(A_N\oplus A_i)$
とした時、最大の $B_i$ を求める問題と読み替えられます。

愚直にこれを計算すると $O(N^2)$ となって、間に合わないため、工夫する必要があります。

ビットの問題では各ビットに着目するのが典型なので、それを基に考えてみます。すると、

$A_i$ の $j$ ビット目が0の場合、 $A_1,\ A_2,\ \cdots ,\ A_N$ の $j$ ビット目はそのまま。
$A_i$ の $j$ ビット目が1の場合、 $A_1,\ A_2,\ \cdots ,\ A_N$ の $j$ ビット目はすべて反転する。

ということがわかります。
そのため、 $A_1,\ A_2,\ \cdots ,\ A_N$ のうち、 $j$ ビット目が1の個数(または0の個数)さえ分かれば、以下のように $B_i$ を計算できます。

$cnt_j$ を $A_1,\ A_2,\ \cdots ,\ A_N$ の内、 $j$ ビット目が1である要素の個数とし、
$A_i$ の最大値 $A_{max}$ の最上位ビットを $D$ ビット目とする。

$j=0,1,2,...,D$ について、

$A_i$ の $j$ ビット目が0の場合

$B_i$ に $2^j$ を $cnt_j$ 個分足す： $B_i \leftarrow B_i + cnt_j \times 2^j$
$A_i$ の $j$ ビット目が1の場合

$B_i$ に $2^j$ を $N-cnt_j$ 個分足す。： $B_i \leftarrow B_i + (N-cnt_j) \times 2^j$

このようにすると、全ての $B_i$ を $O(DN)$ で計算できます。 $A_i \lt 2^{30}$ という制約上、 $D$ は最大で29なので、 $j$ のループは最大でも30回となり、余裕を持って間に合います。

なお、操作を一度も行っていない場合も考慮する必要があります。

提出コード

2022-02-11

ABC237F |LIS| = 3

最長増加部分列 ABC DP

解説AC

問題
 公式解説

公式解説で解法だけみて、実装は自力でしてみようと思ったのですが、これも上手くいきませんでした。結局、実装も解説のものを確認しました。

LISの長さが3未満の保持方法

未確定の部分はinf、今回ならM+1としておけばよいようです。
例えば、{2,5}というLISを持つ数列はdp[i][2][5][M+1]という感じになります。

dp遷移におけるループ

a1,a2,a3のループ部分は、単調増加にしたくなります。

イメージ
for a1 = 1 to M+1
　for a2 = a1+1 to M+1
　　for a3 = a2+1 to M+1

しかし、このようにするとM+1を複数含む場合の遷移が起こらないため、だめでした。
そのため、ループ部分は、
for a1 = 1 to M+1
　for a2 = 1 to M+1
　　for a3 = 1 to M+1

と、しておく必要があります。
dp[i][2][5][1] += dp[i-1][1][5][1]ような不正な更新が行われますが、これらは全て0になっているので問題ないということでした。

提出コード

geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

ABC242D ABC Transform

二分木として考える

親と子の番号の関係

$t$ が小さい場合

$t$ が大きい場合

ABC241 参加記録

D - Sequence Query

E - Putting Candies

ABC239F Construct Highway

木の構成可能条件が出てくる理由

$D=2C-2$ かつ $D_i\gt 0$ $\Rightarrow$ 木を構成できる

補足

$D_i = 1$ しか存在しない状態にならない

$D_i \geq 2$ しか存在しない状態にならない

木を構成できる $\Rightarrow$ $D=2C-2$ かつ $D_i\gt 0$

解法

ABC240 参加記録

E - Ranges on Tree

ABC239 参加記録

B - Intenger Division

E - Subtree K-th Max

ARC135 参加記録

A - Floor, Ceil - Decomposition

B - Sum of Three Terms

C - XOR to All

ABC237F |LIS| = 3

LISの長さが3未満の保持方法

dp遷移におけるループ

二分木として考える

親と子の番号の関係

が小さい場合

が大きい場合

D - Sequence Query

E - Putting Candies

木の構成可能条件が出てくる理由

かつ木を構成できる

補足

しか存在しない状態にならない

しか存在しない状態にならない

木を構成できるかつ

解法

E - Ranges on Tree

B - Intenger Division

E - Subtree K-th Max

A - Floor, Ceil - Decomposition

B - Sum of Three Terms

C - XOR to All

LISの長さが3未満の保持方法

dp遷移におけるループ

$t$ が小さい場合

$t$ が大きい場合

$D=2C-2$ かつ $D_i\gt 0$ $\Rightarrow$ 木を構成できる

$D_i = 1$ しか存在しない状態にならない

$D_i \geq 2$ しか存在しない状態にならない

木を構成できる $\Rightarrow$ $D=2C-2$ かつ $D_i\gt 0$