ABC lessons learned3

AtCoder Beginner Contest lessons learned (ABC 201-250)

ABC 6,8問体制(126..最新)のD問題をだいたい解いたので、そこから得た教訓をまとめていきます。

トップページへ

ABC 201-210

ABC 201-D

コードはこちら

ゲーム理論とミニマックス法である。

2人の得点差だけに意味がある。得点差が正なら先手の勝ち、得点差が負なら後手の勝ち、得点差が0なら引き分けと定義する。マスに移動したときの得点を、

• 先手なら素直にマスの得点(+1なら+1, -1なら-1)
• 後手なら先手が如何に損するか、と読み替えて正負を入れ替える(+1なら-1, -1なら+1)

として、先手は得点差を最大化、後手は得点差を最小化するように移動すればよい。

盤面の外にはみ出さないようにするのだが、マスから一手移動する先をキューで管理するとTLEするので、ゴールまで(またはスタートから)距離が $i$ なマスをforループで求める。慣れてないとこの処理が意外と大変である。

ABC 202-D

コードはこちら

上の桁から順番に決めていく。

• 未決定の桁のうち、最上位桁をaをして残りの組み合わせがk以下なら、最上位桁をaをして残りの桁を決める
• そうでなければ最上位桁をbにして、kから残りの桁が取りうる組み合わせを引いてあら、残りの桁を決める
• aとbのどちらか一方が残っていなければ、残りはbだけまたはaだけに決まる

aとbの組は $2^{a+b}$ なので、組み合わせの数は 32-bit intでは収まらないが64-bit intには収まる。

ABC 203-D

コードはこちら

答えが整数 $n$ ちょうどであることを確認するのは大変だが、答えが $n$ 以上または以下であることを確認するのは容易である。

中央値を求めるのではなく、中央値 $median$ を決め打ちする。中央値を決める順位の定義 $rank = \lfloor k^2/2 + 1 \rfloor$ より、

1. すべての池で中央値を超える要素数が $rank$ 以上なら中央値を上げられる
2. いずれかの池で中央値を超える要素数が $rank - 1$ 以下なら中央値を下げられる

と $left-right$ 間を二分探索する。中央値を超える要素数を池ごとに数えるのは、二次元累積和でできる(累積和の逆算が池の要素数)。境界条件がややこしいが、境界条件 $left+1=right$ ではrightが二番目を満たす最低値であり、求める答えである。

ABC 204-D

コードはこちら

値域から計算量が少ないことが読み取れる。

$T_i$ が1000通り、 $N$ が100なので、 $T_i$ の和は10万通りしかない。よってオーブンを使う時間として10万通りがありうるか否かを計算すればよい。 $sum(T_{1..N})/2$ 以上の最も近い和が答えである。

ABC 205-D

コードはこちら。もっと簡潔に実装できる。

$K_i$​ がAに含まれるなら、Aに含まれない数まで滑っていくと考える。 $A_j$ 以下でAに含まれない整数の数は、Aを昇順に並べ替えてスキャンすると分かるので、これを二分探索すればよい。

ABC 206-D

コードはこちら

Union-find木は推移関係を表現できる。

AをBに置き換え、BをCに置き換えれば、AはCになるという推移則が成り立つ。なのでAからB、BからCに置き換えると分かっているなら、AからCまたはCからAへの置き換えは要らない。これをunion-find木で管理する。答えはunion-find木に追加した回数である。

ABC 207-D

コードはこちら

この種の数学問題は正解率が低いので、獲れると差がつく。

重心で回転すれば、二つの図形が一致するならすべての点が重なる。一方を固定すれば、回転角は点の数だけしかない。原点からの距離が一致する点を見つけて(見つからないなら二つの図形が一致しない)角度をそろえ、すべての点の座標が一致するかをどうかを一通りの回転角で試してみる。

すべての点の座標が一致するかどうかを総当たりで計算してよいのである。我ながら惜しかった。

ABC 208-D

コードはこちら

頂点数が少ないグラフには、ワーシャルフロイド法が使える。

ワーシャルフロイド法のループは外から順に、経由地、出発地、到着地にする。この順番を間違えると解けない。

ワーシャルフロイド法は、経由地の番号が浅い順に最短距離が更新される。この途中結果を集計すれば、問題の答えが求まる。

ABC 209-D

コードはこちら

二点間の距離は、余分に往復しても計算結果が変わらないことがある。

例えばオイラーツアーは、行きを枝の重み $w$ 、帰りを $-w$ にすれば余分な経路は足し引き0にできて二点間の最短距離(共通の祖先で折り返す)が求まる。

この問題では、一往復すると距離は偶数増えるので、最短距離か寄り道したかで、二点間の距離の偶奇は変わらない。なので二点間の移動は必ず根を経由することにして、根からの距離の和にしても、二点間の距離の偶奇は変わらない。距離が偶数なら街で、奇数なら道路上で出会う。

ABC 210-D

コードはこちら

盤面を回転すれば絶対値を外せる。

ということで、盤面を4回回転して、左上の駅の方が高いという仮定の下で求める。DPを上手く使う。なんとなく解るというだけでは実装できないので、よく理解する必要がある。

ABC 211-220

ABC 211-D

コードはこちら

辺の距離が等しいのでBFSで解く。

キューには距離を載せ、それとは別に頂点1から他の頂点への距離と、他の頂点に行く組み合わせを管理する。

• 辺をたどると最短経路にならない頂点(迂回路の先に頂点)はキューに載せない
• 辺をたどると最短経路以下になる頂点については、その頂点に行く方法の数を足す
• つまり辺の先の頂点が最短経路ちょうどのとき、辺の先の頂点をキューに載せないが、その頂点に行く方法の数を足す。これがこの問題の肝である。

鉄則本の力試し問題 C14の要領で解いたら、ダイクストラ法なので $O(N*log(N))$ 解法だったために 1791 ms のTLEぎりぎりだった。ここでは辺の長さは固定なのでBFSでよく、過去問の知識を手直しせずそのまま使ってはいけない。

ABC 212-D

コードはこちら

下駄を履かせる。

変数に一斉に同じ数を足す操作は、足した値をオフセットとして持てば、それぞれの変数を更新しなくて済む。オフセットの初期値は0である。

ABC 212-E

コードはこちら

制約をよく見る。

行列演算のコストが高すぎてダブリングは使えない。よって別の方法を探す。 $M \leq 5000$ なので、とりあえず道がつながっているものとして組み合わせ計算し、つながっていない道の分だけ組み合わせを引けばよい。

道の遷移行列を直に掛けると $O(N^3)$ になるので、つながっていない道の分だけ計算すると $O(N^2)$ になる。自己ループもつながっていない道として加えておく。

ABC 213-D

コードはこちら

辺の数が頂点の数-1で、すべて頂点が連結なら木である。

辺を std::vector<std::vector<Num>> で管理すると、頂点から次にたどる頂点を並べ替えできる。あとはDFSで訪ねればいい。この方法はオイラーツアーなので、スニペットにしておく。

ABC 212-E

コードはこちら

小さな距離と大きな距離

壁の無いところに一歩踏み出す時の小さな距離を $1$、壁があるが壊したら行けるところまでいく大きな距離を $10^7$ とする。

壁がなければ行ける場所の、現在地からの相対座標。

std::vector<std::pair<Num, Num>> diffs_short {
    {-1, 0}, {1, 0}, {0, -1}, {0, 1}
};

壁を壊して行ける場所の、現在地からの相対座標。

std::vector<std::pair<Num, Num>> diffs_long {
    {-2, -1}, {-2, 0}, {-2, 1},
    {-1, -2}, {-1, -1}, {-1, 0}, {-1, 1}, {-1, 2},
    {0, -2}, {0, -1}, {0, 1}, {0, 2},
    {1, -2}, {1, -1}, {1, 0}, {1, 1}, {1, 2},
    {2, -1}, {2, 0}, {2, 1}
 };

これらをすべてのマスから相対座標で行った先について、双方向の枝を張る。後は左上から右下までダイクストラ法で最短距離を求め、大きな距離で割ると答えが求まる。小さな距離はいくら長くても答えは変わらない。

壁を壊して進むならそれはゴールに向かう最短経路なので、壊した2x2の壁の中には一度入ったらそこから出るしかなく、壊した2x2の壁の中を大きな距離で動くことはありえない。

公式解説によれば01BFSで解けて、その方が実装が簡単で速い。

ABC 214-C

コードはこちら

灰diffだが、AtCoder Daily Training MEDIUM 2023/11/23 18:30 start で解いて手こずった。

