快速解决 atcoder 英文题面看不懂的方法（大雾）

经常有人说 atcoder 英文题面看不懂，但是我们都知道 atcoder 不止有英文题面！

所以为了解决英文题面看不懂的问题，我们的第一步操作是：

改变显示语言！

首先你需要背下来所有假名的音，以及大部分表示否定的说法（例如 ない、ません 等等）。

例 1

一个比较简单的例子：ARC137F。题面：

長さ 11 の棒があります． 棒の左端から距離 xx 進んだ点を，座標 xx の点と呼ぶことにします．

すぬけ君はこれから NN 回，以下の操作を行います．

  • [0,1][0,1] の中から一様ランダムに二つの実数 x,yx,y をとる． 座標 min⁡(x,y)\min(x,y) から座標 max⁡(x,y)\max(x,y) までを覆うようなシールを棒に貼る．

なお，すべての乱数は独立であるものとします．

シール同士は重なることがあります． シールが K+1K+1 枚以上重なっている点がない時，これを良い状態と呼ぶことにします．

NN 枚のシールを張り終えたあと，良い状態である確率を mod 998244353\text{mod\ }{998244353} で求めて下さい．

（后面有一段老生常谈的有理数模 998244353 定义，不过想必大家都知道定义是啥。）

step 1

去除一些显然没有用的。

比如这里有一个“すぬけ君”，如果你比较熟悉 atcoder 的传统题面以及平假名的话不难发现这个“す（su）ぬ（nu）け（ke）”就是那个总是出现的“Snuke”。

人名自然是没用的，可以去掉。

step 2

观察一下片假名子串。

  • ランダム：发音 ra-n-da-mu，稍微意会一下即可得到对应含义“random”。
  • シール：发音 shii-ru，比较神秘，需要结合“棒に貼る”意会一下得到含义“seal”。

然后，结合中文不难猜测“一様ランダム”即为“均匀随机”。

step 3

经过 step 1 和 step 2 处理的题面：

長さ 11 の棒があります． 棒の左端から距離 xx 進んだ点を，座標 xx の点と呼ぶことにします．

これから NN 回，以下の操作を行います．

  • [0,1][0,1] の中から均匀随机に二つの実数 x,yx,y をとる． 座標 min⁡(x,y)\min(x,y) から座標 max⁡(x,y)\max(x,y) までを覆うような贴纸を棒に貼る．

なお，すべての乱数は独立であるものとします．

贴纸同士は重なることがあります． 贴纸が K+1K+1 枚以上重なっている点がない時，これを良い状態と呼ぶことにします．

NN 枚の贴纸を張り終えたあと，良い状態である確率を mod 998244353\text{mod\ }{998244353} で求めて下さい．

提取否定子串（已经在上面加粗），忽略全部假名。

長/ 11 /棒/． 棒/左端/距離 xx 進/点/，座標 xx /点/呼/．

/ NN 回，以下/操作/行/．

  • [0,1][0,1] /中/均匀随机/二/実数 x,yx,y /． 座標 min⁡(x,y)\min(x,y) /座標 max⁡(x,y)\max(x,y) /覆/贴纸/棒/貼/．

/，/乱数/独立/．

贴纸同士/重/． 贴纸/ !(K+1K+1 枚以上重/点/時)，/良/状態/呼/．

NN 枚/贴纸/張/終/，良/状態/確率/ mod 998244353\text{mod\ }{998244353} /求/下/．

step 4

靠中文和 OI 相关意会一下。

长度为 11 的棍子． 称距离棍子左端点距离为 xx 的点为坐标为 xx 的点．

进行 NN 次如下操作：

  • 在 [0,1][0,1] 中均匀随机两个实数 x,yx,y． 坐标 min⁡(x,y)\min(x,y) （？）坐标 max⁡(x,y)\max(x,y) 覆盖一个贴纸．

操作之间互相独立．

贴纸可以重叠．称一个状态是好的当且仅当没有 K+1K+1 个贴纸重合．

求覆盖完 NN 枚贴纸之后，得到一个好的状态的概率 mod 998244353\text{mod\ }{998244353}。

