min(Ai+Bj,Aj+Bi) の最大値を求めたいときのテク

これは Cow and Fields の解説で見たテクニックなのですが、他でも見たことがある気がするのでまとめておきます。

今回解きたいのは以下の問題。

 長さ $N$ の $2$ 整数の組 $(A_i,B_i)$ があります。

このとき、相異なる $2$ つを選んだ時の $min(A_i+B_j,A_j+B_i)$ の最大値を求めてください。

$2\le N\le {10}^5$

$|A_i,B_i|\le {10}^{18}(1\le i\le N)$

 まず、 $A_i+B_j\le A_j+B_i$ となるときに $A_i+B_j$ が min として採用されることを確認します。この式を変形すると

$A_i-B_i\le A_j-B_j$ となります。

ということは、全要素を $A_k-B_k$ の値の昇順にソートすると任意の $i<j$ について $A_i-B_i\le A_j-B_j$ が成立します。とすると、前にある要素から $A_i$ を、後ろにある要素から $B_j$ を採用することになります。

$A$ について前から累積maxをとって $\alpha$ 、 $B$ について後ろから累積maxをとって $\beta$ 、とすると、$max({\alpha }_k+{\beta }_{k+1})(1\le k\le N-1)$ が解となります。

 計算量は、ソートをボトルネックとした $O\left(N\log N\right)$です。

Distinct Boxes(AWTF2019-D)

この記事では、 D - Distinct Boxes の解説の内容をざっくり日本語に翻訳します。

(簡単のために空の箱を1つ作ることを認めておき、最後に解を-1するという前提で議論を行います。)

この問題では、「解 $K$ を先に仮定して、$K$ が実現可能かどうかは二分探索可能なので二分探索する」という方針をとります。

まず、図のような感じで、箱に入ったそれぞれの色のボールの数とxy座標系を対応させます。

ここで、この平面に対してある直線 $px+qy=C$ (p,q,Cは定数)を引くことを考えます。

図は $2x+y=4$ を引いた場合の例です。

この直線の下に来る格子点に対応する箱をすべて作るということは、ある意味では「最適」です。

天下り的発想ですが、ここで $(B,R)$ についての解を座標平面上の対応する点に書き込んでみます。

すると、図のような感じで、「解が $K$ となる前線」は必ず上側凸包となるのですが、これを証明します。

まず、先ほどの $2x+y=4$ の例を見てみましょう。

このときに、今 $7$ 箱作りたいとしましょう。

今はこの直線を基準にとっているので、直線より下の $6$ 点(に対応する箱)は作るのが最適です。しかし、 $7$ 箱目を $(0,4),(1,2),(2,0)$ のどれにするかはこの間でのタイブレイクルールに依存します。そのことを掘り下げます。

今、 $K$ 箱を作る時に引いた直線を $3x+5y=C$ としましょう。

ここで、今 $C=56$ で $(2,10),(7,7),(12,4),(17,1)$ の $4$ 点がタイであるとし、既に $K-2$ 箱作っていてここから $2$ 点選ばねばならない状況だとします。

ここで、 $(2,10),(7,7)$ を選べば $K$ 箱の合計が $X,Y$ になるとします。

このとき、 $(7,7)$ を $(12,4)$ に交換した場合、 $(X+5,Y-3)$ でも $K$ 箱作ることが出来ます。

さらに、 $3x+5y=56$ より上側の点はまだ選ばれていないことにも注意すると、 $\left\{\right(X,Y),(X+5,Y-3),(X+5,Y\left)\right\}$ の三角形領域にある点は全て $K$ 箱作ることが可能です。

こんな感じで、線分の上サイドを次々に切り出す格好になります。(ここで、$(X,Y)$ より左側の点についてはたとえ直線の上サイドであっても $K$ 箱作れるかどうかはまだわかっていないことに注意して下さい。)

これで、構成可能な点の上側凸包については $K$ 箱作れることが分かりました。

ここで、万一前線の下側で $K$ 箱作れるような場合が存在した場合、 $(X,Y)$ で構成可能なら $(X+1,Y),(X,Y+1)$ でも構成可能なことは元の問題に立ち返れば明らかです。そうなれば前線が全体的にずれ込むことがすぐに確認でき、またずれ込んだ点でも先ほどの上側三角形が作れるという議論が成立します。

よって、前線がちょうど上側凸包であることが示せました。

さて、これを利用して求解します。これは以下の3重の二分探索で実行可能です。

1. 解 $K$ を仮定して二分探索(決め打ち二分探索)

2. 決め打った解に対して、$K$ 箱作ろうとする場合の直線 $px+qy=C$ の傾きを $p+q={10}^{10}+19$ などの条件を付けて二分探索(総和を十分大きい素数にとると全ての傾きを考慮できる)。傾き $(p,q)$ を与えると必要なボールの数 $(B,R)$ を返すようなものを作ることを考える。(これは下の 3. で行う)

二分探索はだいたい画像左側のような分岐で進みます。

最後に、この二分探索が常に画像左側において左上か右下に入ってしまった場合。この場合は(凸包上で)隣り合い辺をなす構成可能点が求まっているので持っている球数を表す点が構成可能点同士を結ぶ点の上側か下側かを判定すればよく、これはベクトルの外積を利用すると可能です。

3. $px+qy=C$ の $C$ 部分を二分探索。直線の下側にある点の $(B,R)$ の総和は $min(B,R)\le 2000$ までしか考慮しなくてよいことを利用すると求められる。

完全グラフ K2N を N−1 個のハミルトン閉路と 1 個の完全マッチングに分解する