時刻で高速シミュレーションする。初期値はすぬけ君 $i=1..N$ がそれぞれ時刻 $T_{i=1..N}$ に宝石を受け取ったとして、 std::set 型の集合 $S$ に載せる。 $S$ は時刻 $t$ とすぬけ君の番号 $i$ の組 $[t,i]$ からなる。

すぬけ君 $i$ が初めて宝石をもらう時刻を $U_i$ として $\infty$ で初期化する。 $S$ のうち最も時刻の早い要素 $t,i$ を取り出して削除する。 $t \leq U_i$ なら何もしない。 $t < U_i$ なら $U_i$ を $t$ にし、 $[t+S_i,i+1]$ を $S$ に加える。 $i+1$ は $mod N$ である。キューから取り出すごとに、 $U_i$ が確定するすぬけ君が一人いるか宝石が一つ減るかいずれかが成立するので、ループは $O(N)$ 回、計算量は $O(Nlog(N))$ である。

公式解説通り二周させると $O(N)$ 解法になる。実装は こちら

ABC 214-D

コードはこちら

辺の重みの最大値に関心があるなら、その辺より重い辺を除けばいい。

ということで、軽い辺から重い辺に向かって順番に辺を追加して、最終的に木になるようにする。辺 $(u,v)$ を一本追加したときに、その辺によって推移的に連結可能になる(互いに行き来できる)頂点は、 $u$ の連結成分(最低1個)と、 $v$の連結成分(最低1個)との相互間なので、両連結成分の数の積である。

連結成分はunion-find木で管理する。辺が無い頂点の連結成分は1個で、 atcoder::dsu::size もそうなっている。

ABC 215-D

コードはこちら

エラトステネスの篩っぽいことをする。

これは公式解説通りである。 $A_i$ の素因数の倍数をすべて削除済という印をつける。同じ素因数は一度だけ行う。エラトステネスの篩はかなり計算量が小さいので、似たようなことを頑張って実装しても大変なだけである。

ABC 215-E

コードはこちら

N=10ならBitDP

なのだが、加算方法が4通りあってよく場合分けしないと解けない。

ABC 216-D

コードはこちら

シミュレーションしてもいいが、しなくても済むことがある。

色が $I$, $J$ 、個体が $I_1$, $I_2$, $J_1$, $J_2$ のボールがある。詰んでいる状況は以下の通りである。

• 同じ筒に $I_1$, $I_2$ がある
• $I_1$ の上に $J_2$ かつ $I_2$ の上に $J_1$ がある (1と2を入れ替えても対称なので同じ)

これだけ検出すればACできた。解を示せと言われたらトポロジカルソートでできるらしい。

ABC 216-E

コードはこちら

上から整地する。

楽しさが最大のアトラクションに、楽しさが二番目になるまで乗りまくる。次に楽しさが最大だったおよび最初は二番目のアトラクションに、楽しさが三番目になるまで乗りまくる。以下同様に楽しさを整地して、K回乗るかすべてのアトラクションの楽しさが0になるまで乗ればよい。このとき満足度が最大になるので貪欲法で解ける。Kが中途半端に余ったときの処理に気を付ける。

別解として二分探索がある。 こう実装した。

ABC 216-F

コードはこちら

C配列はできれば使いたくない。

この問題の本質ではないのだが、C配列のサイズを一桁間違えたためにバッファオーバーランが発生して結果がおかしくなり、ジャッジサーバがREするまで気が付かなかった。できれば範囲チェック付きの配列を使いたい。そもそもこの問題で二次元配列は必要ない。

本題に戻ると $(A_i, B_i)$ を $A_i$ でソートしておけば、 $S$ の和の上限がいくつかを明示的に管理する必要は無くなる。例によって $DP[i][v]$ として $i$ は集合 $S$ に $i$ 番目まで詰めたかどうか、 $v \leq 5000$ は $S$ の値の和である。 $DP[0][0]=1$ として外ループは $i=1..N$ 、内ループは $0 \leq v \leq 5000$ について解けばいい。

$i-1$ 番目までを $S$ に詰めた ( $B_{i-1}$ を詰めたかどうかは問わない)組み合わせの数を $DP[i-1][v]$ とする。 $B_i$ 番目を $S$ に詰めたときに $DP[i][v+B_i] = DP[i-1][v]$ であり、 $v+B_i \leq A_i$ なら題意を満たす個数 $DP[i-1][v]$ の総数を加算する。 $B_i$ 番目を $S$ に詰めなければ $DP[i][v] = DP[i-1][v]$ であり、題意を満たす個数は増えない。

ABC 217-D

コードはこちら

STLの使いこなしが問われる。

切れ目 std::set<Num> cuts を順序付けて並べ、 cuts.upper_bound(x) で見つかる。「クエリを処理する時点で切られていないことが保証されます」ので lower_bound でよかった。

ABC 217-E

コードはこちら

コレクションを二つに分ける。

この種の問題で何度も見た通り、ソート済集合と、挿入順序がついた集合の二つを分ける。ソート済集合は std::multiset でも優先度キューでもよい。挿入順序は std::queue だが、クエリ3で空にするので std::vector でもよいかもしれない。

ABC 218-C

コードはこちら

実際にやってみる。

余白の削除と回転はそこそこ長いコードになるので、あらかじめコードスニペットにしておく。

ABC 218-D

コードはこちら

制約をよく見る。

$N$ が小さいので二重ループできる。長方形の頂点は、対角線上の二点を定めれば残りも求まる(x軸とy軸に並行なので)。後は総当たりでよい。

ABC 218-E

コードはこちら

逆から考える。

辺を除くのではなく、辺を付け足すことを考えると、union-find木を活用できる。

報酬が負の辺は除く価値がないので最初から存在することにする。このとき辺を増やせばいつかは全頂点が連結になる。これは最小全域木を構成するアルゴリズムと同じである。

• 辺 $(A_i, B_i)$ の $A_i, B_i$ が連結なら、連結成分は増えないので辺を足す意味は無い。これは辺を除くことの逆操作なので、報酬 $C_i$ をもらえる。
• 辺 $(A_i, B_i)$ の $A_i, B_i$ が連結でなければ、連結成分が増える。報酬はもらえない。

ABC 219-D

コードはこちら

繰り返しになるが、制約をよく見る。

たこ焼きとたい焼きはそれぞれ300個しか食べないのだから、300個以上は一律300個とみなして構わない。そうすれば $A_{1..N}$ から任意の要素を取ったときの和として取りうる値は、301通りしか考えなくて済む。

ABC 220-D

コードはこちら

悩むより手を動かすこともときには大事。

問題文の通り実際に実装すると答えが求まる。 $(10^5, 10)$ 要素のテーブルを作ってもMLEしないので、省メモリを考えるのは時間の無駄である。

意の要素を取ったときの和として取りうる値は、301通りしか考えなくて済む。

ABC 220-E

コードはこちら

重複を上手く数える。

$(i,j)$ と $(j,i)$ を別に数える。これが引っ掛かって解けないことがある。

題意を満たす頂点の組を数え上げるには、木の高さ(根から葉までの辺の数)を $0..N-1$ まで増やしていけばよい。

• 根しかないときは、題意を満たす頂点の組は存在しない
• 高さが1のときは、葉から距離1で到達できるのは根だけ、葉から距離2で到達できるのは根の先にある葉だけである。
• 高さが2のときは、葉から距離1で到達できるのは葉の親だけ、葉から距離2で到達できるのは葉の兄弟と根、距離3以上だと根の向こう側にある頂点に到達する
• 高さが3ときは、葉から距離1で到達できるのは葉の親だけ、葉から距離3で到達できるのは根と葉の間にLCA(最小共通祖先)がある頂点、距離3だと根だけで、距離4以上だと根の向こう側にある頂点に到達する。

高さが2のとき葉から距離2で到達できるのは根と葉の兄弟というのは、高さ1の木と同じである。つまり高さが $i$ のときの組み合わせの数は、 高さが $1..i$ のときの組み合わせを含むことが分かる。より精緻には、木の高さが $i$ で頂点間の距離が $D$ のとき以下の通りになる。

$i*2 < D$ ならどの二頂点をとっても距離が $D$ を超えてしまうので、そのような頂点の組は存在しない。

$i \geq D$ なら、ある頂点 $v$ から距離 $D$ にある頂点 $u$ は根の向こう側にある。そのような頂点は根からの距離が $2^{i-D}$ なので、 $v$ に対応する頂点 $u$ は $max(1, 2^{i-D-1})$ 個である。根の向こう側なので半分になることに注意する。

