phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

ABC155 F. Perils in Parallel

問題

数直線上にN個の爆弾が仕掛けられており、i番目の爆弾はA_iの位置で、スイッチの状態がB_i(OFFは0、ONは1)で与えられる。
制御装置にはM本のコードがあり、j番目のコードを切ると、L_j以上R_j以下の位置にある爆弾のスイッチの状態が入れ替わる。
切るコードをうまく選んで、すべての爆弾の状態をOFFの状態にできるか?
できる場合、どのコードを使うと良いか、答えよ。

制約

  • 1 <= N <= 10^5
  • 1 <= A_i <= 10^9, A_iは互いに相異なる
  • 1 <= M <= 2*10^5
  • 1 <= L_j <= R_j <= 10^9

解法

解説放送より。

範囲に対して操作するのは大変なので、imos法のように、値の差分を保持するような数列を考える。これによって、範囲は始点と終点の2箇所で扱うことができる。

例えば、数直線上の爆弾を左からスイッチの状態が001101のような場合、

0 0 0 1 1 0 1 0     # 元の状態の両端に0を加えたもの
 0 0 1 0 1 0 1   # 上の各隣り合う要素間の差分(xor)を取ったもの

(下から上の数列に戻すには累積xorを前からとっていけば良い)

差分列の方で、要素を2つ選んでそれぞれ0/1を反転させれば範囲更新に対応する処理が行える。


次に、各コードについて考える。
各コードは、差分列でのどの位置とどの位置の0/1を反転させるかに対応している。
この位置は、適当に二分探索などで計算しておくことができる。
したがって、問題は、コード(2要素を選んで0/1を反転)をうまく選んで、差分列のすべて要素を0にできるか?を解くことになる。


差分列のある1になっているような要素に注目すると、そこからコードでつながる他の要素の状況に合わせて1を0にしなければならない。
なので、ある1になっている要素について、そこからコードでつながる連結成分を考える。
(この連結成分は多重辺やループなどを含んでいる)

辺(コード)を選ぶと両端の要素を反転させることができるが、どのように選べばすべての要素を0にすることができるか?
これは、DFS木を作って、リーフから決めていけば求められる。
もし、ある要素eにおいて、子の要素cが1だった場合、eとcの間の辺は使う必要がある。
要素e自体の値は、子の要素に対し、使った辺の数と、要素eの元の0/1によって決まる。これをルートまで繰り返して、ルートでの値が0になればよい。
もし、ルートでの値が1だった場合は、不可能。

ABC155 E. Payment

問題

AtCoder王国では、価値が1,10,100,1000,...,10^(10^100)の紙幣になっている。
今、商品の価値がNであるような商品を買いたい。
各紙幣は十分な枚数を持っているとした場合、この商品を買うために払う枚数とおつりの枚数を適切に最小化した場合、最小で何枚にすることができるか?

制約

  • 1 <= N <= 10^1000000

解法

各桁に注目すると、ある桁での数字N_iをそのまま払う場合は、「払う枚数はN_i枚、お釣りは0枚」で、もしそれよりも大きい価値の紙幣で払う場合は、「払う枚数は1枚、お釣りは(この桁については)10-N_i枚」になる。

したがって、各桁について、そのまま払うか?、より価値の高い紙幣で払うか?の選択が考えられるため、これをdpで求める。

dp[i][j] := i番目の桁で、j=1なら一つ前の桁で高い紙幣で払うことにした、j=0ならしなかった場合の、最小やり取り枚数

遷移は、もらうDPで考えると、i+1番目の桁では、

  • dp[i][0]から、そのまま払う+N_iか、高い紙幣で払う+(10-N_i)か
  • dp[i][1]から、そのまま払う+(N_i+1)か、高い紙幣で払う+(10-(N_i+1))か

の4種類で、

int n = N[i]-'0';
dp[i+1][0] = min(dp[i+1][0], dp[i][0] + n);
dp[i+1][1] = min(dp[i+1][1], dp[i][0] + (10-n));
dp[i+1][0] = min(dp[i+1][0], dp[i][1] + (n+1));
dp[i+1][1] = min(dp[i+1][1], dp[i][1] + (10-(n+1)));

のような感じになる。
(Nにleading-zeroをつけて計算しておくと、最上位付近の桁での計算を木にしなくて良くなる)

ABC155 D. Pairs

問題

