F - Pure ～ワーシャルフロイド・最小閉路・経路(パス)復元～

解法

補足

  • N=1000で通るのか？ギリギリ通る（事前にワーシャルフロイドだけして提出 1000msなのでギリギリ通ることを確認)
    • N=1000
    • O(N3)のワーシャルフロイド。ここが計算量のボトルネックで、実行時間は1100ms. よって109は超シンプルでギリギリ通る
  • uからvに行き、vからuに行くと最小のサイクル
    • そういうu, vをO(N2)の全探索で探す。見つけた後はpath(u, v), path(v, u)を求めればよい
  • path(u, v)はbfsで求めた。配列revで足跡を保存
    • (変数名はpreでもいいかも)

f:id:peroon:20191001042803p:plain

(revを用いた)経路復元

// iからjへの経路
// N : 頂点数
// G : graph (vector<vector<int>>)
VI get_path(ll i, ll j){
  VI rev(N, -1); // どこから来たかを保存
  vector<bool> visited(N, false);

  // bfsして各頂点への最短路を求める
  queue<ll> que;
  que.push(i);
  visited[i] = true;
  while(!que.empty()){
    ll from = que.front(); que.pop();
    for(ll to : G[from]){
      if(visited[to]) continue;
      visited[to] = true;
      rev[to] = from; // どこから来たかを保存
      que.push(to);
    }
  }
  VI ret;
  ret.push_back(j); // 終点から足していく
  
  ll now = j;
  while(true){
    ret.push_back(rev[now]);
    now = rev[now];
    if(now==i) return ret;
  }
}

B - Sorting a Segment ～テストケース生成してナイーブ解と比較 naive～

解法

  • editorialは読み、解説放送も見たとする
  • まったく被りなしの場合は答えがN-K+1で、これが最大。ここからダブルカウントしてしまった分を引いていく
  • まず、Kの幅ですでにsortedな箇所がいくつあるか数える。その数をSとすると、S-1回だけ多く数えているので引けばいい
  • 次に、Kの幅ですでにsortedじゃなくても同じ数列になる場合を考える。例えば以下のような場合

f:id:peroon:20190922171120p:plain

  • K+1の幅で見て、左端がmin, 右端がmaxであればi, i+1はequivalentである
  • これはK+1個を入れたsetを作ることで高速にチェックできる。計算量はiを全部動かしてO(N log(K))
    • 最小値 *set.begin()
    • 最大値 *set.rbegin()
  • iをずらすたびにsetから要素削除・要素追加して更新していく
  • i, i+1がequivalentである数を数えた結果Cだったとすると、Cだけ多く数えているので引けばいい
  • まとめると、answer = N-K+1 - (S-1) - C

テストケース生成

  • 考える幅がKだったりK+1だったり、setのrbeginを使ったりで添え字ミスが発生しやすく、サンプルでは通るが提出後ほとんどWAとなった
  • この機会なのでテストケース生成をちゃんとやってみた
  • アルメリアさんの記事に詳しい https://betrue12.hateblo.jp/entry/2019/09/07/171628
  • 用意するものとして
    • 解法.cpp
    • 愚直解.cpp
    • サンプル入力生成.py
    • それを回す.sh
  • これを回すことで、ローカルでWAとなるサンプルが作れ、最終的に無事ACすることができた

naive解のnaive.outを出力

g++ -o naive.out naive.cpp

サンプル入力生成.py

import random
N = random.randint(4, 10)
K = random.randint(2, N)
print(str(N) + ' ' + str(K))
A = range(1, N+1)
A = list(A)
random.shuffle(A)
print(*A)
  • できるだけ小さいNで見つかったほうが検証が楽

注意 sh too many arguments

  • 出力が複数行の場合、スペースや改行で区切られるが、その比較はうまくいかないようでtoo many argumentsと表示される
  • 比較時のみ、改行やスペースを除去すればちゃんと比較できた
  • 追記：下のように＄変数をダブルクオーテーションでくくると比較できる(ifの行)