• $(v,u)$ の組み合わせは、 $i \ne 2D$ なら $2 |v| \times |u|$ 個である。 $v$ と $u$ は根からの距離が異なるので区別でき、入れ替えたものも数えるために倍にする。
• $i = 2D$ なら、 $v$ と $u$ は対称なので $|v| \times |u|$ 個 である。 $v$ と $u$ は根からの距離が同じで区別できず、入れ替えたものを数えないため倍にしない。ここを間違えやすい。

$i < D$ なら、ある頂点 $v$ から距離 $D$ にある頂点 $u$ は根のこちら側にある。つまり $v$ と $u$ のLCA(最小共通祖先)は $v$ と 根の間にある。LCAを $v$ から近い順、つまり $v$ との距離が $j=1..D$ それぞれについて頂点の組み合わせの数をを求めればよい。これは高さ $j$ の木として既に求まっている。

高さ $j$ 以下の組み合わせを累積和にしておかないとTLEする。 $v$ と $u$ は根からの距離が異なるので区別でき、入れ替えたものも数えるために倍にする。これも忘れやすい。

ABC 220-F

コードはこちら

intだとオーバーフローする。

何か適当な頂点を根にして木を作る。このとき各頂点について子頂点の数(自分自身は含めない)を数え、すべての頂点の深さの和(根は0とする)を集計しておく。DFSで求まる。

根についてはすべての頂点の深さの和が答えである。根の子頂点 $i$ に移動することを考える。 $c$ の子頂点の数を $n_i$ としたとき、 $c$ および $c$ の子頂点に寄ったので距離の和は $n_i + 1$ だけ減り、それ以外の頂点との距離の和は $n - n_i + 1$ だけ増えて、合計で $n - 2(n_i + 1)$ 増える。これを根からDFSで再帰的に求めると、すべての頂点について距離の和が求まる。 $O(N)$ で求まる。

LCAの実装をそのまま使うと $O(N^2log(N))$ になってTLEする。

ABC 221-230

ABC 221-D

コードはこちら

いもす法である。

いつも通り出入りイベントを定義して、同一時刻を圧縮してから計算する。

ABC 221-E

コードはこちら

区間和を $O(log(N))$ で更新するならセグメント木。

$A_i \leq A_j$ かつ $i < j$ なら取りうる組み合わせは $A_i$ で始まり $A_j$ で終わる $2^{j-i-1}$ 通りである。これを $i=1..N$ と $j=(i+1)..N$ について取れば答えが求まる。のだが、このままでは $O(N^2)$ なので一工夫要る。

セグメント木に載せると上手くいく。まず入力を座標圧縮する。 $(A_i, i)$ を辞書順に並べ替えると、 $A$ が小さい順、 $A$ が等しければ $i$ が小さい順に並ぶ。この順序 $ord(i)$ を圧縮後の座標として、セグメント木の添え字にする。次に $A_1$ の解として、セグメント木の添え字 $ord(i)$ の値を $2^{i-2}$ にする。

$A_1 \leq A_j : 1 < j$ になる組み合わせの数については、 $[ord(1), N]$ についてセグメント木の値を足せば答えが求まる。というのはそのようにセグメント木の値を設定したからである。 $A_2$ について求める前に、セグメント木の添え字 $ord(i)$ の値を0にして、以後 $A_1$ との組み合わせは考慮しないようにする。

$A_2 \leq A_j : 2 < j$ になる組み合わせの数については、 $[ord(2), N]$ についてセグメント木の値を足せば答えが求まるがこれは $A_1$ と $A_j$ との距離を反映した2倍の値なので半分にする。このあとセグメント木の $ord(2)$ の値を0にして、以後 $A_2$ との組み合わせは考慮しないようにする。

一般的に $A_i \leq A_j : i < j$ になる組み合わせの数については、 $[ord(i), N]$ についてセグメント木の値を足して $2^{i-1}$ 割ったものが答えである。 $ord(i) = 0$ なら0通りである。これを $i=1..N$ について求めて足せば $O(Nlog(N))$ で答えが求まる。

ABC 222-D

コードはこちら

制約をよく見ると、値域が狭い。

基本は数列の $i$ 番目までみて、 $C_i=J$ なら $dp[i][j]$ 通りである。 $dp[i][j]$ を引っ張ってくる元は、最も広い区間で $dp[i-1][a_{i-1}..b_{i-1}]$ なので、jについて累積和を取らないとTLEする。

ABC 222-E

コードはこちら

久しぶりに連立方程式。

ある頂点から他の頂点に行く経路は、BFSで経路を記録しながら求まる。よってある辺を何回通るかも分かる。

1回以上通る辺が $p$ 本あるなら $dp[i][j]$ すればよい。 $i=0..p$ 番目の辺について、赤く塗られた辺を $j$ 回通った回数を逐次的に求めればよい。一回も通らない辺が $q$ 本あるなら何色で塗ってもいいので、組み合わせの数を $2^q$ 倍する。始終点の頂点が常に等しい場合は $p=0$ なので注意する。

Rが0通りの場合があるのに注意する。 $R - B = K$, $R + B = p$ より $R \times 2 = K+p$ なので、 $K+p<0$ または $K+p$ が奇数ならRは0通りである。

ABC 223-D

コードはこちら

A happens before B という条件は有効グラフで表現できる。

すべての条件をを満たす解があるなら、トポロジカルソートで解を得られる。トポロジカルソートに一意性はないが、優先度キューを使うとできるだけ頂点番号が最小のものから並べた解が得られる。

トポロジカルソート可能と循環(サイクル)が無いことは同値である。トポロジカルソート後の頂点数が入力より少なければ、トポロジカルソートできなかった、つまりサイクルがあったと分かる。

ABC 223-E

コードはこちら

考察が大変。

長方形が2個なら、指定された面積以上なのだから横幅一杯広げて、その上に他の長方形を乗っければよい。縦横は交換して試す。

長方形が3個なら、まず下に一個置いて残り2個をを上に置けばいい。縦に積むか横に積むかはそれぞれ試す。縦横は交換して試す。

$A,B,C$ の順列、並び替え後の $A,B$ に対して $A$ を縦置きか横置きか ($X,Y$ を入れ替えればいい)、 $B$ を縦置きか横置きか、という24通りを総当たりすればよい。実装は こちら

ABC 223-F

コードはこちら

遅延セグメント木。

( と ) を +1 と -1 に読み替えて、括弧の収支が合えばいい。つまり区間 $[L,R]$ の区間和が0で、部分区間和 $[L,L..R]$ の最小値が0以上であればいい。

区間和はセグメント木で管理し、クエリ1でセグメント木のノードを入れ替える。これとは区間和の最小値を遅延セグメント木で管理する。

• ノードは整数とする
• 区間に対するクエリは、区間の最小値を返す。単位元は負の無限大にする。
• ノードに対する作用素は整数の可算にする

ノード $L,R$ を入れ替えると、先頭からの区間和つまり累積和 $cumsum$ は $S[L,R)$ を入れ替える前の $S[R]-S[L]$ だけ増える。これは遅延セグメント木にうってつけである。これ以外の区間は増えない。 $S[R,N]$ は変わらないが、境界を一つ間違えやすいの注意する。

クエリ2に対しては、 $S[L,R)$ の区間和が0で、 $S[L,R)$ の区間和の最小値が0以上つまり $cumsum[L-1]$ 以上なら正しい括弧列である。便宜上 $cumsum[0] = 0$ とする。区間更新一点取得できるデータ構造なら遅延セグメント木でなくてもよい。

ABC 224-D

コードはこちら

状態遷移はグラフで表現できる。

この種のパズルは、コマではなく空白を動かすと考える。すべてのコマの状態を遷移前と遷移後を辺で結び、状態間の最小距離が答えだ。よってBFSで求まる。C++で1秒掛かる。

空白を 9 する。 123456789 をゴールとして、 123456789 から 987654321 までの順列を網羅することで、遷移元の状態をすべて挙げることができる。状態を数値として持っても文字列として持ってもいいが、BFSの枝と距離を std::vector ではなく std::map で持たないとメモリが足りない。

ABC 225-C

コードはこちら

最上行の条件は二つある。二つ目を忘れると after_contest が通らない。

• 右隣の列は、7で割った余りが1ずつ増える
• 右隣の列は、(7で割っていない元の)値が1ずつ増える

最上行以外は、直上の行に7を足した値である。

ABC 225-D

コードはこちら

電車の前と後を別の頂点と考える。

公式はfrontとbackという二つの頂点配列を用意し、車両をindexとしている。頂点を一つの配列で管理し、奇数を車両の先頭、偶数と車両の末尾としてもいいが、公式のように上手く考えないとif文だらけでコードが長くなる。