N個の整数A_iが与えられる。
このうち、2つを選んだ積の組合せをすべて考えると、これはN*(N-1)/2個できる。
小さい方からK番目の積が何になるか答えよ。

制約

  • 2 <= N <= 2*10^5
  • 1 <= K <= N*(N-1)/2
  • -10^9 <= A_i <= 10^9

解法

積を小さい方から並べた数列Bを考える。(これは実際には列挙できない)
Bのうち、「x未満の個数」が高速に求められれば、K番目の要素は、「x未満の個数がK未満」の部分を二分探索すれば求められる。

例えば、Bが「1,2,4,4」の場合、「x未満の個数」をmとすると、

x 1 2 3 4 5
m 0 1 2 2 4

のようになるので、K=3だった場合は、xが4と5のところで分かれるので3番目に来るのは「4」だとわかる。(K=4でも、K未満となる位置は同じなので、答えが「4」であることがわかる。)

したがって、Bにおける「x未満の個数」を高速に求めれば良い。


今回、A_iは0や負もあり得るため、その積はやや複雑になっている。
正だけだった場合は、A_iを小さい順からソートして、二分探索でx未満となる位置を求めて個数を計算すれば、O(N*log(N))で求められる。
しかし、今回は負もあるため、負*負や負*正の時を気をつける必要がある。

実装的には、A_iを「①0未満のもの」と「②0以上のもの」と分けて、
①*①と①*②と②*②それぞれで個数を求めて合計してあげればよい。



(①*①のときは、負*負になるため、逆順にソートして上げると順方向の二分探索ができる。
①*②のときは、負*正になるため、②側のものを逆順にソートしてあげると順方向の二分探索にできる。
②*②のときは、正*正なので、そのまま二分探索してあげれば良い。)

ABC153 F. Silver Fox vs Monster

問題

N体のモンスターが一列に並んでいる。
i番目のモンスターは、座標x_iにいて、体力がh_iである。

今、爆弾を座標xに落とすと、x-D以上x+D以下の範囲にいるモンスターにダメージAを与えることができる。
すべてのモンスターの体力を0以下にするために必要な爆弾の個数の最小値を求めよ。

制約

  • 1 <= N <= 2*10^5
  • 0 <= D <= 10^9
  • 1 <= A <= 10^9
  • 0 <= x_i <= 10^9
  • 1 <= h_i <= 10^9

解法

一番左にいるモンスターについて考えると、このモンスターを倒すためには、このモンスターを含む範囲の爆弾を倒すのに十分な回数落とす必要がある。
このモンスターの位置を左端とするような爆弾投下を十分な回数を透過したあと、次に一番左になるモンスターについても同様に考えていける。
したがって、貪欲法で、左から順番に処理していけば良い。


爆弾の投下によって、2*Dの範囲にいるモンスターに「A*投下回数」のダメージを与えることになるが、愚直にループを回すとO(N)かかってしまって間に合わない。
これは、遅延セグメント木やStarrySkyTree、imos法をしながら進めればO(logN)やO(1)で更新・取得ができる。

ABC133 F. Colorful Tree

問題

N個の頂点からなる木がある。
各辺iは、頂点a_iとb_iをつないでおり、1~N-1の整数で表される色c_iと、辺の長さd_iが割り当てられている。
このとき、以下のQ個の問いに答えよ。
「問いj: 色x_jのすべての辺の長さをy_jに変更したと仮定して、二頂点u_j, v_jの距離を求めよ」

(注意:各問いは独立で、変更は他の問いに影響しない)

制約

  • 2 <= N <= 10^5
  • 1 <= Q <= 10^5
  • 1 <= c_i <= N-1
  • 1 <= d_i <= 10^4

解法

まず、単純に2頂点間の距離を答えるだけの場合は、根付き木にして、LCAを求めて、「depth[u_j] + depth[v_j] - 2 * depth[lca(u_j, v_j)]」で求められる。

問いは、色x_jの辺の重みをy_jにするので、根付き木において、ある範囲内における色x_jの「辺の重みの合計」や「辺の数の合計」がわかれば、

答え=「(u_jとv_jの距離) - (u_jとv_jの間の色x_jの辺の重み合計) + y_j * (u_jとv_jの間の色x_jの辺の変数合計)」

で求められる。
なので、基本的に、「根付き木について、根からある頂点までの間にある色がxの辺の重みや個数」を求めることが本質的な問題になっている。


