ICPC2018国内予選 H問題

今年もチームcatsatmatで出場しました。4位で通過出来て嬉しかったです。

• H問題

前原先生の記事
木上のナップサック問題
でだいたいわかりますが、コードを載せておきます。

まず、素直な解法として、dp[v][c] := vの部分木についてコストcで得られるmaxとおくとO(nkk)ですが、このままでは高速化が難しいです。

ポイントは、各頂点vの子たちを、vの必要量の昇順に並べておくと、ある子に潜ることが出来る時その手前の子たちも全部使えて、このことを利用するとdpの配列を持ちつつdfsすることができるという点です。これだけでオーダーが良くなるのは不思議な感じですね。これに加えて各頂点に使える上限があるので面倒になっています(このパートはスライド最小値をやると線形で解けます)　よって時間計算量はO(Case * NK)です。100*100*10^5 = 10^9を8秒なので結構実装に気を使わないといけません。

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; ++i)

typedef vector<int> vi;
typedef long long ll;
typedef vector<ll> vl;

const ll inf = -1e18;
const int MN = 110;
const int MK = 100010;

inline void chmax(ll &x, ll y) { if (x < y) x = y; }

int n, k;
vi g[MN];
int h[MN], s[MN], lo[MN];
vl dp[MN];
int deq[MK];

void dfs(int v, vl vec) {
    vl &res = dp[v];
    
    int l = 0, r = 0;
    
    for (int i = 0; i <= k; ++i) {
        if (vec[i] != inf) {
            ll x = vec[i] - (ll)i * s[v];
            while (l+1 <= r) {
                int id = deq[r-1];
                if (vec[id] - id * (ll)s[v] <= x) {
                    --r;
                } else {
                    break;
                }
            }
            deq[r++] = i;
        }
        if (l+1 > r) {
            res[i] = inf;
            break;
        } else {
            res[i] = vec[deq[l]] - (ll)deq[l] * s[v] + (ll)s[v] * i;
            if (deq[l] <= i - h[v]) {
                ++l;
            }
        }
    }
    
    for (int to : g[v]) {
        dfs(to, vec);

        vl &nx = dp[to];
        
        for (int i = 0; i <= k; ++i) {
            chmax(vec[i], nx[i]);
        }
        
        l = r = 0;
        for (int i = 0; i <= k - lo[to]; ++i) {
            if (nx[i] != inf) {
                ll x = nx[i] - (ll)i * s[v];
                while (l+1 <= r) {
                    int id = deq[r-1];
                    if (nx[id] - id * (ll)s[v] <= x) {
                        --r;
                    } else {
                        break;
                    }
                }
                deq[r++] = i;
            }
            if (l+1 > r) {
                nx[i] = inf;
                break;
            } else {
                ll val = nx[deq[l]] - (ll)deq[l] * s[v] + (ll)s[v] * i;
                chmax(res[i + lo[to]], val + (ll)s[v] * lo[to]);
                if (deq[l] <= i - (h[v] - lo[to])) {
                    ++l;
                }
            }
        }
    }
}

int main() {
    while (cin >> n >> k, n) {
        rep(i, n) dp[i] = vl(k + 1, inf);
        rep(i, n) g[i].clear();
        rep(i, n) cin >> h[i];
        rep(i, n) cin >> s[i];
        for (int i = 1; i < n; ++i) {
            int p; cin >> p; --p;
            g[p].push_back(i);
        }
        for (int i = 1; i < n; ++i) {
            cin >> lo[i];
        }
        rep(i, n) {
            sort(g[i].begin(), g[i].end(), [&](int a, int b) {
                return lo[a] < lo[b];
            });
        }
        vector<ll> vec(k + 1, inf);
        vec[0] = 0;
        dfs(0, vec);
        cout << *max_element(dp[0].begin(), dp[0].end()) << endl;
    }
    return 0;
}

2016-2017 National Taiwan University World Final Team Selection Contest