还有一个介词不太确定。但是肯定不能是往点上放贴纸，不然答案肯定是 00。再结合一个 min 一个 max，不难猜到是这个区间覆盖一个贴纸。

最终结果：

长度为 11 的棍子． 称距离棍子左端点距离为 xx 的点为坐标为 xx 的点．

进行 NN 次如下操作：

  • 在 [0,1][0,1] 中均匀随机两个实数 x,yx,y． 坐标 min⁡(x,y)\min(x,y) 到坐标 max⁡(x,y)\max(x,y) 覆盖一个贴纸．

操作之间互相独立．

贴纸可以重叠．称一个状态是好的当且仅当没有 K+1K+1 个贴纸重合．

求覆盖完 NN 枚贴纸之后，得到一个好的状态的概率 mod 998244353\text{mod\ }{998244353}。

可以对照一下英文题面，是正确的。当然实际操作时可以直接对照样例和 I/O 格式。

例 2

下面是一个更困难的例子：AT_diverta2019_2_e。

还是先把题面拉下来。

NN 個のマスが横一列に並んでおり、左から順に 11 から NN までの番号がつけられています。高橋君はこれらのマスに積み木を積もうとしています。 まだそれぞれのマスには積み木が 11 つも積まれていません。

積み木をバランス良く積みたい高橋君は、以下の操作を繰り返して全てのマスに積み木がちょうど HH 個ずつ積まれている状態にしようとしています。

  • 11 マスに積まれている積み木の最大値を MM 個、最小値を mm 個とする。mm 個の積み木が置かれているマスを 11 つ選び (複数ある場合はどれを選んでもよい)、そのマスに積まれた積み木が MM 個以上 M + DM\ +\ D 個以下になるように積み木を正の個数積む。

高橋君のために、この操作を繰り返して全てのマスに積み木がちょうど HH 個積まれている状態にする方法が何通りあるか数えてあげてください。答えは非常に大きくなる場合があるので、109+710^9+7 で割った余りを出力してください。

step 1

去除没有用的，这里没有用的更明显，就是“高橋君”。后面还有个很明显的模 109+710^9+7 也可以顺带翻译过来。那个从 11 到 nn 编号也挺明显的。

NN 個のマスが横一列に並んでおり、从左到右编号 1−N1-N。これらのマスに積み木を積もうとしています。 まだそれぞれのマスには積み木が $ 1 $ つも積まれていません。

積み木をバランス良く積みたい、以下の操作を繰り返して全てのマスに積み木がちょうど HH 個ずつ積まれている状態にしようとしています。

  • 11 マスに積まれている積み木の最大値を MM 個、最小値を mm 個とする。mm 個の積み木が置かれているマスを 11 つ選び (複数ある場合はどれを選んでもよい)、そのマスに積まれた積み木が $ M $ 個以上 M + DM\ +\ D 個以下になるように積み木を正の個数積む。

この操作を繰り返して全てのマスに積み木がちょうど HH 個積まれている状態にする方法が何通りあるか数えてあげてください。模 109+710^9+7。

step 2

翻译片假名子串。

  • バランス ba-ra-n-su，结合题目名称，明摆着的 balance。
  • マス ma-su，可能不是英文音译。但是不重要，当它是啥都行。

NN 個の masu が横一列に並んでおり、从左到右编号 1−N1-N。これらの masu に積み木を積もうとしています。 まだそれぞれの masu には積み木が 11 つも積まれていません。

積み木を balance 良く積みたい、以下の操作を繰り返して全ての masu に積み木がちょうど HH 個ずつ積まれている状態にしようとしています。

  • 11 masu に積まれている積み木の最大値を MM 個、最小値を mm 個とする。mm 個の積み木が置かれている masu を 11 つ選び (複数ある場合はどれを選んでもよい)、そのマスに積まれた積み木が $ M $ 個以上 M + DM\ +\ D 個以下になるように積み木を正の個数積む。

この操作を繰り返して全ての masu に積み木がちょうど HH 個積まれている状態にする方法が何通りあるか数えてあげてください。模 109+710^9+7。

step 3

提取否定子串，忽略全部假名。否定子串在上面加粗。