f:id:phyllo_algo:20200125122823p:plain
1を根として、根付き木を考え、辺についてのEuler Tourを作ると上記のようになる。
行きがけは重みを+、帰りがけは重みをーにして累積和を取ると、ある頂点vの根からの距離は、頂点vの根方向への辺eの重みの累積和を見ればO(1)で求められる。
(例:頂点5は、根方向への辺がe4で、それに対応するeuler tourのインデクスはi=3なので、その重みの累積和は50、とわかる)
辺の数についても同様に求められる。

ある色xについて考えると、この累積和のように、範囲内にある、色がxのものだけについて注目して累積和を求められばよいことがわかる。
f:id:phyllo_algo:20200125123315p:plain
なので、Euler Tourを各色ごとに分解して累積和を計算しなおしたものを考える。

ある頂点vについて、根方向への辺eに対応するeuler tourのインデクスがiだった場合を考えると、色がxのものだけに注目したい場合、その色だけ取り出した表の中でi以下となるインデクスを二分探索で求めてあげれば、ある色の辺だけについて重みの合計を求められる。
辺の数についても同様に求められる。

したがって、1つの問に対して、O(logN)程度で答えられるので、間に合う。

Euler Tourを使ったLCA

Euler Tourを作る際に、根からの深さを一緒に求めておく。
これを、RMQなどで、あるEuler Tourの範囲での最小の高さになっている辺(頂点)を求めてあげればよい。

ABC132 F. Small Products

問題

正の整数K個を一列に並べたもので、隣接するどの2つの整数の積もN以下であるようなものの個数を求めよ。
答えは10^9+7のあまりで求めよ。

制約

  • 1 <= N <= 10^9
  • 2 <= K <= 100

解放

計算量を無視して考えると、
dp[i][j] := i番目の整数がjだった場合の通り数
のように考えられる。
この遷移は、dp[i][j] = Σ_{1<=k<=N/j} dp[i-1][k]のようにして求めていける。

この計算量を減らすことを考える。
i番目が整数jと考えているときに、遷移のΣの「1<=k<=N/j」は、累積和を求めておけばO(1)で求められるので、O(K*N)になる。
さらに、この「N/j」に注目すると、例えばN=100に対し、j=98とj=99はどちらもN/jは1となっていることがわかる。
このように、N/jが同じになるjは遷移の右辺が同じになるので、まとめて計算することを考える。

N/jとしてありえる値は、j=1~√Nまでに対して、jとN/jを実際に出してみて、出てくる整数を考えれば良い。(setなどに入れておく)
この整数以外の、抜けてる整数は、個数がわかるので、出てくる整数のところにまとめて数え上げればよい。
したがって、全体でO(K*√N)程度で求められる。

yukicoder No.973 余興

問題

N個のシュークリームが一列に並べてあり、左からi番目のシュークリームはa_iキロカロリーである。
AさんとBさんは、Aさんから始めて交互に以下のいずれかの操作を繰り返す。

  • 左側にあるシュークリームを含む、位置が連続した1個以上のシュークリームを食べる
  • 右側にあるシュークリームを含む、位置が連続した1個以上のシュークリームを食べる

ただし、一度に食べられるシュークリームの合計カロリーはXキロカロリー以下にしなければならない。

最後にシュークリームを食べた人が負けとする場合、どちらも勝利を目的に最適行動をした場合、どちらが勝者になるか判定せよ。

制約

  • 1 <= N <= 5000
  • 1 <= X <= 10^9
  • 1 <= a_i <= X

解法

単純には、
dp[i][j] := 残っているシュークリームの左端がi番、右端がj番の時、この状態で取る人が勝てるか?
というものを考えると、dp[1][N]が答えになる。
しかし、これは、遷移がO(N)かかりうるため、全体ではO(N^3)で間に合わない。


ここで、dp表の形を考える。
f:id:phyllo_algo:20200121232440p:plain
(画像はN=5の場合)

このdp表を埋める場合の遷移は、
f:id:phyllo_algo:20200121232553p:plain
「右からいくつかシュークリームを食べる」場合は、マスの左側にあるマスで負マスがあれば、そこに遷移することで、相手に負けさせることができる。
「左からいくつかシュークリームを食べる」場合は、マスの下側にあるマスで負マスがあれば、そこに遷移することで、相手に負けさせることができる。
(遷移できる範囲はXによって決まっているので、各位置での遷移範囲はO(N^2)で前計算しておく。)