今回は、記事の名前の通り「完全グラフ $K_{2N}$ を $N-1$ 個のハミルトン閉路と $1$ 個の完全マッチングに分解」していこうと思います。

まず、この分解の意味について。具体的には Doofish Matrix という問題を解くときにこれを調べててヒットしなくてなかなか困ったのですが、やりたいこととしてはざっと以下のような感じです。

完全グラフ $K_{2N}$ の辺数は $N(2N-1)$ だが、もし辺を余すことなく完全マッチングに分解できるなら、ここから $2N-1$ 個のマッチングが取れるはず…?

ここで、とりあえず辺をダブらないようにいい感じにとる話として、 

Complete GraphのHamilton cycle(path)への分割 - YKK++ という記事が存在するのが記憶にありました。

この記事内では、「完全グラフ $K_{2N}$ を $N$ 個のハミルトンパスに分解する」「完全グラフ $K_{2N-1}$ を $N$ 個のハミルトン閉路に分解する」方法が示されています。これも競プロでよく見る内容なので、覚えておきたいものですが、今回はこちらを適用することは残念ながらできなさそうです。

さらにいろいろ資料をあたった結果、 ハミルトン路 - Wikipedia に、

完全グラフ $K_{2N}$ は、 $N-1$ 個のハミルトン閉路と 1-正則な全域部分グラフ (すなわち、 $1$ 個の完全マッチング) に分解できる。

という記述がありました。少し考えると、以下のようなことがわかります。

$K_{2N}$ のハミルトン閉路の長さは当然ながら $2N$ 。これは偶数なので、交互に辺を取っていくと $2$ つのマッチングが取れる。

ということは、$N-1$ 個のハミルトン閉路と 1-正則な全域部分グラフ (すなわち、 $1$ 個の完全マッチング) に分解できるなら、$2\times (N-1)+1=2N-1$ 個のマッチングを取れることにもなる。

ただ、Wikiには結論しか書かれておらず、肝心の手段は書いていませんでした。う～む、こんな時に限って使えない…

そこで、検索言語を英語まで広げてなんとかたどり着いた記事が graph theory - Simple decomposition of $K_{2n}-I$ into hamiltonian cycles - MathOverflow 。

但し、ここには概略しか書いていないので、以下で僕なりに解釈して編み出した具体的な構成法を示します。

まず、頂点に $-(N-1),-(N-2),...,-1,0,+1,...,+(N-2),+(N-1)$ という番号を付けた後、余る $1$ つの頂点を特別な頂点 $sp$ とします。(これは最初に引用した記事の番号付けの仕方と同じです)

この上で、 $0$ と $\pm 1$ を結びます。次に、 $\pm 1$ と $\mp 2$ とを結びます。(複号同順です) これ以降は、 $\pm k$ と $\mp k$ とをどんどん結んでいきます。

最後に、 $\pm (N-1)$ と $sp$ とを結んで $1$ つのハミルトン閉路が完成。

これを、時計回りに $2$ 頂点ぶん回したグラフ (図では $0$ の部分を $+2,+4,-3$ に対応させる感じ) を次々に取っていけば、最後に $1$ つのマッチングが残ります。

<ざっくりとした証明>

図は $N=5$ ( $10$ 頂点)の場合ですが、まず、「辺の長さ」を(周上で何頂点離れた頂点を結んでいるか?)で定義します。

すると、図の分解だと、

• $-1,0$ を起点とする長さ $1$ の辺
• $+3,+4$ を起点とする長さ $2$ の辺
• $-2,-1$ を起点とする長さ $3$ の辺
• $+2,+3$ を起点とする長さ $4$ の辺
• $+4,-4$ を起点とする頂点 $sp$ につながる辺

というように隣り合った $2$ 頂点を起点として辺を分類できます。言葉で言うなら図のクロスしている辺を1単位と見ている感じ。これを $2$ 頂点ずつずらしてとっていくと、辺がダブらないのは自然な感じがしますよね。

で、これを $N-1$ 個分とると辺が尽きます。一度ハミルトン閉路を取るたびに各頂点の次数は $2$ ずつ減少します。辺が尽きたときの全ての頂点の次数は $1$ です。このとき、「すべての頂点が次数 $1$ である頂点数 $2N$ のグラフ」は、「 $1$ つの完全マッチング」であることがわかります。

というわけで、この方法はうまくいきます。完全(無向)グラフの辺を余すところなく使う分解は、「完全グラフ $K_{2N}$ を $N$ 個のハミルトンパスに分解する」「完全グラフ $K_{2N}$ を $N-1$ 個のハミルトン閉路と $1$ 個の完全マッチングに分解する」「完全グラフ $K_{2N-1}$ を $N$ 個のハミルトン閉路に分解する」あたりでほぼ網羅だと思うので、全て理解しておくと構築問題などで役に立つでしょう。ちなみに、 完全有向グラフはハミルトンパスを持つ - フィボナッチ・フリーク というような話題もあったりするので、こちらも押さえておくと吉です。

あの〜、お詫びと言っては何ですけどちょっと数え上げでよく見るらしい「主客転倒」の解説今から書くんで…

この記事は Dwango Programming Contest 6th でNosubをやってしまったお詫びとして書かれたものです。このコンテストのB問題もこの記事の中で解説されます。

まず、この記事で説明する「主客転倒」とは、

得点 $A_i$ をいくつか足した和で表される総得点 $S_i$ が沢山あって、ありうる全ての場合について $S_i$ を足し合わせたいときに、 $A_i$ が何回足されるかを考えるテク

