phyllo’s algorithm note

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

このブログについて

注意

このブログは、競技プログラミングの問題を解いたログを残しているもので、間違っていたり、証明しているとは限らないものが記載されている可能性があります。

記述された情報を利用して発生した問題については、一切責任を負えませんので、自己責任でお願いします。

RECRUIT 日本橋ハーフマラソン 2022夏(AtCoder Heuristic Contest 013) 参加記

概要

RECRUIT 日本橋ハーフマラソン 2022夏(AHC013)の参加記です。

atcoder.jp

結果は、16位とよかったですが、結構迷走してました。

問題

サーバルームがグリッドで与えられる。
各マスはサーバか空きマスで、サーバはK種類がそれぞれ100台ずつ存在する。
今、サーバの移動を何回か行ったあと、サーバ間を接続する、という操作を行って、できるだけ同種のサーバで大きなクラスタを作りたい。
操作を100K回まで行えるとき、クラスタで決まるスコアを最大化せよ。

2 <= K <= 5
NはKによって範囲が決まる(疎〜密)

最終的に提出したアプローチ

  • 盤面を状態に持つ焼きなまし+不純物除去&遠くのサーバを持ってくるルールベースの処理
  • 評価関数は、スコア関数そのまま。差分更新。
  • 近傍は、以下を適当にKごとに割合を変えて遷移
    • サーバ間を接続する&さらにそのクラスタから別の接続を試みる
    • サーバ間の接続を切る、切ったあとにさらに片方のクラスタから別の接続を試みる(繋ぎ変え)
    • ランダムにクラスタを選んで接続をすべて切る
    • (まだ初期位置ならば)4近傍のいずれかにできるだけ接続を保って動かす
    • すでに初期位置から動いていたら、初期位置に戻すか、他の4近傍に"できるだけ接続を保って"動かす
  • 焼きなましの結果で、小さなクラスタができていた場合、それらの接続を解除して、ルールベースで、不純物除去&遠くのサーバを持ってくることで改善
  • あと細かい高速化で若干イテレーション回数を増やした

時系列振り返り

思ったより迷走していたので、提出やメモ書きを元に、振り返り(垂れ流し)。

1日目

  • 問題を読む
  • seed=0、これはスライドパズルっぽいし、BeamSearchが有効そう?
  • 直前にAHC011の復習にn-puzzleソルバーをBeamSearchで書いていたので、ソルバーをちょっといじって動かしてみる
  • 調整、高速化がしんどそうなので保留
  • とりあえず、問題特有の性質やらスコアなどを考える
  • 多少異種が混ざっても大きなクラスタを作るのが良さそう
  • 操作列だけど、比較的普通の探索っぽい
  • 状態も、ある良い状態の近くに良い状態がある感じになってそうなので、そんなに探索空間もガタガタしていなそう
    • 普通にBeamSearchや山登り/焼きなまし系でいけそうか?
  • 「移動の最適化」と「接続の最適化」がある
  • 移動が決まったら、盤面に対してスコアが最大になるクラスタをフローとかで求められないか?
  • 異種がからんでくると難しそうだし、異種を無視すると全然作れなそう、、、
  • 疎なときはどかしてつなぐとかはできそうだけど、密はスライドパズルしないといけなそう
  • 想定解は、疎なとき焼きなまし、密なときBeamSearchとかだろうか
  • クラスタは木でよさそうだけど、木だと接続の仕方次第でカバーしきれないケースもありえる?
    • 木じゃなくて領域でもって、あとで木にするとか
  • というか、移動に文脈があるのに、焼きなましできるのか?
  • クラスタの接続/切断で差分更新できるか考える→できそう。クラスタの種類ごとの個数がわかればO(K)で求められる
  • 移動操作をどうするか?
  • とりあえず、greedyに復元できるか毎回試してOKな移動だけにすれば(遅いけど)できそう
  • または「1手だけ動かす」でも壊れなそう
  • 探索空間を狭めてしまうけど、良い解があるなら全然ありっぽい

2日目

  • いろいろ考察
  • 疎なとき向けに1手制約の盤面を状態に持つ自明な焼きなましを書く&調整→提出182k
  • うーん
  • 悪くはないけど、ここのまま進めてよさそうか判断し難い

