目次
ミラティブ プログラミングコンテスト2025(AtCoder Beginner Contest 414)E,F,G問題メモ
E - Count A%B=C
問題文
- 整数の組 $(a, b, c)$ であって以下の条件を満たすものの個数を $998244353$ で割ったあまりを求めてください。
- $1 \leq a,b,c \leq N$
- $a,b,c$ は相異なる。
- $a$ を $b$ で割ったあまりは $c$ に等しい。
制約
- $3 \leq N \leq 10^{12}$
- $N$ は整数
解法
$b$ の値を固定したと考える。
$c$ は(制約より $0$ はないので)$1$ 以上 $b$ 未満の値を取る。
$b,c$ が決まったとき、$a=kb + c$ と表せ、 $k$ は $1$ 以上 $\lfloor \frac{N-c}{b} \rfloor$ 以下の値を取り、 それぞれに異なる $a$ ができる。
よって、$\displaystyle \sum_{b=1}^{N} \sum_{c=1}^{b-1} \left\lfloor \frac{N-c}{b} \right\rfloor$ が答えとなる。
そのまま求めるのは当然TLEなので、高速化を考える。
例えば $N=12345, b=100$ の時、
- $c=1~45$ の時は $\lfloor \frac{N-c}{b} \rfloor=123$
- $c=46~99$ の時は $\lfloor \frac{N-c}{b} \rfloor=122$
つまり、$b-1$ 通りの値を取る各 $c$ において、$\left\lfloor \frac{N}{b} \right\rfloor - 1$ は確定で、あと $N \% b$ 個の $c$ について追加で $1$ だけ加算されると考えられる。
- $\displaystyle \sum_{b=1}^{N} (b-1)\left(\left\lfloor \frac{N}{b} \right\rfloor - 1 \right) + (N \% b)$
- ↓
- $\displaystyle \sum_{b=1}^{N} (b-1)\left(\left\lfloor \frac{N}{b} \right\rfloor - 1 \right) + N - \left(\left\lfloor \frac{N}{b} \right\rfloor \times b \right)$
- ↓
- $\displaystyle \sum_{b=1}^{N} N+1-b-\left\lfloor \frac{N}{b} \right\rfloor$
$N+1-b$ の $b=1~N$ の総和は簡単に求まる。
$\lfloor \frac{N}{b} \rfloor$ の総和も過去問にあり、$O(\sqrt{N})$ で求められる。
F - Jump Traveling
問題文
- 頂点に $1$ から $N$ の番号がつけられた $N$ 頂点の木および整数 $K$ が与えられます。$i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を双方向に結んでいます。
- あなたはいま頂点 $1$ にいます。以下の操作を $0$ 回以上繰り返すことができます。
- あなたが今いる頂点からの距離が $K$ であるような頂点を一つ選び、その頂点に移動する。ただし、$2$ 頂点間の距離は $2$ 頂点を結ぶ単純パスに含まれる辺の個数とする。
- 各 $k=2,\ldots,N$ に対して、操作を繰り返して頂点 $k$ に移動することができるかどうか判定し、移動できるならば操作回数の最小値を求めてください。
- $T$ 個のテストケースが与えられるので、それぞれについて解いてください。
制約
- $1\leq T\leq 10^5$
- $2\leq N\leq 2\times 10^5$
- $1\leq K\leq 20$
- $1\leq u_i\lt v_i\leq N$
- 与えられるグラフは木
- 全てのテストケースに対する $N$ の総和は $2\times 10^5$ 以下
- 入力は全て整数
解法
一瞬、「頂点 $1$ を根とした木の、深さが $K$ の倍数にある頂点にしか行けないのでは?」と勘違いしたが、 $K=5$ の時、2 遡って 3 別の枝を進む、みたいなことができるので、その限りではない。
$K$ が小さいので、$O(NK \log{(NK)})$ がギリギリ通りそう。
頂点を倍加して、ノード $(i,j)$ を「頂点 $i$ に移動距離を $K$ で割った余りが $j$ の時に到達した状態」を表すとする。
$i=1~N$ と $j=0~K-1$ に対して、$(u_i,j)→(v_i,(j+1)\%K),(v_i,j)→(u_i,(j+1)\%K)$ に辺を張れば良い。
ただし、このままBFSしても正しく求まらない。
「2 遡って、“同じ道を” 3 引き返す」みたいな移動まで可能になってしまうためだ。
探索時、どの頂点から来たかも持たせて、その方向には引き返せないようにする必要がある。
- ノード $(i,0)$ からは、どの頂点へも移動可能
- $j \neq 0$ のノード $(i,j)$ からは、直前の頂点 $p$ へは引き返せない
- 次に $p$ 以外の頂点からそのノードを訪れた際に、頂点 $p$(ノード $(p,j+1)$)へ移動することができる。
- 3回目以降に訪れた際は、全ての移動可能なノードへ既に訪れているので探索を広げる必要は無い。
よって、最短距離の他に「ノードを訪れた回数」と「1回目にどの頂点から来たか」も持ちながら BFSすることで、不正な移動をしないように探索することができる。
処理の場合分けをサボって「2回目に訪れたときも、$p$ だけではなく、1回目と同じように直前頂点以外へ探索を広げる」としても、多少時間は延びるが、間に合う。
ただし、その場合は「2回目に訪れた際も1回目と同じ頂点から探索される」という可能性が発生し、回数だけで判定すると結果が正しく求まらない。
ちゃんと「異なる頂点から」2回目に探索されたときに、探索を広げる必要がある。
G - AtCoder Express 4
問題文
- AtCoder 王国には東西に伸びる路線があり、この路線には駅 $1,2,\ldots,N$ があります。駅 $i\ (1\leq i\leq N)$ は座標 $x_i$ に位置しています $(x_1 \lt x_2 \lt \ldots \lt x_N)$。
- この路線で AtCoder Express 社は $M$ 種類の特急列車を運行しています。
- $i$ 種類目の特急列車は以下のように運行されます。
- 乗車できる駅は駅 $l_i,l_i+1,\ldots,r_i$ のいずれかである。
- 降車できる駅は駅 $L_i, L_i+1, \ldots, R_i$ のいずれかである。ここで、列車の進行方向は東西のどちらか一方向であり、$r_i\lt L_i$ または $R_i\lt l_i$ のいずれかが成り立つ。
- 運賃は、初乗り運賃として $c_i$ がかかり、乗車駅から降車駅までの距離に応じた金額が加算される。具体的には、駅 $s\ (l_i\leq s\leq r_i)$ から駅 $t\ (L_i\leq t\leq R_i)$ まで移動する場合の運賃は $c_i+|x_s-x_t|$ である。
- あなたはいま駅 $1$ にいます。各 $k\ (2\leq k\leq N)$ について、特急列車を乗り継いで駅 $1$ から駅 $k$ まで移動することができるかどうか判定し、移動できるならば移動するために必要な運賃の合計の最小値を求めてください。
制約
- $2\leq N\leq 10^5$
- $1\leq M\leq 10^5$
- $0\leq x_1 \lt x_2 \lt \ldots \lt x_N \leq 10^{12}$
- $1\leq l_i\leq r_i\leq N, 1\leq L_i\leq R_i\leq N$
- $r_i\lt L_i$ または $R_i\lt l_i$ のいずれかが成り立つ
- $1\leq c_i\leq 10^{12}$
- 入力は全て整数
解法
区間に辺を張るテク。
グラフとセグ木の融合が面白く妙に記憶に残るテクであり、いつか使ってみたいと思いつつ、
ABCやARCで「もしやこれは」と思って試したが解法は全然違っていた、という空振りを繰り返していた中、
ついにABCで出題されたので、なんか勝手に感慨深さを覚えている。
(まぁ本番はFに時間かかってGまで行けなかったんだけど)
ただ、この問題は上記のリンクの図からさらにひとひねり必要。
運賃が「どこで乗ってどこで降りても $c_i$ 固定」というわけではなく、
距離に応じた金額を加算しなければならない。
ただし加算分はどの電車でも一緒なので、セグ木的な辺の中に入れ込むことができる。
具体的には、末端ノードから中間ノードへの移動コストが 「その中間ノードが表す右端までの距離」と一致するようにコストを設定すれば良い。(右へ移動する電車の場合)
i 0 1 2 3 ... 距離差 20 30 40 末端ノード ○ ○ ○ ○ ... 20↘ ↙0 40↘ ↙0 ┌ ○ ○ 中間ノード┤ 70↘ ↙ 0 : ○
「乗車側/降車側」「右へ移動する電車/左へ移動する電車」で、辺の向きやコストが異なるため、 計4通りの“セグ木っぽい中間ノードと辺”を用意する必要がある。
これができたら、次に各電車が結ぶ(乗車側の区間)→(降車側の区間)間にリンクを張ることを考える。
電車 $i$ の乗車側区間からは、$[l_i,r_i]$ の区間をセグメント木で取得・更新するときに 訪れるノードと同じ頂点($O(\log{N})$ 個)それぞれから、電車 $i$ を表す頂点に向けてそれぞれ辺が張られる。
この時の各辺のコストは、 「中間ノードが表す区間の右端から、電車 $i$ の乗車区間の右端までの距離」としておけばよい。
降車側も似たようなことをやる。
また、「$r_2$ から $L_1$ までの距離」と「固定コスト $c_i$」も、乗車側か降車側、どっちかの辺に持たせる必要がある。
(または1つの電車を2頂点で表現し、2頂点を結ぶコストとして表現してもよい。以下の例はそのタイプ)
乗車側 乗車側 電車 電車 降車側 降車側 末端ノード 中間ノード ノード1 ノード2 中間ノード 末端ノード 8o... ........○-----, ,-------→○...... o8 8o... ......○-------→○-----→○------→○........ o8 8o... ....○---------' `---→○.......... o8 --①┘ --②┘ ---③┘ ---④┘ --⑤┘ 乗車側の各末端ノードから ①まで: 各中間ノードが表す区間の右端までの距離 ②まで: その電車の乗車区間の右端 r1 までの距離 ③まで: L1 までの距離(固定コスト c も加算) ④まで: 各中間ノードが表す区間の左端までの距離 ⑤まで: 各降車側の末端ノードまでの距離
このようになって、各乗車側の末端ノードから、各降車側の末端ノードへ、正しいコストで経路が繋がる。
左へ移動する電車の場合も、同じように考えられる。
統一的な書き方ができて比較的バグらせにくい実装では $9N'+2M$、 少し頑張って節約すると $5N'+M$ 頂点で必要なグラフを構築することができる。 (※ $N'$ は $N$ 以上の最小の2冪)
グラフが構築できれば、後は普通にDijkstraするだけ。
グラフの辺が正しく張れているか可視化しづらいので、バグ取りが大変。