TopCoder SRM 720 Div1 Med
n, k (n>=k) が与えられる。n x n行列で、任意の行及び列を取り出した時、その中で異なる要素がk個になるような行列を構成したい。このような行列の中で、全要素について異なる要素が最大のものを一個構成せよ。
なんかEasyでも良さそうな問題。(今回はEasyがやたら難しかったので問題を取り違えた説もある)。まず全要素を0で並べた行列を作成し、1行目は {1, 2, 3,...,k, 0, 0, 0, ...} 、
2行目は{0, (k+1), (k+2), (k+3),...,(k+k), 0, 0, 0, ...} という感じで、{1, 2, 3..k, 0, 0, ..} という数列を非ゼロ要素をk-インクリメントしながらローテーションしたものを並べると目的の行列が構成できる。
Hackケースとして、ローテーションではなく末尾を落とした場合がたくさんあった模様。
Codeforces Round #429 D. Leha and another game about graph
無向連結グラフが与えられる。自己ループはないが二重辺は存在する。各頂点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
長さ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
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)。
