geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

ABC214 参加記録

C -Distribution

すぬけくんの番号を0-indexedとします。i番目のすぬけくんが宝石をもらう最短時刻ans[i]が分かっていれば、i+1番目(正確には(i+1)%N)のすぬけくんが宝石をもらう最短時刻ans[i+1]は、

ans[i+1] = min(T[i+1], ans[i] + S[i])

で求まります。これをT[i]が最も小さいものから始めて、順に一周分計算すれば全ての時刻が求められます。

 

最初、常に1番目のすぬけくんから計算を始めていたため、WAとなりました。解説の通り、2周すれば問題なかったです。

提出コード:https://atcoder.jp/contests/abc214/submissions/25035652

 

D - Sum of Maximum Weights

全て計算するのは間に合わないので、競プロ典型90問にもありますが、辺e=(u,v)の重みwについて、答えとする総和への貢献度を考えてみます。

 

一旦、最大値という条件を無視して、異なる2頂点のパスで通過する辺の重み全ての総和をとることを考えます。2頂点のパスがeを通るような2頂点の組み合わせは、辺eを切断した時の[頂点uが属する部分木の頂点数]×[頂点vが属する部分木の頂点数]だけ存在します。よって、各辺の重みwについて、

[頂点uが属する部分木の頂点数]×[頂点vが属する部分木の頂点数]×w

が総和への貢献度で、これの総和をとると答えになります。

例) x-y-z-u-v-a-bという木があり、u-v間の辺eを通過するパスを構成する2頂点の組み合わせを考える。u-v間で切断した時、

x-y-z-u 4個

v-a-b 3個

の二つの部分木ができ、(x,y,z,u)から1頂点を選び、(v,a,b)からもう1頂点を選ぶと、そのパスはeを通過するので、eを通る組み合わせは12通りであり、eの重みwは12回総和に足されることになる。

 

では、最大値という条件を加えてみます。

木の重みの最大値の総和への貢献度は上記と同じように求まります。ここで、最大値の貢献度を答えに加算しておけば、以降最大値を持つ辺は切断して考えても問題ないことがわかります。よって、重みが大きい順に、「貢献度を計算してその辺を切断する」ということを繰り返せば、答えが求まります。

 

しかし、辺を切断して順に部分木の頂点数を求めるのは困難です。逆の発想で、重みを小さい順に考え、重みの最小値について貢献度を計算し、最小値を持つ辺を接続していくというのどうでしょうか。この方法で問題なく、しかも木を接続するのはUnion-Findによって実現でき、部分木の頂点数も取得できます。

提出コード:https://atcoder.jp/contests/abc214/submissions/25041623

 

E - Packing Under Range Regulations

貪欲法っぽいとは思いましたが、解けなかったので解説を見ました。

貪欲法の予想は合っていました。今回はどのような貪欲法だったかというと、

「x番目の箱に入れられるボールであって、まだ他の箱に入っていないボールのうち、Rが最小のものをx番目の箱に入れる」

でした。

 

Lの小さい方から順番に入れていく必要があるので、L,Rの昇順にソートされている必要があります。この貪欲法で大丈夫な理由は、Rが大きいものはその後の箱に入れられる可能性があるため、Rが最小のものを選ぶことが今後の割り当てを考える上で最善となるため、でした。

 

後々の状況をよくできる、というのは貪欲法の考え方でよく見る気がします。あとは、あるものとあるものを入れ替えても状況が悪化せずにスコアを上げられる、などもあるでしょうか。

 

実装は自力でしてみましたが、WAが結構出てしまい、状況を網羅するのがややこしかったです。一番WAを出していたのは、入れるボールがなくなった時点(i==N)で、ループを抜けていましたが、キューに候補のボールがなくなるまではループしなければいけませんでした。

提出コード:https://atcoder.jp/contests/abc214/submissions/25121459

F - Substrings

解説なしでACできました。

Web版の公式解説と違った方法でした。

(嘘解法でないという保証はできないですが)

 

根本の考え方は同じで、重複した部分列ができるのを避けるというものです。

 

i番目までの文字を考慮したときにできる部分列の総数を考えます。(解説では末尾がS_iであるものに限定されています。ここでは、限定していないすべての部分列を考えます。)

 

i番目より前で、初めてi番目の文字と一致する位置を、j番目とします。

 

j番目ではj-2番目までに作られた全ての部分列に対して、S_jを付加しています。そのため、j-2番目までに作られた部分列にS_iを付加すると、重複が発生します。

 

そこで、i-2番目までの全ての部分列にS_iを付加した後、重複した分のj-2番目までに作られた部分列の分を引きます。これによって、重複のない部分列の総数が得られます。

 

dp[i]:=i番目までを考慮して得られる文字列の総数

とします。なお、実装上Sの前に空文字が2つあると想定し、初期状態は

dp[0] = dp[1] = 1とします。

 

遷移は、以下のように、場合分けが起こります。

(1) S_iを付加しない場合

  i-1番目までにある全ての部分文字列が引き継がれます。よって、

  dp[i] += dp[i-1]

(2) S_iを付加する場合

  i-2番目までにある全ての部分文字列にS_iを付加します。よって、

  dp[i] += dp[i-2]

  ここで、S_iと同じ文字が既に出現している場合、

  その直近の位置をj番目とします。

  j-2番目までに現れた部分文字列にS_iを付加すると、

  S_jを付加した部分文字列と重複が生じるので、これを取り除きます。よって、

  dp[i] -= dp[j-2]

 

これで、dp[|S|+2]から部分文字列の総数を得ることができます。

提出コード:https://atcoder.jp/contests/abc214/submissions/25333036