ABC 226-D

コードはこちら

最少公約数を使えばその倍数は表現できる。

$N$ が小さいので、総当たりで最小公約数を求められる。あとは std::unique なり std::set なりで重複を排除する。

ABC 226-E

コードはこちら

考察が大変。

頂点から辺が一本から出ないのだから、頂点の数と辺の数が等しいことが必要条件であることが分かる。というより解説を読むまで気が付かなかった。大変なのは十分条件でもあることで、公式解説に長い文章がある。分かってしまえば実装は7分でできるが、何時間考えても答えが見えなかった(サイクル検出は関係なかった)。

再実装 したものを自分の言葉でまとめると以下のようになる。条件に重複が多く、実は最後の条件だけ調べればよい。

• $N \ne M$ なら各頂点から辺が一本ずつにはできないので、0通り。下記に含まれるので、明示的に計算しなくてよい。
• グラフを $G$ 個の成分に連結成分分解して、すべての連結成分が以下の条件を満たすなら、答えは $2^G$ 通り。
  • 連結成分は2個以上の頂点を含む(1頂点しかなければ辺を出せない)。これも下記に含まれるので、明示的に計算しなくてよい。
  • 無向グラフとみなしたときの、頂点の次数の和は、頂点数x2に等しい。これがないと1 WAする。

上記の条件を満たす場合、なもりグラフなので必ずサイクルちょうど1つ存在する。サイクルの向きは右回りと左回りの二通りあり、サイクル外からサイクルに向かう枝はサイクル側に向けるしかないので一通り、よって連結成分において向きの付け方は必ず二通りである。

ABC 227-D

コードはこちら

二分探索と、縦の物を横にする。両方思いつくのは結構大変である。

条件を満たすのにちょうど $K$ 人必要なことを示すのは難しい。しかし $K$ 人以上ならできて $K-1$ 人以下ではできないことは示せそうである。

$N$ 個のプロジェクトを構成可能かどうかは、プロジェクトに人を集めるのではなく、部署からプロジェクトに人を出せるかどうか判断する方が簡単である。

部署からプロジェクトに出す人数は、プロジェクトの数か部署の人数かどちらか少ない方である。よって人数が多い部署から プロジェクト1,2,... に人を出し、足りなければその次に人数が多い部署からプロジェクト3,4,... に人を出す、というのを繰り返せば $N$ 個のプロジェクトを構成可能かどうかわかる。縦のものを横にするとすんなり解ける。

例によって整数の二分探索は、幅が2のときが大変なので、 $(right - left) > 1$ に限る。体で覚える。

ABC 228-D

コードはこちら

指定された値以上に滑っていくことを想像する。

std::set::lower_bound がうってつけである。

• 値が -1 の要素を全部入りとして集合 std::set で持っておく
• 添え字が $x_i$ 以上(Nは0にループする)で -1 の要素は集合にあるはずだから探す
• $A_h$ が $x_i$ から来たことを書き留めて、クエリ2で返す。まだ書き留めてないなら、クエリ2の返り値は-1である。

公式解説通り区間管理を実装すると こうなる 。かなりコードが長くなるのでこの問題では要らないが、他の問題でこの種の実装を正確にできる必要はあるだろう。

Union-find木を用いて区間を束ねると こうなる がそこそこ実装量がある。

ABC 228-E

コードはこちら。Pythonである。

こちらの記事 が正解である。だが $a^b \quad mod \quad M$ の実装を間違えて、 $a \quad mod \quad M = 0$ のときにバグっていたので解けなかった。

64-bit整数を受け付けるように、 __int128 を使うなり (提出したコード) 、 boost::multiprecision::cpp_int を使うなり (提出したコード) 、PythonやRubyの任意精度整数なりを使えばよい。いずれにせよ累乗を求めるコードはしっかりデバッグしておく。

ABC 229-D

コードはこちら

二分探索には向かないが尺取り法ならいけそう。

先頭からみて、連続するXが最長何個か求める。これも公式解説は累積和を用いたすっきりした解法で、私の元の解法はif文だらけでごちゃごちゃして見づらい。尺取り法も二分探索と同様に、型に嵌めて覚える。

なので累積和を使って解き直したのが こちらである。 X ではなく . を数えるのがミソである。

• $S$ の先頭からの . の個数の累積和 cumsum を取る。
• $S$ の $i$ 文字目およびそれ以後で、 . が $k+1$ 回現れる場所を求める。これは $cumsum(i-1)+k$ を std::lower_bound で求めれば分かる。
• 返ってくるイテレータ it は . が $k+1$ 回に現れる位置で、該当するものがなければ $S$ の末尾である。これは言い換えれば、 . が $k$ 回現れ、その後に X が0回以上現れ、その直後の位置である。よって it - (it.begin()+i) が、 $i$ を始点として X を最大で連続できる個数である。
• これを $i=1..N$ について求める。

尺取り法で実装すると こうなる

ABC 229-E

コードはこちら

Union-find木は辺を削除できない。

なので辺が無い状態から辺を付け加える。連結成分の数はライブラリからは直接求められないが、以下から求まる。初期状態は頂点も辺もないので連結成分は0個である。

• 頂点1個を加えたら1増える
• 辺を1本加えて、非連結成分な頂点を結んだら1減る

ABC 230-D

コードはこちら

Greedyでいけそうと思ったらgreedyな件である。

並べ替えをどうするかで実装量が変わる。公式解説は非常にすっきりして、そうでないとif文だらけになる。229-D と同様に、尺取り法のような単純なループで実装する方法を覚える。尺取り法はleftをfor eachしてカウンタをインクリメントする方が、条件に合うときだけイテレータをインクリメントするより書きやすい。 こう 実装する。Leftとrightの両方を自由に動かすとややこしい。

ABC 230-E

コードはこちら

除算の商を固定して、その商になるような割る数を考える。

$d = \lfloor n/i \rfloor$ を満たす $i$ は $\lfloor n/d \rfloor - \lfloor n/(d+1) \rfloor$ 個である、 $\sqrt{n}$ に対して対称性があることを利用する。考えるとややこしいので、こちらの解説のまま実装した。

ABC 231-240

ABC 231-D

コードはこちら

ループ検出はトポロジカルソートでできるが、union-find木の方が簡単である。

木構造つまり連結している頂点同士はたどっていけるがループが無い、という状況で、連結成分にある頂点同士を短絡するとループになる。というのをunion-find木だと簡単に確認できる。それと、次数が3以上の頂点があると題意を満たさないことも忘れずに検出する。

ABC 231-F

コードはこちら

座標圧縮してセグメント木

問題文を解釈するのがややこしいが、要するに高橋君が $j$ を選び、青木君が $i$ を選んだ時に、 $A_i \leq A_j$ かつ $B_i \geq B_j$ になるような $(i,j)$ の組み合わせの総数を求める。まず $A$ と $B$ を座標圧縮し、もとのインデックス $i$ に対して、 $A_i$ を昇順に並び替えた時の順位 $ord(A_i)$ を求める。同様に $ord(B_i)$ も求める。

$ord(A_i)=1..N$ の順に走査すれば $A_i \leq A_j : i < j$ は必ず達成できる。よってこの $B_i \geq B_k$ となる $k$ の数を求めればよい。これは $B_i$ となる $B$ の数をセグメント木の添え字 $ord(B)$ に載せてから $[B_i..N]$ の要素の和を数えればよい。載せてからなのは $i$ 自身も条件を満たすからである。

221-Eより大変なのは $A$, $B$ とも同じ値が複数個ありえることに注意する点だ。同一値の $A$ に対して $B_i$ を別々に管理する。同一値の $B$ に対して $B$ の値自身も $B_i \geq B_k$ を満たすので、まずセグメント木に $ord(B_i) = |B_i|$ を設定してから、 $sum([B_i..N]) * |B_i|$ を総組み合わせ数に足す。

$A_i,B_i$ の組が複数個あるときの処理を公式解説は巧妙に実装している。その通り実装したものが こちら である。セグメント木に加算するのが累計した後というのが絶妙で、こうすると簡潔に実装できる。

ABC 232-D

コードはこちら

再帰がそれほど深くなければDFSで書ける。

公式回答は右下から左上に向かってループで実装している。左上から右下に向かっても同じことができるし、ループではなくDFSでも解ける。ループは右下から左上に向かって このよう もしくは このよう に行い、左上から右下に向かうと上手くいかない。それと $(1,1)$ 以外の初期値は0ではなく $- \infty$ にしないと壁を飛び越えて到達してしまう。

