テルの競プロメモ

競プロに関するメモ

数弱による ABC168-E "・(Bullet)" 解説

かなり詳しい解説記事は既にあったのですが、
自分は数弱で、ちょっと難しいと思った部分もあったので、詰まった箇所を補足します。

余りの計算や連想配列(map)に pair を入れるやり方に慣れておらず苦しみましたが、楽しんで解けました。
この map の使い方は、結構役に立つ気がします。



今回は、以下のブログ記事を参考(というか解法自体はそのまま同じ)に解きました。
AtCoder ABC #168 : E - ∙ (Bullet) - kmjp's blog

余りの計算は、こちらが参考になりました。
「1000000007 で割ったあまり」の求め方を総特集! 〜 逆元から離散対数まで 〜 - Qiita

問題

E - ∙ (Bullet)

難易度:AtCoder Problems での Difficulty : 1836(青中位)

自分の提出

概要

コンテスト中は、この問題はどう整理していいか分かりませんでした。
ここが数弱たる所以ですが、ともかくこの問題は、まず数式的に考えて整理しないといけない問題だったようです。

具体的には、2つのアプローチがありますが、どちらも結論は同じになります。
(一旦、美味しさや香りがゼロになる場合のことは考えずに進めます。)

1. 与えられた数式 Ai*Aj + Bi*Bj = 0 を変形する
2. イワシの性質 (Ai, Bi) を、平面上の座標(ベクトル)と考える

<1. 式変形>
与えられた数式を変形すると、Bi/Ai * Bj/Aj = -1 となります。
これだけでも問題は解けるのかもしれませんが、数弱的に、式変形しただけだとなんだか怖い(?)ので、2. に進みます。

<2. 平面上の座標と考える>
座標と考えるって何やねんって感じですが、下図のとおりです。
イワシiの(美味しさAi, 香りBi)を、(A, B)を座標軸とする平面上の点だと考えます。
f:id:TeruMiyake:20200518171140p:plain

図の中には2尾のイワシ i, j がいることになりますが、実は、問題で与えられた Ai*Aj + Bi*Bj = 0 というのは、この2つのイワシの傾き(原点からイワシに向けて引いた直線)が垂直に交わっているということらしいです。
(ベクトルが直交している時、それらの内積は0、ということらしいです)

また、「傾きが垂直ということは、お互いの傾きを掛け合わせると -1 になる」という数学の知識があります。
傾きというのは、普通のxy平面だと y/x, つまり今回で言うと Bi/Ai のことですから、やはり Bi/Ai * Bj/Aj = -1 という結論が出てきました。

ちなみに、こうして座標で考えてみると、「仲が悪くなるペアは固定されていて、複雑に絡み合っていない」という重要な事実が分かります。
現実の複雑な人間関係のようにはなっていなくて、傾きが垂直になっているペア同士が仲が悪いだけで、それ以外の組み合わせは全員仲が良いということです(0が絡む場合は別ですが)。

自分はこれが分からず、複雑な人間関係の相関図みたいなものをイメージして迷宮入りしました……。

解法の概要

さて、どうやら、Bi/Ai * Bj/Aj = -1 となるようなイワシは仲が悪いので、それをなんとかしてうまい感じに数え上げればいいという気がしてきました。

……しかし、ここでまた詰まりました。
一体何をどうやってどのように数え上げれば、解法にたどり着けるか全く分かりません。

これは、連想配列C++ でいうと map )を賢く使うことで解決します。

f:id:TeruMiyake:20200518171119p:plain

「各イワシを、水槽に分けていく」ということを考えます。
水槽に分けて数を数えていくことが、バケツソートで使うバケツの考え方に似ていますので、バケツと呼ぶことにします。

今回は、「2つのセクションに区分されたバケツ」を沢山(最大N個ほど)用意します。
このバケツに、各イワシ「お互いに仲の悪いイワシは、同じバケツの別のセクションに」入れていきます。

バケツに入れ終わったら、最後に「同じバケツの違うセクションからは同時にイワシを取らない」ということに気を付けながら、数え上げをすればいいということになります。
(公式の解説PDFだと、ここまで分かればあとは基礎的な数え上げの範疇、と言っているのだと思います)

どんな連想配列を作ればいいか

