AtCoder ABC164

2020-04-26(日)に行われたAtCoderBeginnerContest164の問題をA問題から順に考察も踏まえてまとめたものとなります．
後半ではDEFの問題を扱います（時間の関係上Dしかまともにまとめられてないです）．前半はこちら．
問題は引用して記載していますが，詳しくはコンテストページの方で確認してください．
コンテストページはこちら
 公式解説PDF

D問題　Multiple of 2019

問題文
"1"から"9"までの数字のみからなる文字列$S$が与えられます。
次のような条件を満たす整数の組$(i,j)$ $(1 \leq i \leq j \leq |S|)$の総数を求めてください。
条件:$S$の$i$文字目から$j$文字目までを$10$進法の整数としてみると、この整数は$2019$の倍数である。

最初，制約が$(1 \leq S \leq 200000)$だと思って，愚直にやってTLEでした．
Cまでの問題がいつも以上のハイペースで解けていたので，都合よく解釈してましたね．
TLE出て，問題読み直して絶望しました．

$(1 \leq |S| \leq 200000)$

そりゃ間に合わないわ…
その後，E問題とF問題見に行って，残り90分をこの問題に使うことを決心しましたが，解けませんでした．
終わったあとTwitter上を見ると，どうやらABC158 E問題の類題とのこと．
やっぱり，しっかりと解けなかった問題を解き直ししないことには，成長は見込めないなと痛感しました（凡人はひたすら，過去問をやり，類似問題を解けるようにするしかないないですよね汗）．
張り切って解説読んだり，過去の問題見て記事にまとめようと思ったのですが，4/28に @Seika139 さんが，「数弱でも分かる ABC164 D問題 (剰余演算)」というタイトルの記事を投稿していて，そっと自分が書いていたものを消しました．
こんなにまとまっている記事あったら，もう書けないです（汗）
そして，この記事も参考にさせてもらい，学ばせていただきました．
とりあえず，コードも「数弱でも分かる ABC164 D問題 (剰余演算)」に掲載されているものを参考に提出しました．

abc164d.py

S = input()[::-1]
ans = 0
mods = [0] * 2019
mods[0] = 1
current = 0
x = 1
for s in S:
    current = (current + x * int(s)) % 2019
    ans += mods[current % 2019]
    mods[current % 2019] += 1
    x = x * 10 % 2019
print(ans)

個人的に，ans += mods[current % 2019] でコンビネーションの計算ができることをそもそも知らなかったので，勉強になりました．
基本的には，参考にした記事に書いてある$D[j] = D[i]$となる組み合わせの数を数える必要性があるのですが，自分は$n$が決まってから計算する方法しか知りませんでした．

例えば，今まで$D[i]=5$となる$i$が$m$個見つかっていて，新しく$D[j]=5$となる$j(i\not=j)$が見つかったとき，

{}_{m+1} C _2 = {}_m C _2 + m

であることから，$m$を足してくことで計算できるとは...
恥ずかしながら知りませんでした．
これで，計算をし終えた後に${}_n C _2$を計算する必要がないんですね．

参考にした記事に書いてないような気がしたので少し，書けたらと思うのですが，mods[0] = 1してる理由についてのことです．
これは$D[i]=0$のときについての話です．
参考にした記事で挙げている例では，$D[i]=0$が出ていないので，二つほど例を挙げてD問題を終わりたいと思います．

入力例1 "18171"

入力例1は$S=18171$のときです．このとき$D[i]$は$i=0$から順に，
$1, 71, 171, 95, 0$
となります．
ここで，$D[j] = D[i]$であるものが存在しないため，出力を"0"にしてしまいそうですが，"18171"は$2019$の倍数です．
次に入力例2を見ていきます．

入力例2 "1817118171"

入力例2は$S=1817118171$のときです．このとき$D[i]$は$i=0$から順に，
$1, 71, 171, 95, 0, 1069, 1196, 1089, 605, 0$
となります．
$D[4] = D[9]$であるため，出力を"1"にしてしまいそうですが，"18171"は$2019$の倍数であり，"1817118171"も$2019$の倍数であることから，正しい出力は"3"となります．

結論

$D[i]=0$のみは特殊で，2か所の$D[i]=0$と$D[j]=0$を選ばなくても，$D[i]=0$のみで割り切ることができるため，数が異なります．
参考にした記事では，