BFSで実装するときは、優先度キューで距離が短い順に処理し、優先度キューに同じマスを二度投入しないように seen[y][x] でガードする。ガードしないとTLEする。実装は こちら か こちら

ABC 232-E

コードはこちら

$x,y$ という変数名に引っ張られない。

最初に重要なことだが $(x,y)$ を直交座標系で考える。つまり問題文の $x$ , $y$ を入れ替えて、縦(行が増える方向)を $y$ , 横(列が増える方向)を $x$ とする。この解釈が逆だったために2時間溶かしてしまった。

DPとしては4種類用意する。つまり $x=x2 \land y=y2$, $x=x2 \land y \ne y2$, $x \ne x2 \land y=y2$, $x \ne x2 \land y \ne y2$ である。

$x=x1, y=y1$ として、 $x=x2 \land y=y2$, $x=x2 \land y \ne y2$, $x \ne x2 \land y=y2$, $x \ne x2 \land y \ne y2$ のうち当てはまるものを一通り、当てはまらないものを0通りとして初期化する。後は以下のDPを $k$ 回遷移する。

• $x=x2 \land y=y2$ は、 $x=x2 \land y \ne y2$ , $x \ne x2 \land y=y2$ の各点からそれぞれ一通りの方法で行ける
• $x=x2 \land y \ne y2$ の各点へは、 $x=x2 \land y=y2$ から $h-1$ 通り、 $x=x2 \land y \ne y2$ の各点から $h-2$ 通り、 $x \ne x2 \land y \ne y2$ の各点から一通りの方法で行ける
• $x \ne x2 \land y=y2$ の各点へは、 $x=x2 \land y=y2$ から $w-1$ 通り、 $x \ne x2 \land y=y2$ の各点から $w-2$ 通り、 $x \ne x2 \land y \ne y2$ の各点から一通りの方法で行ける
• $x \ne x2 \land y \ne y2$ の各点へは、 $x=x2 \land y \ne y2$ から $w-1$ 通り、 $x \ne x2 \land y=y2$ の各点から $h-1$ 通り、 $x \ne x2 \land y \ne y2$ の各点から $h+w-4$ 通りの方法で行ける

ABC 233-D

コードはこちら

下駄を履かせる、つまりオフセットで考える。

$k = sum(A_l..A_r) = sum(A_1..A_r) - sum(A_1..A_{l-1})$ である。つまり $l-1$ までの累積和をオフセットとして累積和を検索すればよい。

ABC 233-E

コードはこちら

自力で筆算を実装する。縦の物を横にする。

なので任意精度整数の足し算と、10で割る操作を実装すればよい。しかし10で割る操作をそのまま実装すると計算回数が桁数の2乗になってTLEする。なので上位 $i$ 桁を $i=1..size(X)$ について求めた累積和を求める。こうすれば上から $i$ 桁目には、 $i=(1..i-1)$ 桁の数字の和と、下の桁からの繰上りを足せばよい。最上位桁の繰上りを忘れないように。

任意精度整数を用いた別解をC++と boost::multiprecision::cpp_int で実装したらTLEした。

ABC 234-D

コードはこちら

一度圏外に落ちたら復活できない。

のでこれまでの上位K番目までの値を std::priority_queue で持ち、数がくるごとに圏内か圏外か調べて集合を更新する。 std::multiset で持つ場合は こう する。

ABC 234-E

コードはこちら

候補を全列挙してもよいことがある。

等差数は少ないので全列挙してよかった。これは思いつかなかった。

$X$ 以上の等差数を辞書順比較で実装したらかなりのコード量になる。先頭の桁の数字が $c$ 、桁の数字の差を $d$ として、等差数 $N = c, c+d, c+2d, ...$ について

1. すべての桁について、数字が0以上9以下に収まる
2. $N \geq X$ である。つまり辞書式順序で以下が成り立つ

• 上から $i$ 桁目が Xより大きい $X_i < c+d*(i-1)$
• 上から $i$ 桁目が Xと同じ $X_i = c+d*(i-1)$ で $i+1$ 桁目についてこれらの条件を満たす

となる $N$ を求める。先頭の桁が $c$ , $d=-9..9$ について上記の条件1,2を満たす数を求める。それでだめなら $c+1$ , $d=-9..9$ について条件1を満たす数を求める(条件2は必ず満たすので調べなくていい)。全桁 $c+1$ なら($d=0$) $X$ より大きな等差数なので、そういう $N$ は必ず見つかる。

全列挙すると こちら 。 $10^{17}-1$ ではなく、 $10^{18}-1$ まで列挙する。

ABC 234-F

コードはこちら

$log(N)$ 多いのはTLE

後で並べ替えるのだから、 $S$ の各文字を昇順に並び替えて、 aaa..zzz と同じ文字は常に連続して出現すると考えて差し支えない。そのような $S$ について、一文字ずつ増やすDPを考える。

${n \choose k} : n,k \leq 5000$ はメモ化再帰で求めることができるが、このメモ化は $O(1)$ で求まる配列に置かなければならない。 std::map だと $log(N)$ 倍の時間が掛かってTLEする。

数えるのは順不同の文字列なので、同じ文字が何回出るかを求める。例えばaが3回、bが2回, cが5回とする。

• a が1回、 a が2回、 a が3回出て、 a 以外の文字がない組み合わせは1通りずつ( a , aa, aaa )。
• b が1回出るということは、 a の1..3回の並びに b を差し込むということである。差し込む場所は a の前後併せて4か所である。
• 一般的に b を含まない長さ $L$ の文字列があって、 $i$ 個の b を差し込む組み合わせは、 $L$ の各文字もそれぞれの b も区別しないで並べる順列組み合わせなので ${L+i} \choose i$ 通りである。
• よって $L$ が $combi(L)$ 通りあるなら、 $L$ の順序を保ったまま b を差し込む組み合わせは、 $combi(L) \times {{L+i} \choose i}$ 通りである。
• これを空文字列から最大長の $L$ 、ここでは空文字列、 a , aa, aaa について求める。

これを a,b,c について逐次的に求める。

• 初期値として、空文字列は1通りある
• 空文字列に a を加えて $i$ 文字にする組み合わせは、 $combi(empty) \times {i \choose i} = 1$ 通り
• a しか含まない長さ $L$ の文字列に b を加えて $i$ 文字にする組み合わせは、 $combi(|L|) \times {L+i \choose i}$ 通りある。これを $L$ の長さ $0..max(|L|)$ と、 b の個数 $0..|b|$ の組み合わせについて求める。
• a,b しか含まない長さ $L$ の文字列に c を加えて $i$ 文字にする組み合わせは、 $combi(|L|) \times {L+i \choose i}$ 通りある。これを $L$ の長さ $0..max(|L|)$ と、 c の個数 $0..|b|$ の組み合わせについて求める。以下同様に、まだ加えていない文字種に対して同じことを行う。
• 最後に空文字列以外のすべての組み合わせの数を足す

${{L+i} \choose i}$ をすべての $(L,i)$ についてメモ化で求める計算量が $O(N^2)$ で、ある $(L,i)$ について ${{L+i} \choose i}$ が定数で求まるなら、上記のループも $O(N^2)$ なので、全体の計算量は $O(N^2)$ である。

ABC 235-D

コードはこちら

探索するかどうか悩むより、BFSに任せよう。

DFSでもスタックを使い切らず答えが求まるが、BFSすべきだろう。遷移先の数字は6桁しかないので、Nから1を作るより1からNを作る方が簡単である。

Nから1を作るときに $i$ について逆操作できる(順操作すると $i$ になる数がある)条件は以下の通りである。なかなか2 WAsが取れなかった。実装は こちら 。

• $i$ を $a$ で割り切れる
• $i$ が10以上である
• $i$ の上から二桁目が0ではない。 $i$ の最下位桁は0ではない、というのは条件ではないので注意する。

ABC 235-E

コードはこちら

クエリ先読み

本来の辺と、クエリで加える辺の両方を区別せずにMSTに加えようとすればよい。クラスカル法で重みの小さい辺から加えていき、クエリで加えることに成功した(非連結成分同士を結ぶ)ならそのクエリは Yes を返し、加えられないときは No と返す。クエリの辺はunion-find木に加えるつもりというだけで、実際に加えてはならないので注意する。

ABC 236-D

コードはこちら

重複する組み合わせをできるでだけ数えない。

XORは動的計画法できないので総当たりしかないが、 $N=8$ だと思って雑に組むとTLEする。重複なしに組み合わせを網羅する方法を実装する。組の対称性から以下の通り決められる。

