足跡-sokuseki-

りかの日進月歩の記録

Codeforces Round 498(Div.3) E. Military Problem

Problem - E - Codeforces

問題概要

 N 頂点の根付き木が与えられる。根は1である。
ある頂点が命令を与えられると、自分の子のうちまだ命令が与えられていない1つの頂点(複数あれば頂点番号が最も小さい頂点)に命令を与える。命令が葉まで伝搬すると、自分の子のうちまだ命令が与えられていない1つの頂点(複数あれば頂点番号が最も小さい頂点)に命令を与えることを繰り返す。

 q 個のクエリが与えられる。 i 番目のクエリでは頂点  u_i に命令を与えた時に k_i 番目に命令が伝えられる頂点を答える。

制約

 1 \le N, q \le 2 \times 10^5

解法

事前に頂点0からDFSをして、命令が伝わる順番を計算しておく。このとき、ある頂点に命令が伝わる順番を記録しておくことによって、各クエリに O(1) で答えることができる。
全体の計算量は  O(q)

Submission #40441251 - Codeforces

Codeforces Round 498(Div.3) D. Two Strings Swaps

Problem - D - Codeforces

問題概要

長さ  N の2つの文字列a,bが与えられる。文字列はともに小文字のアルファベットから構成される。
はじめに、好きな回数だけ以下の置換操作を行うことができる。

  •  1 \le i \le N となる  i を一つ選び、  a_i を任意のアルファベットに置換する

その後、以下の3つの操作を繰り返して文字列a,bを等しくしたい。

  •  1 \le i \le N となる  i を一つ選び、  a_i  b_iを入れ替える
  •  1 \le i \le N となる  i を一つ選び、  a_i  a_{n-i+1}を入れ替える
  •  1 \le i \le N となる  i を一つ選び、  b_i  b_{n-i+1}を入れ替える

最初の置換操作の回数の最小値を求めよ。

制約

 1 \le N \le 10^5

解法

  •  1 \le i \le N となる  i を一つ選び、  a_i  b_iを入れ替える
  •  1 \le i \le N となる  i を一つ選び、  a_i  a_{n-i+1}を入れ替える
  •  1 \le i \le N となる  i を一つ選び、  b_i  b_{n-i+1}を入れ替える

の3つの操作をすることによって、{ a_i ,  a_{n-i+1},  b_i ,  b_{n-i+1} }を自由に入れ替えることができる。
また、  i \neq j のとき、{ a_i ,  a_{n-i+1},  b_i ,  b_{n-i+1} }と{ a_j ,  a_{n-j+1},  b_j ,  b_{n-j+1} }は独立している。
よって、 1 \le i \le \frac{N}{2} について置換操作の回数を計算して足し合わせればよい。

{ a_i ,  a_{n-i+1},  b_i ,  b_{n-i+1} }の4つの文字が全て等しければ置換操作はしなくてよい。
また、{ a_i ,  a_{n-i+1},  b_i ,  b_{n-i+1} }に2つの等しい文字が含まれているときも置換操作はしなくてよい。

そうでないとき、 a_i  a_{n-i+1} の片方だけを置換すればいいか、両方とも置換する必要があるかを調べればよい。

[追記:解法が一部間違っていたので訂正しました]

Codeforces

Codeforces Round 498(Div.3) C. Three Parts of the Array

Problem - C - Codeforces

問題概要

長さ  N の数列dが与えられる。
この数列dをA,B,Cの3つの連続する区間に分割する。(長さ0の区間が存在しても良い)

Aの長さをa、Aの要素の総和をsum1とする。
同様に、Bの長さをb、Bの要素の総和をsum2、Cの長さをc、Cの要素の総和をsum3とする。
なお、長さ0の区間の要素の総和は0とする。

sum1=sum3であるときのsum1の最大値を求めよ。

制約

 1 \le N \le 2 \times 10^5
 1 \le d_i \le 10^9

解法

数列dの前からと後ろから累積和を取っておく。
sum3を大きい方から決め打ちして、sum3と等しくなるようなsum1があるか二分探索で求める。あればそれを出力して終了する。
計算量はO(N log N)


Submission #40442600 - Codeforces

Codeforces Round 498(Div.3) B. Polycarp's Practice

Problem - B - Codeforces

問題概要

長さ  N の数列Aを  k 個の連続した区間に分割する。
分割後の各区間の最大値の合計を最大化せよ。

解法

数列Aの要素の大きい方から  K 個が、それぞれの区間の最大値となった時が答えである。
よって、そうなるように分割すれば良い。


Submission #40421573 - Codeforces

Codeforces Round 498(Div.3) A Adjacent Replacements

Problem - A - Codeforces

問題概要

長さ  N の数列Aが与えられる。
次の操作を順番に行う。

  • 数列Aに出現する 1を全て 2に置き換える
  • 数列Aに出現する 2を全て 1に置き換える
  • 数列Aに出現する 3を全て 4に置き換える
  • 数列Aに出現する 4を全て 3に置き換える
  • 数列Aに出現する 5を全て 6に置き換える
  • 数列Aに出現する 6を全て 5に置き換える
  • 数列Aに出現する 10^9-1を全て 10^9に置き換える
  • 数列Aに出現する 10^9を全て 10^9-1に置き換える

すべての操作が終わった後の数列Aを答えよ。

