問題一覧 > 通常問題

No.866 レベルKの正方形

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 45
作問者 : e869120e869120 / テスター : tatyamtatyam
7 ProblemId : 3318 / 出題時の順位表
問題文最終更新日: 2019-08-16 21:17:54

問題文

注意:この問題は高速な言語でなければ実行時間制限に間に合わない可能性があります。

$H$ * $W$ のマス目があります。上から $i$ 行目、左から $j$ 列目のマスを $(i, j)$ と表します。左上のマスは $(1, 1)$、右下のマスは $(H, W)$ となります。
さて、マス $(i, j)$ には英小文字 $c_{i, j}$ が書かれています。

左上のマスが $(a, b)$, 右下のマスが $(c, d)$ $(1 \leq a \leq c \leq H, 1 \leq b \leq d \leq W, c-a=d-b)$ である正方形領域について、この正方形領域の中に含まれる文字の種類数がちょうど $P$ 種類の時、この正方形を「レベル $P$ の正方形」とします。
レベル $K$ の正方形がいくつ存在するか求めて下さい。

制約

全ての入力データは以下の制約を満たします。

  • $H, W$ は $1$ 以上 $2 \ 000$ 以下の整数
  • $K$ は $1$ 以上 $26$ 以下の整数
  • $c_{i, j}$ は a から z までの英小文字のうちいずれかである

入力

$H$ $W$ $K$
$c_{1, 1}c_{1, 2}c_{1, 3}$...$c_{1, W}$
$c_{2, 1}c_{2, 2}c_{2, 3}$...$c_{2, W}$
$c_{3, 1}c_{3, 2}c_{3, 3}$...$c_{3, W}$
...
$c_{H, 1}c_{H, 2}c_{H, 3}$...$c_{H, W}$

出力

最後に改行してください。

サンプル

サンプル1
入力
4 4 6
abcd
bcde
cdef
defg
出力
0

条件を満たす正方形領域はありません。

サンプル2
入力
4 4 3
abcd
bcde
cdef
defg
出力
9

以下の $9$ 個の正方形領域が条件を満たします。

  • 左上 $(1, 1)$, 右下 $(2, 2)$ の正方形領域
  • 左上 $(1, 2)$, 右下 $(2, 3)$ の正方形領域
  • 左上 $(1, 3)$, 右下 $(2, 4)$ の正方形領域
  • 左上 $(2, 1)$, 右下 $(3, 2)$ の正方形領域
  • 左上 $(2, 2)$, 右下 $(3, 3)$ の正方形領域
  • 左上 $(2, 3)$, 右下 $(3, 4)$ の正方形領域
  • 左上 $(3, 1)$, 右下 $(4, 2)$ の正方形領域
  • 左上 $(3, 2)$, 右下 $(4, 3)$ の正方形領域
  • 左上 $(3, 3)$, 右下 $(4, 4)$ の正方形領域
サンプル3
入力
20 20 13
ncununuineuinouicnur
nhuimjiehuiomiojioje
jimiomuimmdrwumuioer
mimiajifhpmiowjiojor
kiojioansngimumapois
jimuipammhupheohmudp
hunpumimhuewijfuhrur
jipamuyfiuhrmpvyxphu
jiamsmxoyuuwhdehuutr
ioamuusuieumhufupyrr
mopmuaiomdumruuruype
popuauximueimurmfumr
ouiweuyoduwiumfryisj
koklnxuamurhphuremeu
immuwmupmpunyaygyweh
mumhxeyomxbwuhamhisd
moumzuihmyoetyrouish
zamuepiioouuomeymgoa
mamouzhoiedieoygmoer
upahumgeyurogebyjajd
出力
119

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。