AtCoder Beginner Contest 164 D,E,F問題メモ

AtCoder Beginner Contest 164

D - Multiple of 2019

• 長さ $N$ の'0'～'9'からなる文字列 $S$ が与えられる
• 連続する区間 $[l,r]$ で、$S_l～S_r$ を10進数の整数として見たときに2019の倍数となっているようなものはいくつあるか求めよ
• $1 \le N \le 2 \times 10^5$

つい最近、似たような問題が出た気がする。復習大事。

• E - Divisible Substring

• AtCoder Beginner Contest 158 D,E,F問題メモ

E - Two Currencies

• $N$ 頂点 $M$ 辺のグラフに見立てた都市と鉄道がある
• あなたは今、都市1にいて、金貨を超沢山、銀貨を $S$ 枚持っている
• $i$ 番目の鉄道は都市 $U_i$ と $V_i$ を結び、運賃は片道銀貨 $A_i$ 枚、所要時間は $B_i$
  • 金貨では支払えない
• 各都市では両替ができて、都市 $i$ では金貨1枚を銀貨 $C_i$ 枚に、時間 $D_i$ で両替できる
  • 何枚でも両替できるが、時間はその都度かかる
• 都市 $2～N$ のそれぞれについて、到達できる最短時間を求めよ
• $2 \le N \le 50$
• $N-1 \le M \le 100$
• $1 \le A_i \le 50$
• $0 \le S \le 10^9$
• $0 \le B_i,C_i,D_i \le 10^9$

頂点を多重にする最短経路探索の練習的問題？

$N,A_i$ がなかなか少なめ。

運賃があるなら時間優先で各都市に向かいたいが、足りない場合、どこかで両替の必要がある。 遠く離れた都市でメッチャ速く両替できるなら、わざわざそこまで行って両替して、帰ってくるみたいなこともあり得る。 なので、1回訪れた都市を再度訪れるかも知れないので、普通のDijkstraなどでは上手くいかない。

だが、もし2回目に訪れたとき、1回目より所持銀貨が同じや少なかったら……？

その場合、2回目から時間 $t$ かけて訪れられる都市は、1回目の時点でも当然同じ経路を辿れば同じように訪れられる。 従って、トータルでは絶対に遅くなるので、それ以上探索を広げる必要は無い。

所持銀貨の情報も合わせて考慮すればよさそう。

Dijksra法を使うとし、頂点を「$(v, s)=$ 都市 $v$ を、所持銀貨 $s$ で訪れた状態」とする。$DP[v,s]$ をその状態に至れる最短所要時間とする。

とある $(v,s)$ に時間 $t$ で到達できた場合、以下の2通りの遷移を行う。

• 両替する
  • $DP[v,s+C_v]←DP[v,s]+D_v$
  • 更新したなら、$(v,s+C_v)$ をキューに追加
• 移動する
  • $v$ から伸びる鉄道 $i$ を使って移動する（もう一方の都市を $u$ とする）
  • $DP[u, s-A_i]←DP[v,s]+B_i$
  • 更新したなら、$(u,s-A_i)$ をキューに追加
  • ※ただし、運賃が足りる場合のみ

ここで $s$ は、都市が50個しか無いので最遠でも $49$ 回鉄道に乗ればよくて、鉄道1回の運賃も50以下なので、 多くとも $50 \times 49 = 2450$ さえ持っていれば、それ以上両替の必要は無い。

よって、頂点数は $O(N^2A_{max})$ となる。

辺数も、1頂点から伸びる1本が約2450倍に複製される感じなので、$O(NMA_{max})$ となる。

優先付きキューを使うと、Dijkstraの計算量は $O((N^2A_{max}+NMA_{max})\log{N^2A_{max}})$ で、上限の数字を当てはめるとだいたい6375000となる。

これは実際、Pythonではちょっと厳しくて、下手なことをするとTLEになってしまう。

たとえば、1回都市 $v$ を訪れたなら、そこで両替できるだけしてしまうという考えもある。

• $(v,s+C_v)$ をキューに追加
• $(v,s+2C_v)$ をキューに追加
• $(v,s+3C_v)$ をキューに追加
• …

だがこうすると、Dijkstraの実装によっては、キューに同じ状態を示す頂点が多く積み上がってしまうことになり、TLEとなる。（この事実に気付くのに時間かかった）

両替は1度に金貨1枚分とし、それがキューから引っ張り出されたら、改めてもう1枚両替を考慮すればよい。

F - I hate Matrix Construction

• 整数 $N$ と、長さ $N$ の4つの数列 $S,T,U,V$ が与えられる
  • $S,T$ は '0','1'のみからなる
• 以下の条件を満たす $N \times N$ 行列を一例、構築せよ
• 条件
  • $S_i=0$ の時、$i$ 行目の要素を全て BitwiseAnd すると $U_i$
  • $S_i=1$ の時、$i$ 行目の要素を全て BitwiseOr すると $U_i$
  • $T_j=0$ の時、$j$ 行目の要素を全て BitwiseAnd すると $V_j$
  • $T_j=1$ の時、$j$ 行目の要素を全て BitwiseOr すると $V_j$
• $1 \le N \le 500$
• $0 \le U_i,V_i \lt 2^{64}$

数字を2進数で見たとき、ある桁の処理は他の桁に影響しないので、桁毎に考える。$U,V$ は 0/1 の2通りだけを考えればよくなる。

                       S  処理  U
      _   _   _   _  | 1   or   1
      _   _   _   _  | 1   or   0
      _   _   _   _  | 0  and   0
      _   _   _   _  | 0  and   1
    -----------------+
