精進 ARC-070D No Need

途中まで気付けていたのですが

二分探索が分からなかった...

二分探索できない、勉強しなきゃ

どこまで気づいていたか

・ナップサック的にギリギリまで詰め込む

・ソートしておく

・不必要以下の大きさのカードは不必要

・必要以上の大きさのカードは必要

以下と以上の条件が出たら二分探索じゃないですか

確かにそうだ

ちゃんと把握しなきゃ、練習しなきゃ

Submission #2090524 - AtCoder Regular Contest 070

精進　ARC-069D Menagerie

あーこんなに簡単だったのか....

気づくの苦手すぎるので意識することを書いておく

どの問題でも「何が決まればいいのか」を把握しておく

広義昨日のForestも

「辺の数」と「森の形」と「頂点の小さい順」が決まれば

答えが導ける

ということだった

そういうことだね...

今回の場合は

「最初の２つの動物の種類」が決まれば

すべて決定できる

ということだった

あーやっぱり

「ここがわかってれば解けるのになぁ」という気持ちにならないと

頑張るぞ

Submission #2090026 - AtCoder Regular Contest 069

精進 APC-001-D Forest

こういう考え方が足りなさ過ぎてつらい

頑張らないとね

精進1

理想な考察の仕方を連ねてみるが(あっている保証がない)

要するに何するんですか (What is this?)

森を木にするための最小コストを調べます

答えはどんな形ですか (Answer?)

森にある木をすべて頂点で結んだ形

頂点はどうやって選びますか (How?)

すべての木をつなぐ->木のうち最低一つの頂点は使う

あとは小さい順

何個頂点を選びますか (Time?)

木を構成するにはn - 1の辺が必要

もうm本引いてあるので n - m - 1

引く辺の頂点はかぶってはいけないので

2 * (n - m - 1)個頂点を選べばいい

簡単ですね

はい

木を作って

木の中でもっとも小さいのを取り出して

あとは個数分だけ取り出す

もうすでに木ができているケースがあるので注意

apc001.contest.atcoder.jp

JOI'2018 本選体験記

お疲れさまでしたーーーーーー

だがしかし大爆死....

来年頑張るね

次出ようかなとか考えてる人も参考までに

プラクティスの日

はい誕生日()

僕は会場に受付終了30分前ぐらいにつきました

えープロばっかり赤いなみんな

綾鷹を入り口付近で抱きしめているとツイートすると

えかすどプロと、るましプロが寄ってきてくれましたー

初めましてーーっていう感じ

僕はここで携帯の電源がなくなります(ア)

新幹線の中では充電しましょう

プラクティス受ける全完

漁師がプラクティスTLEが判明

とがさんに会う

たのちい

夜は独房に入れられます()

ですがTwitterのおかげで

えかすど、るまし、漁師でアニメが見れた

ほんとたのちい

本選

150点！死！！！

DEGwerさんの解説面白すぎか

早く黄色になりたいな

JOI本選難易度8埋め

結論

自力 6/10

解説 4/10

あーっていう感じです

あみだくじ

自力

何も取り除かなかったときの経路を記録しておき

取り除いた時の経路を調べる

散歩

解説

マスを進めるごとにx2ずつ変更の周期が上がることはわかっていたが

そこからが無理だった...

認証レベル

自力

それぞれどのくらい認証レベルを上げればいくつの部屋に入れるかを記録

歩くサンタクロース

解説

全部調べず、真ん中のところだけ調べるという発想が無かった

釘

自力

三　角　形　i　m　o　s

現代的な屋敷

自力

ダイクストラをしました

フクロモモンガ

自力

ダイクストラをしました

鉄道運賃

解説

入次数とかの知識と経験が足りなかった

準急電車

自力

特急->準急->普通

の順番で使うということに気がついた

JOIOI王国

解説

2分探索はアでした

これ本選大丈夫か?

JOI本選に向けてアルゴリズムを整理しておく

情報オリンピックまであと2週間!

まだまだアルゴリズムを覚えれていない気がするのでちょっと整理

情報落ちしていることが多数なので

参考までにお願いします

ダイクストラ法

AiとBiを距離Ciで結ぶなんか出てきたら疑っていい

//距離記録用のテーブル
ll dist[100010];

//辺
struct edge
{
    int to;
    ll cost;
};

//辺を記録
//edges[a].push_back({b,c});という感じで
vector<edge> edges[100010];

//queueに突っ込む型を用意
typedef pair<ll,int> P;

priority_queue<P,vector<P>,greater<P>> que;

//初期値
dist[1] = 0;
que.push(P(0,1));


while(!que.empty())
{
    ll d = que.top().first;
    ll v = que.top().second;
    que.pop();

    //無くても動くし、無い方がいい場合がある
    if(d > dist[v]) continue;
    
    //C++11のforeach
    for(edge& e : edges[v])
    {
        if(d[e.to] < d + e.cost)
        {
            d[e.to] = d + e.cost;
            que.push(P(d[e.to],e.to));
        }
    }
}

ベルマンフォード法

負の辺があってもできる

for(int i = 0;i < V;i++) d[i] = 1000000;

//最初の点は距離はゼロ
d[1] = 0;

while(true)
{
    bool update = false;
    for(int i = 0;i < E;i++)
    {
        const edge& e = es[i];
        if(d[e.from] != 1000000 && d[e.to] > d[e.from] + e.cost)
        {
        d[e.to] = d[e.from] + e.cost;
        update = true;
        }
    }
    if(update == false) break;
}

