ABC164 参加メモ - tinumu's reminder

１ヶ月位競プロをしていなかった(生活も難しい)
ただ、Ratedのコンテストには出続けていた(そうでなければ自分の実力を確かめられないため)
今回は問題(特にD, E)が自分にとって解きやすかったのでそこで速解きしてパフォは良かった
1929->1974(+45, Highest) Perf = 2311

A, B, C

Aは数の比較して終わり
Bは $\lceil C/B \rceil と \lceil A/D \rceil$ で倒すターン数が分かるので比較して終わり
Cはsetに入れるとできる

D

この問題はABC158-Eを少し特殊にした版　だけどABC158-Eの解で十分間に合うのでそれでやる
tinumukiti631.hatenablog.com
要点はSuffixに関する答え $U_i$ は $\mathrm{O}(N)$ で求められるのと、 $2019$ と $10$ は互いに素になっているので、 $U_i - U_{j+1} = 0$ になっていれば部分文字列は $2019$ で割り切れることになる。つまり、 $U_i = U_{j+1}$ であるような $(i, j)$ を求めればいいので、これはmapとかで左から数を記憶しながらやっていくと、求めることができる。

E

高校の頃に最短路系の問題はかなり解いた気がする。
ヘビのJOI君(JOI2016-2017-yo6)とか解くとこういうのは思いつくと思う

まず、最短時間を求めたいけど、銀貨が減るので補填しながら行かなければいけない。
ただ、[現在の駅][銀貨の数] の条件があれば、答えを最小のものにまとめても大丈夫
ところで、消費する銀貨は $1$ エッジで $50$ までになっているので、 $N$ 回移動することを仮定しても $2500$ くらいにしかならない。よって、大体配列のサイズは $N^3$ 程度になる。

$D_i$ の重みで銀貨を $C_i$ だけ増やすエッジと、銀貨を消費しながら $B_i$ だけ重みをつけて駅を移動するエッジの２つを適切に貼れば、あとは Dijkstra することでこの問題は解ける。

F

発想自体はそんなに難しくないと思う、実装がきつすぎるんだよな。
実装の方針をちゃんと立てるのは大事。というか、実装方針に関する考察という概念が競プロにはあるんじゃないかと思う(これは言わずもがなかもしれないが)。

まず、bitごとに操作が独立なので、bitごとに考えるという方針ができる。(ここで、 $u_i, v_j$ は $U_i, V_j$ に対して着目しているbitの値ということにしておく。)
$a$ の値はとりあえずすべて $0$ にしておく。どんどん $1$ を増やしていくというやり方だ。

次に、 $a_{i,j}$ について $1$ でなければならないところと $1$ にしても解に影響を与えないところを考える。
$1$ でなければならないところは列か行に対して「論理積が $1$ 」である。これを探して、適切に $1$ にする。
$1$ にしても解に影響を与えないところは、論理和論理積にかかわらず、 $u_i = v_j = 1$ であるようなところである。このようなところは、 $0$ になっている利点がないので $1$ にしてしまおう。

このようにしておくと、条件を満たさないところというのが、「論理和が $1$ になる必要があるような行または列でまだ $1$ になっていないところ」に限定される。

まず条件を満たさない行について考えると、行の中の要素のうちどこかを $1$ にできればいいわけである。
$1$ にするのが許される列は、「論理積が $0$ 」の列に限る。このとき、その列にある $0$ の数が $2$ 以上あれば列の値を $0$ に保ったままにしながら要素を $1$ に変換することができる。
このような列を見つけながら各行やっていくと、行に対する条件を満たせる。
列の条件も上記のことを同じようにやっていけば満たすことができる。しかも独立なので行の操作に依存していない。

これで $a$ は完成する。これは $a$ の解を持つものに関しては必ず正しいものを構築できる。ということは、正しいものを構築できていないものは $a$ の解を持たないということになるので、 $a$ が条件を満たしているのか判定して満たしていないものを $-1$ を出力すれば良い。
その他は、 $a$ として出力する。