code-festival-2017-quala.contest.atcoder.jp 要素がアルファベットの行列が与えられる。各行及び各列が回文になるように要素を並び替えたい。可能かどうか判定せよ。 まずすべての要素について、a～zの登場回数をmod4でカウントしておく。 そして行及び列…
agc019.contest.atcoder.jp 格子マップ及びいくつかの頂点が与えられる。格子の辺は100m、与えられた頂点にはN個の噴水があり、半径10mの外周を通ることが可能である。格子点は同一水平線上または同一垂直線上にたかだか1個である。 スタートとゴールが与え…
agc019.contest.atcoder.jp 文字列Aが与えられる。任意の添字i, jを選び、連続部分文字列A[i]..A[j]を反転させる。(i=jならなにもしないのと同値)。この操作を1回だけしたときに得られる文字列は何通りあるか？ 左の文字から順に数えていく。今見ている文字…
agc019.contest.atcoder.jp アイスティーの単価がQ, H, S, D円でそれぞれ0.25l, 0.5l, 1l, 2l買える。在庫はいくらでもある。Nリットルのアイスティーを買いたいとき、必要な金額はいくらか？ 要は2lのものをいくら買うか、ということである。まずリットル単…
F - Sandglass 容量Xで一秒間に1砂がおちる砂時計がある。時刻集合r[i]が与えられて、各時刻に砂時計をひっくり返すことがスケジュールされている。時刻0で砂時計の上半分をAという。 このとき、q個のクエリ「初期のAにある砂の量がaのとき、時刻tのAの砂の…
E - ConvexScore 点集合が与えられる。部分集合Sが凸包の頂点をなすとき、そのSのスコアをexp(2, (Sの内部と境界にある点の数) - |S|) と定義する。この点のすべてのSについてそのスコアの和を求めよ。 スコアの意味をよく考えてみると、点集合全体の部分集…
E - Bichrome Tree 頂点数Nの木とN個の数列X[i]が与えられる。各頂点に対し、ある非負整数を割り当て、かつ白または黒に塗り分けるとき、次の条件をみたすようにしたい。 条件：頂点i を根とするサブグラフについて、頂点i と同じ色の配下(i自身も含む)のノ…
D - Restoring Road Network 隣接行列形式でN都市間の距離が与えられる。この隣接行列で表された距離が最短距離となるようなN都市間の経路グラフは構成できるか？できるならば、経路の長さの和が最短であるようなものの経路の和を求めよ。 隣接行列に対してW…
C - Sugar Water A, B, C, D, E, Fが与えられる。空のビーカーに次の操作のいずれかを何回でも行える。 100A[g]の水追加 100B[g]の水追加 C[g]の砂糖追加 D[g]の砂糖追加 現在水100[g]当たりE[g]砂糖が溶け、ビーカーには最大F[g]の砂糖+水が入るとすると、…
時間かけてACした問題は復習も兼ねてブログに書くべきなんだけど、通した時点で力尽きてしまうのなんとかしたいですね。3連休に一気に積みAC？をまとめるか…
arc082.contest.atcoder.jp 順列p[i]が与えられる。何回かp[i] とp[i + 1]をSwapするという操作を行い、すべてのiについてp[i] ≠ i となるようにしたい。操作の最小回数を求めよ。 p[i] = i となるような連続部分列があったとする。この時、この部分列の長さ…
arc082.contest.atcoder.jp 数列a[i]が与えられる。ある数Xを選んで、各a[i]に対して-1, 0, +1のいずれかを加えることで、a[i]=Xとなるiの個数が最大になるようにしたい。最大値を求めよ。 v[n]=(a[i]=nとなるようなiの個数) という配列を作っておきます。す…
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 + キーを押す時間 * 文字列の長さ」で比較するだけ。
arc038.contest.atcoder.jp 位置iにある石を移動させるゲームを行う。位置iの石は左に1からC[i]の範囲で好きなだけ動かすことができる位置0にある石はそれ以上移動させることができない。先攻と後攻どちらが勝つか。 まずは位置iに石が1個ある時のGrundy数を…
agc017.contest.atcoder.jp ＋字型の図形の情報が幾つか与えられる(正確な定義は問題文参照)。この図形を下辺が地面にピッタリ付くように並べていく。例えば┴みたいなのは延々と並べていける。与えられた図形をすべて用いてそのように並べることは可能か？ …
arc078.contest.atcoder.jp 公開されない整数Nが存在し、システムに整数nを入力とするクエリを出すと、下記の条件の時Yesが帰ってくる。 n≤N かつ str(n)≤str(N)を満たす n>N かつ str(n)>str(N) を満たす この時、最大64回の質問でNを特定せよ。 まず分かる…
arc078.contest.atcoder.jp 木が与えられる。頂点のうち、1点は白、もう1点は黒、残りは色なしの状態である。先手は白に塗られた頂点から隣接する頂点にだけ、後手は同様に黒の頂点だけ色を塗っていくことが可能である。ただし、既に塗られたところには上塗…