外側のwhileループはV - 1回しか行われない もしV回目に辺の更新が行われたなら負の閉路があることにある

経路を示すとき

ダイクストラ法であれば値を更新する際に

prev[e.to] = v;

としてやれば目的の頂点から始点までを辿れる

Union-Find木

グループ分けが必要なとき

struct UnionFind
{
    vector<int> par;
    vector<int> rank;

    UnionFind(int sz) : par(sz) , rank(sz,0)
    {
        for(int i = 0;i < sz;i++)
        {
            par[i] = i;
        }
    }

    int root(int x)
    {
        return  par[x] == x ? x : par[x] = root(par[x]);
    }
    bool unite(int x,int y)
    {
        x = root(x);
        y = root(y);
        if(x == y)
            return true;

        if(rank[x] < rank[y])
        {
            par[x] = y;
        }
        else
        {
            par[y] = x;
            if(rank[x] == rank[y]) rank[x]++;
        }
        return  false;
    }

    bool same(int x,int y)
    {
        return root(x) == root(y);
    }
};

二分木探索

lower_bound...x以上の数で最小の数
upper_bound...xより大きい数で最小の数

配列はソートしておかないと使えない

ナップサックDP

これを見て気分を落ち着かせましょう

DPは幅が多すぎてア

Segment Tree

区間に対しての操作に強い

これを解いておこう

値の更新は下から

値の取得は上からというのをベースに考えておけばOK

ll MAX = (ll)(1LL<<31) - 1LL;
struct Segment
{
    vector<ll> node;
    int n;
 
    Segment(const vector<ll>& v)
    {
        int sz = v.size();
        n = 1;
        while(n < sz) n *= 2;
 
        node.resize(n * 2 - 1,MAX);
        for(int i = 0;i < sz;i++)
        {
            node[i + n - 1] = v[i];
        }
 
        for(int i = n - 2;i >= 0;i--)
        {
            node[i] = min(node[2 * i + 1],node[2 * i + 2]);
        }
    }
 
    void update(int in,ll x)
    {
        in += n - 1;
        node[in] = x;
 
        while(in > 0)
        {
            in = (in - 1) / 2;
            node[in] = min(node[in * 2 + 1] , node[in * 2 + 2]);
        }
    }
 
    ll getmin(int a,int b,int k = 0,int l = 0,int r = -1)
    {
        if(r == -1) r = n;
 
 
        if(r <= a || b <= l) return MAX;
 
 
        if(a <= l && r <= b) return node[k];
        ll nl,nr;
 
        nl = getmin(a,b,2 * k + 1,l,(l + r)/2);
        nr = getmin(a,b,2 * k + 2,(l + r)/2,r);
 
        return min(nl,nr);
    }
};

i += n - 1を頭に入れておきたい

遅延評価Segment Tree

遅延評価する...eval(int k,int l,int r)

値を区間で変化させる...getminみたいにlazy[]に入れていく、このとき

1.最初に評価する(eval)
2.値を変化させた後、評価させる

これを基本に

前に書いてた記事

トポロジカルソート

有向グラフが順方向になるようにソートする方法

vector<int> edge[10010];

//入次数
int h[10010];

int V;
int E;

    cin >> V;
    cin >> E;

    for(int i = 0;i < E;i++)
    {
        int s;
        int t;

        cin >> s >> t;

        edge[s].push_back(t);

    //向かってきている辺の数をカウントする
        h[t]++;
    }

    stack<int> st;

    for(int i = 0;i < V;i++)
    {
        if(h[i] == 0) st.push(i);
    }

    vector<int> topolo;

    while(!st.empty())
    {
        int v = st.top();
        st.pop();

        topolo.push_back(v);

        for(int to : edge[v])
        {
            h[to]--;

            if(h[to] == 0)
            {
                st.push(to);
            }
        }
    }

入次数が0のところをstackに突っ込んでいく感じ

またこれをqueueにすると違う経路が得られる可能性がある

思いつく限りで書きました

もっとあると思うがここには余白が狭すぎるし

何しろ自分の知識の幅が狭すぎる

JOI 2010-2 お菓子の分割

https://joi2010ho.contest.atcoder.jp/tasks/joi2010ho_b

案外すっと解けたけど色々新しいことが体験できたので記す

問題の意味を変える

棒を切って渡すという感じだが、

このような問題とも読み取れる

どちらか受け取る人を決める
次切るまで、1ミリを受け取り続ける
切った時コストを払い、
またどちらか受け取る人を決める

なので

dp[i][j][k] := 次からkの人(0の時自分、1のとき相手)が受け取り、今i番目まで見て、自分がjミリ受け取っているとき最小のコスト

とすれば

1.そのまま受け取り続ける

//自分が受け取る
dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j - 1][0]);
//相手が受け取る
dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j][1]);

2.自分が受け取った後、切る

if (j > 0)
{
    //切った後受け取る人を自分にする
    dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j - 1][0] + t[i]);
    //切った後受け取る人を相手にする
    dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j - 1][0] + t[i]);
}

3.相手が受け取った後、切る

//切った後受け取る人を自分にする
dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j][1] + t[i]);
//切った後受け取る人を相手にする
dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j][1] + t[i]);

これで解いた

ただ、iの部分をそのまま利用するとMLEしてしまう

しかし前回の記録にアクセスするのはi-1の分だけなので

最適化することができる

これでAC

僕のコード