B 問題。長さ $ N $ の数列 $ A $ が与えられて、総和が変わらないように再分配し、$ \sum _ i \sum _ j | A_i - A_j | \quad (i<j) $ が最小になるようにして最小値を求める。
均等に配るのが最適と簡単に証明できる。最後の一周配られる数を $ x $ とすると答えは $ x (N - x) $。
D 問題。部分点がある。$ a \oplus _ k b $ を $k$-itwise XOR ということにして、これは $ k $ 進数にして各桁ごとに $ \pmod k $ の和を取るという演算と定義される。$ 0 $ から $ N-1 $ のパスワードを $ N $ 回使って当てるというインタラクティブ問題なのだが、$ 1 $ 回外すと、元のパスワードを $ x $ 、間違ったパスワードを $ y $ として $ x \oplus _ k z = y $ のような $ z $ に変更されてしまう。
D1 は $ k=2 $ で固定。これにより $ \oplus _ k $ は $ \oplus $ になって、$ z = x \oplus y $ 今までの $ y $ の累積 xor を持っていれば元々のパスワードが $ 0,1,2, \cdots $ の順に検査できる。
D2 も基本方針は同じ。ただ $ k=2 $ の時と違ってしっかり符号を考えなくてはならない。$ z = y \ominus _ k x $ のように書ける。元々の演算が各桁の和なので逆も簡単に定義できる。計算量を小さくするために $ y $ の方を累積させていきたいが、結構符号合わせが面倒でしばらく地蔵になっていた。
C 問題。解けね～。参っていた。しかし TL を見ると自分がボツにした「 $ p $ 以外の確率の状態を持てば十分で、$ Invalid $ が出るまでは $ \frac{v}{2} $ 刻みだし状態数は見た目より制限される」という解法がはびこっている。は～これは $ v $ がちっちゃかった時に結局状態数 $ 10^{8} $ ぐらいは余裕で行きそうだなと思ってあきらめたのだが、よく問題文を見直すと $ 0.1 \leq v \leq 0.9 $ と書いてある。ゴミ～～～。
これだから俺は同じ単位・次元の数値で、$ 1 $ つだけしれっと入力制約のところで弱い制約になっているのを許せないんだよね。
せめて太字にしませんか？
帰って失意のまま夕食をたべた。
そのまま就寝しようと思ったが、自分がかなり解釈に困っていた E - White and Black Balls についての話題が Twitter であったら熨斗袋さんが鏡像法で考えると分かり易い（？）旨のリプライをいただいた。
鏡像法って言うと、あの $ 1 $ 年の頃に物理学をやっていて、鏡像の点電荷を想定することで見通しが良くなるような計算手法だった気がするなあと思いながら
結局どこら辺が嬉しいのかいまいちわからず、その旨を返しておいた。
問題概要は簡単。$ N $ 頂点 $ M $ 辺の DAG が与えられて、頂点 $ A_i $ から $ B_i $ に到達可能かどうかのクエリ $ Q $ 個に答える。
sample の隣接行列を書いてしばらくグッと睨んでいた。
しばらく睨んでまともな解法がなさそうなことに気づき $ 64 $ bit をまとめて処理することを考える。
到達可能性の行列は頂点番号の降順（トポロジカル順序の逆順）に構築可能だ。
$ u < v $ であるような頂点 $ u,v $ を考えたときに、$ u $ の到達可能性を bit vector で考えたとき、
$ u $ が $ v $ に直接到達可能ならば、 $ v $ の到達可能性の bit vector との OR で更新すれば良いことが分かる。直接到達可能な頂点数は辺の数の $ M $ と一致するため、全体で到達可能性行列は $ O(MN) $ で前計算出来る。
OR をとるパートで $ 64 $ bit ずつ処理すれば $ 64 $ 倍速くなり、多分間に合うのだろう。まあ $ 64 $ bit というかワードサイズなのだが…
ここで書き始めるも、Memory Limit を思い出し計算すると $ 1200 $ MB ぐらいかかりそうなことが判明。最悪や。
冷静になると、DAG の到達可能性なので、$ M _ {i,j} \quad (i \leq j) $ の部分だけあれば十分なので大体半分ぐらいになるから足りそう。
この手の高速化は結構カツカツな状況が多いので offset やブロックのインデックスを求める時に割り算を使うと終了しそう。ワードサイズは当然二冪なのでビットシフトや AND を使おう。でも二冪定数の割り算ぐらいビット演算に最適化してくれそうだけど…どうだろ…
色々工夫して頑張って書いたら $ 500 $ ms を割ったので、記念にソースを貼っておく。
まあ測定結果とかキャッシュミス率とかを監視しながらチューニングをしたわけではないのでもっと速くなるかもしれないけど。
やったことを箇条書きしてみる。
$$
\left\{
\begin{align}
&K - Y \leq r \leq R \quad \cdots (4) \\
&K - Z \leq g \leq G \quad \cdots (5) \\
&K - X \leq b \leq B \quad \cdots (6)
\end{align}
\right.
$$
のような制約が得られて、これはかなり分かり易い。$ r $ を決めうってみる。この時に $ g + b = K - r $ であるような場合の数が高速に求められれば解ける。
式 $ (5),(6) $ に注意しながら、有効な $ b,g $ について、$ \binom{G}{g} $ や $ \binom{B}{b} $ の配列を構成すれば、その畳み込みをすれば欲しいものが手に入る。FFT を使えば $ O(K \log K) $ でできる。結局ボトルネックも FFT なので、この計算量で解けた。AC。
B: 水色のボールが $ A $ 個入っていて、$ 1 $ 回の操作で 水色のボールと赤色のボールをそれぞれ $ B, \quad C $ 個入れる。
水色のボールが赤色のボールの $ D $ 倍以下の個数になるのに必要な操作回数の最小を答えよ、という問題。
$ A + Bx \leq CD x $ を満たす最小の $ x $ を求める問題。$ A $ は自然数なので、$ B < CD $ でないと絶対に式を満たすことはない。
後は式を整理して $ x \geq \left \lceil \frac{A}{CD-B} \right \rceil $ となれば解けている。
さてひとしきり休んだところで、昨日解説を見た E 問題について再考する。
最短経路数問題について、「特定の斜め線を通る経路数を、線対称に移動した始点からの経路数と考えることができる」
という事実は、知っておいて損はない。しかし自分はこの手の特殊操作テクニックが苦手なのでなんとか別のアプローチでいけないものか考える。
形式的冪級数とかも関わってくる領域なので、合わせて勉強しようとして色々調べているとあっという間に時間が過ぎていく。
そもそもフィボナッチ数の一般項を誤差なく求めたいと思ったりして mod sqrt を発見して感動するなど、
かなりわき道にそれた検索行為をしているためこうなってしまう…
目的のものだけを調べることってできなくないですか？俺に集中力がないのは認めるが、みんなそうだと思いたい。
06/16 (WED)
10:00 起床。そういえば書いたショートレポートを提出していなかったので起床即提出。
朝食を食べる。
水曜日はピアノなので練習していくことになるが、午前中はイマイチ練習できる状況にないので別の事をする。
E - White and Black Ballsの非天才的解法を模索しているが、依然として成果がない。
非天才的解法の模索がかなり面倒なことは、TL にも AtCoder のページにも誰も解説を上げていない時点で想像はできたが、かなり苦しい。
具体的には体調も気分もノっていなかったので漫画を読んでいた。
今週のジャンプを月曜に買ったのに読んでいなかったので読んでいた。
最近のジャンプは猛烈に次が気になる漫画がなくて困っている。
いや、ヒーローアカデミアと Dr. STONE は続きが結構きになるかも。
ただ、ハンターが連載している時期は、毎週次のハンターが読みたくて狂いそうになっていたのだが、そういう感覚はすっかりしなくなってしまったな。
色々やっている内に夕食の時間になり食べた。サッサと食べてしまい SRM に備えていた。
が、しかし自分は大事なことを見落としていた。SRM 807 はどうやら Only rated for Div. 2 らしかった。
昨日の日記に黄色になりたいとか書いていたが理論上不可能なことだった。
直前にそのアナウンスに気づいたが、Combined とのことで多分難しい問題もあるだろうということで参加した。
A 問題。文字列 $ S $ が与えられて、文字列当てゲームみたいなことをする。
文字列を推測する側のプレイヤーが文字を指定すると、その文字が書かれた index が全て明かされる。
推測する側のプレイヤーが指定した文字のリストが与えられるので、現在推測される文字列を不明な位置を '_' として返せ、と言う問題。
無難に $ 26|S| $ 回ループして処理した。
B 問題。長さ $ N $ の整数列 $ A $ を考える。このうち $ 1 $ つの値がわからなくなっている。
この数列は、すべての要素の平均の値が数列中に現れるという性質を持つ必要がある。
$ N - 1 $ 個の要素が与えられるので残り一個の整数の候補のリストを返せ、という問題。
数式を書けばよくて、$ \frac{ \sum _ {i=1} ^ {N - 1} A_i + X}{N} = A_k \quad (1 \leq k \leq N - 1) $ の $ X $ を求めれば良くて簡単な一次方程式。
と思いきや、$ \frac{ \sum _ {i=1} ^ {N - 1} A_i + X}{N} = X $ も考える必要がある。Hack のためにこれが要るケースを作っておいた。
最後に重複を除けば OK。
C 問題。長さ $ N $ の整数列 $ A $ が与えられる。
十進数で考えたときに $ 2 $ 整数の「違い」を「足りない桁は $ 0 $ 埋めして違っている桁の数字の数」と定義したときの全てのペアに対する「違い」の和を求めよ、という問題。
こういうのは桁ごとに見る。以上。
D 問題。長さ $ N $ の数列 $ A $ と $ LO,HI $ という整数が与えられる。
$ LO $ より大きく、$ HI $ 以下の部分和の個数を数えよ（和が同じでも index の set が異なれば異なる）、と言う問題。
制約を見ると $ LO,HI $ が大きく、 $ N \leq 40 $ 。こんなのは半分全列挙する。以上。
upper_bound と lower_bound を取り違えていて頭を悩ませていたのは内緒。
A 問題。$ N $ 個の石が与えられてそれぞれの力が $ A_i $ で与えられる。力は distinct である。一回の操作で左右端のどちらかから石を取り出すことができる。力が最大と最小の石を両方取るには最小で何回の操作が必要か、という問題。
distinct なので最大最小の石の index を事前にもっておいて、それぞれの石について左右のどちらから取るかを全探索することで最小回数が分かる。
B 問題。$ N $ 人の子供がいて $ i $ 番目の子供は $ A_i $ 個のキャンディを持っている。子供を何人か選んでキャンディを全て預かり、それらのキャンディを自由に再分配することができる。最終的にすべての子供が持っているキャンディの数を同じにしたい。この時最小の選ぶ子供の人数を答えよ、という問題。まずキャンディの数の平均が整数になっている必要がある。あとは平均より多くの数のキャンディを持っている子供を選択すれば十分。
C 問題。長さ $ N $ の整数列 $ A $ が与えられて、$ L \leq A_i + A_j \leq R $ となるような $ i,j (i<j) $ の組を数え上げろ、という問題。
昨日の SRM の D の半分全列挙マージパートと同じ。
D 問題。$ A $ と $ B $ の $ 2 $ つの整数が与えられる。 $ 1 $ 回の操作では、それぞれの数をその正の約数で割る。
ちょうど $ K $ 回の操作で、$ A=B $ にすることはできるかどうか判定しろ、という問題。
$ A,B $ の一方がもう一方の約数になっている場合回数の下限は $ 1 $ 回。しかし $ A=B $ の場合のみ $ 2 $ 回になる。そのほかの場合も $
2 $ 回。次に上限を考えると、$ A,B $ の素因数の数の和が操作回数上限である。よってこれに合うようにする。
素因数の数を求めるパートが一番つらいが、これは $ \sqrt{10^{9}} $ までの素因数を事前に列挙しておくのが良いらしい。
本番中は焦って高速素因数分解を yosupo judge からパクってきたが、なんか System Test で落ちていた（涙…）。
F 問題。初期値 $ L $ として $ 1 $ ずつ足していって $ R $ にすることを考える。$ R - L $ 回のの演算で変化した桁の数の合計を答えよ、という問題。$ 10^{x} $ の倍数になるときに $ x+1 $ 桁だけ変化していることに気づくので、$ 10^{k} \quad (0 \leq k \leq 9) $ の倍数の数を足し上げれば解ける。面倒なので $ L=0 $ の問題を解けば引き算で良い。
G 問題。$ X $ 個の赤いボールと $ Y $ 個の青いボールがあって、これらを使って $ A $ 個の赤いボールと $ B $ 個の青いボールのセット、もしくは $ B $ 個の赤いボールと $ A $ 個の青いボールのセットを作りたい。作れる最大のセットの数を求めよ、という問題。
こういうのはとりあえず数式を立てると良さそう。
$$
\left \{
\begin{array}{l}
Ax+By \leq X \\
Bx+Ay \leq Y
\end{array}
\right .
$$
B 問題。$ N $ 個のシナリオが与えられる。$ i $ 番目のシナリオでは $ A_i $ 円を失ってしまう。それぞれのシナリオは等確率で起こる。
$ x $ 円 (任意の値) 払って保険に入ることによって、$ A_i $ 円を失った時に $ \min(A_i, 2x) $ 円補填してもらえる。
最終的に失うお金の期待値の最小値を求めよ。
明らかに $ 2x $ が $ A_i $ 以上かどうかで性質が変わる。$ A $ をソートして累積和を事前計算することで、 $ x = \frac{A_i}{2} $ の場合を全て試すのを高速にできる。AC。
C 問題。むずすぎ。本番は落とした。フィボナッチっぽいことに気づいていたのに、考察を続ける堪え性がなかった。
任意の整数は、隣接しないフィボナッチ数の和で表現できるため、計算するとちょうど $ 130 $ ぐらいで目標を達成できる。
明らかに 3,4 を繰り返さないと間に合わない大きさの数字だったので、早く気づくべきだった。
D 問題。本番わかったのだが、落とした（？？？）。$ 2N $ の非負整数が与えられて、$ 2 $ 人が交互に数字を取ってきてその xor が黒板に書かれて、最後に黒板に書かれた最大値がスコアになる。
先行の人は最大化したいし、後攻の人は最小化したい。
xor の最大値を考えるので、整数列中で一番高い位置の pop している bit に着目するのが良いだろう。
着目すると、この bit が pop している整数が偶数個なら、ミラーリング戦略を取ることでスコアでその bit が立つことを防げて最適。
奇数個なら、スコアで必ずその bit が立ってしまう。故に、後攻はなるべくそれより下位の bit で小さくしたい。
着目している bit が立っている整数集合とそうでない集合間の要素同士の xor でもっと小さいものが答えになる。これは Binary Trie で効率よくわかる。
偶数の場合に立ち戻る。偶数の場合はミラーリング戦略で良いが、どれとどれを組ませるかは後攻が決めることができるので再帰してその右側の bit で同じ問題を解く。
桁数が $ 30 $ 程度なので再帰しても十分間に合う。また着目した bit が pop していない整数の集合に対しても問題を解いて、結果をマージする。
これで解けたはずだったが、chmin のところが chmax になっていて落とした・・・無念・・・
E 問題。本番は読んだだけだった。冷静になると、比較的にわかりやすい貪欲で解けることに気づいた。
ただ ad-hoc 要素が強いな。本番この問題に突撃するのは勇気が要りそうだ。
この問題と D は記事にしようかな。
B 問題。これも難しかった。つかみどころがなくしばらく困っていた。パラメータが少ない定数個しかない問題は再帰的な構造が存在することを疑ってみるのがいいと思いだした。ここで $ x $ の時の答えを $ f(x) $ として改めて観察すると、一番外側をペアにするとき中の状態は $ N-1 $ と同じになり、 $ f(N-1) $ だ。同様にして外側 $ i $ 個ずつをペアにするときは $ f(N-i) $ であることが分かる。あとは、包含関係が存在しないパターンが残されている。この場合すべてのペアの距離が同じなのでよく考えると、$ N $ の約数の数だけこのパターンがある。約数の個数を前計算した上で累積を持ちながら DP をすることで計算可能。あとで思ったのだが左端をどことつなぐか考えるというアプローチも悪くなさそうだ。
C 問題。こういうの得意なはずが AB のムーブの焦りからか落とした。一つ目の木で根からの任意の頂点へのパスに含まれる頂点集合で、二つ目の木では祖先-子孫の関係が一切ない部分集合の最大値を求めれば OK。根から頂点へのパスを全探索するみたいな問題は、DFS で行きがけに追加、帰りがけに削除みたいなことをしてやるのが鉄板。当然この時は revert が可能なデータ構造である必要があるのに注意。頂点の数を最大化するため、追加した頂点で祖先-子孫の関係ができてしまいそうになった時子孫の方を残すのが常に最適である。自分の思いついた解法は、頂点追加時に遅延セグ木(双対セグ木)で部分木を頂点番号で塗りつぶす。そしてその子孫が追加されそうになった時に、祖先の塗りをクリアして改めて子孫の部分木を頂点番号で塗りつぶす、というもの。revert も自明に可能。これで解けた。今回子孫は祖先より頂点番号が大きいことが保証されるため逆パターンは考えなくてよい。
しかし Twitter を見ていると、単純に頂点を set に追加して、追加した頂点の Euler Tour 順の直前と追加した頂点を見て、追加した頂点が直前の頂点の子孫（部分木内に存在する）なら直前の頂点を削除する、で良いことが分かる。たしかに追加前が祖先-子孫の関係が存在しないことが保証されているため簡単に証明ができる。賢い。しかもこれの優れている点は上の青字の制約を満たさない木の制約の時も逆パターンが簡単に書ける。遅延セグ木で逆パターンをやろうとすると割と地獄だし定数倍重そう。
夕食の後、いつも通り水曜の午前中締め切りのショートレポートを書くために講義を視聴する。が、なんか今週は課題がなかった。
そのあと今週のジャンプを読む。今週で一番話が動いたのは呪術廻線かな。あとは、どう持っていきたいのかよくわからなかった野球漫画が打ち切りになりそうな雰囲気がある。呪術廻戦は結構世間的に人気らしいのでネタバレを平気な顔して書くことが憚られるな。Dr. STONE はなんかとりあえず仲間は全員復活した。死人も生き返ってしまう。すぐ打ち切られる漫画は大体方向性がよくわからないため、話がブツ切れに感じられてしまい、結果として話の大きな流れを全然思い出せないんだよな。
ゼミが終わったので典型を AC しておく。このあとはだらだら漫画を読んでいた気がする。
適度な頻度で自分が読んでいる漫画についてこの週記に記録してもいいかもしれない。気が向いたら記録をしてみる。
ネタバレに気を使った方がいいかなとか思うと感想を入れることができないのだが、まあこんな週記を読む人も多くないしいいかも。
E 問題。問題文に沿って遷移を考えると、ある $ Y $ 座標にいけるかどうかを考えながら $ X $ 方向に進んでいくみたいなことにすれば良さそう。
ただ座標の幅が広いのでそのままはできない。$ N $ から隣接する黒色だけ考えれば良いから最悪でも $ M+1 $ の幅だけ考えれば良い。
$ X $ 方向に進んでいくと黒が存在したらその時点で $ Y $ 座標隣接のどちらかがに到達可能であった場合、黒の $ Y $ 座標に到達可能にする。
よく考えると、これは $ M $ 回しか行われないため、in-place にやれば間に合う。
完全に実装方針を間違えている。死ぬほど時間をかけながら AC。この時点で F を通さなければ黄色になれなそうなことに気づきくそ焦る。