今回は、普通に連想配列C++でいうとmap)を使っても解けません。
イワシの傾きごとにバケツ(連想配列の各要素)を作りたいのに、傾きは整数ではなく実数だからです。
実数を連想配列のキーにできればいいですが、誤差があるので多分難しいです。

ということで、今回は連想配列のキーとして、タプル(C++でいうと今回はpair)を用います。
連想配列[(a, b)] = (セクション1のイワシの数, セクション2のイワシの数)
となるように、keyにもvalueにもintのタプルを持つ連想配列を作って、それをバケツとして使います。

注意点1

ここで注意点があります。
これが今回の重要なポイントで、難しい部分だったと思います。

例えば、(1, 2) のイワシと (-2, 1) のイワシは仲が悪いですが、同様に (2, 4)のイワシや、(3, 6)のイワシ、また、(-1, -2) のイワシも、(-2, 1) のイワシと仲が悪いのです。
つまり、「具体的な値は違うけど、傾きが同じイワシ」は、同じバケツに入れなければいけないということです。

これを解決するためには、最大公約数(gcd)を使います。
(2, 4) や (3, 6) や (-1, -2) のイワシは、結局のところ、「(1の倍数, 2の倍数) のイワシと言い換えられます。
ということは、(a, b) の 最大公約数で割って互いに素な状態にし、(負, 負)なら符号をひっくり返して(正, 正)にすれば、統一した表現に変えられます

また、(-1, 2) と (1, -2) なども同様に、傾きは同じ別のイワシということになっています。
これらも統一しないといけないため、(正, 負) のものは符号をひっくり返して、(負, 正)に統一することにします。

この統一化の作業を、参考として挙げた記事では「正規化」と呼んでいます。
公式の解説PDFだと、「既約分数で表す」に当たる部分です。

注意点2(ゼロが絡む場合)

ゼロが絡む場合は、特殊なバケツに入れて区別します。

<(0, 0)のイワシ
まず、美味しさも香りも 0 のイワシは、どんなイワシと組み合わせても 数式の答えが0になるので、どんなイワシとも組み合わせられない(もちろん、(0,0)のイワシ同士も組み合わせられない)孤高のイワシです。
よって、そいつ専用のバケツ(図の右下)に入れます。

<(0, *), (*, 0) のイワシ
次に、(0, 任意の整数), (任意の整数, 0) のイワシです。
こいつらは、数式に当てはめてみると、お互い仲が悪く、また、(1~N, 1~N) の普通のイワシとは仲が良いと分かります。
よって、この組み合わせは2つのセクションに区分されたバケツに入れたいです。
そこで、こいつは「(0, 0)」とラベルのついたバケツに入れることにします。
本当は(0, *), (*, 0)なので違いますが、こうすることで、最後の計算を統一的に行うことができます。

実際の数え上げ

これで、各イワシをバケツに入れることができました。
あと少しです。
MODのとり方に気を付けながら、丁寧に計算をしていきます。

1. 普通のイワシ((0, *), (*, 0) のイワシも含む)の取り方

各バケツの両方のセクションから同時に取ることはできません。
なので、各バケツからの取り方は「セクション1の取り方の個数」+「セクション2の取り方の個数」となります(同時に取れないので「×」ではなく「+」)。
セクション1からの取り方は、各イワシの数だけ「取るか取らないかの2択」をするわけなので、2^イワシ です。
ということで、 2^セクション1のイワシ数 + 2^セクション2のイワシ数 としたいですが、これだと「1つもイワシを取らない場合」をダブルカウントしていますので、
2^セクション1のイワシ数 + 2^セクション2のイワシ数 - 1 が正解です。
(なお、引き算をするときにはMODが負になることがありますので、負になっていたら + MODをしなくてはいけないので注意です。)

各バケツ毎の取り方の組み合わせは自由なので、毎回の計算で出た数値は足していくのではなく、掛けていきます

2. 孤高のイワシの取り方

孤高のイワシは、他のどんなイワシとも一緒に入れることができません。
別の言い方をすると、「そいつ1匹でしか入れられない」ということです。
ということで取り方は「孤高のイワシの数」そのものです。

また、孤高のイワシを取る場合は普通のイワシを取れないので、これは掛け合わせず、足し算をします。

3. 何も取らない場合はNG