結構前のコンテストですが、G問題がシンプルだけどどこか新鮮で面白かったので紹介します
Dashboard - 2016-2017 National Taiwan University World Final Team Selection Contest - Codeforces

概要
N個(値段:p_i)の空でない部分集合であってK番目に値段の和が小さいものを求めよ(復元なし)
2 ≤ N ≤ 2 × 10^5
1 ≤ K ≤ min(10^6, 2^N - 1)
1 ≤ p_i ≤ 10^8

解法
まずpを小さい順にソートします。もちろん2^N通り全列挙は出来ないのと、Kはあまり大きくないので、小さい順に列挙することを考えます。
ここで、ある集合の1番右のものの次を続けて使うorある集合の1番右をやめてその右隣を使うという遷移をすることにすると、価値が単調に増加するように遷移出来て嬉しいことがわかります。(イメージしにくいですが)
よって、priority_queue等で管理しつつ遷移していくことでO(KlogK)で解くことが出来ました。

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

const int MN = 200010;

int N, K;
int p[MN];

int main() {
	scanf("%d %d", &N, &K);
	rep(i, N) scanf("%d", &p[i]);
	sort(p, p + N);

	using Data = pair<ll, int>;
	priority_queue<Data, vector<Data>, greater<Data>> que;

	que.push(mp(0LL, -1));

	ll la = -1;
	++K;

	while (K--) {
		Data t = que.top(); que.pop();

		ll val = t.fi;
		int pos = t.se;

		la = val;

		if (pos == N-1) continue;

		//add next
		que.push(mp(t.fi + p[pos + 1], pos + 1));

		//replace
		if (pos != -1) {
			que.push(mp(t.fi + p[pos + 1] - p[pos], pos + 1));
		}
	}

	cout << la << endl;

	return 0;
}

ACM-ICPC 2016 Asia Tsukuba Regional 参加記

チームcatsatmatで出場してABCDEFGの7完11位でした。真面目にUSキーボードの練習をしたので今度はJISがわからなくなって困っています。しかし環境に慣れていなかったのはアレかなあ　自分はgeditで頑張りました

まずコンテストパートについて

自分はパソコン操作が苦手なのでAはとりあえずさっさと書ける人(catupper)が通した

Bをshiatsumatが読んでやるだけというので書いてもらっている間に, 自分がCを読んでcatupperに話したら一瞬で区間と言われすごい(小並感)となった B少し面倒ということで実装が軽そうなCを先に通すことにした　FAだった

そしてBの続きをやってもらって無事AC

Cをやっている間にshiatsumatたちがDを読んでにぶたんではと言っていたが普通に嘘なことに気付いた　あぶなかった
普通にO(N^2logN)で出来ることはすぐにわかったが, 26倍とかをつけるとTLEが不安だと思った(ここでとりあえず投げたらみたいな声が出たので投げたが普通に手元でテストするべきだった...(その後結局手元で最大ケースを作って試したので))
vectorをsetに突っ込むのをやめて適当なhashにしたがTLE
ここで両方setに突っ込んでから答えを求めるのが自明に無駄で片方しか突っ込まないことにしたら2倍速くなってACした
この辺でかなりもたついてしまった...

Dをやっている間に問題を読み進めてもらう
Eは後回しで良くないという感じになりその後のFはshiatsumatが解法を思いつき, Gはcatupperが読んでいて問題を説明して貰うと自分が思考停止segment treeと言ってしまい面倒な方針になってしまった(実際にはsegtreeがすぐ書ければよかったが, 座圧しにくくて必要なところだけ作るsegtreeになったため(JOIのapples的な))ライブラリを写さずsegtreeパートにバグを埋めるのに気付くのに時間がかかって残念

FGを書いたりデバッグされたりしていてHはかなり大変そうに見えたので大人しく自分がEを書くことに
というかFはあんまり通されなかったのにすごい(小並感)
FとGで共にWAを出して並列にデバッグしたため同じくらいにACとなった

