ABC167 F. Bracket Sequencing
問題
N個の「(」または「)」からなる文字列S_iが与えられる。
この文字列をすべて連結して括弧列を構成できるか判定せよ。
括弧列とは、
- 空文字列
- ある括弧列Aが存在して、「(」「A」「)」の順で連結した文字列
- ある空でない括弧列A, Bが存在して、「A」「B」の順で連結した文字列
制約
- 1 <= N <= 10^6
- すべての文字列の長さの合計は10^6以下
- S_iは空でない
解法
括弧列は、「(」を+1、「)」を-1として扱うと、
- 合計が0になる
- 途中で0未満にならない
をどちらも満たす。
よって、各文字列を「最大どこまでマイナスになるか？」と「最後はどこに位置するか？」で考えればよい。
大きなマイナスのある文字列があった場合、そのマイナス分で負にならないように最初にプラスを増やしておく必要がある。
なので、「最後はどこに位置するか？」がプラスになっているものを全部使って、できるだけ高い位置まで持っていきたい。
このとき、できるだけマイナスが少ないものから使っていけばよく、途中でマイナスになってしまう場合はNo。
全部使ってできるだけ高い位置まで来たら、今度は「最後はどこに位置するか？」がマイナスなものをうまく使って徐々に下っていきたい。
実は、逆方向から見てみると、終点位置から逆に上記と同様の方法で、負にならないよう同じ高さまで持っていけるか？を考えればよい。(線対称)
途中で負にならず、両側からたどった最終位置が同じ地点ならばvalidな括弧列が作れ、そうでなければ作れない。
ABC165 C. Many Requirements
問題
長さNの数列Aで、以下の条件を満たすものを考える。
- 1 <= A_1 <= ... <= A_N <= M
また、Q個の(a_i, b_i, c_i, d_i)が与えられる。
スコアを「A_{b_i} - A_{a_i} = c_iを満たすd_iの総和」とするとき、スコアの最大値を求めよ。
制約
- 2 <= N <= 10
- 1 <= M <= 10
- 1 <= Q <= 50
- 1 <= a_i <= b_i <= N
- 0 <= c_i <= M-1
- (a_i, b_i, c_i) != (a_j, b_j, c_j) (i != j)
- 1 <= d_i <= 10^5
解法
数列Aの個数は、M個から重複ありでN個選んでそれを昇順に並べれば生成できるので、重複組合せで求めることができる。
おおよそ、10_H_10 = 19_C_10で、大きそうに見えるが、実際はそんなに多くない。
(だいたいの見積もりとして、「Σ_{0<=y<=x} x_C_y = 2^x」から「x_C_y <= 2^x」と考えられる。)
2^20 = 1,048,576 = 10^6
2^24 = 16,777,216 = 1.6 * 10^7
全数列が列挙できるので、それに対してQ個の条件を満たすものの和を計算すればよい。
yukicoder No.1035 Color Box
問題
1～Nまでの異なる番号が書かれた箱に、M種類のペンキを使って塗りたい。
このとき、M種類すべてを使って、各箱は必ずいずれかの色に塗られているとする。
このとき、色の塗り方は何通りあるか？
制約
- 1 <= M <= N <= 10^5
解法
N個をM個に割り当てる問題の場合、写像12相が考えられる。
この場合、区別するN個の玉を、区別するM個の箱に割り当てる問題として、各箱には1つ以上入れる場合になる。
式としては、包除原理から「Σ_{i=1}^M (-1)^{M-i} * Comb(M, i) * i^N」となる。
ABC144 D. Water Bottle
問題
底辺が1辺a cmの正方形で、高さがb cmである直方体に、体積x cm^3の水を入れる。
これを底辺のどれか1辺を軸に傾ける。
水が溢れないように傾けられる最大の角度を求めよ。
制約
- 1 <= a <= 100
- 1 <= b <= 100
- 1 <= x <= a * a * b
解法
θだけ傾けた場合を考える。
このとき、傾けたa cm側とb cm側がどちらも無限に長いと仮定すると、
水面となす三角形のa cm側の長さs cm、b cm側の長さt cmとおけば、
体積は、「s * t * a / 2 = x」、角度から「t/s = tan θ」がわかる。
これからs, tがわかる。
この時点でt >= bであれば、こぼれていることになる。
また、t < bでも、s >= aである場合は、水面反対側の側面に接して台形のような感じになっている。
この場合も、同様に変数をおいて、長さと角度からb cm側の水面の位置が求められる。
これでb cmよりも長ければ、こぼれていることになる。
そうでなければこぼれていない。
あとは、θを二分探索でもとめればよい。
ABC161 F. Division or Substraction
問題
正の整数Nが与えられる。
2以上N以下の整数Kを決めて、NがK未満になるまで次の操作を繰り返す
- NがKで割り切れるならNをN/Kに置き換える。そうでないなら、NをN-Kに置き換える
最終的にNが1になるようなKはいくつあるか？
制約
- 2 <= N <= 10^12
解法
まず、「NがKで割り切れる」というのは、Nを割れる数＝Nの約数である。まず、これが割る場合のKの候補となる。
Nの約数dでNを割ったあと、それがまだdで割れるなら操作の条件から割り続ける必要がある。
なので、Nをdで割り切れるだけ割った後の値N'が最終的に1になるかを考えれば良い。
上記以外で、引き算をしてから割り算が発生するか？考える。
引き算してから割り算が発生する＝「X-KをしてからKの倍数になるか？」ということだが、これはXがKの倍数のときしかありえない(上の事例)ので、引き算をしてから割り算が発生することはない。
したがって、Nの約数以外は、引き算のみが行われると考えて良い。
最後に、あるKがあって、あるXが引き算操作のみで最終的に1になるか？を考える。
これは「X-Kを繰り返して最終的に1になるか？」であるが、引き算操作だけ考えればよいので、
1 -> 1+K -> 1+2K -> 1+3K -> 1+4K -> ...
となるKのみである。
言い換えると、
X = 1 + mK (m>0の整数)
の場合に最終的に1になるので、XはKで割ってあまりが1の場合＝「X mod K=1」であればよい。
割り算が発生するケースは、Nの約数について、割れるだけ割ったあとの値XがX mod K = 1を見れば良い。
割り算が発生しないケースは、X=Nの場合＝「N = 1 + mK」になる場合なので、K=(N-1)の約数が答えになる。
約数列挙と割れるだけ割る操作の部分の計算量がかかるが、約数列挙はO(sqrt(N))程度、割り切れるだけ割る操作は、約数の個数*O(logN)程度なので、十分高速に求められる。
ABC161 E. Yutori
問題
N日間のスケジュールSが与えられ、i日目の予定S[i]がoならその日は仕事ができて、xなら仕事はできない。
このスケジュールの中、K日選んで仕事をしたい。
ただし、ある日に仕事をしたら、その直後のC日間は働いてはいけない。
このとき、必ず働く日の日付をすべて答えよ。
制約
- 1 <= N <= 2*10^5
- 1 <= K <= N
- 0 <= C <= N
- 条件を満たすように働く日を選ぶことが可能
解法
最大でM回働けるとする。
これは、日付の順方向にできるだけ最小の日付を取れるだけ取っていけば求められる。
このM回のうち、x回目に働く可能性がある日には幅がある。その幅の範囲にoの日が1個だけならば、その日は必ず選ぶ必要がある。
この幅＝幅の両端を求めたい。
これは、日付の順方向に最小の日付を取れるだけ取っていった場合と、逆方向に同様に向かって取っていった場合を考えれば、それぞれの両端の日付がわかる。
両端の幅の日付が同じ場合＝その幅の中にoの日が1つだけであるので、その日を出力すればよい。
ABC140 E. Second Sum
問題
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 <= N <= 10^5
解法
よくある手として、あるP_iが2番目に大きいものであるような範囲を考える。
A, B, C, D > E、「・」はE以下、として、
・・・A・・・B・・・E・・・D・・・C・・・
のようになっている場合、Eが2番めに大きいものであるような範囲は、
・左側が「Bの右」から「E」まで、右側が「D」から「Cの左」までになっている範囲
・左側が「Aの右」から「B」まで、右側が「E」から「Dの左」までになっている範囲
のような感じになっている。
それぞれの範囲はその区間の個数をかけ合わせたものになるので、それらの和を求めればよい。
これをうまく実装する方法として、setを使う方法がある。
まず、setに-1を2つ、Nを2つ入れておく(ただしそのままだと重複するので、-2,-1,N,N+1にしたり、pairで異なるようにしておく)。
そして、値が大きい順に、setに入れて、その位置をfindなどで探索。そして、そのイテレータから1つ前、2つ前、1つ後、2つ後の要素のindexを取得すればよい。
ABC140 D. Face Produces Unhappiness
問題
N人の人が一列に並んでおり、各人が左を向いているか右を向いているかの情報が文字列Sで与えられる。
各人は、目の前の人が自分と同じ方向を向いていればhappyであり、そうでなければunhappyである。
ここで、0回以上K回以下で、好きな回数だけ以下の操作ができる
- 1 <= l <= r <= Nを満たすl,rを選び、左からl～r番目の人の列を180度回転する
このとき、happyな人の人数は最大で何人にすることができるか？
制約
- 1 <= N <= 10^5
- 1 <= K <= 10^5
- |S| = N, S[i] = LまたはR
解法
操作によって変化する量を確認する。
すると、変化する部分は、指定したl,rの付近のみで、l-1とl、rとr+1の文字のみを考えればよいことがわかる。
今、unhappyな人をできるだけ減らしたいので、そのような人の部分を操作によって減らしていければ良い。
例えば、
LLLLRRRRRRLLLLL
のような場合は、Rの部分を操作するとすべてLになり、unhappyな人がその両端の2人分減らすことができる。
したがって、隣り合う文字列が異なる個数Xを求めて、最大K回まで-2していくことができるので、最終的に「N-1-max(0, X-2*K)」が答えになる。
反省
- 考察をちゃんとできれば無駄な実装なしで簡潔にできる
yukicoder No.1013 ○マス進む
問題
N個の要素からなる順列Pを無限につなげた数列Tを考える。
T上のi番目にいる場合、1回の移動では、「i+T_i番目」に移動する。
K回後に何番目にいるか？をi=1,...,Nについてそれぞれ求めよ。
制約
- 1 <= N <= 10^5
- 1 <= K <= 10^9
- Pは{1,2,...,N}を並び替えた順列
解法
K回後の移動先を高速に求めるためには、ダブリングが有効。
xの位置にいるとき、1回後、2回後、4回後、8回後、、、の移動量を求めておく。
これは、
db[i][j] := 位置がj=x%Nに2^i回移動した場合、いくら移動するか？
を考えると、
db[0][j] = P[j]
として、
// jから2^(i+1)回移動したときの移動量 ＝ jから2^i回移動したときの移動量 ＋ jから2^i移動したあとの位置から2^i回移動したときの移動量 db[i+1][j] = db[i][j] + db[i][(db[i][j]+j)%N]
で更新できる。
そして、j番目のK回の移動先は、jからスタートして、Kのビットが立っているiについてdb[i][pos%N]を加算し続けていけば求められる。
ABC104 D. We Love ABC
問題
文字列TのABC数を以下の条件を満たす整数の組(i,j,k)の個数とする。
- 1 <= i < j < k <= |T|
- T_i = 'A'
- T_j = 'B'
- T_k = 'C'
文字列Sが与えられるが、SはA,B,C,?の4つの文字からなり、?は、AまたはBまたはCに展開した文字列を考える。
?がQ個あった場合は、3^Q個の文字列に対し、それぞれのABC数の和を求めよ。
和は10^9+7で割ったあまりで求めよ。
制約
- 3 <= |S| <= 10^5
解法
「どのA,B,Cを選択したか？」というのを区別する必要がある。
したがって、
dp[i][j][k] := i文字目までで、選択したABCの個数がj個で、最後の文字がkである通り数
のように、選択した個数を状態にしたdpを考えてあげれば良い。
(どれを選択したかは覚えておく必要がなく、すでにAまで選択したか？すでにBまで選択したか？すでにCまで選択したか？がわかればよい。)
i番目がAまたは?である場合、
// そのAを選択しない
dp[i][j][0] += dp[i-1][j][0] + dp[i-1][j][1] + dp[i-1][j][2]
// そのAを選択する
dp[i][1][0] += dp[i-1][0][0] + dp[i-1][0][1] + dp[i-1][0][2]
i番目がBまたは?である場合は、
// そのBを選択しない
dp[i][j][1] += dp[i-1][j][0] + dp[i-1][j][1] + dp[i-1][j][2]
// そのBを選択する
dp[i][2][1] += dp[i-1][1][0] + dp[i-1][1][1] + dp[i-1][1][2]
i番目がCまたは?である場合は、
// そのCを選択しない
dp[i][j][2] += dp[i-1][j][0] + dp[i-1][j][1] + dp[i-1][j][2]
// そのCを選択する
dp[i][3][2] += dp[i-1][2][0] + dp[i-1][2][1] + dp[i-1][2][2]
のような更新を行えばよい。
答えは、Σ_{k=0,1,2} dp[|S|][3][k]で求められる。
ARC060 D. 桁和
問題
2以上の整数bと、1以上の整数nに対し、関数f(b,n)を以下のように定める。
- n < bのとき、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の最小値を求めよ。
存在しない場合は-1を出力せよ。
制約
- 1 <= n <= 10^11
- 1 <= s <= 10^11
解法
どこから攻めればよくわからないので、実験として、サンプル(n=87654)でbを2～1000ぐらい表示してみると、早い段階でほぼ2桁になっていることがわかる。
2桁になるのは、b>=sqrt(N)付近で、そこまでは全探索しても問題ないので、2<=b<=sqrt(N)あたりまでは全探索する。
ここで見つからなければ、b>=sqrt(N)を探索する。
b=N+1のときは1桁になって、それ以降のbではsもNより大きくならないので、2桁の部分を考えればよい。
2桁であるので、n=p*b+qとp+q=sであることがわかる。
pとqがあるが、2式あるので削除でき、n=p*b+(s-p)と書ける。
pをループで回すと考えると、b=(n-(s-p))/pとなって、pが決まればbも一意に決まる。(bが1以下の場合は無視)
pはどこまで探索する必要があるかを考えると、n=p*b+qで、b>=sqrt(N)であるので、実はpもsqrt(N)程度までで十分であることがわかる。
ABC110 D. Factorization
問題
整数N, Mが与えられる。
a_1 * a_2 * ... * a_N = Mであるような、長さNの数列aの何通りあり得るか10^9+7で割ったあまりで答えよ。
ただし、数列aとbが異なるとは、あるiが存在してa_i != b_iであることをいう。
制約
- 1 <= N <= 10^5
- 1 <= M <= 10^9
パナソニックプログラミングコンテスト2020 E. Three Substrings
問題
3つの文字列a,b,cが与えられる。
これらの文字列は、以下の方法で作られたことがわかっている。
- ある文字列sがあり、その連続部分文字列tを取り出す
- tのいくつかの文字を'?'に置き換える
このとき、元の文字列sの長さとして考えられる最小の長さを求めよ。
制約
- 1 <= |a|, |b|, |c| <= 2000
- a,b,cは英小文字または'?'からなる文字列
解法
aとbの合体した文字列に、cがマッチするか？をチェックすると、全体でO(|a| * |c| * |c|)かかってしまって間に合わない。
そこで、文字列aを固定して、文字列bと文字列cがあり得る位置を全探索することを考える。
すると、文字列bと文字列cがあるiとjの位置におけるかどうか？のチェックはO(1)かO(logN)程度で行わなければいけない。
文字列aに対して、文字列bがある位置iにおけるかどうか？は、前計算でO(|a|*|b)で求めておける。
具体的には、文字列aの前後に十分な長さの'?'からなる文字列を付け加えたものを考えれば良い。
同様に、文字列aに対して、文字列cがある位置jにおけるかどうかも、前計算しておける。
したがって、文字列bと文字列cがi,jにおけるかはO(1)で判断できる。
しかし、これでは不十分で、文字列bと文字列cの相対的な位置関係がvalidかどうかも必要になる。
ただ、これも同様に文字列bに対して文字列cの相対的な位置k(負もありえる)がおけるかも前計算できるので、O(1)で判断できる。
よって、文字列bと文字列cの位置を全探索すれば、その時の元の文字列sの長さが求められるので、それの最小値を返せばよい。全体でO(N^2)程度。
パナソニックプログラミングコンテスト2020 D. String Equivalence
問題
長さNの、英小文字からなる文字列を考える。
ある文字列sとtは、以下の条件の時「同型」という。
- |s| = |t|
- 任意のi,jに対して以下のいずれかが成り立つ
- s[i]==s[j] かつ t[i]==t[j]
- s[i]!=s[j] かつ t[i]!=t[j]
また、文字列の標準形とは、
- 任意のsと同型な文字列tに対し、s<=t(辞書順)が成り立つ
このとき、長さNの標準形をすべて辞書順かつ昇順で出力せよ。
制約
- 1 <= N <= 10
解法
N=1と2はサンプルにあるので、N=3のときの標準形を考えてみる。
1種類～3種類までの文字を考えると、
1種類 aaa (bbbはaaaがあるので標準形ではない) 2種類 abb aab aba (baa, bab,bbaは標準形ではない) 3種類 abc (bac,bca,cab,cbaは標準形ではない)
したがって、
aaa aab aba abb abc
の5パターンが考えられる。
next_permutationなど、単純に生成しようとしてしまうと、無駄な重なりを含めて生成してしまうため、時間がかかってしまう。
ここで、生成された文字列から法則を考えてみると、
最初の文字は'a'でなければならない。('b'以降の文字が来る場合はそれを'a'にすることができてしまうため)
次の文字は、'a'か、または、'b'でなければならない。('c'以降の文字が来る場合はそれを'b'にすることができてしまうため)
同様に、その次の文字は、'a'か'b'か'c'でなければならない。
が、それまでに使った文字が'a'のみの場合は、'a'か'b'でなければならない。
・・・のような規則があることがわかる。
したがって、それまでに使った文字で最大の文字+1の文字が次に使えることがわかる。
ABC138 F. Coincidence
問題
整数L,Rが与えられる。
整数の組(x,y)がL<=x
制約
- 1 <= L <= R <= 10^18
解法
(解説放送より)
a xor bは各ビットの繰り上がりのない足し算と考えられる。
y%xは0からx-1までの整数であり、y xor xはx<=yであるので、yの方が一番高いビットがxの一番高いビットよりも上回ってしまうとy xor xがxよりも大きくなってしまって条件を満たせない。
したがって、yはxと一番高いビットが同じところまでのものになる。
また、このとき、y/x=1を満たすので、y%x = y-xと書くことができる。
y xor xの方は、a xor bが「a+b-2*(a&b)」と書けることから、
y-x = y+x-2*(y&x) <=> 2x = 2*(y&x) <=> x = y&x
を満たすx,yの組を探す問題と言い換えられる。
xとyのANDがxと一致するというのは、xとyの各ビットが(0,0), (0,1), (1,1)の場合のものなので、これを桁DPで求める。
条件として、「L<=x」「y<=R」「最も高いビットが同じ」もあるため、それぞれ境界ギリギリか？とすでに(1,1)で使ったか？をフラグに持たせると、
dp[i][j][k][l] := i桁目で、j=xはLギリギリか？、k=yはRギリギリか？、l=すでに1番高いビットが(x,y)=(1,1)で出てきているか？を満たす個数
のように書ける。
遷移は、複雑になるので、(x,y)について、(0,0), (0,1), (1,1)が入ってくるとして、ダメパターンと次の遷移パターンを列挙する
- l=0(まだ1番高いビットがでてきていない)のときで、(0,1)だったらダメ
- j=0(xがLギリギリ)のときで、Lのiビット目が1なのにxが0なら下回るのでダメ
- k=0(yがRギリギリ)のときで、Rのiビット目が0なのにyが1なら上回るのでダメ
- (1,1)なら一番高いビットが出てくることになるのでl=1に遷移
- Lのiビット目が0でxが1ならL
- Rのiビット目が1でyが0ならy
のように書けばよい。
最終的な答えは、iが大きい方から計算して、i=0のときのj,k,lの全パターンをあわせたものを出力すれば良い。