イワシを1匹も取らない場合」は問題の設定に合わないのでNGです。
1. の計算の際、各バケツでイワシを1匹も取らない場合を含めて計算していますので、「全バケツでイワシを1匹も取らなかった場合」も答えにカウントしてしまっています。

ということで、最後に1を引いて、出来上がりです。
(私はここでまた「負になった場合に+MODする」のを忘れて、10分バグらせ続けました。)

類問

atcoder.jp

問題を読んでも「え? これ類問?」となるかもしれません(実際、公式解説PDFにも想定解として載っていません)が、
今回のように「mapで作ったバケツにpairを入れる」テクと、またもやバケツにおけるテクである「バケツに数以外(boolなど)を入れる」というテク(今回は使っていないですが)によって、かなり直感的に分かりやすく実装しやすい解き方ができます。

提出コード

AGC036-B "Do Not Duplicate" の周期性について

問題

B - Do Not Duplicate

この問題は、周期性をO(N)で求めることができて、それを使って解けるらしいが、以前はそれが理解できなかった。
結局、その時はダブリングを使って解いた

悔しかったので改めて考え直し、なんとか証明を理解できた(と思う)。
ネット上で見つかるこの周期性についての解説記事では、説明が簡潔だったり、高度に数学チックだったりで、自分には理解できないものが多くて苦労した。
そこで、証明の過程をメモしておく。

概要

問題の入力例4を例にとって考える。
元の数列は {3 1 4 1 5 9 2 6 5 3 5} なので、問題の手順を進めていくと、以下のように状況が進む。
以下の色分けは、処理が始まって、一度数列が空になるまでを示す。(例えば最初の赤色の部分で言うと、先頭の3がもう一度出たときに数列が空になる)
この動き1つ1つを、3の直前から次の3の直後にジャンプする感覚で、「ジャンプ」と呼ぶことにする。
この例の場合、3から5、5から9、9から2にジャンプしている。