• 組1には、人1が必ずいて、人 $2..2N$ の誰か組む
• 組2は、組1が $(1,2)$ なら人3が必ずいて人 $4..2N$ と組む。そうでなれば組1は $(1,i), i\ne 2$ なので、組2には人2が必ずいて、人 $3..2N$ のうち人 $i$ 以外と組む。
• 一般的に組 $k$ には、まだ組んでいない人のうち最も小さい番号の人を固定し、それ以外の残りの人と組む

これをDFSかループ実装すると、すべての組み合わせを再帰的に求められる。

ABC 236-E

コードはこちら

DPだけでは解けない。

$i$ 番目のカードと $i+1$ 番目のカードの少なくとも一方を選ぶ、というのは如何にもDPである。しかし選んだカード列を保持すると、 std::vector<Num> をコピーして末尾に $i$ を追加する処理でTLEすると予想し、それ以上何も思いつかなかった。平均値はこれまでの平均値と要素数があれば加重平均を取って更新できるが、中央値はそうはいかない。

公式解説にある通り、平均値と中央値を決め打ちして二分探索するのだが、何要素あったかを数えないというのが巧妙である。これは思いつかなかった。

ABC 237-D

コードはこちら

返り値のイテレータが何かSTLの仕様を把握しておく。

イテレータによる挿入は、挿入した要素を指すイテレータを返す。よって挿入した場所の前後に挿入する処理は、返り値のイテレータを連鎖させればよい。挿入コストが定数の std::list を使う。

ABC 237-E

コードはこちら

ポテンシャル

ダイクストラ法のminをmaxに取り換えたら、 after_contest_01,05.txt だけTLEした。公式解説2を自分で実装したら違うテストケースがTLEした。ということで自力では解けなかったので、結局公式解説1をそのまま実装した。

ABC 238-D

コードはこちら。解説のように解析的に解かず、かなりややこしい解き方をしたがこれでもACできる。

式変形が問われることがある。

詳しは公式解説を参照。直観的な説明は、加算器を思い浮かべて桁の繰上りが起きない条件とは何かを考えれば分かる。

ABC 238-E

コードはこちら

累積和の使い方

累積和の要素に依存関係を持たせてグラフを作り、連結かどうか調べる、というのが答えだが全く思いつかなかった。なので公式解説を読んで実装した。水diff以上は解法を全く思いつかないことがある。

ABC 239-D

コードはこちら

Min-max戦略である。

先手が何をしても後手が最善を尽くせば後手必勝、そうでなければ先手必勝である。これを総当たりで求める。

ABC 239-E

コードはこちら

入力範囲に注目する。

$K \leq 20$ なので、すべての頂点について上位20位を保持して構わない。DFSで求まる。部分木といえば、オイラーツアーでも解けるらしい。

ABC 239-F

コードはこちら

重実装かもしれない青diffを解いてみた。

高速道路を連結するなら、異なる連結成分をつなぐのが得である。そこで街を連結成分に分けて、あと何回連結するかをマージテクで管理する。

• 街 $i$ をあと何回連結できるかを、入力 $D_i$ で管理する。連結するたびに1減らす。
• 連結している街の集合 $G_j$ に含む、 $D_i > 0$ な街を $S_j$ で管理する。集合の代表元に関連付ける。
• 連結している街の集合 $G_j$ を何回連結できるかを、 $Cnt_j$ で管理する。集合の代表元に関連付ける。

もっとも連結しにくい街の集合( $Cnt_l$ が最小)な $S_l$ と、もっとも連結しやすい街の集合( $Cnt_r$ が最大)な $S_r$ を選ぶ。これらにはそれぞれ $D > 0$ な街があるはずなので、それらを高速道路で連結する。

街を連結すると $D$ が1減る。連結後に $D = 0$ な街を除く。街の集合を連結すると、 $S_{l+r} = S_{l} \cup S_{r} $ , $Cnt_{i+j} = Cnt_i + Cnt_j - 2$ になる。 $Cnt_{l+r} = 0$ なら $S_{l+r}$ をこれ以上管理する必要はなく、そうでなければ $S_{l+r}$ の代表元と関連付ける。

これを繰り返すと、連結できる街が無くなるか、街の集合が一つになるか、どちらかである。すべての街が連結でなければ(街1を含む連結成分の大きさが $N$ 以外なら)解なしである。

残りの高速道路の新設枠を、連結可能な街同士を連結成分かどうか問わず連結して、高速道路を $N-M-1$ 本新設した状況にする。 $D < 0$ な都市があれば解なし、そうでなければどの街を連結したか履歴を出力する。

方針は公式解説2と同じだが、もう少し軽い実装がありそうだ。

ABC 240-D

コードはこちら

たまにはスタックを使う。

$k$ 番のボールで消えるのは $k$ 番だけなので、 $k$ 番以外のボールが見えるまで消せばよい。これはスタックがうってつけである。

ABC 240-E

コードはこちら

題意を諦めずに読み解く。

問題文がとてもややこしいので読解に時間が掛かるが、要するに部分木を葉ノードで分類する、ということである。つまりある二つの部分木について、葉ノードが互いに素なのか包含関係かということを、通し番号で表現する。これは葉を左から右(あるいは右から左)に番号をつければよいので、DFSの訪問順に葉ノードに番号をつければよい。短く実装すると このように なる。

ABC 240-F

コードはこちら

冷静にピーク値を計算する。

$\sum_{1}^{n} x = x \times n$ の累積和として $B_{y_{i}}$ が求まり、 $base=B_{y_{i-1}}$ と $\sum_{i=1}^{n} x = x \times i(i+1)/2$ の累積和として $C_{y_{i}}$ が求まる。よって $C$ のピーク値が 区間 $(x_i,y_i)$ の終わりなら、区間の終わりの値だけ計算してその最大値を求めればいい。区間内のすべての添え字について $B,C$ を求めるとTLEする。

区間の終わりが答えではないない場合が二通りある。以下も求めて、最大値を取ると答えになる。

• 答えが先頭要素だけつまり $x_1$ のときがある。空集合で0は答えではないので注意。
• 区間の途中にピークが来る場合がある。具体的には、 $x_i < 0, base=B_{1+y_{i-1}} > 0, B_{y_{1}} < 0$ のときである。このときは区間の先頭を1番として位置 $p=base/-x$ にピーク $C_{y_{i-1}} + \sum_{i=1}^{p}(base+x \times i)$ が来る。この条件判定で区間を1間違えて $base=B_{y_{i-1}} > 0$ にするとWAする。

注意点として、負の数の除算を避けて、正の数の除算にする。 $x<0$ のときは $-x$ で割る。

ABC 241-250

ABC 241-D

コードはこちら

解説を読むと様々な方法があって面白い。

クエリ先読みをするかしないかどちらでも行ける。クエリ先読みをしないかつSTLの範囲で解くなら、 std::multiset と std::multiset::upper_bound を使えばよい。座標圧縮してセグメント木やBITでも行けるらしい。

ABC 241-E

コードはこちら

鳩の巣定理

状態遷移における状態は $N$ 個しかないのだから、 $N < K$ なら $K$ 回の遷移で必ず同じ状態 knot を2度通ることが鳩の巣定理から言える。つまり初期状態 0 から knot までいき、 knot から knot へのサイクルを回り続けることが分かる。高々 $N$ 回のシミュレーションで knot を求められる。その後は、

• 初期状態 0 からサイクルの手前まで
• サイクルを回り続ける
• サイクルの途中で $K$ 回が尽きる

までのそれぞれについて、追加するアメを数える。初期状態 0 からサイクルの直線までの累積和と、サイクルの始点から始点に戻る直前までの累積和を求めることで、大きな $K$ に対しても $O(N)$ で答えが求まる。累積和を使ってコードを改良したものが こちら

ダブリングでも解けると思ったが上手く定式化できなかった。実際公式解説にある通り、ダブリングでも解ける。

ABC 242-D

コードはこちら

ゴールからスタートに再帰する。 ABC 巡回を何回進めるかは $t$ の大きさと $k$ のビットだけで求まり、順序を問わないのが着眼点である。

再帰の方向を間違えるとどうしようもないことがある。公式解説のようにゴールからスタートに再帰するとあっさり解ける。しかしスタートからゴールに再帰すると、ノード数が $10^{18}$ を超えたところでどうしていいか分からなくなる。

一応スタートからゴールにたどることもできる。 $k$ を0-basedにするため1引いておく。注意深く実装すると AC できる。

