読者です 読者をやめる 読者になる 読者になる

はまやんはまやんはまやん

hamayanhamayan's blog

AtCoder Beginner Contest 058 / AtCoder Regular Contest 071 解説

http://abc058.contest.atcoder.jp
http://arc071.contest.atcoder.jp
www.youtube.com


以下、解説


























A. ι⊥l

http://abc058.contest.atcoder.jp/submissions/1211086
問題文通り判定をする

B. ∵∴∵

http://abc058.contest.atcoder.jp/submissions/1211132
問題文通りくっつけていく

C. 怪文書 / Dubious Document

http://arc071.contest.atcoder.jp/submissions/1208264
全ての文字列に含まれる文字は入れ替えてOK、つまり、文字の順番は関係無い。
まず、「C[i][c] := i番目の文字列に文字cが何個あるか」を計算する
全ての文字列で作れる共通文字列にある文字cが使える回数はmax{i=0...N-1}C[i][c]回である。
そして、辞書順最小のものを出力する必要があるため、その回数分文字をくっつけるが、辞書順で小さい方の文字からくっつけていくと答え。

D. 井井井 / ###

http://arc071.contest.atcoder.jp/submissions/1209490
結論から言うと、x軸での全ての区間の長さの総和をsmx、y軸での全ての区間の長さの総和をsmyとすると、答えはsmx*smyとなる。
これは(a+b+c)*(d+e+f) = ad+ae+af+bd+be+bf+cd+ce+cfとなるから的な感じだけど、良いサイトとかが見つからない。

あとはその区間をどう計算するかということだけど、それぞれdpを作って考える。
dp[i] := [0,i]~[i,i]の区間の総和
dp[i] = dp[i - 1] + len[i] * (i + 1)
このように更新していく。
すると、全ての区間の総和はdp[0] + ... + dp[N-1]となる

それを求めて(calc_sm関数)、掛けると答え
すべての区間の総和の求め方は、もっと凄いのが解説放送で紹介されている。

E. TrBBnsformBBtion

http://arc071.contest.atcoder.jp/submissions/1209296
これも結論から言うと、2つの区間の文字列を全てAに変えて、3つ毎のAを消した時に同じになるか判定する。


まさにこれ。SRMでもこういう問題が出た。

各クエリでやるべきことは
1. Sの範囲[a,b]とTの範囲[c,d]のAの数とBの数を高速に数える
2. BをAAにする
3. 3つごとのAを消した時に同じになるか判定する
だが、
1. 累積和でAの個数を持っておく(Bの個数は(範囲の個数)-(Aの個数))
2. 「(Aの個数) + (Bの個数) * 2」個のAとなる
3. mod3で比較して同じであれば消した時に同じになる。
これをやるとAC

F. Infinite Sequence

http://arc071.contest.atcoder.jp/submissions/1212119
解説放送通り実装したので、解説放送を見ながら、見てもらえると分かる。
dp[i] := 数列のi番目以降が全て同じになる数列の組合せ
dpを上手く定義することで簡潔に考えることができる。
この辺が下手だな・・・