ABC165 F. LIS on Tree
問題
N頂点からなる木が与えられる。頂点iには整数a_iが書かれている。
すべての頂点について、頂点1から各頂点までの最短経路に出現する整数の列での最長増加部分列(LIS)の長さを求めよ。
制約
- 2 <= N <= 2 * 10^5
- 1 <= a_i <= 10^9
解法
数列における最長増加部分列(LIS)はdp+lower_boundで求めることができる。
(dp[i]に対して、無限大で初期化し、lower_boundでa_iを使って更新していく)
木についても同様の方法を考える。
頂点1からどこかの葉頂点までは数列として求められる。
木の場合は、その途中から頂点が分岐しているが、途中までdpテーブルが共通にしたいが保存しておくことは難しい。
テクニックとして、頂点を処理した後に前の状態に戻す(巻き戻し)、という方法が使える。
dfsで頂点1から頂点を辿る。頂点を処理するときはdpテーブルのどこかの値を1つ書き換える。しかし、書き換える前の位置と値を保存しておけば、戻るときにその値に戻せば各頂点でのdpテーブルの状態を揃えられる。
yukicoder No.1141 田グリッド
問題
H * Wのグリッドがあり、各マスには、非負整数A_ijが書かれている。
今、2個の整数(r,c)がQ個与えられるので、それぞれについて、その行rと列cを除いた部分の非負整数の積をmod 10^9+7で求めよ。
制約
- 2 <= H, W <= 10^5
- 4 <= H * W <= 10^5
- 0 <= A_ij <= 10^9
- 1 <= Q <= 5 * 10^4
- 1 <= r_i <= H
- 1 <= c_i <= W
解法
A_ijが0もあり得ることに注意。
0が1つでもある場合は、答えは0になるため、それ以外の答えになる場合というのは(r,c)ですべての0が除いている必要がある。
単純に、r行とc列の積をそれぞれ求めていて、後で割る、という求め方だと、0の配置の仕方のパターンがいくつか考えられ、実装がとても面倒になる。
効率的な方法は、求めるべき積の範囲が四隅からの長方形の形になっていることから、四隅からの累積値(累積和っぽく積を求める)をしておけば0のパターンを考えずに求められる。
yukicoder No.1140 EXPotentiaLLL!
制約
- 1 <= T <= 5 * 10^5
- 1 <= A <= 10^18
- 1 <= P <= 5 * 10^6
yukicoder No.1139 Slime Race
問題
数直線上に、スライムがN匹いて、i番目のスライムは、時刻0で、座標x_i、速さv_i(正の方向)でいる。
この数直線上で、同じ座標になる場合は、「衝突」し、以下のようになる。
- 番号が小さいスライムがその他のスライムをすべて吸収し、吸収されたスライムは消滅
- 吸収したスライムは、自分自身の速さ＋吸収したスライム速さの和、の速度になる
ここで、すべてのスライムについて、時刻0から時刻tまでに走った距離の合計をf(t)とする。吸収され消滅したスライムはその時点で走るのを終了したとみなす。
f(T) >= Dとなる最小の整数Tを求めよ。
制約
- 1 <= N <= 10^5
- 1 <= D <= 10^9
- 1 <= x_i, v_i <= 10^9
- i < jならばx_i < x_j
解法
シミュレーションや二分探索では難しい。
そこで、吸収の前後について考える。
あるスライムa,bがt_1で衝突し、t_2まで進む場合を考えると、合計移動距離は、
v_a * t_1 + v_b * t_1 + (v_a + v_b) * t_2
になる。
展開すると、v_a * (t_1 + t_2) + v_b * (t_1 + t_2)になるので、結局、吸収されないで進んだ場合と同じになることがわかる。
したがって、吸収は無視して考えてよいので、結局f(T)はT * すべてのスライムの速度の和v_sum、となり、これがD以上になるTは、切り上げの式から、
T = (D + (v_sum-1)) / v_sum
となる。
ABC172 F. Unfair Nim
問題
石の山がN個あり、i番目の山にはA_i個の石がある。
2人で「交互に、石の山を一つ選び、そこから1個以上の石を取り除く。先に取り除くことができなか唸ったほうが負け」というゲームを行う。
このゲームは、2人が最適に考動する場合、ゲーム開始時にどちらが勝つか判定できるが、ここで、1番目の山から0個以上A_1個未満の石を2番めの山に移すことができ、後手が必勝になるようにしたい。
このようなことが可能な場合、移動する石の個数の最小数を、不可能な場合は-1を出力せよ。
制約
- 2 <= N <= 300
- 1 <= A_i <= 10^12
解法1
上記のゲームはNimで、すべてのA_iのxorを取った値が0ならば後手が勝てる。
石を移した後の1番目の個数をa、2番目の個数をbとする。
Nimの条件から、A_3 xor ... xor A_N = Xとすると、条件は「a xor b xor X = 0」で、Xを右側にうつすと「a xor b = X」でないといけない。
他の条件として、問題文から、1番目から2番目にいくつ移してもその合計の石の数は変化しないので、「a + b = A_1 + A_2 = S」と書ける。
また、1番目の山からは0個以上A_1未満なので、「0 < a <= A_1」でないといけない。
よって、求めるものは、
a xor b = X
a + b = S
0 < a <= A_1
を満たす最大のa、ということになる。
一般に、和とxorは「a + b = a xor b + 2 * (a and b)」という関係式が成り立つため、この式から、「S = X + 2 * (a and b)」=>「a and b = (S - X) / 2」が成り立たないといけない。
S-Xが奇数の場合は等式が成り立たないので、不可能。
a and b = Dとしておくと、D(andの条件)とX(xorの条件)はそれぞれビット単位での条件なので、ビットごとに見れる。
各ビットについて、DとXのビットからa,bのビットの組み合わせを考えると、
(0,0) => aもbも0じゃないといけない
(0,1) => aとbは(0,1)か(1,0)が可能
(1,0) => aもbも1じゃないといけない
(1,1) => aとbの組み合わせはありえない
という条件でなければならないことがわかる。
したがって、DとXでどちらも1になっているビットがある場合は、不可能。
それ以外の場合は、DとXが(0,1)になっている場合だけa側を1にするかb側を1にするかの選択肢がある。
aは、「0 < a <= A_1」を満たす必要があるので、A_1以下になるよう最大のaをDとXのビットの条件を選びつつ求めれば良い。
まず、DとXが(1,0)の場合はaもbも1じゃないといけないことから、Dで1が立っているビットはすべてaでも1にしておく。
このときすでに「0 < a <= A_1」を満たせないならば、不可能。
そうでないならば、DとXが(0,1)のところで、A_1を超えないように1か0を選べるが、これは、上位ビットで1を選ぶのはそれより下位のビットで1を選ぶよりも大きい値にできることから、貪欲に上位ビットから「入れた場合にA_1を超えないかどうか」をチェックして、超えないなら入れていく、という方法で求めれば良い。
最終的に、aが0になってしまう場合は、不可能。そうでなければ、A_1 - aを返せば良い。
(全体の流れは、条件式を取り出す→式変形→ビットごとに見る→最大化するため上位ビットから貪欲に選ぶ)
解法2
途中までは解法1と同じで、
a xor b = X
a + b = S
0 < a <= A_1
を満たす最大のaを直接的に求めたい。
これはあるビットについて考えると、それより下位ビットで最大のものだけわかれば十分そうというものから、桁DPを考える。
条件を状態として持つように考えると、各ビットについては、そのビットと下位ビットからの繰り上がりを考える必要があるので、
dp[i][j][k] := 下からi桁目までで、繰り上がりをしているか(j=0,1)とA_1以下かどうか(k=0,1)の条件のときの、最大のa
というものが考えられる。
今、i,j,kでループを回している場合、aとbのビットの組み合わせ(4通り)を考える。
このとき、
xorを取った値がXのそのビットの値を一致しない場合はスキップ。
和(jとaとb)を取った値がSのそのビットの値を一致しない場合はスキップ。
和を取って桁上りがある場合は、次の状態はj=1に遷移、そうでなければj=0に遷移。
A_1以下かどうかは、A_1のビットと比較して、「aが1、A_1が0」ならば満たせていない、「aとA_1のビットが同じ」なら状態は継続(次の状態もkになる)、「aが0、A_1が1」ならば満たす。
とできるので、これで遷移先で最大値を保持するよう回せば良い。
最終的な答えは、dp[最大ビット][0][0]で、これが存在しない場合や0の場合は許されないので、不可能。そうでなければA_1-dp[最大ビット][0][0]を返せばよい。
ABC173 F. Intervals on Tree
問題
N頂点N-1辺からなる木が与えられる。
頂点には1からNまで番号がつけられている。
整数1 <= L <= R <= Nについて、関数f(L,R)を以下のように定める。
- Sを番号がL以上R以下の頂点からなる集合とする
- 頂点集合Sと両端がSに属する辺からなる部分グラフにおける連結成分の個数をf(L, R)とする
このとき、Σ_{L=1}^N Σ_{R=L}^N f(L, R)を求めよ。
制約
- 1 <= N <= 2*10^5
解法
ある辺eに注目すると、そのeがaとbをつないでいる場合、Lがa以下、Rがb以上の場合に含まれる。
この辺eが追加されると、上記のような(L,R)で、連結成分が1つ減ることになる。
したがって、辺がない場合での連結成分数の合計を求めて、各辺について、Lがa以下、Rがb以上の場合、a*(N+1-b)個のL,Rのペアで連結成分が-1になるの引いていけば良い。
「辺がない場合での連結成分数の合計」は、Σ_{i=1}^N (N*(N+1)/2)で求められて、これから各辺のa*(N+1-b)を引いていけばよいので、O(N)で求められる。
ARC056 C. 部門分け
問題
N人の社員をいくつかの部門に分ける。
社員iと社員jの間には、信頼度w_ijがあり、部門に分けたときのスコアを「(部門の数)*K - 異なる部門に属する2人の間の信頼度の合計」とする。
スコアが最大になるように部門分けをした場合のスコアを返せ。
制約
- 1 <= N <= 17
- 1 <= w_ij <= 10^6
- w_ii = 0
- w_ij = w_ji
- 1 <= K <= 10^6
解法
各社員をbitで表現して、すでに割り当て済みの部分を1、そうでないものを0として考える。
dp[S] := 状態がSのときのスコアの最大値
とすると、dp[S]は、部門数が1の場合か、Sの1の部分が2つに分けられたTとRの組み合わせから再帰的に求められる。
例えば、S=1100111の場合、1つの分け方としてT=10xx110とR=01xx001のようなものが考えられるが、このTとRから構成された場合のSでのスコアは、「dp[T] + dp[R] - TとR間の信頼度合計」のように求められる。
SからTとRのような部分集合は、O(3^N)で列挙できるので、「TとR間の信頼度合計」が高速に求められればよい。
「TとR間の信頼度合計」は、「Sで1になっている社員間の信頼度合計」から、「Tで1になっている社員間の合計」と「Rで1になっている社員間の合計」を引いたもので求められるので、前計算O(2^N * N^2)で用意しておけば、O(1)で計算できる。
M-SOLUTIONS プロコンオープン 2020 F. Air Safety
問題
現在、各飛行機が(X_i, Y_i)を飛行しており、x,y座標を正か負の方向に進んでいる。
すべての飛行機は秒速0.1で進んでおり、同時刻に同じ座標に来てしまうと衝突してしまう。
飛行機の中で、一番早く衝突してしまう飛行機が衝突までの何秒かを求めよ。
衝突する飛行機がない場合は、SAFEと答えよ。
制約
- 1 <= N <= 200000
- 0 <= X_i, Y_i <= 200000, X_i,Y_iは整数
- 方向U_i = U, R, D, L
- 飛行機の位置(X_i, Y_i)はすべて異なる
解法
衝突する可能性があるのは、左右からぶつかってくる場合と真正面からぶつかってくる場合が考えられる。
まず、真正面からぶつかってくる場合を考える。
x座標とy座標で、同じ座標で、UとD、LとRのペアは衝突する可能性がある。
しゃくとりのように、ソートして、小さい方からRのものより大きい一番近いLのものについて、距離がDだった場合は、D*10/2秒後に衝突する。
次に、左右からぶつかってくる場合を考える。
RのものとDのものを考えると、Rのものが(x_i, y_i)で、Dのものが(x_j, y_j)とすると、x_j-x_i=y_j-y_iの場合に衝突する。
これを移項すると、x_j-y_j = x_i-y_iなので、Dに進む(x_j, y_j)のうち、x_j-y_jがx_i-y_iと一致する飛行機だけを考えればよい。
したがって、x_i-y_iをそれぞれもとめて、一致するものについて考える。
一致するものについて、RとDの飛行機をx座標でソートすると、しゃくとりのように処理すればO(N)で一番近い衝突する飛行機がわかり、(x_j - x_i)*10秒後に衝突するのがわかる。
また、RのものとUのものを考えると、Rのものが(x_i, y_i)で、Uのものが(x_j, y_j)とすると、x_j-x_i=y_i-y_jの場合に衝突するので、移行するとx_i+y_i=x_j+y_jのものなので、上記と同様に一致するものについて考えれば良い。
さらに、LとD、LとUについて同様の処理をすればよい。
ただし、この4パターンをそれぞれ別々に処理を書くとかなり行数になってしまったり、コピペコードだと修正漏れなどわかりにくいバグを埋め込みやすくなってしまう。
これについては、各座標について、反転や回転を行うと「RとDの場合」と等価な処理にできるので、実装量を減らせる。
M-SOLUTIONS プロコンオープン 2020 E. M's Solution
問題
グリッド上に、N個の都市があり、i番目の都市は、(X_i, Y_i)に位置する。また、都市の人工はP_iで与えられる。
今、x=0とy=0に鉄道が走っており、x軸またはy軸に平行なK本の鉄道を追加で建設できる。
各都市の人々は、一番近い鉄道まで、グリッドに沿って歩くことになる。
K=0～Nについて、鉄道を最適に建設した場合の人々の歩く距離の合計の最小値を答えよ。
制約
- 1 <= N <= 15
- -10000 <= X_i, Y_i <= 10000
- 1 <= P_i <= 1000000
- 各都市の位置はすべて異なる
解法
x軸方向だけ考えてみる。
x座標について、鉄道を最適に作る場合というのは、都市のあるx座標のどれかになる。
(各人レベルに分解して考えるとΣ|A_i-x|の最小値を求めたいが、これは最適値が中央値になる)
よって、鉄道を建設するのは、各都市の座標だけ考えれば良い。
x軸とy軸方向に、N通り建設の仕方があるが、それぞれ全探索を考える。
ただし、合計はK本しか引けないので、x軸でi本建設したらy軸ではK-i本しか使えない。
また、同じ都市について、その都市については1つでも鉄道が通っていれば歩く距離は0になるので、x軸でもy軸でも鉄道を建設するのは意味はない。(他の都市を選んでたまたま鉄道が通るのは構わない)
したがって、N個の都市について、x軸に鉄道を建設、y軸に鉄道を建設、鉄道を建設しないの3通りを考える。
この列挙は、bit演算でO(3^N)でできることが知られている。
よって、各軸で鉄道を引く座標が与えられるので、各都市から見て鉄道までの最小の距離を求めればよい。
しかし、これに毎回O(N^2)かけてしまうと、TLEしてしまう。
これは、前処理で、O(2^N * N^2)で各軸について、その都市を選んだ場合のその軸での
鉄道までの最小距離、というのをN個の都市について求めてメモしておけば、O(N)で計算でき、最終的にO(N * 3^N)の計算量で求められる。
M-SOLUTIONS プロコンオープン 2020 D. Road to Millionaire
問題
N日間の株価の1株あたりの金額A_i円がわかっている。
最初、1000円の所持金から、毎日株の売買(所持金や持っている株数までで)が可能な時、最終日の所持金を最大化せよ。
制約
- 2 <= N <= 80
- 100 <= A_i <= 200
解法1
No.664 超能力者Aと株価予測 - yukicoder
を思い出した。。。
売るときと買うときは、全部売ったり全部買ったりするのが最適。
(以下、正しいかわからないけど、自分の理解のメモ)
(X株,Y円)のときにx株だけ売ることを考えると、A_iでz株だけ売って、A_jで(x-z)株を売るので、(X-x株, Y+z*A_i+(x-z)*A_j円)になる。
A_i > A_jの場合は、z=xの場合が所持金最大になり、A_i <= A_jの場合は、z=0の場合が所持金最大になる。
なので、売るときは全部売るのが最適。
X-x株だけ残した場合でも、最終日に株を残す意味はなく、どこかで売ることになるが、A_kとA_lのときに売る場合でも同様に議論できて、結局どこかでまとめて売るのが最適になる。
また、買う時は、売るときに全部売っているはずなので、0株の時を考える。
(0株,Y円)で、所持金を少し残して、X株買えるうちx株だけ買うことを考えると、A_iでz株だけ買って、A_jの時x-z株を買うので、(x株, Y - (z*A_i + (x-z)*A_j)円)になる。
上記と同様に、zはz=0かz=Xの場合が最適になるので、どこかで全力買いすればよい。
また、上記と同様に、売るときは全部売るので、X株中一部だけ売買するのではなく、全部株をどこかで買ったほうがよくなるので、全部売る、全部買う、だけを考えれば良い。
dp[i][j] := i日目で、株数がjのときの所持金の最大値
を考える。
遷移は、何もしない、全部売る、できるだけ買う、の3通りになる。
ここで、株数jがどの程度まであり得るか考える。
jは、100で買って200で売る、というのを繰り返した場合、1000円から10->20->40->80->...と2日で2倍にしていけてしまう。
したがって、株数は10 * 2^40ぐらいまでありえてしまう。
一方、遷移をもっと詳細に考えてみると、株数が0の時は、所持金があるはずで、それを全力買いするか、何もしない、の2通りが考えられる。
株数が0でない場合は、制約より所持金の残りで1株だけ追加購入する、何もしない、全部売る(株数が0になる)、の3通りになる。
ただ、1株だけ追加購入するというのは、全部売ってからその株を全部買う場合とおなじになるので、考えなくて良い。
したがって、あり得る株数は、0と、0から所持金で買える最大株数、過去の最大株数で何もしない場合の株数、程度しかなく、状態数はかなり少ない。
よって、unordered_map< ll, ll > dp[85]とかで処理してあげれば十分高速に解ける。
解法2
dp[x] := x日目での所持金の最大値
とすると、i日に買ってj日に売る、ということを考えれば良いので、O(N^2)。
ABC173 E. Multiplication 4
問題
N個の整数A_iが与えられる。
この中からK個の要素を選び、それらの積が最大になるものを答えよ。
ただし、積は10^9+7で割ったあまりで答えよ。
制約
- 1 <= K <= N <= 2*10^5
- | A_i | <= 10^9
解法
まず、負、0、正に分類し、パターンに分けて考える。
「負」の数＋「正」の数がKに足りない場合、必ず0を使わないといけなくなるため、答えは0になる。
また、K=1の場合は、「正」「0」「負」の順に一番大きい数字があるものを1つ返せば良い。
したがって、上記を除いた、
- 「負」の数＋「正」の数がK以上ある
- K >= 2
の場合を考えれば良い。
まず、Kが奇数の場合は、「正」の数を必ず1つ以上含めないといけない。
したがって、「正」で最大のものを先に入れておくことでKを偶数の場合と同様に考えることができる。
次に、Kが偶数の場合、「負」を2個いれるか、「正」を2個いれるかを考えれば良い。
「正」が1個だけ入れる場合は、必ず後で「正」のものを1個入れないとパリティが合わないので、2個入れると考えて良い。
したがって、「負」の昇順で連続する2個と「正」の降順で連続する2個を作り、その掛け算の大きさが大きい順にK/2個になるよう選べば良い。
上記でK個選べない場合は、「0」を入れて答えを0にするが、「0」がなければ「負」と「正」の整数の絶対値が小さいものからK個かけ合わせた負の値を返せばよい。
ABC013 D. 阿弥陀
問題
N本の縦棒を横に並べ、上から順にM個の横棒を同じ高さに2本以上入らないようにしてあみだくじを作成する。
i個目の横棒は、a_iとa_i + 1の縦棒を線で結んでいる。
さらに、このあみだくじを縦にD段積んだものを考える。
最終的にi番目から入った場合、何番目の縦棒から出てくるか？をN本すべてについて求めよ。
制約
- 2 <= N <= 10^5
- 0 <= M <= 2 * 10^5
- 1 <= D <= 10^9
解法1
x番目がy番目に動く、という遷移はO(M)で求められる。
1段でこの遷移になるので、2段、4段、8段、、、の場合もダブリングで求められる。
(1つ前を2回行った場合を考えれば良い。)
あとは、Dを2進表現したときビットが立っているところの遷移が行われるので、これをO(N)で求めれば良い。
全体でO(M + N log D)。
解法2
各番号をノードとして、遷移先に辺を張った有向グラフを考える。
この有向グラフは、制約から、自己ループか有向閉路を作る。
各番号は、その番号が所属する有向閉路内をD回遷移することになるので、所属する有向閉路のノード数をXとすると、D mod Xだけ動くのと変わらない。
有向閉路を配列として持っておいて、もし今見ている番号がi番目だとしたら、(i+D) mod X番目にある数字になるのでこれはO(1)で求められる。
したがって、全体でO(M + N)で求められる。
ABC163 E. Active Infants
問題
N人の幼児が一列に並んでいる。左からi番目の幼児の活発度はA_iである。
幼児たちを1回だけ任意の順番に並び替えることができ、並び替える前にx番目にいた幼児が並び替え後にy番目になった場合、その幼児のうれしさはA_i * |x-y|になる。
うれしさの合計は最大でいくつにできるか、求めよ。
制約
- 2 <= N <= 2000
- 1 <= A_i <= 10^9
解法
i番目にいる幼児のうれしさは「A_i * | i - 移動先 |」となっている。
A_iが大きい幼児から考えると、できるだけ前方か後方に移動したほうが絶対値の中が大きくなるので、そのように動かしたい。
各幼児について、できるだけ前方に配置するか、できるだけ後方に配置するか、が考えられるので、これをdpで求める。
dp[x][y] := 前方にx人、後方にy人すでに配置しているときのうれしさの最大値
とすると、(x,y)のときに前方に配置するか後方に配置するかの遷移で更新できる。
最終的にdpで最大値を答えれば良い。
ABC171 F. Strivore
問題
文字列Sが与えられる。次の操作をK回繰り返してできる文字列は何通りあるか？
- 好きな英小文字1文字を好きな位置に挿入
10^9+7で割ったあまりで答えよ。
制約
- 1 <= K <= 10^6
- 1 <= |S| <= 10^6
解法
最終的な文字列は、
「? ? ? S[0] ? ? ? S[1] ? ? ? ... S[|S|-1] ? ? ?」
のような形になっている。
ここで、重複しないように、S[i]がS[i-1]より後で最初にその文字でてくると考える。
そうすると、S[i-1]からS[i]の間にある?にはS[i]以外の25文字種しか割り当てられない。
そして、最後の文字S[|S|-1]より後ろの?には、任意の文字が割り当てられるので、26文字種が使える。
したがって、各S[i]の前後の?が何個かが決まれば、上記の文字種分選べるので、答えが求められる。
S[|S|-1]より後ろの?がx個とする。
このとき、残りのK-x個の?をS[i]の前のどれかにいれる組み合わせは、重複組合せから「{N-1+K-x}_C_{K-x}」通り、K-x個は25種から選べるので「25^{K-x}」通り、最後の?は26種から選べるので「26^x」通り、になり、これをかけ合わせたものがxのときの通り数になる。
xを0～K個のときで求めて足し合わせればよい。
ABC171 C. One Quadrillion and One Dalmatians
問題
a～zまでの文字を使って整数Nを表現する。
N=1のときa、N=26のときz、N=27のときaa、N=702のときzzのように、Nを1増やすたびに一番最後の文字が
- zでない場合はインクリメント
- zの場合は、一つ前の文字をインクリメントしてaに戻す
ようなことを繰り返して作る。
このとき、Nがどのような文字になるかを答えよ。
制約
- 1 <= N <= 10^15 + 1
解法
x進数のように見えるが、微妙に異なる。
例として、a=0,z=25として26進数を考えると、zの次が1*26 + 0でbaのようになってしまいうまく表現できない。
また、0を別に考えたa=1,z=26として27進数を考えると、zの次が1*27 + 0でa0のようになってしまうため、0の付近でうまく表現できない。
気づくべきこととして、答えの文字長がMというのがわかった場合、そこの中では26進数になっている。
この場合、番号が何番から始まっているか？がわかれば、それを引いた整数が26進数で表現するとどうなるか？から復元すれば良い。
番号が何番から始まっているか？は、
M=1の場合、1
M=2の場合、1 + 26
M=3の場合、1 + 26 + 26^2
...
のように規則的に増えていくので、実際に増やしてみて該当する数字を求めておく。