[3 1 4 1 5 9 2 6 5 3] [5
3 1 4 1 5]
[9 2 6 5 3 5
3 1 4 1 5 9]
[2 6 5 3 5



このジャンプについて、以下のことが成り立つと色んな記事で言われていた。
・「初期状態(a0=3を数列sに加える前の状態)から、何ジャンプ目(何回数列が空になったか)に再び先頭(数列sが空の状態で、次に数列に追加しようとする要素がa0である状態)に戻ってくるか」を、O(N)でシミュレーションして求めることができる

これができれば、(操作の回数の計算などはとりあえず置いておくとして、)確かに計算量的には「O(N)で求め、操作回数がKを超えないギリギリのところまで周期を使って処理をすっ飛ばし、残りを愚直にシミュレーションする(残りの操作回数はK%(1周期のジャンプ数)なので間に合う」という感じはするけど、本当にそうなのか疑問だったし、やり方も分からなかった。

疑問に思った箇所

色々と分からなかったが、大きく3つの疑問があった。

1. ジャンプ回数は少ないかもしれないが、操作の回数はそれよりずっと多い。その処理はどうすればいいのか。その処理は本当にO(N)で間に合うのか
2. そもそも、本当にどこかで周期するのか
3. 周期するとして、初期状態には必ず戻ってくるのか(どこか途中の箇所でグルグルとループしてしまうことはないのか)

疑問1. ジャンプをどのように計算するか

各ジャンプを考えるとき、愚直に1つずつ操作を進めていくと、到底間に合わないので、工夫する必要がある。

入力例4で考える。
まず、数列内の各要素(Ai)を同じ数毎に分け、「どのインデックスで登場したか(何番目に登場したか)」を配列として持っていく。
数列が{3 1 4 1 5 9 2 6 5 3 5}なので、以下のような形(0-indexed)。
1 : {1, 3}
2 : {6}
3 : {0, 9}
4 : {2}
5 : {4, 8, 10}
6 : {7}
9 : {5}

こうすると、「どこの直前からジャンプすると、どこの直前に着地するか」を求めることができる。

例えば、a1=1 の直前からジャンプすると、次に1が出るのはa3なので、a4の直前にジャンプする。
また、a4=5 の直前からジャンプすると、次に5が出るのはa8なので、a9の直前にジャンプする。
a7=6の直前からジャンプすると、次に6が出るのは同じくa7なので、a8の直前にジャンプする。

このように、各配列内に入れたインデックスに順番に着目していくことで、「どこからどこにジャンプするか(遷移元と遷移先)」をO(N)で確認することができる。
具体的には、今回の場合だとスタート地点がa0=3なので、0->10->5->6->7->8->0 となって戻ってくる。

また、「各ジャンプにつき、実際の操作回数は何回か」というのも、登場するインデックスの差分を取れば求められるから、先程の疑問1.は解決できたことになる。
(もちろん、疑問2. 3.の周期性が前提となる。周期性がなければ、結局、O(K<=10^12)回計算しなくてはならず間に合わない。)

疑問2. そもそも本当にN回で周期するのか

これは比較的簡単に証明することができる。
(自分はよく考えないと分からなかったが、多くの人にとっては自明のことかもしれない。)

N回ジャンプしても、周期しなかったとする
すると、

[スタート地点→1回目の遷移先→2回目の遷移先→……→N回目の遷移先]

上記のスタート地点及び各回のジャンプ先が全て異なっている、つまりN+1個の異なる地点が存在することになる
しかし、地点の数はNしかない(地点とは、1<=i<=Nのことだから)ので、そんなことはありえない。
よって、N回以内に戻ってくるということになる。

というか、分かってみれば当たり前のことだった。
N回以上ジャンプするのに、N個しか地点が無いのだから、どっか同じ場所に2回以上ジャンプするに決まってる(=周期する)。

ちなみに、このことを「鳩の巣原理」というらしい。
当たり前のことのようだが、突き詰めるとすごく役に立つらしく、調べたらなかなか面白かった。
鳩の巣原理 - Wikipedia

疑問3. 本当に初期状態に戻ってくるのか

周期することは分かったが、本当に初期状態に戻ってくるのか。
どこか別の地点でループしてしまって、初期状態に戻ってこないことはないのか。
これも個人的にはわりと難しかった。

背理法で考える(そんな大げさなものでもないけど……)。
「初期状態に戻ってこず、別の場所で周期してしまう」というのは、以下のような状態である。

f:id:TeruMiyake:20200517164525p:plain
(図はGRAPH×GRAPHにて作成)

この図では、1からスタートして、1->2->3->4->5->2->3……と、2から先でループしてしまい、スタート地点の1に戻ってこない。
こういうことはありえない、と証明したい。

この図ではどうしてこうなってしまったのかと考えてみると、「地点2に、地点1と地点5の両方から遷移しているから」ということが分かる。
つまり、「異なる地点から、ある同じ地点に遷移する」ということがあるようだと、スタート地点以外でループしてしまうことがありえる、ということが分かる。

そういうことはあるのか。



2パターンに分けて考えてみる。

[先]は、「遷移先」を示す。
[消]は、今回のジャンプで消える先頭と末尾の部分(同じ数字を持つai)を示す。
※ここで地味に大事なのは、「ある場所に遷移してくる」ためには「直前の数字が出てきたとき、先頭の数字が同じ数字である」必要があるので、[先]の直前は必ず[消]であるということ。



1)[消]が数列内に1つしかないパターン
*********消先

この場合、[先]に遷移するパターンは「[消]の直前からスタートして、次の周の[消]がきた瞬間に全て消える」という1パターンしかない。
つまり、異なる遷移元から遷移してくることはありえない。



2)[消]が数列内に複数あるパターン
*消A***消B*消先

この場合、1つ目の[消]がスタート地点なら、以下の図のとおり2つ目の[消]を見た時に全消しとなり、Bに遷移してしまう。
消A***消*消先

2つ目の[消]がスタート地点なら、[先]が遷移先となる。
*消A***消B*消

3つ目の[消]がスタート地点なら、次の周で1つ目の[消]を見た時に全消しとなり、Aに遷移してしまう。
*消***消B*消先



以上から、別の遷移元から同じ遷移先に遷移しようとしても、できないことが分かった。
すると、スタート地点から遷移していった先で、スタート地点に戻ってくる前にループしてしまうことはありえないので、疑問3.も解消された。

まとめ

