2018-02-14

2018/2 solved(1)

solved programming

2/1

imulan.hatenablog.jp

2/2

よくわからなかったけど、実験してみると規則性があったのでそれを実装した。

考え方としては、まず全てのセルには1か-1しか置くことが出来ない。その上で、k=-1のとき、行をベースに見ると-1を n*(奇数) 個置く必要があるのに対し、列をベースに見ると-1を m*(奇数) 個置く必要があるので、 nとmの偶奇が異なるとこれが矛盾するのでこの場合は0となる。それ以外のケースは全て実現可能で、具体的に数えるのは左上の (n-1)*(m-1)マスは自由に設置可能で、あと最後の行と列はそこからユニークに定まると考えられる。

2/3

2/4

2/5

CF 894 C - Marco and GCD Sequence

まず、setに1があるなら自明に可能で、間に1を挟んだ数列を出せば良い。それと同じ要領で、1が無い時もset内の全てのもののgcdを取ったものがset内の最小の値に一致していれば可能で、それを間に挟んでいけば良い(submission)。

2/6

CF 894 D - Ralph And His Tour in Binary Country

グラフの構造は、バランスの取れた二分木になるように必ずなっていることが分かる。0を根と見なし、各頂点 $i$ に対して、 $i$ を根とする部分木内の頂点に対して、それぞれ $i$ までの距離がどれくらいになるかを配列で持つ。これは、一見 $O(n^2)$ になりそうに見えるが、SegmentTreeの空間計算量が $O(n)$ になるのと同様で、 $O(n)$ になっている。この情報を持っておくことで、クエリに対して、次のように答える： $A$ からスタートして、根の方向に辿りながら、今辿ってこなかったもう片方の子の部分木に対して、距離が $h$ 以下になっているものを数え上げる。求めたいものの和は、累積和を持っておくことで、二分探索で見つける事ができる。よって、各クエリに対して $O( (logn)^2 )$ で答えられるので、全体として $O(nlogn + m(logn)^2 )$ となる(submission)。

CF 894 E - Ralph and Mushrooms

SCCして、DAGにしておく。すると、強連結成分内の辺に関しては、何回でもまわることが可能なので、枯らすまで回収することが出来る。SCCした後もDAGになっている辺は、一度しか通れない。すると、SCCすることによって、頂点に価値があり、辺にも重みのあるDAGができあがり、後はこのDAG上で価値を最大化するDPをすれば良い(submission)。

2つの区切り位置を全探索。あとは累積和で数える(submission)。

2/7

CF 877 C - Slava and tanks

偶数番目を打った後に、奇数番目を打ち、もう一度偶数番目を打つのが効率よく倒せる。

2/8

CF 877 D - Olya and Energy Drinks

一直線にすすめていく時に、今よりも真に小さい値でたどり着けるセルにぶつかったら、そこからスタートさせたほうが得なので、それ以降を打ち切って良いと考えることで基本的には1歩ずつ進める時と同じbfsのような計算量が実現できる(submission)。

CF 877 E - Danil and a Part-time Job

オイラーツアー + セグ木。セグ木は、区間に対する反転とaddが出来るものを作れば良い(submission)。

imulan.hatenablog.jp

CF #427(Div.2) Virtual

ABCDの4完。自分のRollingHash定数倍重いし、baseは2つだけで十分かも...

2/9

2/10

2/11

2/12

CF 835 E - The penguin's game

まず、返ってくる値の種類は0, x, y, x^yの4種類しかない。更に、specialなものを1つのみ含むsetを見つけられれば(そのときはyかx^yが返ってきている)、あとは二分探索によってどれがspecialなのかを見つけることが出来る。specialなものを1つのみ含むsetをいかにして見つけるかという問題になるが、これは $i$ 番目のbitが立っているものだけをクエリに含める、ということをすると、必ずどこかで異なるbitが発生するので、見つけることが出来る。見つけるのに10回、見つけた後の二分探索に(要素数は全体の半分なので)9回で見つけることが出来る。片方の答えがわかれば、もう片方の復元は初めに聞いた10回の情報を利用してbitごとに復元ができる(submission)。

2/13

AOJ 2152 - Restrictive Filesystem

setで空いている区間と埋まっている区間を別に管理しながら頑張る。入れる場所がかなり分割されて $O(n^2)$ かかりそうに感じるが、実際は全体では抑えられる(submission)。

2/14

AOJ 1195 - Encryption System

途中まで制約を見誤っていて(文字の長さが100まであると思っていた)、謎の考察をしたりできるだけ高速に動くようにちょっと変な工夫をしたりとかしていたけどそれまでに現れた文字と何文字目かをみていけば計算できる(submission)。

2018-02-08

CF 877 F - Ann and Books

Codeforces programming

問題

Problem - F - Codeforces

問題概要

長さ $n$ の数列 $a$ と整数 $k$ が与えられる。クエリ $(l,r)$ :「閉区間 $[ l,r]$ 内の連続部分列で、その和が $k$ になるものの個数を答える」が $q$ 個与えられるのでそれぞれに答えよ。

$1 \le n \le 10^5$
$-10^9 \le a_i \le 10^9$
$-10^9 \le k \le 10^9$
$1 \le q \le 10^5$
$1 \le l \le r \le n$

アイデア

prefix sumを使えば、ある区間の和は $O(1)$ で取ることが出来る。以下では $p_i$ と表す。

Mo's Algorithm(詳しくは他の人の詳しいを解説を見たほうが良いが、要素の更新がない/クエリ先読み可/区間の端を1だけ伸縮させた時の値の変化を簡単に得られる時に有効)を使って区間の左端/右端を1伸ばす/縮める時に答えがどう変化するかを更新していきながら、該当するクエリと区間が一致した時に答えを記入していく、という流れになる。

具体的に何が分かると嬉しいかを考えてみる。いま、閉区間 $[ l,r]$ に対する情報を持っている状況を考える。

右端を+1

右端を右に動かしたいとする。その時に、答えの増加分は(新たに増える区間は必ず右端が $r+1$ なので)、 $p_{r+1} - p_i = k (i \in [l-1, r ] )$ を満たす $i$ の個数に一致する。

式変形すると、 $p_i = p_{r+1} - k$ となり、これを満たす $i$ が何個あるかは、 $i \in [l-1, r ]$ に対してmapなどで頻度をカウントしておけばこの更新を $O(logn)$ で行える事がわかる。

そして、答えの増分を計算した後に、mapに $p_{r+1}$ の分を足して、完了となる。

左端を-1

左端を左に動かしたいとする。その時に、答えの増加分は(新たに増える区間は必ず左端が $l-1$ なので)、 $p_i - p_{(l-1)-1} = k (i \in [l-1, r ] )$ を満たす $i$ の個数に一致し、式変形すると、 $p_i = p_{(l-1)-1} + k$ となる。

右端を-1

右端を左に動かしたいとする。その時に、答えの減少分は(消滅する区間は必ず右端が $r$ なので)、 $p_r - p_i = k (i \in [l-1, r-1 ] )$ を満たす $i$ の個数に一致する。

答えの減少分を計算する前にmapから $p_r$ の分を除き、 $p_i = p_r - k$ を満たすiの個数を数えて答えから引いておけばよい。

左端を+1

左端を右に動かしたいとする。その時に、答えの減少分は(消滅する区間は必ず左端が $l$ なので)、 $p_i - p_{l-1} = k (i \in [l, r ] )$ を満たす $i$ の個数に一致し、式変形すると、 $p_i = p_{l-1} + k$ となる。よって、答えの減少分を計算する前にmapから $p_{l-1}$ の分を除き、減少分を計算すれば良い。