アルゴリズム忘備録

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

C: 3 Steps - CODE FESTIVAL 2017 qual B | AtCoder

code-festival-2017-qualb.contest.atcoder.jp グラフが与えられる。辺をちょうど3回通ってたどり着ける2点間に新たに辺を引く、という操作をできるだけしたい。ただし、既に辺がある場合は引くことができない。最大で何回操作ができるか? グラフが二部グラ…

CS Academy Round 51 - Tree Coloring

csacademy.com ツリーと色数kが与えられる。この時、あるノードに対して、そのノードから距離1のノードと、距離2のノード両方と色が異なるように頂点を彩色したい。彩色の仕方は何通りあるか。 あるノードに着目する時、距離1または距離2のノードがすべて異…

CS Academy Round 51 - Manhattan Distances

csacademy.com 整数d1, d2, d3が与えられる。2次元格子点座標の3点であって、各点のマンハッタン距離がd1, d2, d3のいずれかになるような3点を構成せよ。できない場合は-1を出力せよ。 マンハッタン距離は距離と名付けてあるだけあって、距離公理を満たす。…

CS Academy Round 52 - Race Qualifying

csacademy.com レースを行い、1~N位までの仮順位をつけた。ただし、それぞれの順位の人はa[i]回違反をしており、ペナルティを受ける。x位の人がk回違反をした場合、x+k位になる。最終順位を求めよ。 仮順位+ペナルティ回数でソートする。ただし、仮順位+…

CS Academy Round 51 - Poisoned Food

csacademy.com a[i], b[i] のN個のリストが与えられる。それぞれ、食料iに対して、a[i]個のポーションが原料として使われており、その中でb[i]個が毒ポーションであるという意味である。最も毒の割合が少ない食料を答えよ。同じ割合の食料がある場合は、一番…

D: Four Coloring - CODE FESTIVAL 2017 qual A

code-festival-2017-quala.contest.atcoder.jp 距離dが与えられる。マンハッタン距離がdの点同士は異なる色で塗られるように格子点を塗り分けたい。塗り分けを一つ構成せよ。 マンハッタン距離を考えるときは、必ず45度回転を考える。そうすると、x軸またはy…

C: Palindromic Matrix - CODE FESTIVAL 2017 qual A

code-festival-2017-quala.contest.atcoder.jp 要素がアルファベットの行列が与えられる。各行及び各列が回文になるように要素を並び替えたい。可能かどうか判定せよ。 まずすべての要素について、a~zの登場回数をmod4でカウントしておく。 そして行及び列…

C: Fountain Walk - AtCoder Grand Contest 019

agc019.contest.atcoder.jp 格子マップ及びいくつかの頂点が与えられる。格子の辺は100m、与えられた頂点にはN個の噴水があり、半径10mの外周を通ることが可能である。格子点は同一水平線上または同一垂直線上にたかだか1個である。 スタートとゴールが与え…

B: Reverse and Compare - AtCoder Grand Contest 019

agc019.contest.atcoder.jp 文字列Aが与えられる。任意の添字i, jを選び、連続部分文字列A[i]..A[j]を反転させる。(i=jならなにもしないのと同値)。この操作を1回だけしたときに得られる文字列は何通りあるか? 左の文字から順に数えていく。今見ている文字…

A: Ice Tea Store - AtCoder Grand Contest 019

agc019.contest.atcoder.jp アイスティーの単価がQ, H, S, D円でそれぞれ0.25l, 0.5l, 1l, 2l買える。在庫はいくらでもある。Nリットルのアイスティーを買いたいとき、必要な金額はいくらか? 要は2lのものをいくら買うか、ということである。まずリットル単…

F - Sandglass - AtCoder Regular Contest 082

F - Sandglass 容量Xで一秒間に1砂がおちる砂時計がある。時刻集合r[i]が与えられて、各時刻に砂時計をひっくり返すことがスケジュールされている。時刻0で砂時計の上半分をAという。 このとき、q個のクエリ「初期のAにある砂の量がaのとき、時刻tのAの砂の…

E: Snuke and Spells - AtCoder Regular Contest 082

E - ConvexScore 点集合が与えられる。部分集合Sが凸包の頂点をなすとき、そのSのスコアをexp(2, (Sの内部と境界にある点の数) - |S|) と定義する。この点のすべてのSについてそのスコアの和を求めよ。 スコアの意味をよく考えてみると、点集合全体の部分集…

E - Bichrome Tree - AtCoder Regular Contest 083

E - Bichrome Tree 頂点数Nの木とN個の数列X[i]が与えられる。各頂点に対し、ある非負整数を割り当て、かつ白または黒に塗り分けるとき、次の条件をみたすようにしたい。 条件:頂点i を根とするサブグラフについて、頂点i と同じ色の配下(i自身も含む)のノ…

D - Restoring Road Network - AtCoder Regular Contest 083

D - Restoring Road Network 隣接行列形式でN都市間の距離が与えられる。この隣接行列で表された距離が最短距離となるようなN都市間の経路グラフは構成できるか?できるならば、経路の長さの和が最短であるようなものの経路の和を求めよ。 隣接行列に対してW…

C - Sugar Water - AtCoder Regular Contest 083

C - Sugar Water A, B, C, D, E, Fが与えられる。空のビーカーに次の操作のいずれかを何回でも行える。 100A[g]の水追加 100B[g]の水追加 C[g]の砂糖追加 D[g]の砂糖追加 現在水100[g]当たりE[g]砂糖が溶け、ビーカーには最大F[g]の砂糖+水が入るとすると、…

ACしたら力尽きてブログを更新する気力がなくなる件

時間かけてACした問題は復習も兼ねてブログに書くべきなんだけど、通した時点で力尽きてしまうのなんとかしたいですね。3連休に一気に積みAC?をまとめるか…

D: Derangement - AtCoder Regular Contest 082

arc082.contest.atcoder.jp 順列p[i]が与えられる。何回かp[i] とp[i + 1]をSwapするという操作を行い、すべてのiについてp[i] ≠ i となるようにしたい。操作の最小回数を求めよ。 p[i] = i となるような連続部分列があったとする。この時、この部分列の長さ…

C: Together - AtCoder Regular Contest 082

arc082.contest.atcoder.jp 数列a[i]が与えられる。ある数Xを選んで、各a[i]に対して-1, 0, +1のいずれかを加えることで、a[i]=Xとなるiの個数が最大になるようにしたい。最大値を求めよ。 v[n]=(a[i]=nとなるようなiの個数) という配列を作っておきます。す…

TopCoder SRM 720 Div1 Med

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

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また…

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

CS Academy Round 42 - Xor Submatrix

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

CS Academy Round 42 - Sorting Steps

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

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

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

SRM719 Div1 Easy LongMansionDiv1

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

E: Young Maids - AtCoder Regular Contest 080

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

D: Grid Coloring - AtCoder Regular Contest 080

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

C: 4-adjacent - AtCoder Regular Contest 080

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

Codeforces Round #427 D. Palindromic characteristics

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

Codeforces Round #427 C. Star sky

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