疑問3. の考察で、別の場所でループせず、必ず初期状態に戻って来ることが分かった。
疑問2. の考察で、そのループは、N回以内のジャンプで成されることが分かった。
疑問1. の考察で、O(N)で前計算をしておけば各ジャンプはO(1)で計算でき、N回のジャンプはO(N)で計算できることが分かった。

よって解ける! 勝利!
(実際には通してないのでコードはありません。ダブリングで一度通したのでいいやってことでサボりました。)

競技プログラミングで使われる英語の定義

競技プログラミング(というか Codeforces)で使われる英語の意味や定義をまとめていきます。

subarray, subsequence, subset, substring 及び contiguous

なんとなく「部分列」系の用語だな~とは分かりますが、字面だけだと定義が曖昧。

まず日本語の「部分列」「連続部分列」は、配列 {1, 1, 2 ,3, 3, 4, 5} に対して、以下のようなもの。
部分列:{1, 1, 3, 5}, {2, 4}, {1, 2, 3}, {5} など(連続していなくてもいい(歯抜けで取り出していい)が、順番は変わってはいけない)
連続部分列:{1, 1, 2}, {2, 3, 3, 4}, {4} など(上記に加え、元の配列の連続している部分のみ)



分かりやすいのは以下の2つ。
subsequence : 日本語の部分列にあたる
contiguous subsequence : 日本語の"連続"部分列にあたる

subarray は注意が必要で、
これは基本的に「連続部分列」、つまり contiguous subsequence と同じものを指しているようです。
contiguous という言葉が無いので「えっ……」という感じですが、複数サイトでそのような記事が出てきます。
(場合によっては、連続でないものも含んで subarray と呼んでくる場合があるかもしれませんが、一般的な用法でないと思われるので、そういう場合は指摘をする必要があるのかもしれません)

subset は、そのまま「部分集合」です。
{1, 3, 5, 7, 9} に対して{3, 5}, {7, 9}, {1, 9} など。
集合なので、そもそも順序といった考えがありません。

substring は、直訳すれば部分文字列に当たりますが、これは注意が必要で、一般的には contiguous (連続)の意味を含むことが多そうです。
ざっと検索した限りでは、日本語でも、「部分文字列」という言葉を「連続部分文字列」という意味で使っている人も多そうです。
でも、下のけんちょんさんの記事を見るに、やはり正しくは「連続」「contiguous」をつけない限りは「連続とは限らない」とするのが良いように思いますが……
qiita.com


下の記事が参考になりました
www.techiedelight.com

prefix sum

前からの累積和のこと
「累積和」の英訳としては、他に cumulative sum, inclusive scan というのもあるらしい。

Wikipediaより)
input numbers 1, 2, 3, 4, 5, 6, ...
prefix sums 1, 3, 6,10,15,21,...

Prefix sum - Wikipedia

ダブリング ~AGC036-B "Do Not Duplicate"~

問題

AGC036-B "Do Not Duplicate" 

700点問題

AtCoder ProblemsにおけるDifficulty(コンテスト中にACした場合の最低レート) : 1707

自分のACコード

 

方針

ダブリングを使う。(ということでダブリングについて書く。とはいえ、あとで「つまずきポイント」に書く通り、公式解説で「ダブリングしたらあとは楽勝」みたいな雰囲気出てるほど簡単な話ではない。少なくとも緑下位の自分にとっては他にも詰まるポイントが多数あった)

なぜダブリングを使おうと考えるのか?

ダブリングを使うのはどういう時かというと、ある操作を沢山したらどうなるかを知りたいとき。今回で言えば、数列の各数値を1つずつ見ていって、手持ち配列に加えたり削除したりすること。他にも、ある頂点から1つずつ遡って祖先を探す(ダブリングの典型であるLCA)とかがあるらしい。

使える条件は、「1回進んだ時の状態」は簡単に分かるが、ずっとず~~~っと先に進んだ状態を知ろうとすると計算時間が全然足りない、という時。

 

ダブリングとはどんな手法か?

前処理

1.「状態jからスタートして、2^i回操作を繰り返したときの状態」を DP[i][j] と定義する

 -- この時点だと「は?」という感じ

2. (重要!)DP[0][各j]を求める

 -- Q. DP[0][各j]って一体何?

 -- A. 「状態jからスタートして、2^0=1回だけ操作したときの状態」、つまり「ある状態から1回だけ操作をするとどうなるか」を全ての状態について求める。これはO(N)でいける。