解法

 a_i が奇数だった場合,  a_i + 1 になった直後の操作で a_iに戻る。
 a_i が偶数の場合は  a_i -1 になった後は何も変化しない。
よって,  a_i が偶数の場合のみ1を引く。

Submission #40417806 - Codeforces

AGC019 C Fountain Walk

C - Fountain Walk

問題概要

東西方向と南北方向にそれぞれ 10^8本の道路があり、となりあう道路間の距離は  100 メートルである。すべての東西方向の道路はすべての南北方向の道路と直交し、すべての交差点は、交差する南北方向の通りの番号を  x 、東西方向の通りの番号を  y として組 ( x ,  y ) で表される。

 N 個の噴水があり、 i 番目の噴水は交差点( X_i,  Y_i)に設置されている。
噴水がある交差点には、交差点を中心とした半径  10 メートルの円が噴水の外周として描かれており、その内部に道路はない。

交差点( x_1 ,  y_1 )から交差点( x_2 ,  y_2 )に移動するのに歩く最短距離を求めよ。

制約

 1 \le N \le 200,000
 0 \le x_1, y_1, x_2, y_2 \le 10^8
 0 \le X_i, Y_i \le 10^8
 i \neq j のとき  X_i \neq X_j
 i \neq j のとき  Y_i \neq Y_j
交差点( x_1 ,  y_1 ) , ( x_2 ,  y_2 ) は異なり、どちらも噴水は設置されていない

解法

交差点で曲がるときは、噴水のある交差点で曲がる方が歩く距離は短くすむ。
交差点で曲がらない場合は噴水がない方が距離は短くすむ。

よって、( x_1 ,  y_1 ) から ( x_2 ,  y_2 )に向かうときに、できるだけ噴水のある交差点を通りながら曲がりたい気持ちになる。
このとき、経由する噴水の数を最大化すると最短距離となるので、噴水の最大の数を求めたい。

簡単のため、( x_1 ,  y_1 ) が左下、 ( x_2 ,  y_2 )が右上にあるとすると、右方向と上方向の移動だけ考えればよい。
よって最短距離に関係のある噴水は、( x_1 ,  y_1 ) を左下、 ( x_2 ,  y_2 )を右上とする長方形領域に含まれる噴水のみである。

長方形の左下から右上に移動する際に経由できる噴水に最大数は、噴水の座標の集合をx座標でソートして、y座標でLISを求めてあげるとよい。(制約よりx座標やy座標が等しくなる噴水は存在しないので、特別な処理はいらない)
よって、噴水がない場合の( x_1 ,  y_1 ) から ( x_2 ,  y_2 ) への最短距離から、LIS の数だけ噴水を経由する距離を引いてあげ得ると答えがでる。( x_1 = x_2 または  y_1 = y_2 で、長方形領域(実際は直線)に噴水が含まれる場合に注意する)

LISを求めるのは  O(N log N) でできるので、全体の計算量は  O(N log N) となる。



Submission #2866777 - AtCoder Grand Contest 019

AGC026 B rng_10s

問題概要

はじめジュースの在庫が  A 本ある。
毎日  B 本購入され、購入後  C 本以下になると夜に  D 本補充する。
永遠にジュースを  B 本購入され続けるか。
クエリは  T 個。

制約

 T \le 300
 1 \le A, B, C, D \le 10^{18}

解法

まず、  A < B の場合は、初日に  B 本購入できないので、必ず No になる。
また、そうでなくても、  D < B の場合は、補充数が購入数に追いつかないのでいつか  B 本購入できなくなるので、 No になる。
逆に、上の2つを満たさない場合で  C \geq B-1 の場合、常に補充が間に合うので永遠に  B 本購入でき、 Yes となる。

この3つの場合を除くと、残りは  A \geq B かつ  D \geq B かつ  C < B-1 の場合である。

このときジュースを  B 本買えなくなるのは、前日購入後にジュースが  C 本より多くて補充されずに、かつ当日  B 本未満だったときのみである。( D < B より補充されていないことがわかる)
つまり、ジュースの残数が  C+1 以上  B-1 以下になってしまうと No となる。

 y 日後までに  x 回補充されたときにジュースの残数が  C+1 以上  B-1 以下になったとすると
 C+1 \le  A + Dx - By  \le B-1
が成り立つ。 mod  B をとると
 C+1 \le A + Dx \le B-1
となる。
式変形すると、 mod  B において、 Dx が [  C+1-A ,  B-1-A ]の範囲に含まれると No である。
mod  B において  Dx のとる値は gcd( B ,  D ) の倍数なので、mod  B において、gcd( B ,  D )が [  C+1-A ,  B-1-A ]の範囲に含まれると No であると言える。


mod  B において、
 l := C+1-A
 r := B-1-A
とおくと、

 l \le r のとき、

  •  l を gcd( B ,  D ) で割った商と  r を gcd( B ,  D ) で割った商が異なる
  •  l が gcd( B ,  D ) で割り切れる

のどちらかを満たす場合のみ、 gcd( B ,  D )が [  l ,  r ]の範囲に含まれる。

 l > r のとき、[  l ,  r ]の範囲は [ (C+1)-A + Bk ,  (B-1)-A + B(k+1) ]の区間の集合となっていて、これは B(k+1) を含むので、かならずgcd( B ,  D )が [  l ,  r ]の範囲に含まれる。


各クエリごとの計算量は O(1) なので、全体の計算量は O(T)

Submission #2864673 - AtCoder Grand Contest 026