naoya_t@hatenablog

いわゆるチラシノウラであります

〈ARC埋め〉ARC 064 E, 067 E, 071 E

AtCoder Performances (thanks to Noiminさんfuurinさん)
f:id:n4_t:20180719224910p:plain:w500

パフォーマンス上げていきたいので600点問題も(それ以上も)埋めます

7月19日

ARC 064 E - Cosmic Rays

  • バリア(円)からバリア(円)に渡っていく
  • スタートとゴールがバリア外だったら?
    • スタートとゴールを半径0の円で囲んでしまえば良いのでは
  • 高々1002ノードのdijkstra (O(N^2))
    • 重なっているバリア同士は距離0、あとは最短距離(中心iから中心jまでの距離-半径i-半径j)

→AC 21'20
https://beta.atcoder.jp/contests/arc064/submissions/2868296

解説解も同様

ARC 067E - Grouping

メモ化再帰で、答えは合うけどサンプル#3が600秒かかる代物が出来上がった…
でも、当然これではいけない(制限時間は2秒!)

DPで、下から足し上げていくと
例えば2人組
2C2/1
2C2/1 * 4C2/2 * 6C2/3 * 8C2/4 * ...
みたいに累積していけるから効率よさそう
N=1000だとN^3/6ぐらいでギリギリ間に合うか?
→AC 74'56
https://beta.atcoder.jp/contests/arc067/submissions/2868645

解説解も同様

これでは一見O(N^3)に見えますが、k の動く範囲は j/i 以下しか考えなくて良いので、そこだけ計算する
ようにするとO(N^2 \log N)になってこの問題が解けます。

なるほど(実際そうしてた)

7月21日

ARC 071 E - TrBBnsformBBtion

  • A→BB→AAB→AAAA→Aのように可逆な変形が可能。
  • A←→BB, B←→AA
  • AをBに、あるいはBをAにすることはできない
  • (空文字列にすると駄目だけど)AAA→ABとかにしておけばそこからAAAを復元することは出来る
  • 文字列を可逆的に変形していくことでA,B,C(=AB=BA=空文字列)のいずれかになる
  • Sの部分文字列とTの部分文字列が同じタイプに変形できるならYES、できないならNOだ

さて
ー AA=B,AB=C,BA=C,BB=A,CA=A,CB=B

  • 左からインクリメンタルにくっつけて行ってよさそう
  • A=1,B=2,C=0 とすればmod 3の足し算
  • 文字列S,TをA=1,B=2に置き換えて累積和を取っておけば各クエリはO(1)
  • mod3なことに注意。(累積和から差分で取り出すとき (ac[b] - ac[a] + 3)%3 のように+3する必要がある)

→AC 35'20
https://beta.atcoder.jp/contests/arc071/submissions/2875465

解説解も同様。
(解説ではA,AA,AAAの3種で說明していたがAA=B,AAA=AB=Cなので等価)