2018/2 solved(1)
2/1
2/2
よくわからなかったけど、実験してみると規則性があったのでそれを実装した。
考え方としては、まず全てのセルには1か-1しか置くことが出来ない。その上で、k=-1のとき、行をベースに見ると-1を n*(奇数) 個置く必要があるのに対し、列をベースに見ると-1を m*(奇数) 個置く必要があるので、 nとmの偶奇が異なるとこれが矛盾するのでこの場合は0となる。それ以外のケースは全て実現可能で、具体的に数えるのは左上の (n-1)*(m-1)マスは自由に設置可能で、あと最後の行と列はそこからユニークに定まると考えられる。
2/3
2/4
2/5
まず、setに1があるなら自明に可能で、間に1を挟んだ数列を出せば良い。それと同じ要領で、1が無い時もset内の全てのもののgcdを取ったものがset内の最小の値に一致していれば可能で、それを間に挟んでいけば良い(submission)。
2/6
グラフの構造は、バランスの取れた二分木になるように必ずなっていることが分かる。0を根と見なし、各頂点に対して、
を根とする部分木内の頂点に対して、それぞれ
までの距離がどれくらいになるかを配列で持つ。これは、一見
になりそうに見えるが、SegmentTreeの空間計算量が
になるのと同様で、
になっている。この情報を持っておくことで、クエリに対して、次のように答える：
からスタートして、根の方向に辿りながら、今辿ってこなかったもう片方の子の部分木に対して、距離が
以下になっているものを数え上げる。求めたいものの和は、累積和を持っておくことで、二分探索で見つける事ができる。よって、各クエリに対して
で答えられるので、全体として
となる(submission)。
SCCして、DAGにしておく。すると、強連結成分内の辺に関しては、何回でもまわることが可能なので、枯らすまで回収することが出来る。SCCした後もDAGになっている辺は、一度しか通れない。すると、SCCすることによって、頂点に価値があり、辺にも重みのあるDAGができあがり、後はこのDAG上で価値を最大化するDPをすれば良い(submission)。
2つの区切り位置を全探索。あとは累積和で数える(submission)。
2/7
偶数番目を打った後に、奇数番目を打ち、もう一度偶数番目を打つのが効率よく倒せる。
2/8
一直線にすすめていく時に、今よりも真に小さい値でたどり着けるセルにぶつかったら、そこからスタートさせたほうが得なので、それ以降を打ち切って良いと考えることで基本的には1歩ずつ進める時と同じbfsのような計算量が実現できる(submission)。
オイラーツアー + セグ木。セグ木は、区間に対する反転とaddが出来るものを作れば良い(submission)。
CF #427(Div.2) Virtual
ABCDの4完。自分のRollingHash定数倍重いし、baseは2つだけで十分かも...
2/9
2/10
2/11
2/12
まず、返ってくる値の種類は0, x, y, x^yの4種類しかない。更に、specialなものを1つのみ含むsetを見つけられれば(そのときはyかx^yが返ってきている)、あとは二分探索によってどれがspecialなのかを見つけることが出来る。specialなものを1つのみ含むsetをいかにして見つけるかという問題になるが、これは番目のbitが立っているものだけをクエリに含める、ということをすると、必ずどこかで異なるbitが発生するので、見つけることが出来る。見つけるのに10回、見つけた後の二分探索に(要素数は全体の半分なので)9回で見つけることが出来る。片方の答えがわかれば、もう片方の復元は初めに聞いた10回の情報を利用してbitごとに復元ができる(submission)。
2/13
setで空いている区間と埋まっている区間を別に管理しながら頑張る。入れる場所がかなり分割されてかかりそうに感じるが、実際は全体では抑えられる(submission)。
2/14
途中まで制約を見誤っていて(文字の長さが100まであると思っていた)、謎の考察をしたりできるだけ高速に動くようにちょっと変な工夫をしたりとかしていたけどそれまでに現れた文字と何文字目かをみていけば計算できる(submission)。