H以降を考えてもらう間にEを自分が頑張って書く
普通に全探索して文字列を生成して, 生成した文字列が正しいかチェックする関数に投げまくる方針だった
構文解析にあまり慣れていないのと, 正しいとは限らない文字列をパースするのがややこしくて結構混乱してしまった
return がところどころ抜けていたり, C++に疎いので例外を投げるのではなくてINFを返す実装にしたらところどころINFだったらINFを返すみたいなのを忘れてしまったりしてデバッグが大変だった
デバッグしていたら出来たので提出したらTLEが返ってきて!?!?!?となった
パースする関数が無限ループしてるのかと思って真面目にチェックしたが結局全列挙パートを速くしたら通ってなんやねんとなった
ここでめっちゃ時間かかったの戦犯ですね...

最後の方はcatupperがHを慌てて書いている間にIを自分とshiatsumatが考えていた
やばそうな方針を誰かが提示しては計算してどれくらいになりそうかチェックするやつをやっていたが,
それまで出ていた方針と, なんか対角線とそれに近い点を取ってくるやつを合わせれば上手くいきそうなことが終了間際にわかった
Iは好き

終了

感想 :
メンバーの実力が近くてGまではまあ誰がどれをやっても解き切れそうな感じだったのは良かったと思う
Iを通せなかったのは反省
HJKは現状厳しい感じだったので各自もう少し実力が必要
やっぱり慣れない環境で問題を解くと時間が凄いかかって大変ですね
surreal numberってなんやねん(呆然)

コンテストパート以外
１日目、着くといきなり受付が英語でここは日本か？？？となった
日常生活で疲れが溜まっていたため交流パートは頑張れなかった
ホテルがこの前泊まったところだった、QOLが高かった(睡眠も良く取れた)
イベントとしてよく出来ていてすごい(小並感)
コンテスト後の懇親会的なものは、ブースがたくさんあって何か思っていたのと違った
クイズを解いたり、色々なものを貰えて嬉しかった(realforceのキーボード, 水樹奈々の謎DVD, その他たくさん)
楽しかったので来年も盛り上がってほしい
C某d某F某s某i某a某の宣伝が多く感じた(たのしみ)

海外の地区には行かないので(行く意味もあまりないけど)
来年もがんばるぞい(東大は地区予選に行くのすら大変なため)

良いコンテストありがとうございました

SA-IS

Suffix Arrayを空間・時間計算量共に線形で構築出来るというアルゴリズムSA-ISを, 以前ふわっと読んだことはあったけれど真面目に読みなおしました. よく出来過ぎだと思う. 細かいところの理解が間違っていたら教えて下さい. ざっくりとした流れしか書きません. ちゃんとした証明とかは元論文を見てください. というかこんな記事よりiwiさんのブログとかがわかりやすいと思うけど自分で忘れないために書きました.

(元論文: Linear Suffix Array Construction by Almost Pure Induced-Sorting)

文字列の最後には最小の番兵を置いておく.

記号を色々定義しておくと,まず
Suf(S,i):=Sのi文字目以降のsuffix
Suf(S,i)がS-type...Suf(S,i)Suf(S,i+1)
Suf(S,i+1)とはSuf(S,i)の先頭を除いたものであることに注意(当たり前だけどはっきり意識した方がわかりやすいと思った)

LMS...Suf(S,i)がS-typeかつSuf(S,i-1)がL-type
LMS-substring...LMSから次のLMSまでの部分文字列(両端含む) また最後の番兵はそれだけでLMS-substringということにする

ここで,LMSたちのsuffix arrayが求まっていたら全体のsuffix arrayが計算出来ることがわかる(Induced-sorting)
まず,考えると出来上がったsuffix arrayでは(先頭の文字,type)でブロックに分けることが出来るのがわかる(L-typeがS-typeの前に来る)

