要反省
https://atcoder.jp/contests/abc194/tasks/abc194_e 問題概要 $ mex(a, b, c\cdots) $は$ a, b, c\cdots $のうちに含まれていない、最小の0以上の整数とする。 数列$ {A _ i} $と$ M $が与えられる。すべての$ A _ i $の連続した$ M $個の部分について、そ…
https://atcoder.jp/contests/soundhound2018-summer-final/tasks/soundhound2018_summer_final_b 概要 長さNの数列{a}が与えられる。K あなたは次の操作を好きな回数だけ行うことができる。 連続するK項を選び、それらの値をすべて0にする。 この時数列{a}…
atcoder.jp 概要 N , Bで、次の条件を満たすようなものが何通りあるかを求めよ。ただし、非常に大きくなる場合があるので、で割ったあまりを求めること。 AとBの要素は、[1, M]の任意の整数 A[i] != B[i] (1 A[i] != A[j] (1 つまり、同じindexでのAとBの要…
atcoder.jp 概要 N個の文字列S[i]が与えられる。それぞれのS[i]は'(' or ')'で構成されている。これらの{S}を好きな順番でつなげ合わせた時、正しいかっこ列を作ることができるのだろうか?できるならYes、できないのならNo。制約: 1
atcoder.jp 概要 最初にx=0という数字を持っている。あなたは、次の操作のうち任意のものを任意の順番で、任意の回数回だけ行える。 (操作1)xを2xで置き換える。 (操作2)xを3xで置き換える。 (操作3)xを5xで置き換える。 (操作4)xを+1もしくは-1する。 操作1…
atcoder.jp 概要 おかずがN種類ある。それぞれのおかずには糖分A[i]、塩分B[i]というパラメータがある。 あなたはおかずを何種類か選んで晩御飯と一緒に食べたい。この時、次の条件を満たすようにする必要がある。 選ばれたおかずが2つ以上存在するのなら、…
atcoder.jp 概要 Nが与えられる。最初がx=1で、高橋君と青木君が交互に次の操作のうちのどれかをする。先手は高橋。 xを2xにする。 xを2x+1にする。 自分の番で操作してNを超えたらその人の負け。Nが与えられるので、その時が誰が必勝なのかを答えてください…
codeforces.com 概要 n_a, n_b, n_cと長さがn_aのa, n_bのb, n_cのcが与えられる。 aの中の1つの要素をx, bの中の1つの要素をy, cの中の1つの要素をzとする。を最小化せよ。制約: 1 ACするまで 1. 何か裏がありそうな式ではあるが、なんやかんやうまく全探…
Problem - D - Codeforces atcoder.jp# ABC194 - F https://atcoder.jp/contests/abc194/tasks/abc194_f 実装重い桁DP 煩雑な実装をバグらせずに書けるのかな? 必要だと思ったものは全動員しよう。自信を持とう。# Edfo103 - C https://codeforces.com/cont…
atcoder.jp 概要 長さNの文字列Sが与えられる。Q回の質問ごとに与えられるkについて、次の条件を満たすような(a, b, c)のセットの数を答えよ。 S[a]=='D', S[b]=='M', S[c]=='C' a c - a 制約: 1
atcoder.jp 概要 N個の要素からなる数列A[]で、floor(N/2)個の要素を選ぶ。ただし、選ばれたものは隣り合ってはならない。その和を最大化せよ。制約: 1 ACするまで 考察ノートを考察パートで載せる。 考察 僕の解法 これが本番中書いた考察ノート。(DPの実…
atcoder.jp 概要 Senくんのスケジュールが記された、長さNの文字列によってあらわされるスケジュール表が与えられる。i文字目が'o'なら働ける日、'x'なら働けない日である。 "ooxox"ならば、1, 2, 4日目にだけ働ける。 Senくんは怠惰なので、1日働いたら次に…
atcoder.jp 概要 サイズNの木が与えられる。頂点に1~Nの番号が振られている。k=[1, N]として次の条件下で問題を解け。 頂点kに最初に赤色を塗る。次に塗ることができるのは、すでに塗った頂点に隣接する頂点、というルールのもとで色を塗るとき、何通りの塗…
codeforces.com 概要 円状にN個の数が並んでいて、時計回り順にt[i]である。次の条件を満たすように、これらの数に色を塗る。 隣り合った異なる値の数字どうしは、必ず異なる色が塗られている。 これを満たすように、最小限に色を使って塗ったときの一例を示…
codeforces.com 概要 N人いて、それぞれのprogramming skill(以降PSと略す)はa_iである。N人でいくつかチームを組む。3人以上の人間で1つのチームを組むことができる。 チームの不満度を、チーム内の最大のPSを持つ人と、最小のPSを持つ人との差と定める。 …
atcoder.jp 概要 長さNの数列A[]が与えられる。次のようにf(l, r)を定める。 l さて、1 制約: 1
atcoder.jp 概要 ある文字列sが存在し、次の操作を考える。 sの空でない連続部分文字列を1つ選び、これをpとする。pのそれぞれの番目を'?'に置き換えるorそのままにする。 この操作で得られた3つの文字列、a, b, cが存在するとき、元のsの最短の長さを答えよ…
codeforces.com 概要 n人の参加者がいる2回コンテストが行われた。Senくんは1回目ではx位、2回目ではy位であった。総合順位は、2回のコンテストで取った順位の和を、全員分広義単調減少になるようにならべて、前からの順位とする。 ほかの参加者が1回目と2回…
atcoder.jp 概要 n個の1~nまで番号がついてる部屋があって、それぞれ1人ずついる。ある部屋にいる一人が別の部屋へと行く行動をアクションと呼ぶ。 アクションがちょうどk回行われたときに、それぞれの部屋にいる人の数の組み合わせの数を10^9+7で割ったあま…
codeforces.com 概要 H*Wのグリッドを与える。そのグリッドには"."と"#"の2つがある。あなたは1*2のサイズのドミノを持っていて、縦向きか横向きのいずれかの向きで、グリッドの2つ連続で"."になってる場所における。 次のq個のこqueryに答えよ。 グリッドを…
atcoder.jp 概要 長さNの数列Aが与えられ、それらの中の2つの要素の組はN*(N-1)/2個あるが、それら積のうち、小さい順にK番にあたる値を求めよ。制約: 1 -10^9
codeforces.com 概要 長さNの数列Aが与えられる。あなたは次の操作を何度してもよい。 Aの連続部分列を1つ選び、その連続部分列の亘る区間をすべてその連続部分列の平均とする。 この操作を繰り返して、Aを辞書順に最小にするとき、Aはどうなるか?制約:1 1…
codeforces.com 概要 N頂点M辺の無向グラフが与えられる。次の条件を満たす全域木を1つ出力せよ。 全域木を構成する辺のうち、頂点1と連結してる辺はD本である。制約: 1 1 ACするまで 1. ひとまず適当にグラフを書いてみると、頂点1から出てるいくつかの辺…
codeforces.com 概要 Xが与えられる。lcm(a, b)=Xを満たすような(a, b)の組のうち、max(a, b)を最小化せよ。制約: 1
atcoder.jp 概要 任意の自然数r, cを使って、(i==r && j = c)の部分を1円をかけて塗ることができる。 N*Nのグリッドが与えられて、そのうちのいくつかが既に塗られてるかもしれない。既に塗られたものに上書きにして塗ってもよい。 この時、全部塗り切るのに…
codeforces.com 概要 nが与えられる。[1, n]の区間に、n人の人が立っている。彼らの座標は、重複しうる。 それぞれの人は、その場にとどまるor座標を-1するor座標を+1することができる。x=1にいる人はx=0に、x=nにいる人は、x=n+1に行くこともできる。これら…
codeforces.com 概要 次の問題をt回解け。 長さnの数列aが与えられる。それの空でない連続部分列のうち、(最大値)-(最小値)>=(連続部分列の長さ)になってるのならば、aはよい数列とする。例えば[1, 1, 4, 5, 1, 4]は[1, 4, 5, 1]は5-1>=4を満たすので、[1, 1…
atcoder.jp 概要 サイズNの木が与えられる。それぞれの頂点を1/2の確率で白、1/2の確率で黒と塗る。 黒で塗られた頂点をすべて含む最小部分木を考える。その最小部分木のサイズの期待値を求めよ。制約: 1
codeforces.com 概要 nとその約数のmが与えられる。n個のa_iから成る数列も与えられる。 1回の操作で数列の要素を1増やすことができる。 あなたは、mで割ったあまりが0, 1, 2, ..., m-1となるものの個数がすべてn/mになるようにしたい。最低の操作回数とその…
codeforces.com 概要 '('と')'のみが含まれる文字列S, Tが与えられる。次の条件を満たす文字列Xを構成してください。 SとTはどちらもXの部分文字列である。 Xはかっこ列としてすべての'(' と ')' は対応されていて、かつその2文字からのみ成る。 Xの長さはあ…