g++ answer.cpp
g++ naive.cpp -o naive.out

while true; do
    python3 ./generate.py > input.txt
    ans1=$(./a.out < input.txt)
    ans2=$(./naive.out < input.txt)
    if [ "$ans1" != "$ans2" ]; then
        echo "Wrong Answer"
        echo "a.out", $ans1
        echo "naive", $ans2
        exit
    fi
done

同じ問題をZ-Algorithm, Suffix Array, Rolling Hashで解く

Quiz

  • https://atcoder.jp/contests/abc141/tasks/abc141_e
  • 3パターンで解いた。とはいえ完全に「けんちょん」さんの記事に依存している
  • 解いた順に書く
  • あとから検索する用に書いている。1度使ったコードは安心感があるため

1. ローリングハッシュ（ロリハ）

2. 接尾辞配列

f:id:peroon:20190916153328p:plain

3. Z-algorithm

好きな順番

  • Z-algo（短いしハッシュ衝突もしないため）
  • ロリハ（理解できるため）
  • Suffix Array（理解できないため）

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

ローリングハッシュの衝突回避と定数倍高速化

f:id:peroon:20210306102041p:plain

Quiz

Submission

衝突した状況

  • 途中のデータでWA. 1つのロリハでは衝突してしまったのだろう

衝突回避のために取れる手段１

  • ロリハを複数本用意する
    • 計算量が本数倍になる。今回の問題では1本で1100msほどかかっているので2本に増やすとTLEする

ロリハを複数本用意するときの知見

  • modを変えた2本を用意したがWAが取れなかった
  • 他のパラメータとして、baseというのがあり、そちらも変えたらWAは消えた
  • しかし本数を増やしたのでTLEは残る

衝突回避のために取れる手段２

  • ハッシュで衝突を発見したあと、実際に部分文字列どうしの比較で追加チェックを行う
  • これでロリハを１つに抑えつつ、衝突も回避できる
  • これで通したのが上記Submissionである
ll hash0 = rh.get(i, i+L);
ll hash1 = rh.get(j, j+L);
if(hash0==hash1 && s.substr(i, L)==s.substr(j, L)){
  // ...
}

別解

別解2 z algorithm

BITを2つ使って範囲加算・範囲和 (区間加算・区間和) range add

ライブラリ Binary Indexed Tree

注意

  • range add, range updateは区別しよう
  • 今回はrange add

使った問題

Submisssion

https://atcoder.jp/contests/abc141/submissions/7551683

できること

  • 範囲加算 [a, b) にwを加える
  • 範囲和 [a, b)の和を求める
  • (計算量 : それぞれlog(N))

内部実装

// ei1333's BIT
struct BIT {
  VI data;
  BIT(){}
  BIT(ll sz) {
    resize(sz);
  }
  void resize(ll sz){
    data.assign(++sz, 0);
  }
  ll sum(ll k) {
    ll ret = 0;
    for(++k; k > 0; k -= k & -k) ret += data[k];
    return (ret);
  }
  void add(ll k, ll x) {
    for(++k; k < data.size(); k += k & -k) data[k] += x;
  }
};
 
// 区間更新・区間和
struct Range{
  BIT P, Q;
  Range(ll sz){
    P.resize(sz+1);
    Q.resize(sz+1);
  }
  // 範囲加算 [a, b) にwを加える
  void update(ll a, ll b, ll w){
    P.add(a, -w*a);
    P.add(b,  w*b);
    Q.add(a,  w);
    Q.add(b, -w);
  }
  // [0, c)
  ll simple_sum(ll c){
    return P.sum(c) + Q.sum(c) * c;
  }
  // [a, b)
  ll sum(ll a, ll b){
    return simple_sum(b) - simple_sum(a);
  }
};

verified

追記：2020/09/19

  • 区間加算はセグ木使う人が多いようだけど、BITのコレで今でも戦えています