ここで、対角の赤矢印方向に順番に求めていけば、あるマスを考えるとき、左側または下側のマスはすでに計算済みとなる。
f:id:phyllo_algo:20200121232822p:plain
ここで、左側、下側に対して勝/負を1/0で表現した累積和をもつように一緒に計算していけば、O(1)で負マスがあるかどうかを判定できる。

これで全体をO(N^2)で計算できる。
また、累積和でなくてもBITなどでO(logN)で計算してもよい。

ABC152 F. Tree and Constraints

問題

N個の頂点からなる木が与えられる。この木の辺を白か黒で塗ることを考える。
M個の制約が与えられ、i番目の制約は「2つの頂点u_i, v_iのパス上の辺には黒色の辺が1つ以上存在しなければならない」となっている。

M個すべての制約を満たすような塗り方の通り数を答えよ。

制約

  • 2 <= N <= 50
  • 1 <= M <= min(20, N*(N-1)/2)

解法(辺に注目してbitDP)

各辺に注目すると、0個以上の制約に関連付いている。
辺を白に塗るか黒に塗るかで、すでに満たした条件かどうかの状態が変化していくので、これはbitDPで、
dp[i][j] := i番目までの辺で、すでに満たした場合bitが1になっているような条件の状態を表すjのときの通り数
として、dp[0][0] = 1からdp[i+1][j] += dp[i][j]かdp[i+1][j|mask] += dp[i][j](maskは辺iに関連する制約のbitマスク)で遷移させていけばよい。

解法(制約に注目して包除原理)

制約に注目すると、「制約をすべてを満たす」= U - 「制約を1つ以上満たさない集合」であり、「制約を1つ以上満たさない集合」は「各制約を満たさない集合」の和集合になっている。
したがって、この「各制約を満たさない集合の和集合」を求める。
これは、(制約1を満たさない集合) + (制約2を満たさない集合) - (制約1かつ制約2を満たさない集合)・・・のようになっており、包除原理で求められる。
また、制約を満たさない集合というのは、その制約すべてのパスの辺が白で塗られている場合なので、そのような塗り方は、白で塗る辺の数をxとして、「2^{N-1 - x}」で求められる。

うまく無駄な計算が発生しないようにしないとTLEするようなので、辺集合をbitで表現するなど無駄なループが発生しないよう気をつける。
(あと、解説放送で、途中計算がどこまで大きくなり得るか?が議論になってた)

ABC151 F. Enclose All

問題

平面上のN個の点が与えられる。
これらすべてを内部または周上に含む円の半径の最小値を求めよ。

制約

  • 2 <= N <= 50
  • 0 <= x_i, y_i <= 1000
  • 与えられる点はすべて異なる

解法

いくつかの点を選び、それが円周上にあると仮定した場合の円を求めて、他のすべての点が含まれるか?をチェックする。

まず、凸包のある2点が周上にあると考えると、その2点の中点を中心にした2点間の距離の半分が候補の円となる。

次に、凸包のある3点が周上にあると考える。
鈍角三角形の場合は、鈍角ではない2点の中点を中心した2点間の距離の半分が候補の円となるが、上記の2点のときに列挙されているはずなのに無視してよい。
鋭角三角形の場合は、その3点を含む外心や半径はwikipediaの「外接円」のエントリで求め方が載っているので、それを参考に求めれば良い。


円に含まれるかのチェック時には、誤差を考慮して比較することを忘れない。

ABC150 D. Semi Common Multiple

問題

長さNの偶数の整数からなる正数列Aと整数Mが与えられる。
任意のk(1<=k<=N)に対して、以下の条件を満たす正の整数XをAの半公倍数と定義する。

X = A_k * (p + 0.5)を満たす負でない整数pが存在する

1以上M以下の整数のうち、Aの半公倍数の個数を求めよ。

制約

  • 1 <= N <= 10^5
  • 1 <= M <= 10^9
  • 2 <= A_i <= 10^9
  • A_iは偶数

解法

Xについて考える。
0.5を1/2として整理すると、
X = (A_k/2) * (2*p+1)
と書ける。
ここで右辺を見ると、(A_k/2)は任意の自然数、(2*p+1)は1以上の奇数になっている。

