n, k (n>=k) が与えられる。n x n行列で、任意の行及び列を取り出した時、その中で異なる要素がk個になるような行列を構成したい。このような行列の中で、全要素について異なる要素が最大のものを一個構成せよ。 なんかEasyでも良さそうな問題。(今回はEasy…

Problem - D - Codeforces 無向連結グラフが与えられる。自己ループはないが二重辺は存在する。各頂点iにはd[i]=0 or 1 or -1 という数が割り当てられている。このグラフのサブグラフを構成して、degree(i) % 2 = d[i] or d[i] = -1 を満たす、つまり、0また…

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]) を最大化した…

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

csacademy.com バブルソートを行う。一回のステップを擬似コード(原文参照、インデックスの上から下まで一回づつやるイメージ)の通り行うとき、何回のステップでソートできるか？ いわゆる単純なバブルソートのSwap回数ということであれば、転倒数が答えであ…

[1708.03486] A Solution of the P versus NP Problem P≠NP予想 - Wikipedia P≠NP 問題については上のWikipediaを見ていただくとして、昨日あたり arXivにP≠NP 予想を証明したという論文がアップロードされました。 ここで、下記に注意する必要があります。 …

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

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

arc080.contest.atcoder.jp H x Wのマス目をN色で塗り分けろ。ただし、色iのマスの数はa[i]であり、同じ色のマスは連結になるものとする。 塗り分け方は左上から真右にいって折り返しのときに一段下がって今度は左、みたいに雑巾で床掃除をするときのような…

arc080.contest.atcoder.jp 数列a[i]が与えられる。並び替えて隣同士の積がかならず4の倍数にするようにできるか判定せよ。 数列の要素を p:4の倍数、q: 偶数であるが4の倍数でないもの、r: それ以外に分類する。 rの隣には必ずpの要素が必要である。また、q…

codeforces.com 自然数kについて、k-palindromeを次の用に再帰的に定義する。 長さ1の文字は1-palindromeである。 文字列がk-palindrome ⇔ 文字列が回文になっている、かつ文字列の左半分(つまり右半分も)が(k-1)-palindromeである。 ただし、文字列の左半分…

codeforces.com 最大100x100の領域に、n個の星が(x[i], y[i])に初期の明るさs[i]で配置されている。星の明るさの最大値はcであり、時間ごとに1づつ増えていき、cに到達すると次の時間に0に戻り、また1づつ増えていく、を繰り返す。この時、q個のクエリ (t[i]…

codeforces.com ある長い数字n(最大10万桁)について、すべての桁の合計はk以上であり、幾つかの桁が書き換えられた数字(桁数は同じ)が与えられる。最小で何桁書き換えられたとかんがえられるか？ 与えられた書き換え済みの数字についてまずは桁の合計を計算…

codeforces.com 2人がタイピングゲームをする。キーの送受信のレイテンシ及び一つのキーを押す時間と、課題の文字列の長さが与えられるのでどちらが勝つか判定せよ。 「レイテンシ * 2 + キーを押す時間 * 文字列の長さ」で比較するだけ。