2020-07-02

精進バチャ1600-2200 #1 メモ

https://kenkoooo.com/atcoder/#/contest/show/01389bb5-a825-4c1a-8958-eb237c1c1d70
生活リズムを壊さないで恒常的に競プロの時間を取りつづけましょう

A - だれじゃ

それぞれの文字の数が一致しているかどうかで $2$ つの文字のアナグラムが同じかどうか判断できる。長さ $K$ と決まっているので、尺取りで見ていくと高速。 set> みたいなのを使ってその時の文字の数の情報を入れていく。共通部分を持ってはいけないので $K$ 文字分 setに入れるのを遅くして、判断すると処理が出来る。

B - All Your Paths are Different Lengths

例えば $L$ が偶数のときのことを考える。
このときにノード $1$ からノード $2$ へ $2$ つエッジを張る。
具体的には、コストがそれぞれ、 $0, L/2$ のエッジを張る。
こうすることで、次のノードについて、 $L/2$ についての問題を考えることで、重複なくパスを作る事が出来る。( $0$ を通った場合、 $0,1, \cdots, L/2-1$ , を通ることになり、 $L/2$ を通った場合 $L/2, L/2+1, \cdots, L-1$ を通ることになり、キレイに分断する)

ただ、 $L$ が奇数の場合は余りが $1$ つどうしてもでてしまう。
そこで、このように辺を張る。

ノード $1$ からノード $2$ へコスト $0$ の辺を張る
ノード $1$ からノード $2$ へコスト $\lfloor L/2 \rfloor$ の辺を張る
ノード $1$ からノード $N$ へコスト $L-1$ の辺を張る。

最後の一つは直接最後に貼ってしまえば良いということである。

そうしたら次はノード $2$ からノード $3$ へ $\lfloor L/2 \rfloor$ についての問題を解く。
これも偶数か奇数かで貼り方を分けてやる。

これを繰り返していくと、エッジの数は $60$ 以内に収まり、 $N \leq 20$ にもなる。

解説解の下位bit押さえてやっていく方法で必要なところだけ分裂させるのも面白い。

C - オレンジグラフ

これは一つの事実に気づくと問題がかなり簡単になる。
「奇数長の閉路を含まないグラフは二部グラフ化できる」ということである。
すると、どっちを左側にするか右側にするかを決めたら( 左右は区別できないので $2^{N-1}$ 通り) 、一意に塗り方が定まる。というのも、側が異なる辺を無造作につなげるだけでいいからである。
そのため、 $2^{N-1}$ 通り全て試す。
このときに決めた割り振りが矛盾する場合は、全部辺を繋ぎ終えた時に連結グラフになっていない。そのような偶奇で全ノードをつなげる手立てがなかったことになるからだ。
矛盾のないものを数えると答えになって正答する。

感想

決めたルールは守りましょう。メモを書くのを当日か次の日くらいにしたい。

2020-06-29

ACPCVC20200525 復習メモ

競技プログラミング ACPCVC

https://kenkoooo.com/atcoder/#/contest/show/25688e6e-acd2-4910-857a-253f76e494b6
この難易度帯はちゃんと確実に解けるようになりたいな

A - Ears

すぬけくんの散歩で入れられる石の区間は $5$ 種類に区別できる。
$x$ の小さい順から、

状態 $0$ : 石を入れられない( $0$ 個)
状態 $1$ : 石を $2$ 以上の偶数個入れられる
状態 $2$ : 石を奇数個入れられる(始点と終点の間)
状態 $3$ : 石を $2$ 以上の偶数個入れられる
状態 $4$ : 石を入れられない( $0$ 個)

というようになっている。これは紙とかに書いてみるとそんな感じに出来ることが分かると思う。

上のことがわかったので、どのタイミングで状態遷移をするかという事を選択するDPを行う事で最小の回数が求まる。
$dp_{i, j}$ : $i$ 番目まで見ていて、現在の状態番号が $j$ であるときの石を入れる必要のある最小の数
この状態があれば問題なくまとめられるのであとはそれぞれの状態で最小になるようにすぬけ君が石を置いていけば、問題なし。

