コンテスト中AC:A〜C,E
D,Fも自力ACできたので、書きます。

コンテスト全体の感想

Dが思いつかなかったので、Eを先に解きました。Eは解法自体はわかったのですが、実装に時間がかかってしまいました。

Fで残り時間10分くらいで、包除原理はわかったのですが、実装は間に合いませんでした。コンテスト後に解きましたが、最初 $S_i$ から作られる文字列の数の計算方法が間違っていました。

Dのように変数か複数ある場合、どれかを固定するという考え方が大事ですね。(一方は全探索できて、片方が決まれば、他は高速に計算できる場合がある)

D - 2-variable Function

$a$ の上限は $10^6$ で、全探索可能です。 $a$ を固定すると、 $b=0,1,\cdots$ に対して $X$ は狭義単調増加です。よって、 $X\leq N$ となるような $b$ を二分探索できます。

提出コード

E - Bishop 2

マスを4倍に拡張し、左上、右上、左下、右下への移動中を表す状態を追加します。具体的には、

$dp[i][j][k]:=$ マス $(i,j)$ にいて状態が $k$ の時の最短距離

とします。
但し、 $k=\{0,1,2,3\}$ とし、
$k=0$ の時、左上に移動中
$k=1$ の時、右上に移動中
$k=2$ の時、左下に移動中
$k=3$ の時、右下に移動中
とします。

まず、同じマス内ではコスト1で方向転換ができます。(同じ向きになるのは無駄ですが、実装が楽です。) 従って、 $k'=0,1,2,3$ について、

$dp[i][j][k']\leftarrow dp[i][j][k]+1$

次に、 $k$ に応じて、以下の通りに進行方向の次のマスにコスト0で動けます。

$k=0$ の時、左上に進める。
$dp[i-1][j-1][k] \leftarrow dp[i][j][k]$
$k=1$ の時、右上に進める。
$dp[i-1][j+1][k] \leftarrow dp[i][j][k]$
$k=2$ の時、左下に進める。
$dp[i+1][j-1][k] \leftarrow dp[i][j][k]$
$k=3$ の時、右下に進める。
$dp[i+1][j+1][k] \leftarrow dp[i][j][k]$

初期値は、既に1回目の移動が始まっていることにする必要があるので、 $k=0,1,2,3$ について、

$dp[A_x][A_y][k] \leftarrow 1$

です。

これをダイクストラ法で解けば良いです。

答えは、 $k=0,1,2,3$ について、 $dp[B_x][B_y][k]$ の中の最小値です。
なお、到達可能かの判定が必要なことに気をつける必要があります。

実装ですが、AtCoderの過去問にも同様の問題があったので、その時の公式解説の実装方法に倣っています。
マス $(i,j)$ の状態 $k$ の頂点番号を

id = 4(i+j*N)+k

とします。
idからi,j,kを得たい時は、C++なら、

i = id/4%N
j = id/4/N
k = id%4

とすれば良いです。
このようにするメリットは、通常のダイクストラ同様に、(距離, 頂点番号)という組だけで管理できる点です。i,j,kを全て管理するなら、構造体などが必要です。
提出コード

F - typewriter

包除原理で解けます。
包除原理についてはネットで調べると出てくるので、詳細は割愛します。
ここでは、小さい例で示します。

$f(S)$ を使用する文字の集合 $S$ のみから得られる長さ $L$ の文字列の数とします。
$g(S)$ を使用する文字の集合 $S$ から得られる全ての長さ $L$ の文字列の数とします。

入力例1でいえば、
$f(S_1)=\{ab,ba,bb\}$
$f(S_2)=\{ac,ca,cc\}$
$f(S_1 \cap S_2)=\{aa\}$

$g(S_1)=\{aa,ab,ba,bb\}$
$g(S_2)=\{aa,ac,ca,cc\}$
$g(S_1 \cap S_2)=\{aa\}$

$g(S)$ は、実は簡単に求められます。 $S$ に含まれる文字は何回使っても良いので、 $i$ 番目の文字は $|S|$ 通りから選ぶことになり、選ぶ文字によって得られる文字列は異なるので、

$g(S)={|S|}^L$ となります。これは繰り返し二乗法により、 $O(logL)$ で計算できます。

(とはいえ、 $g(S)$ の求め方がコンテスト中悩んでしまいました。重複組み合わせと重複並び替えを組み合わせようとしてしまっていました。)

では、 $N=3$ のケースで、包除原理の一例を示します。
今求めたいものは、

$ans = f(S_1)+f(S_2)+f(S_3)+f(S_1 \cap S_2)+f(S_1 \cap S_3)+f(S_2 \cap S_3)+f(S_1 \cap S_2 \cap S_3)$

です。ベン図で他の集合と重なっていない部分の和と考えればわかりやすいです。

初め、 $X=0$ とします。

まず、 $f(S_1),f(S_2),f(S_3)$ を足したいです。

$g(S_1)=f(S_1)+f(S_1 \cap S_2)+f(S_1 \cap S_3)+f(S_1 \cap S_2 \cap S_3)$
$g(S_2)=f(S_2)+f(S_1 \cap S_2)+f(S_2 \cap S_3)+f(S_1 \cap S_2 \cap S_3)$
$g(S_3)=f(S_3)+f(S_1 \cap S_3)+f(S_2 \cap S_3)+f(S_1 \cap S_2 \cap S_3)$

より、 $X$ に $g(S_1),g(S_2),g(S_3)$ を足します。すると、

$X=f(S_1)+f(S_2)+f(S_3)+2f(S_1 \cap S_2)+2f(S_1 \cap S_3)+2f(S_2 \cap S_3)+3f(S_1 \cap S_2 \cap S_3)$

次に、 $f(S_1 \cap S_2),f(S_1 \cap S_3),f(S_2 \cap S_3)$ は一個ずつ多いので減らしたいです。

$g(S_1 \cap S_2)=f(S_1 \cap S_2)+f(S_1 \cap S_2 \cap S_3)$
$g(S_1 \cap S_3)=f(S_1 \cap S_3)+f(S_1 \cap S_2 \cap S_3)$
$g(S_2 \cap S_3)=f(S_2 \cap S_3)+f(S_1 \cap S_2 \cap S_3)$

より、 $X$ から $g(S_1 \cap S_2),g(S_1 \cap S_3),g(S_2 \cap S_3)$ を引きます。

$X=f(S_1)+f(S_2)+f(S_3)+f(S_1 \cap S_2)+f(S_1 \cap S_3)+f(S_2 \cap S_3)$

最後に、 $f(S_1 \cap S_2 \cap S_3)$ が足りなくなったので、足したいです。

$g(S_1 \cap S_2 \cap S_3)=f(S_1 \cap S_2 \cap S_3)$

より、 $X$ に $g(S_1 \cap S_2 \cap S_3)$ を足します。

$X = f(S_1)+f(S_2)+f(S_3)+f(S_1 \cap S_2)+f(S_1 \cap S_3)+f(S_2 \cap S_3)+f(S_1 \cap S_2 \cap S_3)$

この時点で、 $X=ans$ となります。

結局、
$ans$
$= f(S_1)+f(S_2)+f(S_3)+f(S_1 \cap S_2)+f(S_1 \cap S_3)+f(S_2 \cap S_3)+f(S_1 \cap S_2 \cap S_3)$
$= g(S_1)+g(S_2)+g(S_3)-g(S_1 \cap S_2)-g(S_1 \cap S_3)-g(S_2 \cap S_3)+g(S_1 \cap S_2 \cap S_3)$