アルゴリズム忘備録

競技プログラミングとかデータ分析とか

Codeforces Round #429 D. Leha and another game about graph

Problem - D - Codeforces

 

無向連結グラフが与えられる。自己ループはないが二重辺は存在する。各頂点iにはd[i]=0 or 1 or -1 という数が割り当てられている。このグラフのサブグラフを構成して、degree(i) % 2 = d[i] or d[i] = -1 を満たす、つまり、0または1の場合は頂点の次数のmod2にd[i]が一致するようにしたい。このようなサブグラフが存在するか?存在するならば具体的に構成せよ。

 

-1の頂点がない状況を考える。頂点次数のmod 2がd[i]と一致している頂点を「正しい頂点」、一致していない頂点を「正しくない頂点」と定義すると、正しくない頂点同士を結んだエッジは取り除いて除去することができる。また、正しい頂点と正しくない頂点を結ぶエッジは取り除くことによって、正しいと正しくないをSwapすることができる。

 

そこで、ある頂点を根とする全域木を考える(と言っても単に未訪問の頂点をdfsで辿っていくだけである)このとき、正しくない頂点が根から遠いところにある場合は、根の方向のエッジを取り除く(この取り除いたエッジのインデックスはメモしておく)。すると、エッジの両端は正しい頂点になるか、または根に近いほうが正しくない頂点になる、のいずれかになる。これを葉から再帰的に行うことで、最終的に根が正しい頂点になっていれば構成可能ということで、メモしておいたインデックスを除くサブグラフを出力する。

 

次に-1の頂点が1個以上ある場合、同じような考え方で、正しい頂点とみなしておくが、もし接続されたエッジを取り除いたあとも正しい頂点のままとみなしておく。ただし、この時根が正しくない頂点になっていても、-1の頂点に向かって正しくない頂点を移動してけば構成可能になる。このような判定をしないために、元から根として-1が割り振られた頂点を選んでおくと、最終的に根のところは常に構成可能になる。つまり、-1の頂点が1個以上ある場合、常に構成可能になる。O(V)。

Codeforces Round #429 (Div. 2) C. Leha and Function

codeforces.com

 