です。これだけ言われてもよくわからないと思うので、今から具体例をいくつか挙げて説明します。

まずは簡単な例から。

物理好きさんはあるゲームをした。

• $1$ 回目では $A_1+A_2+A_3+A_4$ 点を得た。
• $2$ 回目では $A_1+A_3+A_4$ 点を得た。
• $3$ 回目では $A_2+A_3+A_4$ 点を得た。
• $4$ 回目では $A_1+A_3$ 点を得た。
• $5$ 回目では $A_1+A_4$ 点を得た。
• $6$ 回目では $A_1$ 点を得た。
• $7$ 回目では $A_4$ 点を得た。

このゲームで物理好きさんが得た得点の総和を求めてください。

$1\le A_i\le 100$

これの答えは $(A_1+A_2+A_3+A_4)+(A_1+A_3+A_4)+(A_2+A_3+A_4)...$

とまっすぐ数えるには少々煩わしいです。「ゲームごとの得点」を足し合わせるのではなく、「 $A_i$ を何回足したか」を考えると楽になります。

この問題だと、 $5\times A_1+2\times A_2+4\times A_3+5\times A_4$ というように、何を何回足したかという形で数えてやると楽です。

これが、「ゲームごとの得点の総和」を「$A_i$ が足された回数」に話をすり替えた「主客転倒」です。

次も簡単な例で。

$N$ 個の正整数 $A_i$ があり、これを使って、以下のようなゲームを行います。

• $N$ 回コインを投げる。
• $i$ 回目に表が出た場合 $A_i$ 点を得る。
• $i$ 回目に裏が出た場合 $0$ 点を得る。

最終的な得点は得た得点の総和です。このとき、ありえるコインの面の出かた $2^N$ 通りについて、得られた得点の総和を足し合わせたものを ${10}^9+7$ で割った余りを求めてください。

$1\le N\le {10}^5,1\le A_i\le {10}^9$

この問題で、 $A_i$ が何回足されるかを考えます。

$A_i$ が得点に加算されるためには、 $i$ 回目にコインの表を出せばよく、これ以外に $A_i$ が足されるような方法はありません。

ここで、 $i$ 回目にコインの表が出るような場合の数は $2^{N-1}$ 通りで、この回数だけ得点に $A_i$ が足されます。よって、最終的な答えは $A$ の総和の $2^{N-1}$ 倍です。

「コインの出方」に対してそれぞれ得点を計算するのではなく、「 $A_i$ が得点に加算される回数」を求めるに話をすりかえているので「主客転倒」です。

続いてこちら。

B - Fusing Slimes (下に示す問題文では少し言い換えています)

数直線に $N$ 匹のスライムが左から $1,2,...,N$ の順に並んでいて、番号 $i$ のスライムは位置 $x_i$ にいます。

このスライムたちに以下の操作を $N-1$ 回行います。

• 今残っている番号 $N$ 以外のスライムを $1$ 匹ランダムに選ぶ。
• 選んだスライムを、今残っている中で右隣りのスライムの位置まで移動させる。
• 選ばれたスライムを消す。

ありうるすべてのスライムの選ばれ方 $(N-1)!$ 通りについて、スライムの移動距離の総和を足し合わせたものを ${10}^9+7$ で割った余りを求めてください。

$2\le N\le {10}^5,1\le A_i\le {10}^9$

今度は、「主客転倒」を先に考えてみます。まず、「距離の総和」は「1回の操作の移動距離」をいくつか足し合わせたものです。「1回の操作の移動距離」は、「最初にスライム $k$ がいる位置から、最初にスライム $k+1$ がいる位置までの区間の長さ」をいくつか足し合わせたものです。

各区間について、それが何回答えに足されるかを考えてみましょう。「最初にスライム $k$ がいる位置から、最初にスライム $k+1$ がいる位置までの区間の長さ」について考えます。まず、その区間が答えに足されるためには、そもそも番号 $k$ 以下のスライムが動かないことには話になりません。ここで、スライム $k$ 以下にだけ注目して議論します。

• スライム $1,2,...,k$ が $k$ 個すべて残っている状態から $1$ つ選ばれたとき、残っているスライムの中で一番右にあるものが選ばれたときのみ解に区間が足される。その確率は $\frac{1}{k}$ 。 

• スライム $1,2,...,k$ が $k-1$ 個残っている状態から $1$ つ選ばれたとき、残っているスライムの中で一番右にあるものが選ばれたときのみ解に区間が足される。その確率は $\frac{1}{k-1}$ 。
• ...
• スライム $1,2,...,k$ が $1$ 個残っている状態から $1$ つ選ばれたとき、残っているスライムの中で一番右にあるものが選ばれたときのみ解に区間が足される。その確率は $\frac{1}{1}$ 。 

 よって、「$k$番目 から $k+1$ 番目までの区間」が足される回数の期待値は $\frac{1}{1}+\frac{1}{2}+...+\frac{1}{k}$ 回です。あとは対称性があるのでこれに $(N-1)!$ を掛けたものが答えです。これは逆元を使うとこのまま計算できます。

続いてこちら。

E - Change a Little Bit (下に示す問題文では少し言い換えています)

$0$ か $1$ からなる長さ $N$ の文字列 $S,T$ があります。

ありえる文字列 $2^{2N}$ 通りについて以下で説明する「罰金」を足し合わせたものを ${10}^9+7$ で割った余りを求めてください。