とりあえずLMSたちをその小さい順にブロックに入れていく. LMSの順番だけが重要だとわかるので場所は確定出来なくてよい.
次に,SA[i]を小さい方から見ていって,SA[i]が埋まっていてSA[i]-1がL-typeならばS[SA[i]-1]のブロックの後ろにSA[i]-1を入れる.
というのもSA[i]-1がL-typeならばSA[i]はL-typeまたはLMSで,いずれの場合もSA[i-1]はSA[i]より大きく,またs < tの時'x'+s < 'x'+tであるから小さい方からやるとうまくいく. これでL-typeのsuffix arrayが求まる.
次に,S-typeを埋める.これは今度はSA[i]を大きい方から見てほぼ同じことをする.LMSを入れた場所は上書きしていいことに注意.

以上より,LMSがソート出来ていればsuffix arrayが求まる.

次に,上の手順を行うためにLMSたちをソートする方法を考える.
これは上で定義したLMS-substringたちのランクを文字として扱って(LMS-substringを比較する時には文字にtypeの属性も含める), suffix arrayを求めれば(ここで再帰が呼ばれる)出来ることがわかる.
よってLMS-substringの順位付けを考える. ここにもInduced-sortingが使えるというのがSA-ISのすごいところらしい.

実はこれは,LMSたちの先頭でとりあえずバケットに分けて(同じバケットの中では開始位置が後ろのやつから入れる) induced-sortingすればよい.
これはその文字列のk文字目までソートしてあるとk+1文字目までの情報が...という感じになるのでLMS-substringたちが正しい順番で並んでくれるため
は?という感じだがよく考えると上手く出来ている
sortされたLMS-substringたちのrenameは,まあLMS-substringの和はN未満なので愚直にやってよい(1つ前と同じかどうか調べる)

おしまい

参考:
SA-IS - (iwi) ｛ 反省します - TopCoder部
SA-IS - Shogo Computing Laboratory

JAG夏合宿2016参加記

参加記を書き書き(典型)

去年に引き続きJAGの夏合宿に参加してきたので感想を書きます(合宿代安くて有り難すぎる)

ICPCアジア地区のチーム(catsatmat)のうち自分だけの参加となりました(悲しい)

・day1
合宿初日、コンテストは無し。懇親しなかったのでtozangezan/DEGwerとMTKに行きました。あとyosupoさんがいた

・day2
朝食を食べ損なう。この日はsnukeさんとatahunというチームで出ました。snukeさんはこのセットはOpencupで参加したことがあったらしく記憶がある問題は自分が考えることに。

自分がまずCを書く。朝に弱いのでクソコードを書いてRE。
コードを見てもらっている間に朝なのでH(Good morning!)を通す。
Iが簡単そうだったので書く。WA。(見た目はミスってなさそうだったのでsnukeさんに後でchallengeケースを作ってもらってなるほどなあ...ってなった。実際簡単だけど丁寧にやらないとダメなことが後でわかった)
Iを直す前にCの方針を変えて綺麗に書くと通る(ごめんなさい...)
Dが簡単とのことなのでsnukeさんに通してもらう。
Iをちょっと直してAC。
Fはrng問題のdictionaryみたいな感じだけど3種類しかないので愚直にdpをヒイヒイ言いながら書く。実際TLがきつかったので前計算出来るところをするようにするもTLE。もしやと思ってdpの初期化パートをmemsetから真面目に必要な分だけすることにするとAC。テストケース数を明示してほしい....
Lを考えているとKがわかったとsnukeさんが言うので書いてもらって単独AC。sugoy
Lが区間dpで解けることがわかるも時間切れ。なんか細かいところをすぐミスるなあ...という感じ。Fに時間を吸われすぎた。夜はsnukeさんとMTKに行った。

・day3
朝食を食べ損なう。(2回目)この日はヒカリエのLINE会場。ICPCチームの指圧マットが来てくれたので2人で出ました。

