No.852 連続部分文字列

Quiz

https://yukicoder.me/problems/no/852

AC Code

https://yukicoder.me/submissions/363142

参考

参考２ ngtkanaさん

https://yukicoder.me/submissions/362752

参考３ 解説の4

https://yukicoder.me/problems/no/852/editorial

解法

  • 各文字ごとに分けて求めることができます(a, b, c.., zの26種類を別々に求める)

各連続部分文字列について全ての文字の種類を含んでいるものと仮定します

  • |s|=6の場合を考えてみよう
  • s = "aaaaaa" と仮定すると、部分文字列のとり方は、6+5+4+3+2+1
  • 一般に N * (N+1) / 2

f:id:peroon:20190727023236j:plain

  • 実際はaxxaxa (xはa以外)のようにスキマがあり、その部分は余分にカウントしている
  • スキマごとに数える
  • スキマの長さをMとすると、そこから取れる「aが存在しない部分文字列」はM * (M+1) / 2 個。これを引く
  • 余分に数えてしまった分を引く。上記例の場合は、'a'について
  • 6(6+1)/2 - 2(2+1)/2

もっと一般的に書くと

f:id:peroon:20190727024127j:plain

B - 超大型連休 ～2012年はうるう年～

f:id:peroon:20190725212020j:plain

Quiz

https://atcoder.jp/contests/arc010/tasks/arc010_2

AC Code

https://atcoder.jp/contests/arc010/submissions/6536656

解法

  • 土曜・日曜に休日フラグを立てておく
  • 祝日の場所もフラグを立てる。すでに立っていたら、以降の立っていない箇所を立てる（振替休日）
  • カウントする

scanf

        ll m, d;
        scanf("%lld/%lld",&m,&d);
  • スラッシュがあるので、このように受け取るといい。普段はcinを使っている
  • scanfを使うときは高速化の下記コードをコメントアウトする必要があった
    // cin.tie(0);
    // ios::sync_with_stdio(false);

2012年はうるう年

  • 最初、for文をfor(i, 0, 365)で回していたのでWA
  • うるう年なので、for(i, 0, 366)が正しい

C - ダブレット ～経路復元～

幅優先探索 グラフ

f:id:peroon:20190725190223j:plain

Quiz

https://arc011.contest.atcoder.jp/tasks/arc011_3

AC Code

https://arc011.contest.atcoder.jp/submissions/6535492

解法

  • wordをグラフのNodeとする
  • 編集距離が1のNode同士をつなげる
    • （編集距離と言っていいのは微妙。追加・削除がないので）
  • bfsでfirst wordからlast wordまで到達できるか調べる

経路復元 私Ver

  • 行けることが確定しているならゴールからスタートにたどればいい
  • たどるごとに距離が1小さいNodeに移動すればいい

経路復元 蟻本Ver

C - 五目並べチェッカー ～やるだけ？～

f:id:peroon:20190725025306p:plain

Quiz

https://atcoder.jp/contests/arc012/tasks/arc012_3

AC Code

https://atcoder.jp/contests/arc012/submissions/6530124

感想

  • やるだけかと思っていたが想定漏れが多くて何度もWA
  • 斜めの処理は意外とやったことがなくて練習になった

テストケースをあげます

  • 下記テストケースはACコードで正しく動いたものです

sample-8.in (NO)

...................
...................
...................
......o............
.......o...........
........o..........
.........o.........
..........o........
.....x.....o.......
......x............
.......x...........
........x..........
.........x.........
...................
...................
...................
...................
...................
...................

oを最後に置いたはずなのにxが勝っているのでNO

sample-9.in (YES)

...................
...................
...................
......o.....ooo....
.......o...........
........o..........
...................
..........o........
...........o.......
......x.....o......
.....x.x...........
....x...x..........
...x.....x.........
..x.......x........
...................
...................
...................
...................
...................

xの5連続が2本あっても、交点部分に最後に置いたのなら正常です。YES

sample-10.in (NO)

...................
...................
...................
...................
.......o...........
.......o...........
.....ooooo.........
.......o...........
.......o...........
...................
...................
...................
....x..x...x.......
......x...x........
...................
...x...x..x..x.....
...................
...................
...................

xを最後に置いたのに、その前の時点でoが勝っているのでNO

sample-11.in (NO)

...................
...................
...ooooooooo.......
...................
...ooooooooo.......
...................
...................
....x.x.x.x.x......
...................
....x.x.x.x.x......
...................
....x.x.x.x.x......
...................
....x.x............
...................
...................
...................
...................
...................

sample9と比較しましょう。oを最後に置いてoの勝ちですが、それ以前に勝ちが確定しているのでNO. sample9ではxを1つ取り除いた時に「まだ誰も勝っていない」状態にできますが、sample11ではそれができないという違いがあります。