• $S,T$ について、同じ位置同士で一致しない文字の数を $c$ とする。
• $S,T$ について、同じ位置同士で一致しない文字を $1$ つ選んで一致させる。 $i$ 文字目を修正するときコスト $c\times A_i$ かかる。
• これを文字列が一致するまで繰り返す。この時必要なコストの総和の最小値が「罰金」である。

$1\le N\le 2\times {10}^5,1\le A_i\le {10}^9$

まず、異なる文字のうち、 $A_i$ が大きいものほどつく係数を小さくしたい(= $i$ 文字目を修正する時点で、未修正の文字数をできるだけ減らしたい)ので後回しにするべきです。

ここで、 $A_i$ を降順ソートしたうえで「 $A_i$ が何回解に足されるか」を考えましょう。

まず、そもそも $i$ 文字目が異なる必要があり、これはどの位置についても $2^{2N-1}$ 通りです。では、 $i$ 文字目を直すときに未修正の文字はいくつ残っているでしょうか。これは、 $i$ 文字目を修正する時点で $i$ 文字目より前 (すなわち、 $A_j>A_i$ )の文字 $j$ は最初に異なった場合残っているべきです。各文字について残っている期待値は  $\frac{1}{2}$ で、最後に $i$ 文字目自身が残っているべきなので、係数の期待値は $\frac{i+1}{2}$ となります。

結論、 $A_i$ を降順ソートしたうえで $A_i\times 2^{2N-1}\times \frac{i+1}{2}$ の総和が解となります。

最後にこちら。

F - Surrounded Nodes 

この問題の「穴あき度」は、「$S$ に含まれる白く塗られた頂点の数の期待値」、言い換えれば「ある頂点 $i$ が $S$ に含まれる確率の総和」です。

「ある頂点 $i$ が $S$ に含まれる確率」は、「 $i$ から出る少なくとも $2$ つの辺について、( $i$ から見て)その先にあるノードが $1$ つでも黒い確率」です。

この「少なくとも2つの辺に...確率」は「 $1-$ (1つ以下の辺について…確率)」です。「ある辺について、その先に黒が $1$ つでもある確率」はその先にノードが $k$ 個ある場合 $(1-(\frac{1}{2}{)}^k)$ です。これはdp[ノード $v$ ]={ $v$ の部分木にあるノードの数}という 木DP を使うと求められます。

<練習問題> 

ネタバレ部分は反転文字で書いているので、必要があればテキストを選択して読んでください。

E - Max-Min Sums (500点問題)

「集合 $X$ に対する $f\left(X\right)$ の値」を [配列を昇順ソートしたうえで]「min=a , max=b となるような区間の数」に主客転倒。[同じ長さの区間は累積和でまとめて計算できる。]

Max-Min Sums [AtCoder Beginner Contest 151 E] - はまやんはまやんはまやん (上記とは別の方針での主客転倒)

<まとめ>

「和の形の数え上げ」を見たら、「主客転倒」バックで解く(「どういう「主客転倒」をすると楽に数えられそうか?」を考えて解く)とかなり楽になることが多いです。

ちなみに、この記事でやっていることは結局、「和の形のコストのまとめ方を変える」ということです。コストが積の形などで一見うまくいかなさそうな問題もうまく何らかの和の形に落とし込めばこの手法が効いたりします。(cf. C - Cookie Distribution )

さらに、これは憶測なのですが、「何かしら数えたいものをどうにかして何かしらの和の形に落とし込むとこのテクに帰着できたりする」まで全体の流れをバックで強く意識するともしかすると数え上げがもっと解けるようになるのかな…?とも思っています。これは筆者が身をもって実験していこうと思います。

では、皆さんよい「主客転倒」ライフを!

物理好きさん1人に聞きました!よくやる音ゲー練習法

この記事は、 プログラマーのオススメのゲームの話をする Advent Calendar 2019 - Adventar の24日目の記事として執筆されました。

競プロerの物理好きと言えば音ゲーですよね、ということで音ゲーの話をします。

といっても、特定機種の布教…というよりは「どんな音ゲーでもだいたいこんなことをすれば上手くなる」という大枠の練習法のフレームみたいなことをお話しします。

 (とはいえ、僕のメイン機種である CHUNITHM CRYSTAL (チュウニズム クリスタル)｜セガ新音ゲー を念頭に置いて記事を書いていたりはします。基本操作が音ゲーの中でもかなり簡単なのにAIRという新しい操作感も味わえるので初心者にも少し慣れた方にもオススメです。)

1.まず、知っている好きな曲をやってみる

 「音ゲーといっても何をやっていいかわからない…」という場合には、まず好きな曲をやってみましょう。プレイ前にチュートリアルがあると思うので基本的な操作はそこで覚えておきたいのですが、やはり、知っている好きな曲だと「リズムが分かる」というアドがあります。これはかなり大きいです。まずは一番下の難易度でもいいので、知ってる曲をやりましょう。(知らない曲をやってなんのこっちゃわからない…というのは非常に勿体ない(個人の意見)です)

2.できる難易度の上限を見計らう

その機種を少し頑張ってみようかな…と思った場合、まずやるのが「できる難易度の上限の把握」です。まずは(ある曲の)一番下の難易度から入るのが安全(クリアに失敗すると次のトラック(曲)に進めなくなる機種もあるので)ですが、その難易度が「つまらない」と思ったら思い切って難易度を1段階上げてよい(BASIC→ADVANCED→EXPERT→MASTER)です。暫定的に自分がどれくらいの難易度の譜面ができるというのが分かったら、今度は難易度を表す整数で調整しましょう。Lv9あたりがクリア余裕そうならLv10に上げてみたり、Lv12が難しそうならLv11+に落としてみたり…といった具合です。ここまでの調整がてらその機種を頑張ってみようかどうかの判断はだいたい数百円くらいの投資で可能です。