すぬけ君の最適な石の置き方によって生じるコスト

状態 $0$ : $A_i$ を足す
状態 $1$ : $A_i = 0$ のときは $2$ , そうでないときは $A_i \mod 2$ を足す
状態 $2$ : $1-(A_i \mod 2)$ を足す
状態 $3$ : 状態 $1$ と同様
状態 $4$ : 状態 $0$ と同様

耳DPって何を以ってどうなんだろう

B - Engines

それぞれのエンジンをベクトルと考える。
$2$ つのベクトルがあって、それらを使うとする。
このとき、 $2$ つのベクトルのなす角の内部にあるベクトルたちは明らかに使ったほうが距離を伸ばせる。
そのため、実は $2$ つベクトルが決まりさえすれば最適解に含まれるパターンは全て列挙できたことになる。

以上のことから、角度でベクトルをソートしておいて、２つベクトルを決めてその内部のベクトルの和を取って、それの最大値を求めれば良い。
愚直に実装しても $\mathrm{O}(N^3)$ であるので、制約的に普通に間に合う。

ABC139バチャしてた時はなぜ気づかなかったのか

C - Small Products

$dp_{i, x}$ : 最後の整数が $x$ であるような $i$ 個の整数を並べたときの場合の数と置く。
このdpの愚直な実装だと間に合わない。
だが、 $\lfloor \frac{N}{y} \rfloor = \lfloor \frac{N}{x} \rfloor = t$ であるような $x, y$ は $dp_{i,x} = dp_{i,y} = \sum_{z=1}^{t} dp_{i-1, z}$ となり同じ値になるのでそこだけ考えるとまとめられそう。
$\lfloor \frac{N}{x} \rfloor = t$ になる $x$ の範囲といえば $\left( \lfloor \frac{N}{t+1} \rfloor , \lfloor \frac{N}{t} \rfloor \right\rbrack$ となる。
同時に $dp_{i, t} = \sum_{x=1}^{\lfloor \frac{N}{t} \rfloor} dp_{i-1, x}$ というような更新ができる。
つまり、ある位置から区間への更新と、区間からある位置への更新が位置がずれることなく適切に行える。

そう考えると、やはりdpはまとめられることに気づく。
$i \leq \sqrt{N}$ まで通常の位置を用意して、 $i \geq \sqrt{N}$ からは $\lfloor \frac{N}{j} \rfloor (j \leq \sqrt{N})$ 単位で区間を区切っていって圧縮する。
これをうまく処理すると、 $\mathrm{O}(\sqrt{N}K)$ で処理するDPがかける。
更新の際に $\sum$ が出てきていたが、これは累積和を取りながらDPをやると高速に動く。

実装の方針は全部区間として扱って座標圧縮する方法が一番実装量が少ない気がする。

感想

Cを書かずじまい10日くらい経ってしまった
かなり頭が止まっているのでフル回転させたい。

2020-06-28

ABC172 参加メモ

ABC 競技プログラミング

勤勉ではありません(悲痛)
ABCD4完 520th Perf=1795 (1916->1904(-12))
冷えが青程度に収まってるから良いものの、上限を上げる努力をしましょう

A - Calc

気をつけて書く a + a*a + a*a*a

B - Minor Change

こういうのってfor使わない方法とかあったっけ
cnt += S[i] != T[i]

C - Tsundoku

机Aを読む数 $i$ を決めたら机Bをできるだけ読もうとしてできる読む数 $j$ が決まるので尺取りっぽくやって $\mathrm{O}(N+M)$ で処理可能

D - Sum of Divisors

$j$ の倍数についてカウントするだけでも $\mathrm{O}(N \log N)$ で通るけどちょっと怖いっぽい。 $\mathrm{O}(N)$ 解がある。
$j$ の倍数を $i (i \leq N)$ とすると、 $\sum_{j=1}^{N} \sum_{i} i$ で答えが出てくる。
$i$ は $j, 2j, \cdots nj \left(n = \left\lfloor \frac{N}{j} \right\rfloor \right)$ の和になっているので等差級数の和である。つまりこれは $\mathrm{O}(1)$ で計算できて、 $\sum_{i} i = \frac{jn(n+1)}{2}$ となる。
最終的な答えは $\sum_{j=1}^{N} \frac{jn(n+1)}{2}$ となり、 $\mathrm{O}(N)$ である。
通りそうなら通しちゃうのもコンテストの中では大事だとは思うけどこういうのもちゃんとやらないと

E - NEQ

事象 $P_i$ を $A_i = B_i$ であることとする。
すると今回の $A_i \neq B_i$ というのは $\overline{P_1} \cap \overline{P_2} \cap \cdots \cap \overline{P_N}$ ということになる。
これはド・モルガンで $\overline{P_1 \cup P_2 \cup \cdots \cup P_N}$ となっていて、どうやら事象の和事象の形になるようである。

事象 $P_i$ を $A_i = B_i$ の条件にしたのも、こっちのほうが求めやすいわけで、事象の和事象を包除原理を用いて積事象たちを使って解こうという魂胆である。

今回の事象を包除原理で表すと以下の形になる。
$\displaystyle |\overline{P_1 \cup P_2 \cup \cdots \cup P_N}| = |U| - |P_1 \cup P_2 \cup \cdots P_N|$ ( $U$ は全体集合, $|A|$ は事象 $A$ の起こりうる数)
$\displaystyle = |U| - \sum_{i} |P_i| + \sum_{i \lt j} |P_i \cap P_j| - \sum_{i \lt j \lt k} |P_i \cap P_j \cap P_k| + \cdots$

ここで出てくる積事象たちについて、この問題ではどのように表すかを考える。

各要素が $1$ 以上 $N$ 以下の整数である、ある集合 $S$ がある。 (例えば $N=3$ だったら $S = \{1, 3\}$ とか)
このときの $i \in S$ である $i$ について $A_i = B_i$ である。
このようなものの個数は数え上げできて、 $_{M} P _{|S|} \times (_{M-|S|} P _{N-|S|})^2$ 個となる。
これが $1$ 要素である。
足し上げる時には上記の包除原理の式に則ると $S$ の要素数が偶数の時には +, 奇数の時には - になっている必要があるので、この要素の項は $(-1)^{|S|} \ _{M} P _{|S|} \times (_{M-|S|} P _{N-|S|})^2$ ということになる。

これを全ての $S$ について数えると。すると、次のような式になる。
$\displaystyle ans = \sum_{S \in 2^{ \{1, 2, \cdots N \} }} (-1)^{|S|} \ _{M} P _{|S|} \times (_{M-|S|} P _{N-|S|})^2$
しかしこれだと $2^N$ 回計算してしまうのでそのままだと計算できない。
考えてみると、各項で使っているのは $|S|$ だけであるので、要素数が一致していれば全て同じ答えを出すということが分かる。では要素数が $K$ であるような $S$ の数というのは $_{N} C _{K}$ 個だけあるので、各要素数についてまとめて計算できる。
すると、式は、
$\displaystyle ans = \sum_{K=0}^{N} \ (-1)^K \ _{N}C_{K} \times \ _{M} P _{K} \times (_{M-K} P _{N-K})^2$
となって、無事に数え上げることが出来た。

積事象を考えるときには余事象についての部分的な積事象が高速に求まらないかを考えていく必要がありそう

F - Unfair Nim

解説のpdfとほぼ一緒かも…
これは通常のNimなので、この問題で高橋くんが勝つというのは $A_1 \oplus A_2 \oplus \cdots \oplus A_N = 0$ であることを言う。
操作に置いて $A_3$ 以降は値は変わらないので一つにまとめてしまってもよい。 $A_3 \oplus \cdots \oplus A_N = X$ と置いておく。
$A_1 + A_2 = S$ とおくと、 $a+b = S (0 \lt a \leq A_1)$ であるような $a, b$ で、 $a \oplus b \oplus X = 0$ つまり $a \oplus b = X$ であるような最大の $a$ を見つければこの問題が解ける。
まとめると条件は $3$ つになる。

$a+b = S$
$a \oplus b = X$
$0 \lt a \leq A_1$

ここで $a+b = a \oplus b + 2 \times (a \& b)$ であることを利用すると、
$X + 2 \times (a \& b) = S$ より、 $a \& b = (S-X)/2$ となる。
すると、 $S-X$ が奇数の場合や負になっている場合は答えが無しになる。
新たに $(S-X)/2 = D$ と置くとする。

すると、次のような条件になる。

$a \& b = D$
$a \oplus b = X$
$0 \lt a \leq A_1$

これによってビットごとに独立の計算になったことが良い性質である。ここで色々なことが分かる。
$a \oplus b = X$ との兼ね合いを考えると、 $X, D$ の同じビットが同時に $1$ になっていることはありえない。そのため、 $X \& D > 0$ である場合も答えは無しである。

ここで具体的に解いていく。
まず $D$ のbitで $1$ が立っているところは $a, b$ のどちらも $1$ が立っていないといけないので予め立てておく。
そうしたら $X$ の bitで $1$ が立っているところが気になる。このとき、 $a, b$ のどちらかに $1$ を立てるということをする。
このとき、 $a \leq A_1$ ギリギリのところまで bit を立てれば最大化出来そう。
そのため、上のビットから貪欲に $1$ が立てられるまで立てると、 $a$ を最大化させられる。
ここで最大化した結果として $a=0$ になるのならば、-1を出力する。

これをすると、 $a, b$ は条件を満たしている。移動した回数は $A_1 - a$ で出てくるのでそれを出力して終わり。

bitの計算になったら、足し算はすぐに xor と and に翻訳しないといけないと感じた。

感想

条件を洗い出したりする作業やアルゴリズムを抑えておく作業は事前準備や訓練でちゃんと出来ることなので、問題を解くこととテクニックを覚えることを両立させたい。

2020-06-23

ABC171 参加メモ

ABC 競技プログラミング

atcoder.jp
速さが…足りない！ 427th Perf=1901 1917->1916(-1)

A - αlphabet

isupperを知っている喜びを噛み締める

B - Mix Juice

ソートして $K$ 要素を小さい順に足す

C - One Quadrillion and One Dalmatians

$26$ のべき乗を引いていくと文字数が少ないときのナンバリングが消えていくので最終的に $26$ 進数の値になってくれる。デコードして終わり

D - Replacing

今どの数字が何個あるかは高速に追えるので、それをシミュレーションして総和も同時に計算していけばいい。

E - Red Scarf

$N$ が偶数のときは $a_i$ を全てxorしたときの値が全てのすぬけくんのスカーフの非負整数のxorになっているので、その値から $a_i$ に xorすれば答えが出てくる。

F - Strivore

$K+|S|$ 文字を「置く」事を考える。
これは $?$ を置くか、 $S_i$ を置くかということである。
現在 $k$ 文字目を置こうとしていて、 $S_i$ を置こうか否かというようになっているとき、もし、 $S_i = c$ の $c$ を置こうとしているなら、 $S_i$ を必ず置くものと見ても構わない。明らかに、後に $?$ を残しておいたほうが見られるパターンは多いし、置かない理由が他に無いと思う。
このような遷移にしておくと、実はパターンの重複も起こらず、全パターン列挙できる。
置くときに分岐が発生しないので重複はないし、 $S_i$ 置くことでのパターンの欠如はないのでそうだと思う。

すると、 $dp_{k,i}$ : $k$ 文字目まで置いていて、現在 $S_i$ を置こうとしているときのパターン数
というDPが生まれるが、遷移を見てみると、DPの答えが二項係数に $25^{k-i}$ つけたような数になる。
$i=N$ のとき、少し挙動が異なるが、もう $i \gt |S|$ があるように見てしまって、 $\displaystyle \sum \limits _{i=|S|}^{K+|S|} dp_{K+|S|, i}$ を見てしまっても、最終的な答えが変化しない。というのも、文字がどうであるかはそもそも関係無かったりする。
DPが二項係数に依存するということは、実際にやらなくても求まることがわかるので、 $\displaystyle \sum \limits _{i=|S|}^{K+|S|} \binom{K+|S|}{i}$ を求めて、これが答えになる。

なんかこういうふうに考えたけど解説見るともっと頭良さそう　すげえ

感想

やっぱりオーダーが追いつかないけど DP で考える方策は意外にたくさん使えるんだなぁって思った。
DPに現れる法則性に気づくと、早くなるんだね
ちゃんと解説も見たい。

2020-06-21

AGC046 参加メモ

AGC 競技プログラミング

Cが解けてなかったらBを解きに行かなかったので激冷えするところだった。今回はB,Cをちゃんと通せたので嬉しい 259th Perf=2271 1870->1917(+47)

A - Takahashikun, The Strider

普通に頭のいい方法が思いつかなかったので本番ではシミュレーションした(doubleでいろいろ)。
最初の位置を $A$ , $1$ 回進んだ位置を $B$ として $|AO| = |BO| \wedge \angle AOB = X$ になるような $O$ を取ると、どうやら $O$ を中心とした長さ $|AO|$ の円周上に全て乗るみたい。次移動するところも、 $O$ を経由した角度が $X$ になるようにやっていけば自然となる。実際書いてみると証明っぽいことが出来る(角度を追ってみるとたしかにそうなってることが分かる)。
とすると、同じ角度のところに戻ればいいだけなので、 $kX \equiv 0 ( \mod 360 )$ になるような最小の自然数 $k$ を見つけて終わり。

B - Extension

こういう感じの問題だと、 $dp_{a,b}$ : 現在のマス目の大きさが縦 $a$ マス, 横 $b$ マス( $(a, b)$ と略す) のときの塗られ方の個数とかが求まれば嬉しそう
まあ、たとえ引数が増えたとしても適宜そこは増やすと良さそう

漸化式を求めていきたい。
$dp_{a, b}$ を作るのに必要なものは、 $(a-k, b)$ ( $k$ は自然数 ) から縦に伸ばして行かないとありえない通りと、 $(a, b-m)$ ( $m$ は自然数 ) から横に伸ばしていかないとありえない通りと、どのように伸ばしても作れる通りの $3$ 種類である。

ここで、 $dp_{a-1, b}$ は縦に伸ばさないとありえない通りを全て持っており、 $dp_{a, b-1}$ は横に伸ばさないとありえない通りを全て持っている。
そのため、 $dp_{a-1, b} \times b$ , $dp_{a, b-1} \times a$ たちを足す。すると、どのように伸ばしても作れる通りが $2$ 回加算されてしまうので困る。
どのように伸ばしても作れる通りというのは $(a-1, b-1)$ から縦横に伸ばした時に一番右下のマスを使わないようにする通りと同義であるため、漸化式は、
$dp_{a,b} = dp_{a-1, b} \times b + dp_{a, b-1} \times a + dp_{a-1, b-1} \times (a-1) \times (b-1)$
となり、これを $(C, D)$ までやる。
すると、答えは $dp_{C, D}$ となる。
これはもちろん計算量は $\mathrm{O}(CD)$ であり、十分間に合う。

C - Shift

文字列の区別の仕方が変わらない別の文字列の表現形式を考えてみる。
$0$ の数を $A$ 個とする。
このとき $0$ で文字列を区切って $A+1$ 個の区間に分けて区間 $i$ に $1$ がそれぞれ何個ずつ入っているか $B_i$ を持つような表現にする。
すると、 $1$ 回の操作が $B_j \gt 0$ であるような $j$ を $B_j - 1$ にして $i \lt j$ である $B_i$ のどこかを $B_i+1$ すると言ったような操作になって単純になる。

これで数字を $K$ 回以下左に $1$ こずつ移動させられるときにできるパターン数を数え上げするだけの問題になる。
これは反転させた配列を右に $K$ 回以下移動させる処理と同じであるため、今回はそっちを考える(やりやすいので)。

ここで考えたいのは、値を「置く」という処理を繰り返すということである。
値を置いて、実際に構成しながらパターン数を求めれば答えに間違いはなさそう。
ここで必要な情報は現在位置と現在位置より左の $1$ を何個置いてないか、何回操作を行ったかという情報である。
しかし、一回ある場所に「置いた」時にそこから「取り出す」操作は禁物で、これをすると、同じパターンを重複して数え上げてしまう(構成したものを戻してしまうことになるので、パターン数が増えることは分かるだろう)。
そのため、すでにその位置に要素を一度でも置いたかという状態も持っておく必要がある。

ここでこのようなDPを考える。
$dp_{i,j,k,l}$ : 現在 $i$ 個目までの要素を見ていて、 $i$ よりも左にある $1$ を $j$ 個置いておらず、 $k$ 回操作をすでに行っていて、区間 $i$ に対してすでに数字を一度でも置いたか $l$ が分かるときのパターン数

遷移では次の要素に移るときに元からあった要素を何個見過ごすかを決定する。見過ごした数だけ $k$ が減る。
置く/置かないの操作は $i$ 内で行ってしまって、置くとき、 $j$ が $j-1$ になる。同時に $l = 1$ になる。

$l = 1$ になっていると、元からあった要素を見過ごすことが出来ないのでそのパターンを取り除く必要がある。

見過ごす数を決めるのを for文でやっても、ならされるので、計算量は $\mathrm{O}(N^3)$ となっているはず。
実際、そのforをimosを使って無くしてみたけど、全然早くならなかったため多分同じ計算量なんだと思う。
あと、 $K$ は $N$ 回より多く使わないので予め K = min(K, N); とかしておくと楽だと思う。

感想

Dも時間があれば挑戦してみたい。
数え上げは表現形式を問題に沿うようにつくり上げるのがかなり大事なんじゃないかなと思った。

2020-06-20

ACPCVC20200520 復習メモ

ACPCVC 競技プログラミング

https://kenkoooo.com/atcoder/#/contest/show/a4ae8851-2cd0-46d7-963e-5aceb43e351d

こんなペースでは大丈夫ではない

A - CARtesian Coodinate

とりあえず、どのような場所が距離が最小になるのかということをわかっておきたい。
まずマンハッタン距離を扱ってるので距離の $x, y$ は独立に考えられる。
そのため $x$ 座標について考えると $\displaystyle \frac{N(N-1)}{2}$ の交点を $x$ でソートしたときに $\displaystyle \left\lceil \frac{N(N-1)}{4} \right\rceil$ 個目の $x$ 座標の所が最小の距離になる所かつ最小の $x$ 座標になる。同様に $y$ 座標も同様に求める。

ここで、真ん中の点を見つければ良いということがわかった。
ではそのような点をどう見つければいいだろうか。

また、 $x$ 座標について探してみる。
ここで気づくべきなのは、 $x=X$ であるような直線より左側にある交点の数は高速に求められるということである。
どうやってやるかというと、 $x \rightarrow -\infty$ の直線との交点たちの $y$ 座標の順番と $x = X$ の直線との交点たちの $y$ 座標の順番を比較する。

$x$ を限りなく小さくすると、それぞれの直線の $y$ 座標の順番は変化しなくなり、傾きの大きさだけが関係するようになる( 傾きが大きいほど $y$ 座標は小さくなる)。

このときの直線の番号を $y$ が大きい順に $1, 2, \cdots, N$ のように振る。
このように振ったら、 $x = X$ のときに $y$ が大きい順に見た時に番号の並びが変化している。
$x = X$ のときの番号の並びの転倒数を取ると、これは $x \leq X$ であるような交点の数と一致している。
f:id:tinumukiti631:20200620030825j:plain
青い線は $x \rightarrow -\infty$ の代わりの直線である(傾きが大きい順に直線の $y$ 座標が並んでいるのでここでは同義になる)。

実際には予め直線を傾きの小さい順にソートしておく(このインデックスが $1, 2, \cdots, N$ で $x \rightarrow -\infty$ についての並びと同義になる)。
$x=X$ のときの交点を $y$ が大きい順にソートしてインデックスの並びを見る。この並びの転倒数を見ると交点の数が分かる。
計算量はソートと転倒数を求めるのがどっちも $\mathrm{O}(N \log N)$ でできるので、この調べは $\mathrm{O}(N \log N)$ で出来ることが分かる。

この調べは $x$ が大きくなれば数も増えるという単調性があるので二分探索することで、交点の数がちょうど半分になるところが分かり、そのような $x$ が最小コストの点であることが分かる。
これを $y$ 座標にも同様に行えば終わり。
計算量は二分探索の回数を $M$ とすると、 $\mathrm{O}(MN \log N)$ になるのかな ( $M$ は $100$ もあれば十分)

長い上にわかりにくい解説を書いてしまったな

B - 101 to 010

操作で連鎖が起こるパターンが $2$ パターンしかなくて、 1111...101 か 101111....1 になる。
このパターンの数は $\mathrm{O}(N)$ 個くらいしか無い。
そのため、パターンとそのパターンを全て消すための操作回数の情報をエッジにしてDPを書けば簡単に求まる。
$dp_i$ … $i$ 文字目まで見たときの操作回数の最大値
パターンの始点と終点、操作回数の情報しか要らなかったりする。

なんか雰囲気意外と簡単な気がする。本番で解けなかったから簡単じゃないんですが…

C - Yet Another Palindrome Partitioning

これdiff が B > C なのがかなり直感に反する

「 $s_i$ の文字を並び替えて回文が出来る」というのは「文字数が奇数である文字の種類の数が $1$ 以下」というように置き換えられる。
$dp_{i,bit}$ : $i$ 文字目まで見ていて、 $j \leq i$ である文字列 $\lbrack 1, j \rbrack$ のそれぞれの種類の文字の文字数が奇数であるかどうかの $bit$ があるときの分割数の最小値
みたいな感じのDPの配列を用意しておく。これ自体は大きすぎて無理だが、値は保存されるので配列を使いまわせて $2^{26}$ 個だけ持っておくだけで良い。
このDPがあると、全体の文字列 $s$ の文字数の偶奇を $xd$ に置いておくと、 $dp \lbrack xd \rbrack$ のところに答えが出てくることになる。
分割毎に $1$ 種類だけ奇数を許しているので、分割させれば、DPの遷移的には $2$ のべき乗を xor したところまで許して伝播できる。

ごめんなさい、これについてはコード載せておきます。全然書けない…
どっかでリトライできたらします(こう言っとけばってのがあるけど多分やらないだろうな)

void Main() {
	string S; cin >> S;
	int xd = 0;
	vint dp(1<<26, INF);
	dp[0] = 0;
	for (auto &s : S) {
		xd ^= (1<<(s-'a'));
		for (int i = 0; i < 26; i++) {
			chmin(dp[xd], dp[xd^(1<<i)]+1);
		}
	}
	cout << max(dp[xd], 1) << endl;
}

配列は大きいけど遷移は $\mathrm{O}(N)$ しか無いので早い。

感想

Aとかはちゃんと考えて自力で解けたから嬉しかった。
Cは求まりそうっていうのはしっかりわかる(弁明)
解法の要約ってかなり難しいな全部解説しようとしちゃうか全然書けないかになっちゃう
競プロをしなきゃ精神的に危ういのに本能よそれを理解してくれえ…

2020-06-17

ACPCVC20200617 復習メモ

ACPCVC 競技プログラミング

https://kenkoooo.com/atcoder/#/contest/show/8292b88e-c34a-4b53-bf9a-396ec14abd4d
考察はゆっくりやっていたが、チーム戦で冷静にできるかな…？

A - 五目並べチェッカー

まずお互いの碁の数がおかしくなってたらダメなのでその判定をする。
不正がないと言えるのは、まだどちらも勝利条件を満たしていないか、現在のターンで勝利条件を満たしているかのどっちかである。
まとめると、「 $1$ ターン前において考えられる碁の配置において、全ての状況で勝利条件を満たしている」と、現在のターンに来ることはないので不正があると言える。
そのため、 $1$ ターン前を再現して、その全てに置いて勝利条件を満たしているかを試せば終わり。これは計算も $19^4$ よりは小さそうなので普通に間に合う。

B - 合コン大作戦

男性について要求年収が低い人から見ていく(そのようにソートしておく $i < j$ ならば $B_i \leq B_j$ のような数列にしておく)。

例えば $1$ 番要求年収が低い人は $2$ 番目の男性の要求年収より低い女性たちに対して独占できる。
ここでマッチングを見つければ、その人たちは取り除いても良さそう。

もしここでマッチングを見つけられなかったら、 $2$ 番目の男性も含ませて、 $3$ 番目の男性の要求年収より低い女性たちに対して見てみる。
これは $3$ 番目の男性以降の人には全く関係のない女性たちである。
ここでどちらかのマッチングを見つけたら、できるだけ年収の低い男性を選んでおくと、のちのち男性が選ばれやすくなるはず。

この状態では $1$ 番目の男性も $2$ 番目の男性も要求年収について無視できるし、候補の女性たちについても自分の年収については無視できるので、単純に女性が適切な男性を選んでいくだけで良い。

このようにしてここで選ばれなかった男性たちは、また次の男性を入れて、同じようなことを繰り返していくと最適であることがわかるので、
男性は要求年収で昇順にソート、女性は自分の年収で昇順にソートしながら、男性の年収を multisetで管理しながらしゃくとりのようにやっていくと、この問題を $\mathrm{O}((N+M) \log N)$ ?で解くことが出来る。

ちょっと解説の言語化が難しい(というか解説できてないよねこれ)

C - 増築王高橋君

選び方は明らかにコストが小さいものから選んでいくと最適なことはわかる。
現在選んでいるコストが大きくなれば、もちろん増築回数も増えることになるので、単調増加な性質がある。

現在選んでいるコストを $c$ にすると、建物 $i$ について、何回増築したかというと、 $\displaystyle \left\lfloor \frac{c-A_i}{D_i} \right\rfloor +1$ 回であるため、実施回数は $c$ を決め打ちすると求めることが出来る。すると、 $\mathrm{O}(N)$ で合計で何回増築したかが分かる。

そのため、 $c$ で二分探索することを考える。
$K$ をぎりぎり超える増築回数 $k$ になるコスト $ansc$ が求まると、 $K$ 回増築した場合のコストは、
$\displaystyle \mathrm{simulate}(ansc) - (k-K) \times ansc$ となりこれが答えとなる。
ここで $\mathrm{simulate}(ansc)$ とは、現在 $ansc$ までのコストを見ているときの合計の増築コストを意味していて、現在見ているコストというのがわかっていれば、それぞれの数列の和もちゃんと $\mathrm{O}(1)$ で出てくるので全ての数列に適応した $\mathrm{simulate}$ 関数は $\mathrm{O}(N)$ の計算量になる。ちゃんと $\mathrm{simulate}$ 関数を実装して、この問題を $N \log (KD_{\max})$ で解くことが出来る。

ちなみに $\mathrm{simulate}$ 関数の実装時に計算順序に気をつけないと64bit符号付き整数型でもオーバーフローするところがある。
最大の答えになるケースは多分

だと思うのだが、これ、 $K=10^8$ のために $1$ 番目の数列に $10^8$ 回適応するわけだが、
ここでの数列の和は $\displaystyle KA_1 + \frac{D_1 \times K(K-1)}{2}$ になる。

ここで、着目すると、 $D_1 \times K(K-1) = 9999999900000000000 \geq 2^{63}$ である。
だが、 $\displaystyle \frac{D_1 \times K(K-1)}{2} = 4999999950000000000 \lt 2^{63}$ であるのでできるだけ早く $2$ で割っておきたい。
考えてみると、 $K(K-1)$ は偶数になっているのですぐ割れる。ここを先に割っておけばオーバーフローせずに計算できる。
でもたぶんこれ unsigned long long で十分な気もするな

感想

あんまりこの段階で言うことじゃないかもしれないけど、問題を与えられたら、ちゃんと頭でイメージする必要がありそう