https://atcoder.jp/contests/abc189/tasks/abc189_f 概要 マス目が0からNまであるすごろくが存在していて、あなたは1からMまですべての数が等確率で出るルーレットを持っている。あなたは最初にマス0にいて、マス目Nを目指して、以下のように進む。 マス目$…

https://atcoder.jp/contests/soundhound2018-summer-final/tasks/soundhound2018_summer_final_b 概要 長さNの数列{a}が与えられる。K あなたは次の操作を好きな回数だけ行うことができる。 連続するK項を選び、それらの値をすべて0にする。 この時数列{a}…

F - Knapsack for All SubsetsABC実質初全完を祝って解説記事。 概要 長さNの数列Aが与えられる。また、{1, 2, ..., N}が含まれる集合Xを考える。Xの空でない部分集合Tについて、次のf(T)を定める。 f(T) := Tの空でない部分集合を{t_1, t_2, ..., t_i}とす…

atcoder.jp 概要 最初にx=0という数字を持っている。あなたは、次の操作のうち任意のものを任意の順番で、任意の回数回だけ行える。 (操作1)xを2xで置き換える。 (操作2)xを3xで置き換える。 (操作3)xを5xで置き換える。 (操作4)xを+1もしくは-1する。 操作1…

codeforces.com 概要 H*Wの盤面が存在していて、それぞれのマス(i, j)ごとにはa[i][j]という高さがある。 Senくんははじめ(1,1)にいて、(H, W)まで行きたい。(i, j)にいるとき、次に行ける場所は(i+1, j)と(i, j+1)のうち、高さが(i, j)よりちょうど1だけ高…

atcoder.jp 概要 N個の要素からなる数列A[]で、floor(N/2)個の要素を選ぶ。ただし、選ばれたものは隣り合ってはならない。その和を最大化せよ。制約： 1 ACするまで 考察ノートを考察パートで載せる。 考察 僕の解法 これが本番中書いた考察ノート。(DPの実…

codeforces.com 概要 サイズNの木が与えられて、それぞれの頂点には重みがweight[i]だけ設定されている。 あなたは、この中から次の条件を満たすように、好きなだけ頂点を選べる。選んだ頂点たちの重みの総和の最大値を求めよ。 選んだ頂点たちはお互い距離…

codeforces.com 概要 長さが100万以下の文字列Sが1つあたえられる。構成されてる文字は、アルファベットの最初の20文字、すなわち'a' ~ 't'である。これの連続部分文字列を1つ選んで、1回だけ反転してよい。(しなくてもよい) 操作を終えた時、文字列Sの連続…

codeforces.com 概要 N人いて、それぞれのprogramming skill(以降PSと略す)はa_iである。N人でいくつかチームを組む。3人以上の人間で１つのチームを組むことができる。 チームの不満度を、チーム内の最大のPSを持つ人と、最小のPSを持つ人との差と定める。 …

atcoder.jp 概要 長さNの数列A[]が与えられる。次のようにf(l, r)を定める。 l さて、1 制約： 1

atcoder.jp 概要 サイズNの木が与えられ、頂点には１～Nまでの番号が振られてる。AliceとBobはAliceからゲームを始め、自分の手番が終わったら、相手に交代する。自分の手番では、次の操作を行う。 木の辺を1本取り除く。これによって、木は2つの部分木に分…

ei1333.hateblo.jpこれの例題1について、実装の備忘録。 dfs2の操作 今着目してるidx=子とその親をつなぐ辺は必ず使うとする。 すると、子からさらに孫方向での最長はdfs1で求まっている。欲しいのは親の子方向ではない向きの最大。これは下図のようになる。

codeforces.com 概要 '('と')'のみが含まれる文字列S, Tが与えられる。次の条件を満たす文字列Xを構成してください。 SとTはどちらもXの部分文字列である。 Xはかっこ列としてすべての'(' と ')' は対応されていて、かつその2文字からのみ成る。 Xの長さはあ…

atcoder.jp 概要 偶数長'(', ')'からのみなる列(size 今カーソルは一番左を指している。コスト１を使って、次の操作のうちのいずれかを行える。 カーソルを左右に動かす(動かせるなら)。 カーソルの指してる文字を変更する。'(' -> ')' とか ')' -> '(' であ…

atcoder.jp 概要 0からN(1 )まで、xずつ加算したい。はじめ、xは1である。最小の加算回数は？ただし、次の★の操作は任意回行ってよい。★ xをニコ数倍する。ニコ数とは、2 or 5からのみで構成されるかつ、同じ数字が隣り合わない数のことである。例えば、5, 2…

atcoder.jp 概要 ナップサック問題を解く。一つだけカバンに入れず持ち歩ける。個数は3000個まで、価値、重さはそれぞれ[1, 3000]、入れられる最大の重さは[1, 3000]。最大の価値は？

atcoder.jp 概要 最大10万長の数列が与えられる。この数列は和が10^5以下を満たす。 この数列の部分列のうち、XORしたらKになるのはなん通り存在するのか？

atcoder.jp 概要 最大10万長の文字列Sが与えられる。"yahoo"を0以上の任意の整数回繰り返した文字列とSの編集距離の最短を答えよ。

tdpc.contest.atcoder.jp 概要 人のレーティングはそれぞれ設定されていて、人 i が人 j に勝つ確率は。 人1, 2, 3, 4, ..., 2^Kの順に並び、それぞれ平衡二分木になるようなトーナメントを組む(詳細は問題文参照)。 人1, 2, 3, 4, ..., 2^Kの順に優勝する確…

atcoder.jpこの問題から、次のような一般化された問題を考える。 問題文 N個のものを考える。高速でそのうちの1つを抜いた時の計算結果を求める。

atcoder.jp 概要 長さN(N 入力されるある整数K(1 ある数Xを含む部分集合のうちのすべての「良い集合」で、X自身を除いても「良い集合」となるとき、Xは「「良い集合」を作るのに不必要」と言います。 さて、「不必要」な要素はいくつあるでしょう？ちなみに…

atcoder.jp 問題概要 N人の人でトーナメントして、引き分けなしの勝負をした。最終的に勝ったのは人1である。人2～人N(2

問題文atcoder.jp 問題概要 長さN、要素が最大10^18の数列がある。あなたはK回、このうちの要素のうちの1つを選んで、それを2で割って商を切り捨てる。 K回操作を終えた時、数列のバリエーションを10^9+7で割ったあまりで求めよ。操作の手順が違っても最終的…