• $k > 2^{60} > 10^{18}$ なら、 $S$ の最初の一文字から派生した系列で埋め尽くされる。よって $S(0)$ を $t - 60$ 回 ABC と巡回した文字を起点に60回枝分かれした $k$ 文字目である。
• $k < 10^{18}$ なら、 $S$ の一文字当たり $n=2^t$ 個の葉を持つので、 $S( \lfloor k/n \rfloor)$ 文字目を起点に $S(k \quad mod \quad n)$ 文字目である。
• 根から葉までは、一段降りると ABC の巡回を一文字進み、 $k$ の立っているビット1が1個あるごとにさらに巡回を一文字進む。

ゴールからスタートにたどるコードは、 このように はるかに簡潔である。

ABC 242-E

コードはこちら

辞書順の意味をよく考える。

下準備に、長さ $i=1..1000000$ の文字列の回文の数 $26^{\lfloor (i+1)/2 \rfloor}$ を数えておく。次に文字列の先頭を1文字目として、 1から長さ $N$ の中心の位置 $center = \lfloor (N+1)/2 \rfloor$ 文字目までを決め打ちする。

• 1文字目が C なら、 A または B で始まる長さ $N-1$ の任意の回文と、 C で始まる回文がある。残りの文字を見ていく。
• 一般的に、 $1..(center-1)$ 文字目の文字が $c$ なら、 $ord(c)-ord(A)$ 種類の長さ $N-1$ の任意の回文と、 $c$ で始まる回文がある。ここで $ord(c)$ は $c$ のアスキーコードである。
• 中心の文字が $c$ なら、少なくとも $ord(c)-ord(A)$ 種類の回文は作れる。

なので中心の文字を $c$ と置いたときに回文になるかどうか調べる。これは $i=(center+1)..N$ 文字目の文字をこの順に、反転した位置の $n-i$ 文字目の文字と比べて、勝ち負けを決める。

• 反転した位置より反転前の位置の文字が辞書順で後に来れば勝ちが決まる
• 反転した位置より反転前の位置の文字が辞書順で前に来れば負けが決まる
• 反転した位置と反転前の位置の文字が同じなら次の文字を比べる。すべての文字の組が同じなら勝ち。

勝ちなら中心の文字を $c$ と置いたときに回文になるので、答えを1足す。この処理がややこしい。なお $N$ が奇数か偶数かは気にしなくてよい。

上記をすっきりまとめた実装が こちら である。

ABC 243-D

コードはこちら

完全二分木なら、 $i$ 段目のノード数は $2^i$ 目である。

なので ノード $i \geq 1$ の子ノードは $2i, 2i+1$ と決まる。直に整数演算するとオーバフローするので、いったんtrue/falseの無限列にしてから、二進数とみなして整数に変換する。

ABC 243-E

コードはこちら

青diffを解き損ねた。

ワーシャルフロイド法で最短距離を求め、迂回路が直交路より短ければ直交路は要らない。ここまですぐ分かったがWAが取れなかった。公式解説にある通り、始終点を固定して経由地を総当たりすればよいのだが、迂回路と直交路の距離が同じなら直交路は不要という境界条件を間違えた。

ワーシャルフロイド法は経由地つまりパスを同時に求めることもできる。当初はその方針で解いており、実際このように 解ける 。

ABC 244-D

コードはこちら

転倒数が答えになる。

一般解は転倒数だがこの問題は奇置換か偶置換かだけ区別できればいい。置換は3通り、状態は6通りしかないので全部数えあげればいい。

ABC 244-E

コードはこちら

真面目に数え上げると辛いときはDPを使う。

$0..K$ 回移動して、頂点 $1..N$ にいるとき、 $X$ を通った回数が奇数か偶数かというテーブルを作る。テーブルは奇数と偶数の二種類、移動するごとに直前の移動以外は忘れていいので、用意するのは std::vector<ModInt> table(n+1, 0) を奇数、偶数、前と今の4個である。前と今のテーブルを入れ替えるのは std::swap が便利である。 std::vector<std::array<ModInt, 2>> dp(n); と同じ型の next を持つとswapが楽である。

これをDPで更新する。

• 移動先が $X$ なら、前に $X$ を通った回数が奇数なら今は偶数、前の回数が偶数なら今の回数は奇数である。このように移動元の回数を移動先に加える。
• 移動先が $X$ なら、前に $X$ を通った回数が奇数なら今も奇数、前の回数が偶数なら今の回数も偶数である。

ABC 245-D

コードはこちら

小学生の筆算である。

多項式の除算を筆算するには、単に10進数ではない割り算と考えればよい。

ABC 245-E

コードはこちら

入れ物と入れるものを混ぜる

と言ってしまえばそれだけだが、解説を読むまで何をしていいか分からなかった。235-Eと考え方は同じだった。

チョコレートと箱をまとめて降順に並べればよい。そうすれば縦の長さの降順、縦の長さが等しければ横の長さの降順、縦横が等しければ箱が先でチョコレートが後になる。この順に先頭から見ていけば、チョコレートの縦が収まる箱はもしあるなら見つかっているので、横が収まるぎりぎりの箱に入れればいい。

ABC 245-F

コードはこちら

難しく考えすぎない。

グラフに一つ以上のループがあるなら、ループに到達可能な頂点の集合が答えである。ただし孤立している、つまり辺を持たない頂点はあらかじめ union-find木で除いておく。すべての頂点から出発し、ループまたはループに到達可能な頂点にたどり着いたらそこで探索を打ち切る。これで解けるが有向グラフのループ検出を実装するのが難しい。

公式解説の方法はもっと簡単である。それ以上遷移先がない、つまり出次数が0の頂点を再帰的に刈っていけばよい。実装するとこうなる 。

もう一つの方法は、グラフを強連結成分分解して、頂点数が2以上の強連結成分から到達可能な頂点をBFSで求める方法である。強連結成分から到達できるかどうかは、有効グラフの向きを逆にしておくとBFSで調べられる(そうすればサイクルから枝に向かうし、サイクルは逆にしてもサイクルのままである)。実装は こちら 。

ABC 246-D

コードはこちら

値域に注意する。

$10^{18}$ の三乗根は $10^{6}$ なので、aを固定した全数探索でいけそうである。私はaを固定してbを二分探索で求めたので $log(N)$ 余分に実行時間が掛かっている。公式解説にある通り、 $a$ が増えれば $b$ の上限は単調減少するので二分探索は要らない。単調減少なら二分探索ではなく尺取り法なので $log(N)$ コストが無くなるのは、問題によっては無視できない(TLEする)。

整数の累乗が式で与えられときに定義域や値域を求めよ、という問題は探索範囲を上手く狭めないとTLEする。

公式解説は尺取り法を用いたもっと簡単な方法で、実装すると このよう になる。二分探索をラムダ式で実装すると このよう になる。

ABC 246-E

コードはこちら

BFS。

始点から1手、2手、3手... で到達可能な範囲をBFSで探索すればよい。探索範囲が尽きた時、終点までの最短手番が分かっているか、到達不能(距離が無限大)か分かる。

というのをキューで実装したらキューが長くなりすぎて、TLE, MLE, REが起きた。なので探索範囲を効率的に実装する必要がある。

• 探索範囲、つまり始点からの手番は1手ずつしか増えない
• 一度訪れた場所はキューに乗っているか乗っていたはずだから、キューに載せない

と思って全方位の行先を一気にキューに載せたらTLEぎりぎりのほぼ6秒掛かった。

正解は01BFSである。実装 が大変である。以下の通り正確に実装しないとACできない。

• 距離を方向別に管理する
• 優先度キューの辞書順比較は、距離、座標、向きの順する
• 頂点を訪問したかどうか印をつける
• 終点を見つけたらすぐ出力して終了する
• 距離を更新するのはキューから出した時ではなく、キューに入れた時にする
• 始点には向かう方向がないので特別扱いする

ABC 247-D

コードはこちら

ランレングス符号化である。以上。

ABC 247-E

コードはこちら

区間分割である。

難しく考えすぎない。 $X$ より大きいか $Y$ より小さい値を $[L,R]$ に含むことはできない。なのでそのような値を除いた区間に分割する。

$X=Y$ なら、 $A=X=Y$ が連続する区間に分割する。区間 $[L,R]$ の長さが $l=R-L+1$ なら、この区間には $l(l+1)/2$ 個の組み合わせがある。

$X \ne Y$ なら、 $Y \leq A \leq X$ が連続する区間に分割する。区間内の位置 $p : L \leq p \leq R$ を調べる。 $p$ およびそれ以降で、区間内に最初に $X,Y$ がそろえば、それ以降の位置 $q$ は $p$ と組にできる。