NN 個/ masu /横一列/並/、从左到右编号 1−N1-N。/ masu /積/木/積/。 !(/ masu /積/木/ $ 1 $ /積/)。

積/木/ balance 良/積/、以下/操作/繰/返/全/ masu /積/木/ $ H $ 個/積/状態/。

  • 11 masu /積/積/木/最大値/ MM 個、最小値/ mm 個/。mm 個/積/木/置/ masu / 11 /選/ (複数/場合/選/)、/masu/積/積/木/ MM 個以上 M + DM\ +\ D 個以下/積/木/正/個数積/。

/操作/繰/返/全/ masu /積/木/ HH 個積/状態/方法/何通/数/。模 109+710^9+7。

可以发现上面和下面有一定的重复，因此可以进一步化简。这个进一步化简在上面用删除线表示。

step 4

意会，这里比较困难。

4.1

  • NN 個/ masu /横一列/並/、从左到右编号 1−N1-N。/ masu /積/木/積/。 !(/ masu /積/木/ 11 /積/)。

前面都好说，但是最后一块不太好整。

  • NN 个 masu 从左到右排成一列、从左到右编号 1−N1-N。在 masu 上面放积木。 !(/ masu /積/木/ 11 /積/)。

这里需要看到样例解释。注意到第一个样例 N=2N=2，然后 66 个序列的开始都是 (0,0)(0,0)，所以可以猜到最后那块的意思是“初始每个 masu 上面都没有任何积木”。

4.2

  • 11 masu /積/積/木/最大値/ MM 個、最小値/ mm 個/。mm 個/積/木/置/ masu / 11 /選/ (複数/場合/選/)、/masu/積/積/木/ MM 個以上 M + DM\ +\ D 個以下/積/木/正/個数積/。

第一句、第二句的前半部分好整。

  • 一个 masu 上面最多放了 MM 个积木，最少放了 mm 个积木。选择一个放有 mm 个积木的 masu (複数/場合/選/)、/masu/積/積/木/ MM 個以上 M + DM\ +\ D 個以下/積/木/正/個数積/。

括号里面没有任何附加限制，而且样例解释里面有 (0,0)→(0,1)(0,0)\rightarrow (0,1) 和 (0,0)→(1,0)(0,0)\rightarrow (1,0)，于是我们猜测那串假名就是没有任何特殊限制。

  • 一个 masu 上面最多放了 MM 个积木，最少放了 mm 个积木。选择一个放有 mm 个积木的 masu (有多个可以选的时候则任意选取)、/masu/積/積/木/ MM 個以上 M + DM\ +\ D 個以下/積/木/正/個数積/。

第三句可以理解为放 M∼M+DM\sim M+D 个，或者放到 M∼M+DM\sim M+D 个。注意到样例解释里面有 (1,2)(1,2) 转移到 (2,2)(2,2)，于是只有后者成立。后面那个正整数即可推出是必须放一个（否则答案就是 +∞+\infty）。

  • 一个 masu 上面最多放了 MM 个积木，最少放了 mm 个积木。选择一个放有 mm 个积木的 masu (有多个可以选的时候则任意选取)、将这个 masu 的积木个数增加至少 11，并将其增加到 M,M+DM,M+D 之间。

4.3

  • /操作/繰/返/全/ masu /積/木/ HH 個積/状態/方法/何通/数/。模 109+710^9+7。

还是看样例解释。注意到 H=2H=2，且最终状态都是 (2,2)(2,2)，那么意义就很明显了。

  • 求重复若干次操作使得每个 masu 上都有 HH 个积木的方案数模 109+710^9+7。

最终结果

去掉了那些 masu 因为我自始至终也不知道那是啥。

有一个长度为 nn 的数组，初始全 00。每次操作中，设当前最大值为 MM，选任意一个数组中值最小的位置 aia_i，将其增加 xx，满足 x>0,M≤ai+x≤M+Dx>0,M\leq a_i+x\leq M+D。求使得 aa 中所有数都等于 HH 的操作方案数。

没有对照英文题面，但是我按这个做把题过了，所以应该是对的吧（）