長さnでmin(a[i])>=max(b[i])であるような数列a[i], b[i]が与えられる。F(n, k)を Σ[S⊆{1, 2, ... , n}, #S=k] min(S) / nCk (つまり、k個の要素からなる部分集合の最小値の期待値) とする時、a[i]を並び替えて、ΣF(a[i], b[i]) を最大化したい。最大値を与えるa[i]の並び替えを一つ求めよ。

 

実験してみるとわかるが、F(n, k)はnを固定したときにkの単調減少関数、kを固定したときにnの単調増加関数になっている。(漸化式を立てれば一応証明はできる)

 

更にこちらは実験でしか確かめていないが、F(n1, k1)+F(n2, k2)について、n1>n2のとき、k1<k2の場合のほうがk1>k2のときよりも大きくなる。そのため、a[i]とb[i]はそれぞれ昇順と降順で組み合わせるのが最適とわかる。

 

ほとんど実験だけの問題であるが、あとはソートして組み合わせ、元のb[i]の順序で出力すればよい。O(n logn)。

CS Academy Round 42 - Xor Submatrix

csacademy.com

 

N次元ベクトルVとM次元ベクトルUが与えられる。i行j列の要素が V[i] xor U[j] であるようなN x M行列を考える。この行列の行の連続する部分列、及び列の連続する部分列からなる小行列について、その小行列の全要素のxorをスコアとするとき、スコアの最大値を求めよ。

 

a xor a = 0とかxorの可換性を使う。例えば小行列の行また列が偶数次元の場合、対応する列または行は偶数回xorされることになり、結局0になる。そのため偶数次元側の行または列のxorを考えるだけでよい。

 

また、小行列の行も列も奇数次元のとき、結局偶数個のxorは0になるので、行と列を独立してxorを計算し、それらの組み合わせのxorの最大値を求めればよい。ただしまともにやると行や列それぞれがO(N^2)なので、それらの組み合わせでO(N^4)かかるがこれではTLEする。そこで、行の各部分列について、最大になるような列の部分列のxorをO(logN)で求めるためにTrie木を構成しておく。するとO(N^2 logN)で計算可能である。

 

最後のO(logN)はTrie木の他に、列をソートしておいてbitごとにBinary Searchしてもよいが、若干実装が複雑になる。

CS Academy Round 42 - Sorting Steps

csacademy.com

 

バブルソートを行う。一回のステップを擬似コード(原文参照、インデックスの上から下まで一回づつやるイメージ)の通り行うとき、何回のステップでソートできるか?

 

いわゆる単純なバブルソートのSwap回数ということであれば、転倒数が答えであるが、この場合はステップの考え方がちょっと違う。擬似コードをシミュレートしてみると、あるべき場所よりも右にある要素は1個づつIndexがデクリメントされていき、あるべき場所よりも左にある要素は一気に幾つかインクリメントされる。その為、デクリメントされる回数が最も多い要素を見つけたら、そのデクリメント回数がそのままステップ数になる。

 

見つけ方としては、元の要素とインデックスを持ったa[N][2]配列を用意し、もとの要素でソートする。その後、「元のインデックス - 現在のインデックス」の最大値が答えである。支配項はソートであり、O(N logN)。

P≠NP 予想を肯定的に証明したと宣言した論文がarXivにアップロードされた件

[1708.03486] A Solution of the P versus NP Problem

 

P≠NP予想 - Wikipedia

P≠NP 問題については上のWikipediaを見ていただくとして、昨日あたり arXivP≠NP 予想を証明したという論文がアップロードされました。

ここで、下記に注意する必要があります。

  • arXivはあくまでもプレプリントサーバであること、つまり第三者による厳格な査読等が行われてないということ
  • P≠NP 予想はあまりにも有名で、かつ懸賞金付き問題なので誤った証明が出やすいこと

というわけで、この時点では「証明できた」とはいえないのでまずは査読またはレビュー待ちと言うかたちになります。 

 

この論文をだしたのはドイツの計算機科学者のNorbert Blumという方らしいです。アブストラクトによると、「monotone graphというクラスに対して成立する、クリーク問題に関する下限近似式」なるものがあったのですが、それを修正することで一般のグラフに関しても非複雑度の下限が計算でき、それがexponentialに増加するということがわかったのでP≠NPということが言える、という書き出しでした。

 

クリーク問題というのは有名なP≠NP関連の問題の一つであり、P≠NP予想はある一つの例について証明できれば、他のすべてが証明できる、みたいな性質もあったりします。

monotoneグラフというのは、あまり良くわかってないのですが、サブグラフが似たような構造を取るグラフ、ぐらいの意味に読み取れました。

SRM719 Div1 Easy LongMansionDiv1

Webサイトないので貼れない…

 

N行 半無限列のGridが与えられる。各行はコストt[i]が設定されており、行iの任意の列に到着するごとにコストt[i]がかかる(スタート地点もコストがかかる)。最初(sx, sy)にいる人が四方向に1マスずつ移動して(ex, ey)に移動するための最小コストを求めよ。

 

まず分かることは、y方向(左右方向)に移動する行は一つに決まることである。もしそうでなければそれは最小コストではなくなってしまう。なので、その行で総当りする。スタート地点から上下に総当りの行まで移動し、横に移動してまたゴールに上下に移動する、という行動をすることで最小コストがわかる。O(N)。

E: Young Maids - AtCoder Regular Contest 080

arc080.contest.atcoder.jp

 

N個の順列pが与えられる。この順列pの任意の隣り合った2個の要素を取り除き、別の順列qの先頭に追加する、という操作を繰り返しpがからになるまで行う。最初qが空であるとする時、辞書順最小のqを構成せよ。

 

実験すると、pの先頭及び2番目に来る要素はpの偶数番目(0-indexedとする)の最小値(a[i]とする)、及びその最小値のある場所よりも右にある奇数番目の最小値(a[j]とする)である。これらを取り除いた後、次に来るのは一つ前の操作によって取り除かれたi番目及びj番目を除く [0, i), [i + 1, j), [j + 1, N) の範囲について、それぞれ同じ操作を行い辞書順最小となるものである。この3個のうち、どれが選ばれるかは、それぞれの範囲に置いて偶数番目の要素が最小になる範囲で決定される。

 

そこで、まず「投入された範囲の偶数番目の最小値」が最も小さい物が先頭に来るような、優先度付きキューを用意し、[0, N) の範囲を入れる。このキューについて、先頭を取り出し奇数番目最小の位置も計算し操作を行う。操作を行った後、分割された3個の範囲について、空でなければ、キューに再投入する、という操作を行う。

 

さて、「投入された範囲の偶数番目の最小値」であるが、あらかじめ順列のSegment treeを偶数番目は元の順列、奇数番目はINFを入れておくと、求めることができる。しかし、キューに投入された範囲によっては先頭が元々の奇数番目ということもあり得るため、偶数番目はINF、奇数番目は元の順列という2種類作っておき、範囲の最初の要素が元の順列で奇数番目であったか偶数番目であったかによってどちらのSegment treeを使うかを決定する。

 

ちなみにこのキューのComparatorを素直に書くと優先度付きキューの計算回数がO(logN), Segment treeの最小値計算がO(log N)かかるので、結局O(logN^2)かかってしまう。そこで、キューへの投入時に{left, right, min} と言うかたちで最小値をあらかじめ計算してしまい、3番目の要素でComparatorを書くとO(log N)にすることが可能。

全体ではO(N logN)だと思うのだが、分割の仕方をよくシミュレートしていないのであまり自信はない。