3.ハイスピード調節

音ゲーを始めたいなと少しでも思っている場合、「ハイスピード」の概念は理解していた方がよいです。「ハイスピード」とは、ノーツ(音符)が降ってくる速度のことで、主にそのゲームの設定で変更できます(変え方は機種ごとに違うのであらかじめ調べておくと吉)。ノーツが降ってくる速度が遅いと、ノーツが見分けにくくなり、正確なリズムも把握しにくくなります。逆に、ノーツが降ってくる速度が速いと、ノーツが読み切れません。なので、個人に合ったほどよい速度に合わせて調整してやると、快適にプレイできます。(基本的には、慣れてくるほどハイスピードは上がることが多い(細かいリズムの把握がしやすくなるので)です。)

4.知ってる曲アド練習法

ここからはざっくり自分のよくやる練習法をいくつか紹介します。まずは、「知ってる曲」というアドを利用して練習する方法。自分の知ってる曲はリズムを知っていて有利だという話は先ほどもしましたが、そのアドは音ゲーをやっている限りずっと続きます。自分の知っている曲だと、知らない曲に比べてだいたい(整数の方の難易度で)1段階から2段階くらい上の譜面でも行けてしまうことが往々にしてあります。知っている曲なら、ちょっとまだ難しいか…?というような曲でもためらわずどんどん攻め込むことが大事です。

5.チャレトラ練習法

チャレトラとは、もとは「チャレンジトラック」というmaimaiにあった難しい譜面を条件付きで最終トラックに挑める…といったものなのですが、ここで紹介するのはその思想を借りた練習法です。というのも、最終トラックに少し難しい譜面をやってみるということです。クリアが次のトラックの進出条件になっている(コナミ製音ゲーに多い)場合でも、最終トラックならクリアできなくてもほとんど損害がありません。それをいいことに、例えば(Lv13→Lv13→Lv14)とか(Lv17→Lv18→Lv19)とか、自分ができそうな難易度の上限の1つ上を最終トラックに組み込むことで、難易度の壁を徐々に破っていくことが出来ます。

6.ナイト・オブ・ナイツ練習法

突然ですが、この世には ナイト・オブ・ナイツ という超有名な東方Projectのアレンジ曲があります。この曲はある程度沢山の機種に収録されていて、音ゲーの練習に非常に適しています。理由をいろいろ説明します。

• リズムが非常に縦ノリで覚えやすくノリやすい
• BPMが180と、「そこそこ速い曲」の入り口くらいの速度であり、スピード感に慣れられる
• そのせいか、めちゃくちゃ難しくはないがどの機種でもある程度高めの難易度の譜面が用意されていることが多い
• 8分や16分のリズム感がバランスよく取り入れられている
• 譜面にその機種の癖が出にくく、音ゲー慣れしていればすぐにいいスコアが狙える

 あたりがナイト・オブ・ナイツが練習にいい理由です。個人的には、どの機種でも、ナイト・オブ・ナイツのある程度上の方(概ねその機種の一番上の譜面(MASTERとかMAXIMUMとか)の数値の難易度の平均値以上)の難易度の譜面ができればその機種については相当慣れてきたと言えます。

7.高難度と低難度はバランスよく

「自分ができるギリギリの高難度をやっていて楽しいからそればかりしてしまう…」「チキって高難度ができない…」といった話は、(実力を伸ばしたいという場合には)あまりいい話ではありません。実力を手早くつけたい場合には、低難度(といっても、自分がある程度高い精度を取れるくらいの難易度まで落とせば十分)で高い精度を出す練習もしつつ、高難度にも果敢に挑戦していくという姿勢が大事です。バランスを保とうとするとだいたい難易度の数値の差にして2前後の範囲になるかと思います。

8.「最高評価」を出してみる

その機種において、どんなに簡単な譜面でもいいので、最高評価を出してみましょう。ランクSSSとかの最高ランクでも、FULL COMBO(ノーミスプレイ)でも、ALL JUSTICE,ALL PERFECTのようにかなり高い判定だけに絞ったものでも構いません。これを出すことは、高い達成感とモチベ、さらには「あの曲でもできたしこの曲でもできるかも…?」というようなモチベーションにつながります。

9.同じところのミスが続く場合、そこを意識して手の動きを検討する

同じところでミスが続く場合、自分に何らかの落ち度が多分あります。その場合、自分の手の動かし方があまりよくない…といったことも考えられるので、「どこでいつもミスるのか」を強く意識してプレイしつつ、その場所が来たら自分があらかじめ用意した対策を強く意識して手を動かすことが大事です。

10.究極奥義、理論値狙い

これはおまけなので聞き流してもらって構いません。音ゲーには、「理論上可能な最高スコア」、即ち理論値というものが存在します。当然これは全プレイヤーの憧れになります。ここでは、その理論値をある程度出るようにするところまでを簡単に説明します(実際僕もメイン機種のCHUNITHMでさえちょいちょい出せるかも…程度なので…)。まず、FAST/LATE表示のようなものを利用し、自分が速いか遅いかをよく吟味する必要があります。ただ、そのうえで言うと、たいていの場合自分が速いです。なので、高い精度を出すということは遅め意識とほとんど変わらない…と思ってもらっても大丈夫です。そのうえで、その曲をある程度理解して16分トリルまでの忙しさの譜面なら理論値で抜けられることが多い…くらいにはしましょう。そのうえで、いつも同じ場所で理論値が崩れるならそこを意識する…といったことと、最初のうちは相当理論値が出しにくいのでめげずに頑張ってみる…といったことをすると、ある程度は出せるようになっています。ただ、人によってはコンプレックスになるレベルで出ないこともあったりします。その場合は高難度に対する実力をつけることが理論値を出やすくする回り道だったりもします(実際自分はそうだったかも知れません)

