CS Academy Round 42 - Xor Submatrix
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
バブルソートを行う。一回のステップを擬似コード(原文参照、インデックスの上から下まで一回づつやるイメージ)の通り行うとき、何回のステップでソートできるか？
いわゆる単純なバブルソートの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を見ていただくとして、昨日あたり 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
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)だと思うのだが、分割の仕方をよくシミュレートしていないのであまり自信はない。
D: Grid Coloring - AtCoder Regular Contest 080
H x Wのマス目をN色で塗り分けろ。ただし、色iのマスの数はa[i]であり、同じ色のマスは連結になるものとする。
塗り分け方は左上から真右にいって折り返しのときに一段下がって今度は左、みたいに雑巾で床掃除をするときのような感じでマスを順番に塗っていけば連結になる。あとは各色の数だけ愚直に色を塗ればよい。O(HW)。
C: 4-adjacent - AtCoder Regular Contest 080
数列a[i]が与えられる。並び替えて隣同士の積がかならず4の倍数にするようにできるか判定せよ。
数列の要素を p:4の倍数、q: 偶数であるが4の倍数でないもの、r: それ以外に分類する。 rの隣には必ずpの要素が必要である。また、qは q同士で並ぶ or pのとなりにいることが必要であるが、要はqの数が奇数であった場合のみ、pが1個必要になる。よって、r + q % 2 <= p であればYESである。ただし、qが存在しない時はrprprprみたいに並べることが可能なので、r + 1 <= p であればYES。