Xとしてあり得るものを考えると、
Xが奇数の場合、(A_k/2)もすべて奇数である必要があり、そうならば(A_k/2)の最小公倍数の奇数倍はすべて満たせる。
Xが偶数の場合、(2*p+1)が奇数なので、(A_k/2)もすべて偶数である必要がある。しかも、偶数であるだけでなく、Xを素因数分解してでてくる2^xのxと(A_k/2)を素因数分解してでてくる2^yのyは同じである必要がある。すべての(A_k/2)の素因数分解してでてくる2^xのxが等しいならば、Xは普通に(A_k/2)の最小公倍数の奇数倍はすべて満たせる。そうでなければXは存在しない。

M以下の(A_k/2)の最小公倍数の奇数倍の個数は、(A_k/2)の最小公倍数をLとすると、(M/L+1)/2で求められる。
また、最小公倍数はかなり大きくなり得るが、M以上になった時点で答えは0になるので、そこで打ち切って桁あふれしないようにする。

ABC131 F. Must Be Rectangular!

問題

2次元座標にN個の点が与えられる。
このとき、「座標(a,b),(a,d),(c,b),(c,d)のうちちょうど3箇所に点が存在するようなa,b,c,d(a!=c, b!=d)を選んで、残りの1箇所に点を追加する」という操作を繰り返す。
この操作回数の最大値を求めよ。

制約

  • 1 <= N <= 10^5
  • 1 <= x_i, y_i <= 10^5
  • 与えられる各点に同じ位置のものはない
  • 入力はすべて整数

解法

まず、答えとなる最終的な形を考える。

1回でも操作が行えるような頂点が存在する場合、そこに頂点を追加することで、長方形ができ、追加された頂点によってまた操作ができるようになって、これを繰り返すことで、巨大な格子が作れることがわかる。

したがって、この格子の形が求められれば、その格子の頂点からすでに存在する頂点を引けば操作回数の最大値がわかる。


格子を形成できる頂点は、同じx座標、または、y座標を共有しているはずなので、ある頂点から同じx座標、または、y座標になっている頂点を辿れる頂点すべてを見つければよく、これは、dfsで探すか、x座標とy座標それぞれを頂点とみなしてUnionFindで連結成分を見つけるようにすれば求められる。

あとは、各頂点のグループに対して、最大の操作回数を求めて合計すれば良い。

ABC148 F. Playing Tag on Tree

問題

N頂点の木が与えられる。
最初、高橋くんは頂点u、青木くんは頂点vにいる。

2人は以下の手順で鬼ごっこをする。

  • 高橋くんと青木くんが同じ位置にいるなら終了。そうでないなら、高橋くんは隣接頂点のどれかに移動
  • 高橋くんと青木くんが同じ位置にいるなら終了。そうでないなら、青木くんは隣接頂点のどれかに移動
  • 上記を繰り返す

高橋くんはできるだけ長く、青木くんはできるだけ速く終了するように行動する。
高橋くんと青木くんが最適に動いた場合、ゲームが終了するまでに行動した青木くんの移動回数を答えよ。

制約

  • 2 <= N <= 10^5
  • 1 <= u, v <= N
  • u != v

解法

まず、青木くんの最初にいる頂点vをルートとして各頂点への最短移動をdfsなどで求める。

高橋くんは、各頂点へはこの青木くんの距離よりも短い距離で移動できる場合、自由に移動できる。
なので、高橋くんも同様に頂点uをルートとして各頂点への最短距離を求める。ただし、青木くんの最短距離以下の場合のみ移動できる。

青木くんの最短距離と高橋くんのその頂点への移動距離が等しい場合は、高橋くんから青木くんにぶつかりにいって終わるパターン(サンプル3)なので、答えとしてはあり得るので、それ以上の移動はないが、答えには含めて考えておく。

そうでない場合は、最後の状態に注目すると、高橋くんのターンでは、

        • [ 青木くん ] ---- [ 高橋くん ]

のような場合か

        • [ 青木くん ] ---- [ ] ---- [ 高橋くん ]

のようになっている。
どちらの場合でも、高橋くんがいる頂点の一つ前の地点で終了するので、高橋くんが移動できる範囲で、「青木くんが一番遠くに移動する距離から1引いたところ」が終了状態になるので、これを答えれば良い。

ABC148 E. Double Factorial

問題

0以上の整数nに対し、関数f(n)を以下のように定める。

  • f(n) = 1 (n<2)
  • f(n) = n*f(n-2) (n>=2)

整数Nが与えられる時、f(N)の10進数表記の末尾の0の個数を求めよ。

