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を消した時に同じになるか判定する。
XをアレコレしてYにする、って問題はその中間の状態に両方から近づけてやるって発想がたまに功を奏す気がする
— satanic@FEがんばるぞい (@satanic0258) 2017年4月8日
まさにこれ。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を上手く定義することで簡潔に考えることができる。
この辺が下手だな・・・