3日目

  • RiJを見ながら焼きなましを改善
  • 遅いけど毎回チェックする方式で2手以上動かすようにしてみたけど、あんまり改善してなさそう
  • 特定の向きに同種のサーバがあったら他のサーバを押しのけてでもつなぎに行ったほうが良いかも
  • 近傍を追加→183k
  • ビジュアライザを見ると、接続の仕方次第では繋げられるサーバがある
  • 接続の繋ぎ変え近傍を追加→213k
  • パラメータを調整→231k
  • いい感じ、、、?
  • seed=0(K=2で密)の改善を考える
  • スライドパズル的に分離してつなぐ、ができればいいけど、移動の余裕もないので、理論値は無理そう
  • 密すぎて異種を混ぜずに最大取りに行くのも厳しい
  • うーん

4日目

  • 焼きなましをもうちょっと詰めたい
  • Kが大きいと移動に使える回数の割合が増えるので、Kでパラメータを変更→提出232k
  • コードを読み返す、バグ発見
  • バグ修正→289k
  • 結構上がった!
  • パラメータを調整→291k
  • これはいけるか?
  • 公式ビジュアライザは元の位置がどこから移動したのかわかりにくいので、ビジュアライザを作ることに
  • 何で作ろうか考えたけど、結局1枚絵でよいので、適当にgnuplotで出力
  • ビジュアライザをじっと睨む
  • とりあえずバグってるのを発見
  • いろんなケースを見ると、ルールベースでできそうな改善点が見つかる
    • 異種サーバを取り除けそう(どかす+もってくる+接続)
    • ちょっと離れたサーバを持ってきてつなげるのもできそう(もってくる+接続)
  • 手で計算してみると、数百点ぐらいは普通にあげられそう

5日目

  • とりあえずバグ修正→298k
  • 300kまであと少し!
  • あ、時間のばせば300kのるか?
  • 2.9秒を2.95秒に変更(せこい)→300k
  • やったー
  • ルールベースの実装をどうするか考える
  • 面倒になって適当に書き始める(後に後悔)
  • バグりまくる、再実装しまくる
  • つらい(後悔)
  • がんばって不純物を取り除くルールだけ書いた→304k
  • 微妙、、、
  • とりあえず、ビジュアライザを眺める
  • 1番大きなクラスタがどういう形になるか次第で、2番目以降のクラスタが大きくなれないケースが結構ある
    • 同じseedでもスコアがかなりブレる
  • 大雑把に、どの種類が最大のクラスタかで、K個ぐらいの大きな山があって、どれを登るかは現状だとランダムに選んでしまっている
  • いろいろ試す
  • あんまりうまく行かない
  • 一旦整理→310k
  • 山間を行ったり来たりできる巨大近傍を検討するのが良さそうか、非自明な焼きなましを考えるべきか、そもそも焼きなまし以外か、、、
  • 頭を一旦リセットするためABCにunrated参加
  • 黃パフォでた、、、なぜunratedに、、、

6日目

  • 一旦、後回しにしていた離れたサーバーを持ってくる処理を実装→311k
  • ここもいろいろ最適化の余地がありそうだけど、伸び幅はそんなになさそう
  • それよりも焼きなましの改善のほうが効きそうか
  • 巨大近傍を考える
  • 特定クラスタの全接続削除をして、他のクラスタを大きくするような近傍をやりたい
  • ランダムに他のサーバをつないでみたり、ミニ山登り/焼きなまししてみたり、評価関数を変えてみたり、、、
  • 同程度のサイズの別のクラスタを作るのが結構しんどい
  • あまり重い処理になってしまうと近傍としてはうれしくない
  • 全接続削除近傍だけでも少し伸びてたので一旦提出→315k
  • いろいろ試す
  • うまく行かず
  • 考えながら、バグ修正やパラメータ修正など→327k

7日目

  • バグ修正、パラメータ修正など→331k
  • うーん
  • いろいろ手がついていないところが多い、、、
  • 現状の焼きなましは、一番大きくなれる山を選べるようにするか、巨大近傍がないと厳しい
  • 密なケースも手がついていない。やはりBeamSearch(移動制限なし)のほうが良さそうか?
  • BeamSearchを再度書いてみる
  • 工夫しても実行時間が厳しい、焼きなまし解に勝てない、、、
  • 残り時間もないし、焼きなましに絞る
  • 良さげな巨大近傍が作れない、非自明な焼きなましも今から大きく変えるのも結構厳しい
  • 思いつく近傍を入れていく
  • 近傍を追加、高速化→346k
  • ここらへんが限界か