T     0   1   0   1
処理 and or  and or
V     1   1   0   0

ここで、まずは2つの事実により、確定する行・列がある。（$T,V$ でも同じ）

• $S_i=0$:AND なら、$U_i=1$ の行は全て1
• $S_i=1$:OR なら、$U_i=0$ の行は全て0

これを埋める。この時点で、行と列でかち合うものがあれば、不可能。

                       S  処理  U
      _   _   _   _  | 1   or   1
      0   0   0   0  | 1   or   0  ←確定
      _   _   _   _  | 0  and   0
      1   1   1   1  | 0  and   1  ←確定
    -----------------+
T     0   1   0   1
処理 and or  and or
V     1   1   0   0
     ↑
     1確定だが、既に0が埋まっている

以下のようにすると、かち合うものを検出できる。

• まず行（$S,U$）で確定できるところを埋める。その際、0,1それぞれ、確定したものがあったかを記録する
• 次に列（$T,V$）で確定できるところを埋める際、埋めようとする値と矛盾するものが、行で確定していたら、不可能

さて、次に、確定しないものを考える。

• $S_i=0$:AND なら、$U_i=0$ の列の少なくとも1つは0
• $S_i=1$:OR なら、$U_i=1$ の列の少なくとも1つは1

ここで、未確定の行・未確定の列の個数で、処理を場合分けする。

話は簡単で、未確定マスの中だけで市松模様状に敷き詰めればよい。必ず、どの行・列にも0,1が1マス以上存在するようになる。

                       S  処理  U
      1  [0]  1  [1] | 1   or   1
      1  [1]  1  [0] | 1   or   1
      1  [0]  1  [1] | 0  and   0
      1   1   1   1  | 0  and   1

マスは全て確定している。「確定する条件」の中では、矛盾はない。

後は、未確定条件が全て合致しているか調べればよい。

以下は、列側の要件により全てが“1”で確定した状態で 行側の要件を確認する過程だが、この時に「どれか1つは0」があると矛盾する。

                       S  処理  U
      1   1   1   1  | 1   or   1  [未確定]  どれか1つは1
      1   1   1   1  | 1   or   1  [未確定]  どれか1つは1
      1   1   1   1  | 0  and   0  [未確定]  どれか1つは0 → 矛盾
      1   1   1   1  | 0  and   1  [確定]

これも、確定行同士での矛盾を検出するときと同様、「0で埋まった列があるか」「1で埋まった列があるか」を記録しておけばよい。

市松模様が使えない。この処理にちょっと混乱してWAを連発した。まぁこれは丁寧にいろんなケースを確認していくしかないんだろう。

未確定が1つのみなのが列であるとし、その列で少なくとも1つは存在しなければいけない値が $b$ だとする。

                       S  処理  U
      1   1   _   1  | 1   or   1  どれか1つは1
      1   1   _   1  | 1   or   1  どれか1つは1
      1   1   _   1  | 0  and   0  どれか1つは0
      1   1   1   1  | 0  and   1  [確定]
             ↑
             どれか1つは1 ... 既に満たされている

この場合、未確定列の要件は既に満たされているので、行方向で未確定の要件に求められているものを埋めればよい。

                       S  処理  U
      1   1  [1]  1  | 1   or   1  どれか1つは[1]
      1   1  [1]  1  | 1   or   1  どれか1つは[1]
      1   1  [0]  1  | 0  and   0  どれか1つは[0]
      1   1   1   1  | 0  and   1  [確定]

$\bar{b}$ は、反転したもの（0なら1、1なら0）とする。

                       S  処理  U
      0   1   _   1  | 1   or   1  どれか1つは1
      0   1   _   1  | 1   or   1  どれか1つは1
      0   1   _   1  | 0  and   0  どれか1つは0
      0   1   _   1  | 0  and   0  どれか1つは0
             ↑
             どれか1つは1

この場合、未確定な行の要件で、$\bar{b}$ なものは既に満たされているので、全て $b$ で埋めてよい。

                       S  処理  U
      0   1  [1]  1  | 1   or   1  どれか1つは1
      0   1  [1]  1  | 1   or   1  どれか1つは1
      0   1  [1]  1  | 0  and   0  どれか1つは0 [要件は既に満たされている]
      0   1  [1]  1  | 0  and   0  どれか1つは0 [要件は既に満たされている]
             ↑
             どれか1つは[1]

                       S  処理  U
      1   1   _   1  | 0  and   0  どれか1つは0
      1   1   _   1  | 0  and   0  どれか1つは0
      1   1   _   1  | 0  and   0  どれか1つは0
      1   1   _   1  | 0  and   0  どれか1つは0
             ↑
             どれか1つは1

未確定な行で、入れたい値が $\bar{b}$ なものは、まだ要件が満たされていないので、未確定の残る1列に入れるしかない。

よって、基本は未確定な行の要件で埋めていく。

そうして埋めていって、$b$ の入る行が1つも無ければ、そこで不可能となる。

                       S  処理  U
      1   1   0   1  | 0  and   0  どれか1つは0
      1   1   0   1  | 0  and   0  どれか1つは0
      1   1   0   1  | 0  and   0  どれか1つは0
      1   1   0   1  | 0  and   0  どれか1つは0
             ↑
             どれか1つは1 ... 矛盾!

1つでもあれば、それで列の要件も満たされるので、よし。