<まとめ>

ここまで雑多に練習法をまとめてきましたが、実際にはやり方は人それぞれです。一番大切なのは楽しむことなので、ノリと勢いでいい感じに練習して楽しい音ゲーライフを目指しましょう!

線形でできる予計算的な処理まとめ

この記事は、 Competitive Programming (1) Advent Calendar 2019 16日目の記事として執筆されました。

今回は、 線形時間、すなわち $O\left(N\right)$ でできる予計算的な処理をいろいろとまとめてみようと思います。思いつくがままに並べているだけなので、ヌケモレがけっこうあると思いますが、「こういうのも線形前処理だよ～」みたいなのがあればTwitterとかで連絡していただければ随時足していこうと思います。なお、ここでの予計算的とは完全に個人の主観でちょっとでも「予計算っぽい感じあるかな」って思えば入れています。かなり基準が適当なのでそのへんはご容赦を。

数値計算系

順列の生成

$1,2,...,N$ からなるランダムな順列が1つ欲しい時、これは $O\left(N\right)$ で可能です。マラソンとか乱択とかで役に立つ時が多分あります。具体的には以下のような手順です。

$A\leftarrow \{1,2,...,N\}$ の順列(1-indexed)とする。

for $i=N..1$ step $-1$

  $p\leftarrow (1$ から $i$ までの乱数)

  $A\left[p\right]$ と $A\left[i\right]$ とをスワップする。 

累乗の予計算

$A\left[k\right]=X^k$ のテーブルをあらかじめ構成するのも $O\left(N\right)$ で可能です。但し、 $A[i+1]\leftarrow A\left[i\right]\times X$ というように安直に求めてしまうと、Xが実数である場合に誤差が蓄積してしまいかねません。ここでは、各要素についてその値に至るまでに行われた乗算の回数が $O\left(\log N\right)$ となる実装を紹介します。

// $A\left[i\right]=X^i$ となるようにしたい

$A\left[0\right]\leftarrow 1$

$A\left[1\right]\leftarrow X$ 

for $i=\mathrm{2..}N$

  $A\left[i\right]\leftarrow A\left[i/2\right]\times A[i/2+i\%2]$

ちなみに、行われた乗算の回数が $O\left(\log N\right)$ となる理由は、 dp[行われた乗算の回数]$=\left\{max\right(dp\left[i/2\right],dp[i/2+i\%2])+1\}$ というようなDPをイメージすると理解できます。

nCrをO(1)で求めるための予計算、逆元

$nCr=\frac{n!}{r!(n-r)!}$ なので、これを $O\left(1\right)$ で求めるためには $k!$ とその逆元が求まっていればよいです。 $k!$ を求めるのは容易ですがその逆元を愚直に求めていると予計算テーブルの構成に $O\left(N\log mod\right)$ かかってしまいます。

しかし、以下のように求めると $O(N+\log mod)$ で計算可能です。 $N>>\log mod$ なのでこれは線形です。誰が何を言おうと線形です。

$A\left[i\right]\leftarrow \{i!\}$ と求めておく。

$B\left[N\right]$ を $A\left[N\right](=N!)$ の逆元とする。

for $i=(N-1)..0$ step $-1$

  $B\left[i\right]\leftarrow B[i+1]\ast (i+1)$

  //ここで、 $B[i+1]$ は $i!\times (i+1)$ の逆元なので、ここに $i+1$ を掛けると $i!$ の逆元となる。

逆元についての説明など、さらに詳しくは 「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 - Qiita を参照してください。

また、いくつかの数の逆元をまとめてとることも $O(N+\log mod)$ で出来ます。詳しくは 逆元 - yukicoder Wiki を参照してください。

素数テーブル+(1を除く)最小の約数テーブルの構築

素数テーブルをO(n)で構築する - 裏紙 で示されているものなのですが、エラトステネスの篩を使って $O\left(N\log \log N\right)$ かかる素数テーブルの構築を $O\left(N\right)$ でできます。副産物として、mind[i] = {iの(1を除く)最小の約数} という配列もまとめて $O\left(N\right)$ で得られます。

データ構造系

配列の初期化

これはとても自明な前処理レベルのことですが、配列の各要素の初期化は $O\left(N\right)$ で可能です。いい感じにループを回せば任意の値で初期化できたり、乱数表を格納したりもできます。逆に、配列を重いループの中で愚直に初期化してしまうと重いループの中で線形かかってしまうので、「逆の手で初期状態に戻せる」ような状況ならそちらがベターです。

バケットソート

バケットソートは、値の最大値にも多少計算量が依存しますが、基本的に要素数に線形な時間で backet[i]={iが配列中にいくつ含まれるか}という配列が構成できます。値の最大値が ${10}^5$ 程度もしくは座標圧縮してその程度にできるなら、ソートとしてバケットソートを意識してから問題を解くと見通しがいいことがあります。

0/1配列において自分まで何連続で1が続いたかをまとめて求める