制約

  • 0 <= N <= 10^18

解法

偶数と奇数をそれぞれ考えてみる。

奇数は1*3*5*...と奇数の掛け算なので、答えは偶数にならず、末尾の0はない。

偶数の場合は、1*2*4*6*8*...となるが、10の倍数がいくつ作れるか?が問題になる。
例えば、10=2*5だったり、50=2*5*5のように、素因数分解してでてくる5の数が何個あるかがわかれば、他の2と掛け算して、10が何個作れるか=答えがわかる。

N以下の偶数で素因数分解して5が出てくる回数は、5が何回でてくるか?はN/5で求められる。
次に同時に5が2回出てくるケースを考えると、5^2が何回でてくるか?で、N/(5^2)で求められる。
これを5^25程度まで繰り返してすべての回数の和を求めると、5の出現回数がわかる。
これに2をかけて10にすればよいので、結局、上記の回数の和が答えになる。

ABC129 F. Takahashi's Basics in Education and Learning

問題

長さLの等差数列があり、初項はA、公差はBで与えられる。
この数列の項を順につなげてできる整数を考える。
例えば、3,7,11,15,19という数列の場合は、37111519という整数になる。
この整数をMで割ったあまりを答えよ。

制約

  • 1 <= L, A, B < 10^18
  • 2 <= M <= 10^9
  • 数列の要素はすべて10^18未満

解法

数列の桁に注目すると、ある桁dの区間では数列の値を10^d倍ずつしていったものになっていることがわかる。

数列の要素の桁がdであるような区間について考える。
要素の増え方と10^d倍ずつしていくので、後ろに要素を付け加えていくようなイメージで考えると、ある要素までの計算結果をYとして、今考えている要素がxだとしたら
(Y, x) -> (Y * 10^d + x, x + B)
で更新される。
これをN回繰り返したあとのYを考えればよく、これは行列累乗を使うと、
{( (10^d, 1, 0), (0, 1, B), (0, 0, 1) )^N} * (Y, x, 1)^T
の形で書ける。(行列累乗で数列の一般項を求めるのはよくある)

最初、(Y, x, 1) = (0, A, 1)として、桁dの区間を1,2,3,4,...と連続的に処理していけば答えが求められる。
桁がdであるような区間は二分探索などで求めれば良い。


(行列累乗時に18桁*18桁のような計算がでてしまうが__uint128_tなどを使ってオーバーフローしないようにするMが10^9程度なので、普通に掛け算する前にmodをとっておけば良い。)

三井住友信託銀行プログラミングコンテスト2019 F. Interval Running

問題

高橋くんと青木くんは、直線上を同じスタート地点から走り出す。
同じ方向に向かって、

  • 高橋くんは、T1分を分速A1メートル、次のT2分を分速A2メートル、これを交互に繰り返す
  • 青木くんは、T1分を分速B1メートル、次のT2分を分速B2メートル、これを交互に繰り返す

高橋くんと青木くんは何回で会う(同じ位置にそろう)か?
スタート地点にいるときを除いた回数を答えよ。
無限回会う場合はinfinityを返せ。

制約

  • 1 <= T1, T2 <= 10^5
  • 1 <= A1, A2, B1, B2 <= 10^10
  • A1 != B1
  • A2 != B2

解法

高橋くんの位置と青木くんの位置の2つの変数があり扱いにくいので、二人の相対距離に注目する。
T1分の間は相対速度V1=(A1-B1)で、T2分の間は相対速度V2=(A2-B2)になっている。


場合分けで、もし「V1>0かつV2>0」または「V1<0かつV2<0」だった場合は、どんどん離れていってしまうため、二度と合わないので、0回。

「V1 * T1 + V2 * T2 == 0」となる場合は、T1+T2分ごとに出会うので、無限回会う。

それ以外の場合は、縦軸に相対距離、横軸に時間をとったグラフで「横軸と交差する回数」が答えになる。

相対距離W1 = V1 * T1と相対距離W2 = V1 * T1 + V2 * T2を考えると、W2だけ毎回位置がずれていくので、W1が横軸と交わるまで減らす回数を数えればよい。
W2がW1と同じ符号の場合は、横軸と交わらないので0回。
それ以外は、交わる回数は、2*abs(W1)/abs(W2)で求められるが、割り切れる場合最後に会うのは1回になることに注意。
これに、最初の横軸と交わる1回を加えれば答えになる。