2021/02/14

楽しすぎる家庭菜園

atcoder.jp

unrated

最大全域木(造語?)

南極

atcoder.jp

unrated

ダイクストラで解いた。マス(h,w)から(nh,nw)に移動する時、A(nh,nw)!=0 and A(h,w)!=A(nh,nw)の場合はコストがC(A(nh,nw))かかるとした。それ以外はコスト0。

通学路

atcoder.jp

unrated

親の顔より見た拡張ダイクストラ

総入れ替え

atcoder.jp

unrated

メモ化dfs。mapでメモをするとTLEになったので生配列でやった。

連呼

atcoder.jp

unrated

解けなかった。dpか?O(min(N,M)*(N+M))だから無理→ほうじょでもなさそう→組み合わせか?分からんって感じだった。結論から言うと組み合わせだった。できる文字列は以下を満たす。

①A...AB...BA...AB...B(グループは2*k個)

②A...Aの長さは1or2 長さの総和はN

③B...Bの長さは1以上 長さの総和はM

kを全探索する。②は「A...Aの長さは0or1 長さの総和はN-k」と言い換えると式が立てやすい。③も同様。

ライ麦畑で待ちながら

atcoder.jp

unrated

セグ木を使う。型はpair(数字、その数字の右側にある記号(+ or *))のvectorにした。あるノードのvectorのサイズは高々3なので計算量は大丈夫そう。マージの実装に手間取った。↓のようにすると書きやすかった。

    auto f=[](vector<TA,vector<TB){
        vector<T> ret;
        if(A.size()==0return B;
        if(B.size()==0return A;
        for(auto b:B){
            if(A.back().second=='*'){
                A.back().first*=b.first;
                A.back().second=b.second;
            }else{
                A.push_back(b);
            }
        }
        ModInt sum=0;
        for(int i=1;i+1<A.size();i++){
            sum+=A[i].first;
        }
        if(A.size()<=2return A;
        ret.push_back(A[0]);
        ret.push_back(T(sum,'+'));
        ret.push_back(A.back());
        return ret;
    };
 
根室の巫女

atcoder.jp

unrated

kmp法で作られるテーブルが与えられて、元の数列を復元する問題。

分からなかったから解説を見たけど、よく分からなくて結局自分で考えた。

A[1~i-1]は分かっていると仮定して、A[i]を考える。↓をして問題ない。

①i<=B[i]:あり得ないので"No"を出力してプログラムを終了

②0<B[i]<i:A[i]=A[B[i]]

③B[i]=0:A[i]=今までに使ってない数字

③が駄目な場合は、j>=i and B[j]>=(j-i+1)となるjが存在する場合。その場合は、B[i]が正の値になっているはずなので存在しないことが分かる。

最後に解が正しいかをkmp法を使って判定する。

「ここはこの値で問題ない」を繰り返して解を作って、最後にその解が正しいのかを判定する流れ、構築でよくありそう(適当)。

 

 

日記

いろはコンDay2の残りを埋めた。

 

2021/02/13

虫取り

atcoder.jp

unrated

HLD+遅延セグ木。遅延セグ木のbuildを忘れていて無限にWAがでた。

高速道路 (Highway)

atcoder.jp

JOI 難易度10

HLD+区間和でできそう。上りと下りで時間が違うのが面倒そう。都市xから都市yへのパスは上り(x→lca(x,y))と下り(lca(x,y)→y)に分解できる。セグ木を2個使った。

DFS Game

atcoder.jp

青diff

ある頂点vに駒を置いたとき,vの部分木のコインを全て回収するまでvの親に戻ることはない(そして、vにはもう戻らない)。これに気づいてから木dpができそうだなと思った。dp[v][vに着く駒を動かした人か]=vの部分木での取得コイン数の最大とした。移動する子の選び方を考える。必ず2人で全コインを回収するから、自分の取得コイン数-相手の取得コイン数が最大の子を選ぶ。部分木のサイズが偶数の子に移動すると、次に選ぶ人は変わらないから,得をするなら最初にまとめて選ぶ,損をするなら最後に選ぶ人がまとめて選ぶようにする。

その他

ARC112があった。Bでsetで区間を管理するライブラリが欲しくなった(ライブラリを増やしたい気持ちはあるけど今はAC数を増やしたい……)。いろはコンday2が勉強になりそうだからやりたい。

 

2021/02/10

マスゲーム

atcoder.jp

unrated

gridのbfsをライブラリ化した.

 

38 parrots

codeforces.com

チーム練D

queueを意識せずにセグ木に全部乗せていく。区間のminとgcdが一致すればY。

Fence

codeforces.com

チーム練L

考えると線と円弧になりそう。凸包を作り,その後それぞれ外側の垂直方向にR離した図を考える。離れている部分を円弧でつなげばそれが最小。その円弧は全部集まると円になる。村を大きくする方法ばかり考えてしまった。

虚無4問
その他

チーム練をした。チームとしては良かったと思うけど、僕は微妙だった。Dは思いつきたかったな。明日はHLDの整備をする。

2021/02/08

GCD or MIN

atcoder.jp

黄diff

残る整数は,A[0]...A[N-1]から1個以上取ってgcdを行った形で表せて、Aの最小値以下のもの。A[0]...A[N-1]のそれぞれの約数(残る整数の候補)を求めて、それらが↑の形で表せるかを判定することで解くのを思いついた。判定は、例えばxを考えるとき、A[0]...A[N-1]の中でxの倍数の集合のgcdがxになればokでよさそう。1e9以下の自然数の約数の個数の最大が1344らしいので,多めに見積もって1344*N*Nのループが必要になる。間に合うか怪しかったので解説を見た。

解説は自分の方法と本質的には同じで、より高速化したものだった。連想配列を用意して、A[i]%x==0ならmap[x]=gcd(map[x],A[i])をする。候補の列挙と判定を同時に行っている感じ。

Two Sequences

atcoder.jp

黄diff

ibit目を考える。このとき、aとbの値はi+1bit目以降は無視していい。t=(1<<i)とする。i+1bit目以降は無視した値でのaとbの値の和は[0,4t)になる。この中で、ibit目が1になるのは[t,2t),[3t,4t)。ajを固定して、にぶたんで和がibit目が1になるbの個数を数える。

安全点検

atcoder.jp

JOI 難易度7

にぶたん。後ろから必要な人数を求めていく。

その他

明日は課題のb+-treeを実装する。