要素数 $N$ の0/1配列$arr$について、$A\left[i\right]=\left(\right[i-k+1,i]$がすべて1である最大の$k)$が求めたいとします。例えば、$arr=\left\{01101111\right\}$に対して$A=\{0,1,2,0,1,2,3,4\}$です。これは、以下の単純なアルゴリズムで配列全体で $O\left(N\right)$ で求まります。

$A\left[0\right]\leftarrow 0$

for $i=\mathrm{1..}N$

  if $arr\left[i\right]=0$ then $A\left[i\right]=0$

  else $A\left[i\right]=A[i-1]+1$

これは二次元、それもグリッドっぽい感じの問題で頻出な処理で、この処理を使うと見通しが良くなる問題も結構あります。

BITやSegment Treeの初期化

 それぞれのデータ構造については、 http://hos.ac/slides/20140319_bit.pdf , Binary indexed tree , セグメントツリー入門 , セグメント木 - 個人的な競プロメモ などを参照してください。

BITの初期化が $O\left(N\right)$ というのは見るからに要素をN個しか使っていないため自明ですが、Segment Treeの場合だと、ノード数が $2N$ 程度であるという事実があるので0初期化以外の初期化も $O\left(N\right)$ で可能、というわけです。愚直な初期化だと $O\left(N\log N\right)$ かかってしまうので、初期化についていい感じの実装をしてやると(計算時間的に)お得です。

累積和

何らかの値が入った配列 $A$ があるとします。ここで、この配列に対して $L_i$ 番目から $R_i$ 番目までの和をたくさん求めたいとします。(例えば、DPをするときにkeyが $[L_i,R_i]$ のものだけを遷移させたいとか)

以下のような線形予計算をしておくと、これはクエリあたり $O\left(1\right)$ で可能です。

$B\left[0\right]\leftarrow 0$

for $i=\mathrm{1..}N$

  $B\left[i\right]\leftarrow B[i-1]+A\left[i\right]$

クエリに対しての回答( $L_i$ 番目の要素から $R_i$ 番目の要素の総和)は、

$B\left[R_i\right]-B[L_i-1]$

詳しくは 累積和を何も考えずに書けるようにする！ - Qiita も参照してください。

imos法

先ほどの累積和の応用、言わずと知れた いもす法 - いもす研 (imos laboratory) です。これも線形前処理っちゃそうかな～という感じなので入れます。

全ての要素が0である長さ $N$ の配列に、「範囲 $[L_i,R_i]$ の要素すべてにちょうど $X$ を加える」という形のクエリが $Q$ 個あるとします。

このクエリが最初にあらかじめ与えられるなら、以下のような処理でクエリをすべてまとめて $O(N+Q)$ (配列の長さ+クエリ数に線形)で実行可能です。

$A\leftarrow \{0$ で初期化された長さ $N+1$ の配列$\}$

 for $i=\mathrm{1..}Q$

  $A\left[L_i\right]$に$X$加算、$A[R_i+1]$を$X$減算

for $i=\mathrm{1..}N-1$

  $A[i+1]$ に $A\left[i\right]$ を加算

このimos法の次元を引き上げれば、「二次元上のある長方形の範囲に $X$ 加算する」といったことも可能です。そちらも先ほどのリンクを参照してください。

文字列系

文字列の長さを求める

非常に自明なことですが、文字列の長さを求めるのには $O\left(N\right)$ かかります。逆に言うと、文字列の長さを求める関数では1回あたり $O\left(N\right)$ かかってしまいます。場合によっては一度求めた長さを保存しておくなどすることが必要です。 

シーザー暗号的なもの

これは予計算というよりもはや前処理なのですが、convert[(変換前の文字)] = {変換後の文字}というような配列を構成しておけば、例えばconvert[(小文字)] = {そのまま}、convert[(大文字)] = {同じ文字の小文字} のような配列を作っておくと、大文字小文字吸収にかかる処理時間が文字列の長さに対して線形となります。

Trieの構成

Trieは、ざっくり言うと複数の文字列(の接頭辞)を管理するデータ構造です。詳しくは トライ木 - Wikipedia をご覧ください。このTrieの構成も文字列の長さに対して線形で可能です(実際は文字種が多いと実装によってはそれだけ定数が大きくなりますが)。ちなみに、文字列の追加が発生しないような条件下で、子が1つしかないノードをつぶして圧縮するといったことが要求されることもあり、この圧縮もノード数に対して線形で可能です。 E - Lexicographical disorder がその例です。(これを行うと検索にかかる時間が「文字列の長さに線形」から「絡む分岐の数」へと高速になります)

RollingHash

文字列 $S$ からある区間を取ってきたときに、「区間と与えられた文字列が等しいか?」や「区間同士が等しいか?」などを(確率的に)判定したいときに重宝するのがこのRollingHashです。

ここでは、ある長さ $K$ の文字列 $s(=s[1\left]s\right[2\left]s\right[3]...s[K\left]\right)$ のハッシュ値を

$hash\left(s\right)=id\left(s\right[1\left]\right)\times bas{e}^{K-1}+id\left(s\right[2\left]\right)\times bas{e}^{K-2}+...+id\left(s\right[K-1\left]\right)\times base+id\left(s\right[K\left]\right)\mathrm{mod}M$

$id$ は、 $id{(}^{\prime }{a}^{\prime })=1,id{(}^{\prime }{b}^{\prime })=2,...,id{(}^{\prime }{z}^{\prime })=26$ のような、文字を相異なる数値に変換するなにかしらの関数。

$M$ は、適当な定数。(これは素数が推奨される)

