問題 N個の「(」または「)」からなる文字列S_iが与えられる。 この文字列をすべて連結して括弧列を構成できるか判定せよ。括弧列とは、 空文字列 ある括弧列Aが存在して、「(」「A」「)」の順で連結した文字列 ある空でない括弧列A, Bが存在して、「A」「B」…

問題 長さNの数列Aで、以下の条件を満たすものを考える。 1 また、Q個の(a_i, b_i, c_i, d_i)が与えられる。 スコアを「A_{b_i} - A_{a_i} = c_iを満たすd_iの総和」とするとき、スコアの最大値を求めよ。 制約 2 1 1 1 0 M-1 (a_i, b_i, c_i) != (a_j, b_j,…

問題 1～Nまでの異なる番号が書かれた箱に、M種類のペンキを使って塗りたい。 このとき、M種類すべてを使って、各箱は必ずいずれかの色に塗られているとする。 このとき、色の塗り方は何通りあるか？ 制約 1 解法 N個をM個に割り当てる問題の場合、写像12相…

問題 底辺が1辺a cmの正方形で、高さがb cmである直方体に、体積x cm^3の水を入れる。 これを底辺のどれか1辺を軸に傾ける。 水が溢れないように傾けられる最大の角度を求めよ。 制約 1 1 1 解法 θだけ傾けた場合を考える。このとき、傾けたa cm側とb cm側が…

問題 正の整数Nが与えられる。2以上N以下の整数Kを決めて、NがK未満になるまで次の操作を繰り返す NがKで割り切れるならNをN/Kに置き換える。そうでないなら、NをN-Kに置き換える 最終的にNが1になるようなKはいくつあるか？ 制約 2 解法 まず、「NがKで割り…

問題 N日間のスケジュールSが与えられ、i日目の予定S[i]がoならその日は仕事ができて、xなら仕事はできない。 このスケジュールの中、K日選んで仕事をしたい。 ただし、ある日に仕事をしたら、その直後のC日間は働いてはいけない。このとき、必ず働く日の日…

問題 1からNの順列Pが与えられる。 ペア(L,R)について、P_L, ..., P_Rの中で2番目に大きいものをX_{L,R}とする。 Σ^{N-1}_{L=1} Σ^{N}_{R=L+1} X_{L,R}を求めよ。 制約 2 解法 よくある手として、あるP_iが2番目に大きいものであるような範囲を考える。A, B,…

問題 N人の人が一列に並んでおり、各人が左を向いているか右を向いているかの情報が文字列Sで与えられる。 各人は、目の前の人が自分と同じ方向を向いていればhappyであり、そうでなければunhappyである。ここで、0回以上K回以下で、好きな回数だけ以下の操…

問題 N個の要素からなる順列Pを無限につなげた数列Tを考える。 T上のi番目にいる場合、1回の移動では、「i+T_i番目」に移動する。 K回後に何番目にいるか？をi=1,...,Nについてそれぞれ求めよ。 制約 1 1 Pは{1,2,...,N}を並び替えた順列 解法 K回後の移動先…

問題 文字列TのABC数を以下の条件を満たす整数の組(i,j,k)の個数とする。 1 T_i = 'A' T_j = 'B' T_k = 'C' 文字列Sが与えられるが、SはA,B,C,?の4つの文字からなり、?は、AまたはBまたはCに展開した文字列を考える。 ?がQ個あった場合は、3^Q個の文字列に対…

問題 2以上の整数bと、1以上の整数nに対し、関数f(b,n)を以下のように定める。 n n >= bのとき、f(b, n) = f(b, floor(n/b)) + (n mod b) これは、直感的には、nをb進表記したときの各桁の和を表す。整数nとsが与えられる。f(b, n)=sとなる2以上の整数bの最…

問題 整数N, Mが与えられる。 a_1 * a_2 * ... * a_N = Mであるような、長さNの数列aの何通りあり得るか10^9+7で割ったあまりで答えよ。 ただし、数列aとbが異なるとは、あるiが存在してa_i != b_iであることをいう。 制約 1 1 解法 (約数を列挙したDPや行列…

問題 3つの文字列a,b,cが与えられる。 これらの文字列は、以下の方法で作られたことがわかっている。 ある文字列sがあり、その連続部分文字列tを取り出す tのいくつかの文字を'?'に置き換える このとき、元の文字列sの長さとして考えられる最小の長さを求め…

問題 長さNの、英小文字からなる文字列を考える。 ある文字列sとtは、以下の条件の時「同型」という。 |s| = |t| 任意のi,jに対して以下のいずれかが成り立つ s[i]==s[j] かつ t[i]==t[j] s[i]!=s[j] かつ t[i]!=t[j] また、文字列の標準形とは、 任意のsと…

問題 整数L,Rが与えられる。 整数の組(x,y)がL 制約 1 解法 (解説放送より)a xor bは各ビットの繰り上がりのない足し算と考えられる。 y%xは0からx-1までの整数であり、y xor xはx したがって、yはxと一番高いビットが同じところまでのものになる。 また、こ…

問題 2次元平面上にN個の点があり、各点のx座標、y座標はそれぞれ相異なる。 この点からなる集合Sについて、Sの空でない部分集合Tを考える。f(T) := 各辺が座標軸と平行であってTの点をすべて含むような最小の長方形に含まれる点の個数と定めるとき、Sの空で…

問題 数直線上に1～Nの番号のついたロボットが置かれている。 ロボットiは座標X_iにあり、スイッチを入れるとD_iだけ移動し、直後取り除かれる。 また、以下の操作を好きなだけ行える。 ロボットを1つスイッチを入れる。どれかのロボットが移動している間は…

問題 0から9までの数字からなる長さNの文字列が与えられる。 この文字列の空出ない連続する部分文字列を考える。 部分文字列を数字として見たときに、素数Pで割り切れるものの個数を求めよ。 ただし、0から始まるものでもよく、それらは異なる数字とみなす。…

問題 n個の部屋があり、最初各部屋には1人ずついる。 ここで、ある部屋iから別の部屋j (i != j)へ移ることを「人の移動」と呼ぶことにする。 人の移動がk回起きたことがわかっているとき、各部屋にいる人数の組合せとして何通りあり得るか、10^9+7で割ったあ…

問題 数直線上にN個の爆弾が仕掛けられており、i番目の爆弾はA_iの位置で、スイッチの状態がB_i(OFFは0、ONは1)で与えられる。 制御装置にはM本のコードがあり、j番目のコードを切ると、L_j以上R_j以下の位置にある爆弾のスイッチの状態が入れ替わる。 切る…

問題 AtCoder王国では、価値が1,10,100,1000,...,10^(10^100)の紙幣になっている。 今、商品の価値がNであるような商品を買いたい。 各紙幣は十分な枚数を持っているとした場合、この商品を買うために払う枚数とおつりの枚数を適切に最小化した場合、最小で…

問題 N個の整数A_iが与えられる。 このうち、2つを選んだ積の組合せをすべて考えると、これはN*(N-1)/2個できる。 小さい方からK番目の積が何になるか答えよ。 制約 2 1 -10^9 解法 積を小さい方から並べた数列Bを考える。(これは実際には列挙できない) Bの…

問題 N体のモンスターが一列に並んでいる。 i番目のモンスターは、座標x_iにいて、体力がh_iである。今、爆弾を座標xに落とすと、x-D以上x+D以下の範囲にいるモンスターにダメージAを与えることができる。 すべてのモンスターの体力を0以下にするために必要…

問題 N個の頂点からなる木がある。 各辺iは、頂点a_iとb_iをつないでおり、1～N-1の整数で表される色c_iと、辺の長さd_iが割り当てられている。 このとき、以下のQ個の問いに答えよ。 「問いj: 色x_jのすべての辺の長さをy_jに変更したと仮定して、二頂点u_j…

問題 正の整数K個を一列に並べたもので、隣接するどの2つの整数の積もN以下であるようなものの個数を求めよ。 答えは10^9+7のあまりで求めよ。 制約 1 2 解放 計算量を無視して考えると、 dp[i][j] := i番目の整数がjだった場合の通り数 のように考えられる…

問題 N個のシュークリームが一列に並べてあり、左からi番目のシュークリームはa_iキロカロリーである。 AさんとBさんは、Aさんから始めて交互に以下のいずれかの操作を繰り返す。 左側にあるシュークリームを含む、位置が連続した1個以上のシュークリームを…

問題 N個の頂点からなる木が与えられる。この木の辺を白か黒で塗ることを考える。 M個の制約が与えられ、i番目の制約は「2つの頂点u_i, v_iのパス上の辺には黒色の辺が1つ以上存在しなければならない」となっている。M個すべての制約を満たすような塗り方の…

問題 平面上のN個の点が与えられる。 これらすべてを内部または周上に含む円の半径の最小値を求めよ。 制約 2 0 与えられる点はすべて異なる 解法 いくつかの点を選び、それが円周上にあると仮定した場合の円を求めて、他のすべての点が含まれるか？をチェッ…

問題 長さNの偶数の整数からなる正数列Aと整数Mが与えられる。 任意のk(1X = A_k * (p + 0.5)を満たす負でない整数pが存在する1以上M以下の整数のうち、Aの半公倍数の個数を求めよ。 制約 1 1 2 A_iは偶数 解法 Xについて考える。 0.5を1/2として整理すると…

問題 2次元座標にN個の点が与えられる。 このとき、「座標(a,b),(a,d),(c,b),(c,d)のうちちょうど3箇所に点が存在するようなa,b,c,d(a!=c, b!=d)を選んで、残りの1箇所に点を追加する」という操作を繰り返す。 この操作回数の最大値を求めよ。 制約 1 1 与え…