Codeforces
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だけ高…
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. 何か裏がありそうな式ではあるが、なんやかんやうまく全探…
codeforces.com 概要 サイズNの木が与えられて、それぞれの頂点には重みがweight[i]だけ設定されている。 あなたは、この中から次の条件を満たすように、好きなだけ頂点を選べる。選んだ頂点たちの重みの総和の最大値を求めよ。 選んだ頂点たちはお互い距離…
codeforces.com 概要 サイズNの木が与えられる。根を頂点1とする。 次のようなM個のqueryに答えよ。 k個の頂点を与える。頂点1からある頂点vへ行くパスからの距離が、k個の頂点すべてに対して、1以下となるvが存在するのならばYES、ないのならNOと答えよ。 …
codeforces.com 概要 円状にN個の数が並んでいて、時計回り順にt[i]である。次の条件を満たすように、これらの数に色を塗る。 隣り合った異なる値の数字どうしは、必ず異なる色が塗られている。 これを満たすように、最小限に色を使って塗ったときの一例を示…
codeforces.com 概要 長さが100万以下の文字列Sが1つあたえられる。構成されてる文字は、アルファベットの最初の20文字、すなわち'a' ~ 't'である。これの連続部分文字列を1つ選んで、1回だけ反転してよい。(しなくてもよい) 操作を終えた時、文字列Sの連続…
codeforces.com 概要 2つの長さNの文字列S, Tが与えられる。次の操作を任意回行えるとして、SとTを一致させることはできるか？ x 同時に反転させる。 例えば、S="sen", T="shojin"でx=3の連続部分列を次のように選べる。 S'="sen", T'="hoj" これを同時に入…
codeforces.com 概要 N人いて、それぞれのprogramming skill(以降PSと略す)はa_iである。N人でいくつかチームを組む。3人以上の人間で１つのチームを組むことができる。 チームの不満度を、チーム内の最大のPSを持つ人と、最小のPSを持つ人との差と定める。 …
codeforces.com 概要 n行m列の行列で、毎行のxorの結果はa[1~n]、毎列のxorの結果はb[1~m]として与えられる。これを満たす行列を存在するのならば、YESと答えて、1つ構築せよ。存在しないのならば、NOとだけ答えよ。制約： 1
codeforces.com 概要 0 数列の要素のXORがuと等しく、和がvに等しい
codeforces.com 概要 サイズNの木が与えられる。そのN-1本の辺に、それぞれ1つずつ、0~N-2の数字を重複なく割り当てていく。 頂点uと頂点vの間を通る単一のパス(木なので必ず存在する)上の辺に含まれる数の集合をSとする。Sに含まれない、最小の非負整数をME…
codeforces.com 概要 n人の参加者がいる2回コンテストが行われた。Senくんは1回目ではx位、2回目ではy位であった。総合順位は、2回のコンテストで取った順位の和を、全員分広義単調減少になるようにならべて、前からの順位とする。 ほかの参加者が1回目と2回…
つぎのような問題を考える。 サイズNの無向木が与えられる。木の頂点に色を塗っていき、隣あった頂点には同じ色を塗ってはならない。 木をちょうどK色で塗るとき、何通りの塗り分け方があるか？で割ったあまりを答えよ。制約： 2
codeforces.com 概要 H*Wのグリッドを与える。そのグリッドには"."と"#"の2つがある。あなたは1*2のサイズのドミノを持っていて、縦向きか横向きのいずれかの向きで、グリッドの2つ連続で"."になってる場所における。 次のq個のこqueryに答えよ。 グリッドを…
codeforces.com 概要 長さNの数列Aが与えられる。あなたは次の操作を何度してもよい。 Aの連続部分列を1つ選び、その連続部分列の亘る区間をすべてその連続部分列の平均とする。 この操作を繰り返して、Aを辞書順に最小にするとき、Aはどうなるか？制約：1 1…
Attachments - 2019-2020 ICPC Asia Taipei-Hsinchu Regional Contest - Codeforces 概要 N点与えられる。そのうちの適切な順番で4つの点を選び、作れる最大の四角形の面積を求めよ。制約： 4
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
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…
Problem - D - Codeforces 概要 ある機械を買った。その機械には長さnの、各項が相異なる自然数列が存在する。この機械は、k個の相異なる、[1, n]の数字を入れて、それをaの添え字としたとき、それのk個のaの要素のうち、小さい方から見てm番目の添え字と値…
codeforces.com 概要 n行m列の行列がある。それからa行b列の部分行列を切り出す。(n-a+1) * (m-b+1)個できる。部分行列の項の最小値の和を(n-a+1)*(m-b+1)個分足した値を答えよ。 ただし、n行m列の行列はとして、である。制約: 1 ACするまで 1. 与式で構築さ…
codeforces.com 概要 32bitのIPアドレスがN個与えられる。それぞれのアドレスには、悪いと良いがある。悪いアドレスは必ずブロックし、よいアドレスは必ず通す。何もないアドレスは、通すことにする。 ところで、サブネットというのを定める。192.168.0.1/8…
codeforces.comこのセットの日本語での解説です。足りない問題は時間ができたら埋めます。 A dpでやるかと思ったらこれ順序わからない。順序がわからないDPっぽい遷移はグラフと相場が決まってる。結局グラフの最短路でやる。でもやる際はよくよく考えると辺…
codeforces.com 概要 n個の仕事がある。整数m, x, tがありこれらの仕事を前から順に次のルールで行う。 かかる時間がx以下ならば行う。そうでないなら飛ばす。 mこの仕事を終えたら、そのmこの仕事にかかった時間のぶんだけ休む。 時間がtをぎりぎり超えない…
codeforces.com 概要 nとその約数のmが与えられる。n個のa_iから成る数列も与えられる。 1回の操作で数列の要素を1増やすことができる。 あなたは、mで割ったあまりが0, 1, 2, ..., m-1となるものの個数がすべてn/mになるようにしたい。最低の操作回数とその…
codeforces.com 概要 N日の間、K個の飴を毎日食べたい。近所の菓子屋にはM種類の飴があり、それぞれ[l_i, r_i]日の間に、毎日最大で1つあたりの値段p_i円でc_i個まで売っている。 あなたは、いい感じに購入して毎日K個の飴を食べたい。もしその日に売られて…
codeforces.com 概要 城がNつある。あなたははじめ、K人の戦士を従えて、これを攻略していく。 城には戦力a_i, 補充兵士b_i, 戦略的価値c_iがそれぞれある。城を攻略するには、現在の従えてる戦士がa_i以上である必要がある。城の攻略に成功すると、戦士の数…
codeforces.com 概要 '('と')'のみが含まれる文字列S, Tが与えられる。次の条件を満たす文字列Xを構成してください。 SとTはどちらもXの部分文字列である。 Xはかっこ列としてすべての'(' と ')' は対応されていて、かつその2文字からのみ成る。 Xの長さはあ…
codeforces.com 概要 長さnの数列が与えられる。それぞれの要素a_i(1 さて、すべての1 不能なら"-1"と出力せよ。制約：1