と定義し、これを高速に求めることを考えます。文字列が等しければこの値が一致しますが、逆は成り立ちません。(但し、異なる文字列が同じハッシュ値を取ってしまう確率は実際には低いです。)

まず、長さ $N$ の文字列 $str(=str[1\left]str\right[2\left]str\right[3]...str[N\left]\right)$ に以下のような線形の予計算をかけます。

$A\left[0\right]\leftarrow 0$

for $i=\mathrm{1..}N$

  $A\left[i\right]\leftarrow A[i-1]\times base+id\left(str\right[i\left]\right)\mathrm{mod}M$

 すると、区間 $[i,j]$ を抜き出した文字列 $str\left[i\right]str[i+1]...str\left[j\right]$ に対してのハッシュ値は

$A\left[j\right]-A[i-1]\times bas{e}^{j-(i-1)}\mathrm{mod}M$

と、1回あたり $O\left(\log N\right)$ で求められます。

ハッシュやRollingHashの詳しい説明はハッシュ関数 - Wikipediaや安全で爆速なRollingHashの話 - Qiitaを参照してください。

文字列に関する線形アルゴリズム

文字列の頭良い感じの線形アルゴリズムたち - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ でいくつかの文字列に関する線形時間のアルゴリズムについて有名になりました。詳細や実装は出題された時に写経すればどうとでもなるとしても、どのアルゴリズムを使えば何が線形でできるか知っておいて損はないでしょう。

Z-Algorithm: table[i] = (i文字目を先頭にして、文字列全体の接頭辞と何文字目まで一致するか)

Manacher: table[i] = (i文字目を中心にする、最長の回文の半径はいくらか)

KMP: table[i] = (先頭からi-1文字目までを抜き出したとき、接頭辞と接尾辞が最大何文字一致するか)

という長さ $N$ の配列をそれぞれ全体で $O\left(N\right)$ で求めることができます。

<あとがき>

線形で出来る予計算、いろいろまとめてみたら面白いかもな～って思い立ってまとめてみましたが、結構あるけど思ったよりはない…って感じの分量になりました(引き出しの狭さを痛感しています)。たぶんまだけっこうあると思うので、これも入れてほしい!みたいなものがあればご一報ください。知識の幅をどんどん増やして線形爆速アルゴリズマーになりましょう!(?)

Point Ordering(CF#601 Div1-C)

Problem - C - Codeforces

座標平面上のある凸多角形を構成する$N$点の点集合 $A_1,A_2,...,A_N$がある。
あなたはこの点集合に対して以下の$2$種類のクエリを合計で高々$3N$回問い合わせることができる。

• クエリ$1$ : 三角形$A_i{A}_j{A}_k$の面積の$2$倍を尋ねる。
• クエリ$2$ : $\overrightarrow{A_i{A}_j}\times \overrightarrow{A_i{A}_k}$(ベクトルの外積)の符号を尋ねる。返答が$1$のとき正、$0$のとき零、$-1$のとき負である。

どちらのクエリも尋ね方はt i j k($t$は$1$または$2$のクエリ種別)であり、$1\le i,j,k\le N$かつ$i,j,k$は相異なる必要がある。

この時、以下の条件を満たす要素が$1,2,...,N$である順列$P=\{P_1,P_2,...,P_N\}$を復元せよ。

• $P_1=1$
• $A_{P_1},A_{P_2},...,A_{P_N}$はこの順番で反時計回りに凸多角形を構成する。

なお、ベクトルの外積の定義はもとの問題文にもあるように、$\vec{A}\times \vec{B}=A_x{B}_y-B_x{A}_y$です。外積をスカラーとして扱うあれ。包囲(ttpc2015-H) - physics0523's 精進ログでも用いたものなので、詳しくは当該記事も参照。

とりあえずの発想としては、多角形のある$1$辺$XY$を特定した後、そこに他の頂点を加えてできた三角形の面積は加えた頂点の反時計回り順で見ると単調増加→単調減少となる…といったもの。(ちょっと図で線が混み入ってるのはご勘弁を。) 

 とりあえずある$1$辺$XY$がなんとかして特定できたとして話を進めます。

このとき、$XY$に加えて面積最大となる点を$Z$とします。

すると、$\overrightarrow{XZ}\times \overrightarrow{X{A}_i}$の正負で$A_i$が$X$から見て時計回り側にあるのか反時計回り側にあるのかがわかり、面積の(適切な)順でソートすると点集合が多角形を構成するように点をソートできます。以下の図のようなイメージです。

実装時は、$i,j,k$は相異なる必要があること、即ち、面積$0$となる質問をしてはいけないことや、同じベクトル同士の外積を尋ねてはならないことに注意してください。

さて、ここまで、面積の問い合わせと点がどちら側にあるかの判定でクエリを$2N$回弱使いました。

あと$N$回で多角形の$1$辺を特定します。

これは、以下のようなアルゴリズムで可能です。

1. 適当な$2$点$X,P$をとり、それらを調査済みにする。
2. まだ調査済みでない点が残っている場合、その点を$Q$とする。
3. もし、$\overrightarrow{XP}\times \overrightarrow{XQ}<0$だった場合、$P\leftarrow Q$とする。
4. $Q$を調査済みにし、2に戻る。
5. 最終的な$XQ$は多角形の$1$辺である。

感覚的な証明は図のような感じです。$N$回程度の比較で最小値を求めている感覚に近いかも…?

 これを行うことにより、計$3N$回弱のクエリでこの問題が解けました。

実装の際、$X=A_1$としてやると問題の要求に沿った順列を復元しやすいです。

Submission #65378844 - Codeforces