Aを指圧マットに読んでもらって簡単そうということで提出(難易度順なのかなと思った)。WA。数字が連続していないといけないのを見落としていたらしい。直してAC。
その間に自分がBを読んでゴールまでの最短距離が他のより小さいならOKということがわかったので書く。簡単だけど綺麗だと思った。
AC。
Cが地獄っぽいので指圧マットに任せて(最低)D以降を読んで考えていく。
Dを読むが少しややこしそう...なのでEも読むがまともな解法がありそうに見えなかった。F,Gも読むがほぼ思考せず。幾何は余裕がなさそうかなあという感じだった。(結果的には簡単でしたね...)
そうこうしているうちにCが書けたというので提出してWA。実はサンプル1つ答えが合ってなかったらしいがコンテスト終了まで気付かず大反省。Cのコードをチェックしていてもらう。
Dがわかったつもりになったので書いて提出してWAを貰う。2/3くらいは通っていたのでなんでやという気分になる。
どこがまずいかわからないしEはハッシュでやると子同士で重ねあわせ出来ていい感じっぽいなあと思ったので愚直ハッシュを書いて送ったらACが貰えてびっくりした。
Dの方針を説明して指圧マットにも考えてもらう。自分は")))...)"の列に"("たちを挿入してコストがどうなるかを考察した感じになった(指圧マットはグリッド上の経路として考えていたが結果的な方針は同じだと思ったが...
数分で書けるようなコードだったので指圧マットの方針で書いてもらってAC。激ごめんなさいという感じに...
まだCのWAが取れていなかったのでCを見直してもらってFを考える。最後に使うやつを全部試して後を高速化する方針だとRMQが必要な感じになった。(解説の方針の方がバグりにくそうだったなあ.....)添字が1ずれたりして苦戦しながらなんとかAC。
結局Cはiteratorのインクリメントの前置後置に問題があったらしい。かなしいなあ... サンプルのWAに気付かないのは流石にダメ。

夜はsugim48さん作のAGC004があった。開いてBを少し考えるも問題の解釈とサンプルが合わないのでDを考える。木なので葉からdfsするだけで良いとわかる。Cを考えるもわからない。Bを読み直すと意味がわかる。綺麗。Aを書く。Cはどう頑張ってもわからない....これはまあわからない時はわからないやつだなあという感じになったのでEを考える。状態HHWWなdpが出来そうなことがわかるが遷移にこまる。終了(絶望)

夜MTKにみんなで行くも閉まっていて悲しかった。

・day4
朝食を食べ損なう(3回目) Klabでラブラブ。この日はHecさんとYazatenさんとチームMILK_TEAで出た。(メモ:2015-2016 XVI Open Cup, Grand Prix of Bashkortostan, SKB Kontur Cup Stage 2)

時系列で書くの疲れたので...
A: ColorfulBoardじゃんと思ったとみんな言っていて面白かった。
B: 無理ゲーらしい
C: 公比1かそれ以外で場合分けするも公比1の時1+1+...+1以外のパターンがあるのになかなか気付かずハマった。ごめんなさい...
D: 2分探索出来ないのに注意。1/iの和がNlogNなのでRMQを書いてAC。
E: 読んでない。
F: 問題を見た感じ嘘をつきやすそう。
G: 読んでない
H: ICPCという感じの問題。紙コーディングで詰めたの初めてだった。暦の仕様を読み飛ばして1WAもらった(なんで100日あるんや)
I: 手元でテストすると40回も質問すればx1が一意に定まることがわかったので特定した後はやるだけ。
J: しばらく考えたらdp[i][j]:i番目まで見てAの和=jの時のBの和の最大値 としてdpしてj < pについてdp[n][j]がqより小さければOK
(p,qとA,Bをswapして2回やる) 復元が面倒...
K: しらない
L: aの長さで漸化式が立つことがわかる. 意外とiが膨れ上がることがあるらしくmapとlong longにしたら通った。ちゃんとテストしようね...
M: しらない

なんか家でやる時とオンサイトなコンテストだと全然速度が違って悲しくなる3日間だった。まあ焦るしね

さいごに: クソなぞなぞ: ~ に早く飽きないとまずい

Atcoder Grand Contest No.2

コンテストを寝過ごしたので解いた. Dの一般的なテク感すき. きれい. Bが面白い感あった

Eはとりあえずグリッド上を動くゲームなことまではわかったけどあんま考えてない.

Fの方針が解説と少し違ったので書いておこう.

1~Nの1番左のもの(0は無視)がこの順番にあることにして最後にN!をかける. ここで0は出てくる順番に1~Nと結びつけて良いことがわかる

よって0NN..NN (NはK-1個)から始めて, 0(N-1)(N-1)(N-1)...(N-1), ...., 01...1を間に追加していくことが出来ないか考える.

まず上の考察により新しい0は1番左に. そして0iii,,,iを足す時, 1番左のiは, 現在の列の1番左の(i+1)より左, つまり0でない要素のうち1番左より左に入れないといけないことがわかるが, これは先頭の0の個数を状態として持てばOK.

よってdp[i][j]: 大きい方からi種類追加して先頭にj個0があるような条件を満たす並べ方の個数とおくと, 状態はO(N^2)で
遷移も1番左のiを置く場所を全部試すことで遷移O(N), 合計O(N^3)で計算可能. (実際は二項係数を求めるのにlogがつく)

しかし, 係数の式を考えるとそれは新しい1番左のiの場所にしか依存しないことがわかるので, dp[i][j]のjの大きい方から累積和を持っておくことでO(N^2log hoge)で解くことができる.

解説みたいにグラフにするとわかりやすくて感動した.

追記: 1<=i<=Mについてi!の逆元を求めたい時, M!の逆元を求めた後逆向きにかけていけばO(N^2)で計算出来るの今まで気付いてなかった...というわけでO(N^2)で解けます

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

const ll MOD = 1000000007;

ll f[4000010];
ll invf[4000010];

ll mod_pow(ll x, ll k)
{
    ll res = 1;
    for (; k; x = x * x % MOD, k /= 2) if (k & 1) res = res * x % MOD;
    return res;
}

ll comb(int n, int k)
{
    if (k < 0 || k > n) return 0;
    return f[n] * invf[k] % MOD * invf[n-k] % MOD;
}

int N, K;

ll dp[2010][2010]; // j = num of front 0
ll acm[2010];

int main() {
    f[0] = invf[0] = 1;

    for (int i = 1; i <= 4000000; ++i) {
	f[i] = f[i-1] * i % MOD;
	invf[i] = mod_pow(f[i], MOD - 2);
    }
    
    cin >> N >> K;

    if (K == 1) {
	puts("1");
	return 0;
    }

    dp[1][1] = 1;

    for (int i = 2; i <= N; ++i) {
	memset(acm, 0, sizeof(acm));

	for (int j = 2000; j >= 0; --j) {
	    acm[j] = (acm[j + 1] + dp[i-1][j]) % MOD;
	}

	for (int j = 1; j <= i; ++j) {
	    int pos = (i - 1) * K - j + 1;

	    ll t = comb(pos + K - 2, K - 2);
	    dp[i][j] = (dp[i][j] + acm[j - 1] * t) % MOD;
	}
    }

    ll ret = 0;
    rep(i, 2010) ret = (ret + dp[N][i]) % MOD;
    ret = ret * f[N] % MOD;

    cout << ret << endl;

    return 0;
}

Codeforces #296 Div1 D. Fuzzy Search

問題:
http://codeforces.com/contest/528/problem/D

問題概要は省略します.

典型なのかもしれないけど, あんまりこういうの解いたことなかったので面白かった

解法:

流石にまとめてマッチ箇所を求めるのは大変そうなので, 置く場所は全部試すことにする.
そこで判定を速く出来ればそれでOK

文字が4種類しかないので, 各場所で各文字について判定出来ればOK

まず, Sのi番目に文字Pをあわせるとき, [i-k,i+k]番目にPがあれば良い.
Sの各場所にPを合わせてよいかどうかの配列はimos法などで線形で計算出来る.
そしてTについても各文字がPか否かのbit列にする.

左端をi (0 <= i < |S|-|T|)番目に置いた時, bit演算風に書くとS[i,i+|T|-1] & T[0,|T|-1]がT[0,|T|-1]に等しければその文字Pについてマッチ可能.

よく考えるとこの処理は内積みたいな感じで,
sum S[i+j]*T[j] (0<=j<|T|)がT中の1の個数に等しければOKです.

ここでTをひっくり返したものをT'とすると, T'[|T|-1-j] = T[j]より
sum S[i+j]*T[j]=S[i+j]*T'[|T|-1-j] (0<=j<|T|)となり, これは添字の和が一定なので畳込みになっている
これはFFTで高速に計算出来る(非再帰FFTの中身は相変わらず知りません...)

計算量は結局0(NlogN) (Nは文字列長さ)

コード:

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
 
typedef double Num;
const Num PI = acos(-1.0);
typedef complex<Num> Complex;

void fft_main(int n, Num theta, Complex a[])
{
    for (int m = n; m >= 2; m >>= 1) {
        int mh = m >> 1;
        Complex thetaI = Complex(0, theta);
        rep(i, mh) {
            Complex w = exp((Num)i * thetaI);
            for (int j = i; j < n; j += m) {
                int k = j + mh;
                Complex x = a[j] - a[k];
                a[j] += a[k];
                a[k] = w * x;
            }
        }
        theta *= 2;
    }

    int i = 0;
    for (int j = 1; j < n - 1; ++j) {
        for (int k = n >> 1; k > (i ^= k); k >>= 1) ;
        if (j < i) swap(a[i], a[j]);
    }
}
 
void fft(int n, Complex a[]) { fft_main(n, 2 * PI / n, a); }
void inverse_fft(int n, Complex a[]) { fft_main(n, -2 * PI / n, a); }
 
void convolution(vector<Complex> &v, vector<Complex> &w)
{
    int n = 1, vwn = v.size() + w.size() - 1;
    while (n < vwn) n <<= 1;
    v.resize(n), w.resize(n);
    fft(n, &v[0]);
    fft(n, &w[0]);
    rep(i, n) v[i] *= w[i];
    inverse_fft(n, &v[0]);
    rep(i, n) v[i] /= n;
}
 
string S, T;
int w;
int l1, l2;
int imos[200010];
int ok[200010];

const string gen = "AGCT";

int main() {
    cin >> l1 >> l2 >> w;
    cin >> S >> T;
    reverse(ALL(T));

    for (char c : gen) {
	memset(imos, 0, sizeof(imos));

	rep(i, l1) {
	    if (S[i] == c) {
		int l = max(i - w, 0);
		int r = min(i + w + 1, l1);
		++imos[l];
		--imos[r];
	    }
	}

	vector<Complex> v1, v2;

	rep(i, l1) {
	    imos[i + 1] += imos[i];
	    int f = !!imos[i];
	    v1.pb(f);
	}

	int num = 0;

	rep(i, l2) {
	    int f = T[i] == c;
	    v2.pb(f);
	    num += f;
	}
	convolution(v1, v2);

	for (int i = 0; i <= l1 - l2; ++i) {
	    ok[i] += (int)(v1[i + l2 - 1].real() + 0.5) == num;
	}
    }

    int ret = 0;

    for (int i = 0; i <= l1 - l2; ++i) {
	ret += (ok[i] == 4);
    }

    cout << ret << endl;

    return 0;
}