実際の配列$D$は長さが$N$ではなく$N+1$として、$D[N+1]=0$という空き部屋を一つ用意します。これは文字列$S$をスライスするインデックス$i,j$の選び方が${}_{N+1}C_2$通りあることと関係があります。

と書いてあったので，ここに対応すると思うのですが，$D[N+1]=0$というない部分を追加することで，$D[N+1]=0$と$D[i]=0$の組み合わせを選ぶことが，$D[i]=0$のみを選ぶことに対応するようになります．
これにより計算ができるようになるため，最初に$D[N+1]=0$があるということにするために，mods[0] = 1としています．

実際のコンテストで，ここまで実装に頭が回るようになる気がしない…

E問題　Two Currencies

問題文
$1$から$N$までの番号がつけられた$N$個の都市があります。これらの都市は$M$本の鉄道路線によって結ばれています。
あなたは現在、金貨を$10^{100}$枚、銀貨を$S$枚持った状態で都市$1$にいます。
$i$番目の鉄道路線は、都市$U_i$と都市$V_i$を双方向に結んでおり、片道の運賃は銀貨$A_i$枚、移動にかかる時間は$B_i$分です。運賃を金貨で払うことはできません。
各都市には両替所があり、都市$i$の両替所では金貨$1$枚を銀貨$C_i$枚と交換することができます。交換には、金貨$1$枚あたり$D_i$分かかります。
各交換所では、金貨を何枚でも交換することができます。
$t=2,...,N$について、都市$1$から都市$t$への移動にかかる最小の時間を求めてください。電車を待つのにかかる時間は無視して構いません。

dijkstra法を適用する問題のようでしたが，そもそも単純なdijkstra法の実装ですら慣れていないので，まずはそのあたりを１から勉強しないとなと思います．
提出されたコードの中で最初にpythonでAC通していたKiri8128さんのコードを参考にさせてもらいました．@kiri8128

abc164e.py

from heapq import heapify, heappush as hpush, heappop as hpop
N, M, S = map(int, input().split())
k = 2451
X = [[] for _ in range(N * k)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    u, v = u-1, v-1
    for i in range(a, k):
        X[u * k + i].append([v * k + i - a, b])
        X[v * k + i].append([u * k + i - a, b])

for i in range(N):
    c, d = map(int, input().split())
    for j in range(k - 1):
        X[i * k + j].append([i * k + min(j + c, k - 1), d])

def dijkstra(n, E, i0=0):
    h = [[0, i0]]
    D = [-1] * n
    done = [0] * n
    D[i0] = 0
    
    while h:
        d, i = hpop(h)
        done[i] = 1
        for j, w in E[i]:
            nd = d + w
            if D[j] < 0 or D[j] > nd:
                if done[j] == 0:
                    hpush(h, [nd, j])
                    D[j] = nd
    return D

D = dijkstra(N * k, X, min(S, k - 1))
print(*[min(D[i * k:(i+1) * k]) for i in range(N)][1:], sep = "\n")

まだまだ勉強不足なので，このあたりはゆっくり勉強していけたらと思ってます．

F問題　I hate Matrix Construction

問題文
整数$N$及び長さ$N$の配列$S,T,U,V$が与えられます。以下の条件を満たすような$N×N$の行列$a$をどれか$1$つ構築してください。
　・$a_{i,j}$は整数である。
　・$0 \leq a_{i,j} \leq 2^{64}$
　・$S_i = 0$のとき$i$行目の要素のビットごとの論理積は$U_i$である。
　・$S_i = 1$のとき$i$行目の要素のビットごとの論理積は$U_i$である。
　・$S_i = 0$のとき$i$列目の要素のビットごとの論理積は$V_i$である。
　・$S_i = 1$のとき$i$列目の要素のビットごとの論理積は$V_i$である。
ただし、条件を満たす行列が存在しない場合もあるかもしれません。

現状，DもEも解けていないので，いつかやり直します（汗）
まずは解けそうなところから地道にやっていくしか．

流石にEやFを毎回きちんと整理することはできなさそうです．
時間があるときにやり直せたらと思います．
後半も最後まで読んでいただきありがとうございました．