最終日

  • 微修正→348k
  • なにもわからん
  • ぼすけて
  • 手元で試していた2000ケース、seed=1〜2000を使ってしまっていて、システムテストでは(N,K)を20個ずつなので、揃っていないことに気づく
  • しまった、、、
  • データを見てもそんなに偏ってなさそうで、データを作り直してみるがそんなに変わらなそうで一安心
  • 1ページ目に入れてるけど、いろいろできていないところも多いし、近くの順位の人もバンバン伸ばしてて、1位のスコアを考えると普通に抜かされそう
  • 最終日なので、さらに未提出だった強い人が上がってくると思うので、あとはどこまで耐えられるか、、、
  • ・・・
  • あれ、思ったより耐えてそう?
  • 実行時間を伸ばすとスコアが上がるので、やってなかった高速化だけやって終わろう
  • 高速化→351k
  • ぎり350kこえれたやったー
  • 終了('A`)
  • 順位はよかったけど、結局焼きなまし1本になってしまったし、巨大近傍は入れられなかった、、、
  • 感想戦
  • 山を高速で登るのを繰り返せればよかったのか、、、
  • 焼きなましも全然まだ考える余地があった、、、
  • 復習して、考察の手数を増やして次回以降に活かしたい

AGC040 B. Two Contests

問題

1から10^9まで番号がふられた10^9人が参加する大会があり、この大会では2回コンテストが行われる。
コンテストでは1からNまで番号がついたN問の問題が準備されており、問題iが出題された場合は、L_iからR_iまでの番号の人が正解し、それ以外の人は不正解することがわかっている。
コンテストは1問以上が出題され、問題はN問すべて2回のコンテストのいずれかで出題されなければいけない。
各コンテストで全問正解した人の数の和を最大化したいとき、その最大値を求めよ。

制約

  • 2 <= N <= 10^5
  • 1 <= L_i <= R_i <= 10^9

解法

まず、コンテストに1つの問題がアサインされていたとき、別の問題がアサインされると、元の問題の正解人数以下にしかなりえない。
したがって、まず、「どれか1つの問題」と「それ以外」でコンテストを開く場合を考えてみる。

一番R_iが左側にくるもの(同じ場合はL_iが一番左に来るもの)をlhs、一番L_iが右側に来るもの(同じ場合はR_iが一番右に来るもの)をrhsとする。(lhsとrhsは別の問題になるようにしておく)
すると、lhsかrhsを1問として選んだ場合は、それ以外のものからすぐに求められる。
lhsとrhs以外の問題の場合は、lhsとrhsが必ず含まれるので、lhsとrhsの共通部分が答えになる。(lhsとrhsはそのような選び方をしているので)

ここで、コンテストにrhsをアサインして、他の問題もいくつかアサインすることを考える。
lhsとrhsを除いた問題集合に対して、rhsと共通部分が多い順に問題をソートすると、rhsを含むコンテストの全問正解人数がソートしたものの順番に決めていける。
rhs側に入れなかった問題はlhsを含むコンテスト側に入るが、こちらも簡単にもとめておける。
(rhs側で共通部分の大きさが同じ問題のときは、lhs側に共通部分が大きくなるよう、lhs側の共通部分の多い順にセカンダリソートしておく)

最終的に、「どれか1つ選ぶ&それ以外」のパターンと、「lhsとrhsをそれぞれコンテストにわけ、それぞれにいくつか問題をアサイン」のパターンを求めて、大きい方を返せば良い。

AGC049 A. Erasing Vertices

問題

1からNまで番号のついたN頂点からなる有向グラフが与えられる。
以下の操作をグラフが空になるまで繰り返すとき、操作回数の期待値を求めよ。

  • まだ削除されていない頂点を一様ランダムに1つ選び、その頂点および、その頂点から到達可能な頂点をすべて削除する

制約

  • 1 <= N <= 100

解法

期待値の線形性から、「Σ (頂点vを選ぶ確率) * 操作回数1回」が答えになる。
「頂点vを選ぶ確率」は、頂点vに到達可能な頂点集合(vを含む)をS(v)とすると、その集合において最初に頂点vが選ばれなければならないので、1/|S(v)|の確率になる。

したがって、S(v)をワーシャルフロイドなどで求めておき、各頂点vの1/|S(v)|の和を求めれば良い。

解法2

(↑の解法は厳しいので、別のアプローチから)
https://twitter.com/homesentinel_/status/1327644375128571905


頂点の選び方は、(削除されていても選ぶと考えると、N!通りある。
サンプル1は、N=3なので、
①23
①32
②①3
②3①
③①2
③2①
の順番が考えられる。(3!=6通り)
このうち、頂点を選ぶのは、丸になっているところで、各頂点vについて、丸になっているところを数え上げることを考える。

「その頂点を選んだら頂点vが消えてしまうような頂点の集合S(v)」を考えると、N個のうち、|S(v)|個を選んで、その中では、頂点vが最初に選ばれ、かつ、残りの|S(v)|-1個はどんな並びでも良い。
また、選んでないN-|S(v)|個もどんな並びでも良い。
したがって、Comb(N, |S(v)|) * (|S(v)|-1)! * (N-|S(v)|)!個が頂点vが丸になっている個数になる。

求めたいのは、( Σ(↑の式) ) / N!なので、1/N!をΣの中に入れて、Σ (↑の式)/N!と考えると、
Σ Comb(N, |S(v)|) * (|S(v)|-1)! * (N-|S(v)|)! / N!
= Σ N! / (|S(v)|! * (N-|S(v)|)!) * (|S(v)|-1)! * (N-|S(v)|)! / N!
= Σ (|S(v)|-1)! / |S(v)|!
= Σ 1 / |S(v)|
となる。
したがって、各頂点についてS(v)を求めれば答えが求められる。

ABC031 D. 語呂合わせ

問題

数字列v_iと文字列w_iがNペア与えられる。
数字列v_iの各数字(1文字)は、1からKまでの数字で、それに3文字以下の文字列が割り当てられている。
w_iは、v_iの各数字を割り当てられた文字列にして順番に連結したものになっている。

v_iとw_iから、元の数字と文字列の割当を復元せよ。
複数ある可能性がある場合はどれか一つを出力せよ。

制約

  • 1 <= K <= 9
  • 1 <= N <= 50
  • 1 <= |v_i| <= 9
  • 1 <= |w_i| <= 27

解法

各数字に割り当てられた文字列の長さを決め打つと、w_iから一意に文字列が決められる。
(決まらない場合はその長さの解はなし)

3文字以下のため、3^K通りの組み合わせがあり、それでチェックして条件を満たすものをチェックすれば良い。

ARC107 D. Number of Multisets

問題

正整数N, Kが与えられる。
以下の条件を全て満たす有理数の多重集合は何種類存在するか、mod 998244353で求めよ。

  • 多重集合の要素数はNで、要素の総和はK
  • 多重集合の要素はすべて、1,1/2,1/4,1/8, ... すわなち、1/2^iのいずれか

制約

  • 1 <= K <= N <= 3000

解法

最初にN個の要素に1がK個分埋まった状態「1 1 1 1 ... 1 x x x x ... x」からスタートして、何回か今ある要素を1/2倍した2つに分解する操作をしてN個分埋めたときの状態数を考える。
ただし、重複しないように、1, 1/2, 1/4, ...の順に大きい値から分解していく。

まず、O(N * K^2)を考える。
1から考えると、1がK個あり、このうちk個(k=1~K)を分解し、残りのK-k個を確定させると考える。
すると、これは、N-(K-k)個の要素で2*k個の1/2が埋まった状態を考えるのと同じになるので再帰的に求められる。
したがって、
calc(K,N) := N個の要素のうち、K個が最初に埋まっている場合、上記の操作をしてできる最終的な状態数
とすると、
calc(K,N) = Σ_{k=1}^{k=K} calc(2*k, N-(K-k))
と書ける。
しかし、O(K)かけてしまっているため間に合わない。


ここで別の再帰構造を考えると、「0個確定させる場合(全部分解する場合)」と「(一番値の大きい)1つだけ確定させる場合」だけで考えられる。
0個確定させる場合=全部分解する場合は、k=Kの場合で、calc(2*K,N)になる。
1つだけ確定させる場合は、N-1個の要素でK-1個分埋まった状態calc(N-1,K-1)になり、1つ小さい問題になる。
したがって、各calc(K,N)でO(1)になるので、メモ化再帰等でO(NK)で求められる。

ABC150 F. Xor Shift

問題

非負整数からなる長さNの数列a_iとb_iが与えられる。
今、0 <= k < Nを満たす整数kと、0以上の整数xを決めて、新しく長さNの数列a'_iを
「a'_i = a_{(i+k) mod N} xor x」
のように定める。

a'がbと等しくなるような(k, x)のペアを全て求めよ。

制約

  • 1 <= N <= 2*10^5
  • 0 <= a_i, b_i < 2^30

解法

まず、条件をできるだけ数式で考える。
a'はaをkだけローテートしたものとxのxorしたものになっている。
ここで、前者の「aをkだけローテートした数列をs」とする。
条件は「s_i xor x = b_i」なので、「s_i xor b_i = x」であり「s_iとb_iのxorが一定(=x)」ということになる。
s_jとb_jについても同じなので、「s_i xor b_i = s_j xor b_j」が0 <= i,j < Nで成り立つ。
式を変形すると、「s_i xor s_j = b_i xor b_j」で、j=i+1でも同じなので、結局、「xは考えなくてよく、数列sの隣り合う要素のxorからなる数列s'と、数列bの隣り合う要素のxorからなる数列b'が一致すればよい」ということになる。

数列sは数列aをローテートしただけなので、結局、数列aの隣り合う要素のxorからなる数列を求めておいて、それを2つ並べたところから数列b'と一致する部分を求める問題になる。

これは文字列検索の文脈のZAlgorithmやKMPで求められる。
ZAlgorithmでO(N)で求められる。

ARC106 D. Powers

問題

長さNの整数列A_iと、整数Kが与えられる。
1 <= X <= Kを満たす整数Xそれぞれについて、
(Σ_{L=1}^{N-1} Σ_{R=L+1}^{N} (A_L + A_R)^X ) mod 998244353
を求めよ。

制約

  • 2 <= N <= 2 * 10^5
  • 1 <= K <= 300
  • 1 <= A_i <= 10^8

解法

Σ_{L=1}^{N-1} Σ_{R=L+1}^{N}という形は、行列で考えるところの、対角を除く上三角部分の部分に相当する。
これは、対称性から、「(行列全体 - 対角部分) / 2」で求められる。
したがって、行列全体「Σ_{L=1}^{N} Σ_{R=1}^{N} (A_L + A_R)^X」と対角部分「Σ_{L=1}^{N} (A_L + A_L)^X」が求められばよい。
対角部分は2^X *A_L^Xなので、前計算で求めておける。

次に、「(A_L + A_R)^X」という形に注目する。
これは、「(x+y)^n」の形なので、二項定理より
Σ_{k=0}^{X} Comb(X,k) * A_L^{X-k} * A_R^{k}
と書くことができる。

「行列全体」の式に入れると、kはL,Rと独立でΣの一番外側に持っていけるので、
Σ_{k=0}^{X} Comb(X,k) Σ_{L=1}^{N} Σ_{R=1}^{N} ( A_L^{X-k} * A_R^{k} )
という形になる。

LとRの部分は、「ΣΣx_i*y_j」の形になっており、これは「(Σx_i) * (Σy_j)」となるため、結局、「ΣA_i^k」の値を前計算で求めておけば、高速に求められる。

前計算はO(NK)、各Xでの計算にO(X)程度なので全体でO(K^2)程度になる。

ARC104 C. Fair Elevator

問題

下の階から1~2Nの番号がついた2N階の建物がある。
1階から2N階まで1度だけ動いて、その際、N人の人が乗り降りをした情報と、各階で乗り降りした人は1人のみであることがわかっている。
人iはA_iで乗りB_iで降りたことが記録されており、以下のような条件を満たしていた。

  • 人iがエレベータに乗っているとき、他の人が乗り降りした回数をC_iとする
  • 人iと人jが同時にエレベータに乗っていた瞬間が存在する場合は、C_i = C_jを満たす

ところで、記録(A_i, B_i)の一部は消えてしまっており、消えた情報は-1で表されている。
また、記録が誤っている可能性もある。
残っている記録に矛盾がないような乗降の組み合わせがあるか?

制約

  • 1 <= N <= 100
  • A_i, B_iは-1または1~2Nの整数

解法

まず、明らかに条件を満たさないケースを除く。
「各階で乗り降りが1人のみ」で、N人が2N階で乗り降りしたので、誰も乗り降りしなかった階はないことがわかる。
なので、A_i, B_iが-1ではないのに重複がある場合は、条件を満たせない。
また、A_i, B_iが-1でないときA_i > B_iもおかしいので、条件を満たせない。
以降、上記以外の場合を考える。


C_iの条件を考えると、偶数長の区間[l,r)において、m=(r-l)/2とすると、
・lからl+m
・l+1からl+m+1
・・・・
・l+m-1からl+2m-1
の対応関係になっていないといけない。(隙間なく順番に乗って降りている状況)
このような対応関係がいくつか組み合わさって全部の階について満たしているかを確認すれば良い。

区間dpで考えると、
dp[l][r] := 区間[l,r)で条件を満たすような対応関係があるか否か
とすると、メモ化再帰で、区間[l,r)についてdp[l][r]を求める関数をsolve(l, r)として、
・l~rの間の地点iを区切りに[l,i)と[i,r)の区間がそれぞれ対応関係がある場合はそれを連結して[l,r)でも対応関係がある、とできる
・上記がない場合、[l,r)で対応関係があるかを確認する
とできる。

「[l,r)で対応関係があるか」を考える。
上で書いたC_iの条件から対応関係が決まるので、そのようなものが実際に作れるかをチェックする。
x(=l~l+m-1)からy(=l+m~l+2m-1)という場合を考えると、
・xから乗ってきた人がいて、yで降りた人がいる場合
 ・同じ人でなければダメ
・xから乗ってきた人がいて、yで降りた人はわからない場合
 ・乗ってきた人の降りた階が-1でないとダメ
・xで乗ってきた人がわからなく、yで降りた人がいる場合
 ・降りた人の乗った階が-1でないとダメ
・xで乗ってきた人も、yで降りた人もわからない場合
 ・(特にダメな条件はなし。(-1,-1)の人を割り当てればよい)
でダメな条件がある場合は、ダメで、そうでなければ対応関係が作れる。

最終的にdp[0][2*N]が答えになる。

解法2

dp[i] := i階までで対応関係が作れるか?
で十分で、dp[j]がtrueなら、[j,i)の区間において対応関係が作れるかをチェックすればdp[i]が更新できる。
答えはdp[2*N]。

yukicoder No.1244 Black Segment

問題

N個のセルが並んでおり、1~Nの番号がついていて、すべてのセルが白になっている。
M個のボタンがあり、i番目のボタンを押すと、L_i~R_iのセルの白黒が入れ替わる。
任意の順番で任意の回数ボタンを押すことができるとき、範囲A~Bの部分が黒になっているような状態になるための最小のボタンを押す回数を求めよ。

制約

  • 1 <= N <= 10^5
  • 1 <= M <= 10^5
  • 1 <= A <= B <= N
  • 1 <= L_i <= R_i <= N

解法

A~Bの区間はすべて黒になっている必要があるので、「Aまでの部分」から、各ボタンの範囲は連続的につながっている必要がある。
(そうでないと区間内で白の部分ができてしまう)
なので、「Aまでの部分」を固定して、そこから黒が連続している範囲のdpを考える。

dp[i] := 「Aまでの部分」からiまでの部分を黒、i+1~「B+1以降の部分」までが白の状態にするまでの最小操作回数
とすると、
各iについて、ボタンの範囲を使ってdpを更新できる。
(右方向には、黒くするのでdp[i]+1をRのところに更新。左方向には、黒くしていたものを白く戻すので、dp[i]+1をLのところに更新、的なイメージ)

これはダイクストラ法的に計算すればよく、「Aまでの部分」「B+1以降の部分」をs,tでまとめて扱えば、sからスタートして、tまでの最短距離dp[t]を出力すればよい。

yukicoder No.1243 約数加算

問題

整数A, Bが与えられ、Aに対して「正の約数を1つ選び、Aに足す」という操作を120回まで繰り返して、AとBが等しくなるようにしたい。
テストケースがT個与えられる。
各A, Bに対して、加える約数を列挙せよ。

制約

  • 1 <= T <= 100
  • 1 <= A_i < B_i <= 10^18

解法

A,Bが大きいのでまともに約数を列挙していては間に合わない。

そこで、簡単に大きな数字になりえる2のべき乗のみ考える。
(1~10^18の中で2のべき乗は59個程度しかない)

ある2のべき乗でAが割りきれるとき、2進数的に見ると、Aが「101001...0110000」のような場合、下位の「10000」の部分までになる。これを加えた場合、この1が次のビットに移動し、Aは「101001...1000000」のようになる。
これをBを超えない範囲で繰り返すと、上位の部分はBと同じ&下位の部分が0になっているようなビット列にすることができる。

次に、下位の0の部分がBと一致するように加算したいが、10000に対して、1000や10などは約数になるので、上のビットからBでビットが立っているところの数値は約数になりえるため、そのまま足していけば良い。

ビットのサイズが60桁程度のため、上りと下りで120回以下に抑えられる。

反省

Bを超えない最大のものを選んでいくとき、2^iだけでなく、A/2^iも約数になるが、こっちの方を選んでしまうと、上記の操作よりも多くなってしまう。

ABC177 F. I hate Shortest Path Problem

概要

縦H+1マス、横Wマスのマス目がある。
最初、一番上のいずれかのマスからスタートし、右または下に1マスずつ移動していくことを繰り返す。
ただし、上から1以上H以下の縦iマスの左からA_i~B_iマスについては、下に移動することができない。

上からi (i=1~H)のマスのいずれかに移動するための最小移動回数を求めよ。
ただし、移動できない場合は-1を出力せよ。

制約

  • 1 <= H, W <= 2 * 10^5
  • 1 <= A_i <= B_i <= W

解法

(遅延セグメント木解)

indexが0~Wまである配列を考える。
問題文は、A_i, B_iが与えられたら、A_i-1の値がxだとしたら、A_iマスはx+1、A_i +1マスはx+2、・・・のようにindexに対して等差(公差は正)になるように範囲更新できればよい。
例としては、

最初:0 0 0 0 0 0
↓
(A_i, B_i)=(1,3)、x=1が与えられる
↓
0 1 2 0 0 0

のように更新できれば、1段下に下がったときの各マスへの横方向への移動距離がわかる。
求めたい答えは、全体での最小値で、範囲最小値が取得できれば、それに縦方向の移動距離iを足したものが答えになる。

したがって、

  • 範囲等差(公差は正)更新
  • 範囲min

ができればよい。
これを遅延セグメント木で考える。

遅延セグメント木において、モノイドSに対して作用素Fが適用される場合を考える。

f:id:phyllo_algo:20200930184543p:plain
「範囲等差(公差は正)更新」は、位置が依存しているので、単純にSが「範囲の最小値」だけを保持しているだけでは、FがSに作用したときのSの更新ができない。
(足りない情報としては、「Fの左端」と「Sの左端」の情報がないので、Fの範囲で左からx、x+1、x+2、・・・とした場合、Sの左端の位置でのx+?がわからないので、Sの範囲での最小値がわからない。)

そこで、SとFに「範囲(左端indexと右端index)」を情報ともたせると、位置に依存した計算を行うことができる。

具体的には、

  • Sは「範囲min」「そのSが扱う範囲(左端index, 右端index)」(この問題では右端は不要)
  • Fは「Fの左端での値x」「そのFが適用される範囲(左端index, 右端index)」(この問題では右端は不要)

をもたせる。
(図ではそれぞれの「l」と「r-1」の情報。半開区間で[l, r)のほうがよさそう)

FがSに作用した場合、Sの範囲の一番左の値は「F.x + (S.l-F.l)」で更新できる。
(Sの範囲の一番右の値も「F.x + (S.r-1-F.l)」でわかる)
Sの範囲で一番小さい値は、(公差が正なら)一番左の値になるので、結局Sのminは「F.x + (S.l-F.l)」で更新すれば良い。

f:id:phyllo_algo:20200930184600p:plain
また、SとS'からS''を計算する場合は、

  • 範囲minは、SとS'の範囲minの値で小さい方
  • S''の扱う範囲は、S.lからS'.r-1まで

とわかるので、そのように計算すれば良い。

static const ll INF = (ll)(1e15);

struct S {
  ll val;
  ll range_l, range_r;
};
struct F {
  ll x;
  ll range_l, range_r;
};

S op(S l, S r){
  S ret;
  ret.val = min(l.val, r.val); //範囲min

  ret.range_l = min(l.range_l, r.range_l); //左端
  ret.range_r = max(l.range_r, r.range_r); //右端
  return ret;
}
S e(){
  return S{INF,-INF,INF};
}
S mapping(F l, S r){
  if(l.x == INF) return r;
  return S{l.x+(r.range_l-l.range_l), r.range_l, r.range_r}; //範囲minをSの左端の値にする
}
F composition(F l, F r){
  if(l.x == INF) return r;
  return l;
}
F id(){
  return F{INF,-INF,INF};
}

コード的には、

  int H, W;
  cin >> H >> W;
  lazy_segtree<S, op, e, F, mapping, composition, id> seg(W+1);
  rep(i,W+1){ seg.set(i, S{0,i,i+1}); } //最初は0で初期化
  seg.set(0, S{W+1,0,1}); //index=0だけはW+1(移動できない)にしておく

  rep(i,H){
    int A, B;
    cin >> A >> B;
    {
      S s = seg.get(A-1);
      seg.apply(A-1, B+1, F{s.val,A-1,B+1}); //A-1~Bで範囲等差更新(左端の値を指定)
    }
    {
      S s = seg.all_prod(); //全範囲での範囲min
      if(s.val != W+1) cout << s.val+(i+1) << endl; //移動できる場合は、「横方向移動距離+縦方向移動距離」を出力
      else cout << -1 << endl;
    }
  }

反省

「SとFに範囲情報を持たせる」は汎用的そうで、「範囲f(x,i)更新」とかも同様に扱える。

ABL E. Replace Digits

問題

長さNの文字列Sがあり、すべての文字は「1」になっている。
Q回、整数L, Rと数字Dが与えられるのでいかに答えよ。

  • L番目からR番目の文字をすべてDに書き換え、文字列Sを10進数で書いた整数とみなした値を998,224,353で割ったあまりで表示せよ

制約

  • 1 <= N, Q <= 200,000
  • 1 <= L <= R <= N
  • 1 <= D <= 9

解法

範囲更新、範囲取得したいので、遅延セグメント木の適用を考える。

ある範囲の文字列を10進数で表示してmodをとったものaを考える。
隣り合う範囲のaとa'は、その位置関係で連結した場合、aを10^{a'の範囲の長さ}倍したものとa'を合わせれば求められる。
したがって、モノイドとしては、「その範囲の数字列を10進数とみなしてmodをとった値」と「範囲の長さ」を保持すれば良い。

struct S { mint a; int size; }
S op(S l, S r) {
  mint x = mint(10).pow(r.size);
  return S{l.a*x+r.a, l.size+r.size};
}
S e(){
  return S{0,0};
}

これで、表示する答えは、seg.all_prod().a.val()で取得できる。


次に、範囲更新を考える。
「L~Rの数字をDに書き換える」ので、
あるモノイドSに作用させた場合、サイズは変わらず、S.aは1111....11111にDをかけたものになる。
作用素F'に作用素Fが作用した場合は、後に適用したほうのものになってほしいので、作用素に適用タイミングiをもたせて、それが大きい(後で更新したほう)にする。

struct F { int a, i; };
S mapping(F l, S r){
  if(l.i == -1) return r;
  return S{ones[r.size] * l.a, r.size};
}
F composition(F l, F r){
  if(l.i < r.i) return r;
  return l;
}
F id(){ return F{0, -1}; }

あとは、クエリごとに、seg.apply()してからseg.all_prod().a.val()を表示すればよい。

ABL D. Flat Subsequence

問題

整数列A_iと整数Kが与えられる。
以下の条件を満たす数列Bの長さとして考えられる最大値を答えよ。

  • BはAの(連続とは限らない)部分列
  • どのBの隣り合う要素の差の絶対値もK以下

制約

  • 1 <= N, A_i, K <= 3 * 10^5

解法

セグメント木に「その値が最後になる部分列の最長の長さ」をもたせる。
すると、A_iに対して、「A_i-KからA_i+Kの範囲での最大値+1」が最長の長さになる。
これをA_iに対して更新していき、最後に全範囲での最大値を答えればよい。

反省

「各要素から次に選べる要素に辺をはったグラフにおける最長路」を考えようとして、そのままだと辺数が多すぎるので「各要素から、その要素以降で次に選べる要素の中で一番indexが近いものに辺をはる」とやってしまった。

が、これは嘘解法で、

6 5
10 10 5 11 12 13

みたいなケースで、「10 10 5」を選んでしまう。
(正しくは「10 10 11 12 13」)

ABC178 D. Redistribution

問題

整数Sが与えられる。
すべての項が3以上の整数で総和がSである数列がいくつあるか求めよ。
答えは10^9+7で割ったあまりで求めよ。

制約

  • 1 <= S <= 2000

解法1

dp[i] := 総和がiであるような数列の個数
を考える。

i-1以下がわかっていると考えると、dp[i]は、それらの数列に3以上の数字xを付け足したものは、dp[i+x]の個数の一部になる。
dp[0]=1として、iを小さい方から、dp[i]にxを追加したものをdp[i+x]に加えていけばよい。

  vector<mint> dp(S+1);
  dp[0] = 1;

  rep(i,S+1){
    REP(j,3,S+1){
      if(i+j < S+1){
        dp[i+j] += dp[i];
      }
    }
  }

計算量はO(S^2)。

解法2

整数Sをk個に分割する、と考える。条件として3以上とあるので、先に3*k個を割り当てておけば、S-3*kをk個に0以上割り当てると考えられる。

これは、写像12相で「n個の玉を区別しない、k個の箱を区別する、何も条件なし」の場合であり、Comb(n+k-1,n)で求められる。
したがって、n=S-3*kとして、各kで上記を求めれば良い。
kは、1以上で、S-3*k>=0であるようなkで求めて足し合わせれば良い。
(注意として、S-3*k=0のときも含む。nは0で、Comb(0+k-1,0)が1。)

modのCombは、factとinv_factを前計算O(S)しておけば、O(1)なので、O(S)。