• $p$ 以降で $X$ が出る位置を $p \leq X_{pos} \leq R$ とする
• $p$ 以降で $Y$ が出る位置を $p \leq Y_{pos} \leq R$ とする
• そのような $X_{pos}, Y_{pos}$ が存在しなければ、 $p$ に対する組み合わせは無い
• そのような $X_{pos}, Y_{pos}$ が存在すれば、 $p$ に対して $R + 1 - max(X_{pos}, Y_{pos})$ 個の組み合わせがある

これらを全区間および $p=1..N$ について調べた組み合わせの合計が答えである。センチネルとして $A_{N+1}=0$ (というか $Y-1$ )を加えると最後の区間を数え損ねることが無くなる。

尺取り法で解くと $O(N)$ になるらしいが、 std::lower_bound で $O(Nlog(N))$ でも間に合う。上記の解き方が公式解説1の3番目の解法である。包除原理でも解けるらしい。

もう少し素直な実装を考える。

• 区間 $[1,N]$ を一つ以上の区間 $[L,R,lows,highs]$ に分割する。 $L$ は区間の左端、 $R$ は区間の右端、 $lows$ は $a_i=Y$ となる0個以上の位置(昇順)、 $highs$ は $a_i=X$ となる0個以上の位置(昇順)である。これは $A$ を先頭から走査し、 $Y \leq a_i \leq X$ が連続する区間をまとめればよい。 $R=-1$ を初期値にすると、空の区間にできる。
• 区間は $L$ の昇順に並んでいる。まず空の区間 $R=-1 \lor lows.empty() \lor highs.empty()$ を無視する。そうでなければ $i \in [L,R]$ を先頭から走査し $min(lows), min(highs) \geq i$ の両方が見つかるなら $n - max(min(lows), min(highs))$ が $i$ に対応する右端の個数なのでそれらを合計する。
• 区間内の走査は std::lower_bound で 書ける が、 尺取り法 も覚える。尺取り法なら $[lows,highs]$ を保持する必要はない。

ABC 248-D

コードはこちら

値域に注意する。

$A_i$ は $N$ 以下で20万通りしかない。なのでそれぞれの値がいつ出てくるか数えておけばよい。そうすれば位置を与えた時にそれ以前またはそれ以後の出現位置を、 std::lower_bound で検索できる。

ABC 248-E

コードはこちら

いい実装がありそう。

$K=1$ なら直線は無数にあり、 $K>1$ なら二点を通る直線は一つに決まる。

$N=300$ なので、二点を取ってその延長に他の点があるかどうかを $O(N^3)$ で調べても間に合う。なので総当たりして構わない。同じ直線を二度数えないように管理する。まず直線を通る頂点を定める。

• X軸に平行な直線は、Y座標で管理する
• Y軸に平行な直線は、X座標で管理する
• X軸にもY軸にも平行でない直線は、その直線を通る点の番号が最も小さい頂点番号で管理する。XまたはY軸との交点は浮動小数なので正確に表現できない。

直線の傾きは以下の通りにする。

• X軸に平行な直線は $(1,0)$
• Y軸に平行な直線は $(0,1)$
• X軸にもY軸にも平行でない直線は、傾きの最大公約数で割ったあと、X方向が正になるようにYの符号を適宜反転させる

これで直線の位置と傾きが決まるので、二つの直線が同一か判定できる。直線に $K$ 点以上乗っているかどうか数える。

公式解説は外積を使っている。三重ループを回せばよいが、同じ直線を二度数えないように記録しておく。コードは こちら

ADT HARDで改めて解いたが、直線の同一判定を 以下のよう にした。4つの整数を使って、Y軸との交点(切片)を有理数表現する。ここで向きを正規化するとは、X軸方向の向きを非負にし(そうでなければ符号を反転する)、X方向とY方向の向きを絶対値の最大公約数で割って互いに素にしたものである。

• X軸に平行なら、1, 0, 0, Y軸切片。Y軸切片という意味では、1, 0, Y軸切片, 1 とするのが適切な実装だったが、ここではX軸に平行な直線を互いに区別できれば十分である。
• Y軸に平行なら、0, 1, X軸切片、0。Y軸切片は無いので、他の直線と区別できる一意な値ならなんでもいい。
• そうでなければ、正規化したX方向の向き、正規化したY方向の向き、Y軸切片の分母、Y軸切片の分子を使って、Y軸切片を有理数表現する。

公式解説にあるように、ちょうど $K$ 個を通る直線をちょうど $K$ 回数える方が簡単である。実装は こちら 。二頂点の差を向きとして正規化する方法は上記と同じである。

ABC 249-D

コードはこちら

計算量解析が重要である。

素朴な方法は、 $A_i, A_j, A_k$ が全て異なる、二つが一致 $A_j=1$ 、三つが一致 $A_i=1$ に場合分けして数える。これでも上手くいくがかなりめんどくさい。

公式解説にある通り、二重ループの計算量は実は小さい。 $\sum_{1..i} (1/i) \sim log(n)$ である。なので計算量解析をした上で二重ループに持ち込んで構わない。

ABC 249-F

コードはこちら

後ろから考える。

先頭には $(t_0,y_0) = (1,0)$ があると暗黙に仮定する。 $t=2, y \leq 0$ な置き換えは常に答えを最大化するので採用する。

よって $t=1$ を $p=0..K$ 個無視し、 $t=1$ を最大 $K-p$ 個無視することを考える。これを操作の最後から順に考える。最初の $t_i=1$ となる操作を見つけたとき、答えは以下の和である

1. $y_i$
2. $i$ 以降の $t=2, y \geq 0$ な $y$ の総和
3. $i$ 以降の $t=2, y < 0$ な $y$ のうち、 $y$ の下位 $K$ 個を除いたものの総和

一般的に最後から $t_i=1$ となる $1 \leq p \leq K$ 番目の操作 $i$ を見つけたとき、答えは以下の和である

1. $y_i$
2. $i$ 以降の $t=2, y \geq 0$ な $y$ の総和
3. $i$ 以降の $t=2, y < 0$ な $y$ のうち、 $y$ の下位 $K-p \geq 0$ 個を除いたものの総和

最後から $t_i=1$ となる $K+1$ 番目の操作は無視できず、 $K$ 番目以前の操作が採用されるので考慮しない。

上記の1はその場でわかる、2は累積する、3は std::multiset に $y$ を加えて、 $K-p$ 個に収まらない要素を小さい要素から捨てればいい。要素数は短調減少で、捨てた要素が後から必要にはならない。

ABC 250-D

コードはこちら

やはり値域に注意する。特に変数間の制約は大事。

$10^{18}$ の三乗根は $10^{6}$ なので $q$ の上限は $10^{6}$ と解る。よって $q$ を全探索して $p$ の個数を求めればいい($p$ を全探索して $q$ を求めると $pq^3$ が64-bitに収まらない)。

素数表を二分探索してもいいし、尺取り法でも求まるらしいが std::upper_bound の方がコードは簡潔である。素数表を求める方法は頻出なのでスニペットにしておく。

ABC 250-E

コードはこちら

確率的アルゴリズム

集合を比較するとTLEするのでダイジェストを作る。重複の無い数字の集合 $S = {n_1, n_2, ...}$ についてダイジェスト $\sum_{i} 2^{n_i} \quad mod \quad M$ を定義する。 $A$ の先頭から $i$ を一つずつ増やし、まだ見たことのない $a_i$ が現れたらダイジェストを更新し、みたことのある $a_i$ ならダイジェストはそのままにする。

こうすると $A$ の先頭 $1..N$ 項と $B$ の 先頭 $1..N$ 項のダイジェストが逐次的に求まる。後はクエリごとに $A,B$ のダイジェストが一致するかどうか返せばよい。衝突に備えて $M$ は素数を二通り用意しておく。

Zobrist hashing をきちんと実装したものが こちら。

公式解説は、 集合 $(a_1,...,a_i)$ が $i$ について単調増加することを利用している。実装は こちら

• $i=1..n$ についての集合の大きさ $|a_1,...,a_i|$ を求める。 $|b_1,...,b_j|$ も同様。
• 集合の大きさが $k=1..N$ となるような $|a_1,...,a_i|=k$ と $|b_1,...,b_j|=k$ を逐次的に求める
• 集合の大きさが $k$ のとき、余ったつまり $a$, $b$ のどちらか一方にしかない要素があれば不一致、そうでなければ一致である。
• $x,y$ について、 $|a_1,...,a_x|$ と $|b_1,...,b_y|$ は前計算してあるので、不一致なら No である。そうでなければ集合の大きさ $k$ について集合が一致するかどうか前計算してあるので返す。