3. (超重要!)遷移式 DP[i+1][j] = DP[i][ DP[i][j] ] を用いて、全てのi, jについてDPの値を求める

 -- Q. さっぱり意味が分からないんだが?

 -- A. 例えばi=3とする。DP[3][j] とは、「状態jからスタートして、2^3=8回操作をしたときの状態」である。すると、そこから更に2^3=8回操作をすれば、16=2^4回操作をしたことになる。つまり、「状態jから2^4回操作をしたときの状態 = 状態jから2^3回操作をしたときの状態 から再スタートして 更に2^3回操作をしたときの状態」ということ。

4. これで前処理が完了

 

DPの値を使って、目的のものを求める

例えば、「状態jからQ回操作をしたときの状態を知りたい」とする。

ダブリングを使わず愚直にQ回回せば当然O(Q)なので、Qが大きければTLEする。

 

Q. ここでダブリングを使うとなんで間に合うの?

A. 「2^i回操作したらどうなるか」が分かっているから、Qを2進数で見たときに立っているbit(kとする)」について、DP[k][hoge]を足していけばいい。

 

Q. は?

A. 例えば、Q=13(つまり13回操作をしたときの状態を知りたい)とする。

13を2進数として見ると 1101 なので、k=0, 2, 3のときにbitが立っている。

(ここ重要!)このとき、「2^0=1回操作をする→2^2=4回操作をする→2^3=8回操作をする」という風に考えると、ダブリングで作ったDPを活用できる。

2の累乗を使っているので、O(logQ)で処理できる。

Q回操作をしたときの状態を知るためのコード(C++
int state = 0; // 初期状態 // Qのbit桁数回ループする
for (int i = 0; (Q >> i) >= 1; i++){
  if ( Q & (1 << i) ){
    // i番目のbitが立っていたら、
    // stateに「状態stateから 2^i 回操作をしたときの状態」を代入
    state = DP[i][state];
  }
}

 

まとめ

ダブリングとは、「1回操作をしたときの状態」は簡単に分かるとき、DPテーブルを前処理しておくことで、「Q回操作をしたときの状態」をO(logQ)で計算できる手法!!

 

つまずきポイント

ACコードに至る過程において、緑下位(参加当時)の自分にとって非自明であった部分(自分がどこでつまずいたか)

自分のACコード

ダブリングは分かったけど、答えが求められない

ダブリングの考え方は分かった。「Q回操作をしたとき」、つまり「Q回空にしたあとどうなるか」がO(logN)で求められるんでしょ。でもそのQはどうやって決めるのか? N*K回数値を見なきゃいけないことは分かるけど、それまでに何回数列が空になるか分からないから、ダブリングを活用するところまで持っていけない

-- A. 決め打ち二分探索を使う。

つまり、「空にする過程で飛び越えた数値の合計がN*Kを超えない、最大のQを求める」と考える。そこから先は、愚直にシミュレーションをすれば間に合う。詳しくはコード参照。

また、二分探索、決め打ち二分探索については以下がオススメ。

二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜 - Qiita

「答えを決め打つ」タイプの二分探索を使いこなそう - ARMERIA

 

 そもそも、DP[0][j]、つまり「Ajの目の前からスタートした時、数列がもう一度空になった時に目の前にある数値のindex」をどうやって求めればいいか

 -- A. バケツを使うと時間内に求まる。数列内の数値は1~2*10^5だけなので、int[200001]に「前回登場した位置」を保持しておき、再度出てきたら適切な処理をすればいい。詳しくはコード参照。

 

ダブリングの前処理をしたあと、値を求め方が分からん

ビット演算をうまいこと使えばいける

ビット演算 (bit 演算) の使い方を総特集! 〜 マスクビットから bit DP まで 〜 - Qiita

このブログについて

方針

解説というよりは、自分用のメモとして作成していきます。

ただ、自分が文系かつ非エンジニアのため、数学的な解説が理解できないことが多いので、同じ数弱の同士の役に立てば嬉しいとも思っています。

 

作者

名前:テル

競プロを始めたタイパー

 

Twitter : @TeruMiyake

AtCoder : TeruMiyake 緑

Codeforces : TeruMiyake 水