精進記録: ABC17 - ABC20 C問題

進捗状況

今日もとりあえず4問。

ABC16から先はしばらく簡単

https://tomerun.github.io/atcoder_statistics/estimated_scores.html

 

難易度高いのは 

・ABC009 辞書式順序ふたたび :  667点

・ABC001 風力観測                :  589点

ぐらい？精神を犠牲にすれば明日中に終わらせられるかもしれない。

 

AOJのcourse問題が結構容赦なかったおかげか、まったく歯が立たないというケースはあまりない。

これまで出会った600点以下の問題で必要な知識は基本的に全てAOJで見たことがあるもの(ゲーム木は初めてだったが)。

 

 

 

競プロ力のボトルネックが考察力じゃなくて実装力になってしまっているがどうしたものか。

各種ライブラリの作成も兼ねてAOJ courseをC++でもう一周したほうが良いのかもしれない。

 

 

 

 

 

 

 

以下、解いていたときの考察メモ。

 

 

ABC20 527点

 

 

H, Wの制約が小さいが、Tの制約は大きい。

最短で到達する場合のみ考えればよいので、dfsなりで解ける。

 

xの可能な値に対してループを回すのは明らかに無理だが、

最短到達時刻がTを超えるか否かでxについて二分探索すればよさそう。

 

T(x) < Tなら left = middle+1;

T(x) >= Tなら right = middle;

 

left, rightの初期値として1とTを取っておけばよい。

 

-> 方針は正しいはずなのにTLEしてしまう。部分点。

 

最短経路は全てのx >=2に対して同じなので、dfsは二分探索の最初の一回だけやればよい。

-> 数は減ったが相変わらずTLE。二分探索に問題がある or 一回目すら回ってない。

二分探索はまあ大丈夫だろう。ということは一回目のdfsでTLEしている？

 

H, Wの制約が小さいと思ったが、brute forceでやるには大きい。O(4^30)は明らかに回らない。

 

 

最短経路の決定をもっと高速にやる必要がある。

-> ダイクストラ、ワーシャルフロイド、ベルマンフォード

 

グラフ探索の計算量の感覚が身についてない。もっと考えてからコード書くべき。

実装の楽なワーシャルフロイドを使ってAC。

 

おそらく最速は最短経路をあらわに構成できるダイクストラで、一回目の探索で最短路上の黒、白の数を取得し、それ以降の二分探索での最短距離の計算をO(1)にするというものだが、二分探索なので一回一回が多少重くても通る。

 

 

 

"魔の20番台”突破。

 https://misteer.hatenablog.com/entry/AtCoder_Blue_Done

 

(なお、18, 17は500オーバー)

 

 

ABC19 404点

 

even, oddに分けておいて処理する。

setを使うのが楽。

 

 

 

ABC18 549点

 

全探索だとどのぐらい必要か。

O(500 * 500 * 500 * (500*500))

 

(x,y), Kが与えられたときに塗れるかを判定するにはO(500*500)マスに黒が無いことを確認する必要がある。

ただし、K - 1で塗れることがわかっている場合は、外周だけでよいのでO(R*C* K * 4K)。これでもまだ間に合わない。

K-1について分かっているときに判定をO(1)にできて初めて10^8。

 

Kで菱形が成立することは、(x, y-1) , (x,y+1), (x-1,y), (x+1,y)で菱形が成立していることと必要十分。

 

これで回るか？ O(5*10^8)なので厳しいかもしれない。

falseになったサイトの周辺の探索を行わないようにする。

 

成立していることを bool[R][C]で管理して、Kについてループさせる。

ただし、探索する(x,y)はキューで管理して、falseになったものについてはそれ以降探索しない。

 

この場合、最悪のケースは全て白の場合。

領域からのはみ出しを考えると探索範囲は徐々に減っていくので間に合うか？ 

 

->キューに番兵を置くのを忘れていてデバッグに手間取ったが一発AC。嬉しい。

 

 

ABC17 542点

 

高難易度が続く。

 

ざっくり考えると、li, riの範囲が小さく、スコアの高い遺跡から攻略していけばよい。

貪欲法ができるか？ si/(ri-li)の大きいものから的な。 -> まあ無理でしょ。

 

[li, ri]が重複しないような遺跡の選び方は一般に無数にある。

N, M <=10^5では力押しは到底不可能。

 

-> 復活条件は「すべての種類の宝石を 1 つ以上獲得」だった。

つまり、[li, ri]の重複は許されている。

 

獲得しない宝石について探索する。

 

宝石ｊを獲得しないという条件での最大スコアは、

 

[li, ri]がjを含まない全ての遺跡を順不同で探索する

 

というもの。

 

 

宝石についてループを回すなら、各々はo(N)でなければ間に合わない。

愚直に和を取っていく方法でもデータセット2までなら通りそう。しかしデータセット3を通すにはまた工夫が必要。

 

siの総和から 宝石の位置 j を含む[li,ri]に対応したsiの和を引いたものが欲しい値なので、実質Range add query。

AOJのときに書いた平方分割のコードがあるが我流で汚すぎる。セグ木をやりたい。

 

-> 遅延評価セグメント木のコードを拾ってきて一発AC (自分で書け)。

 

遅延セグメント木を書けるようにしておきたい & ライブラリ化しておきたい。

 

ので、この記事を読み込むことにする。 -> http://tsutaj.hatenablog.com/entry/2017/03/30/224339

 

遅延評価平方分割はAOJでやったので、(遅延評価)セグ木もロジックは分かっているのだが、

better C野郎なのでちゃんとカプセル化された他人のコードで勉強。

 

 

 

 

セグメント木(RMQ)の実装例

 

http://tsutaj.hatenablog.com/entry/2017/03/29/204841

 

structSegmentTree {

private:

    intn;

    vector<int> node;

   

public:

    // 元配列 v をセグメント木で表現する

    SegmentTree(vector<int> v) {

        // 最下段のノード数は元配列のサイズ以上になる最小の 2 冪 -> これを n とおく

        // セグメント木全体で必要なノード数は 2n-1 個である

        intsz = (int)v.size();

        n= 1; while(n< sz) n*= 2;

        node.resize(2*n-1, INF); 

       

        // 最下段に値を入れたあとに、下の段から順番に値を入れる

        // 値を入れるには、自分の子の 2 値を参照すれば良い

        for(inti=0; i<sz; i++) node[i+n-1] = v[i];

        for(inti=n-2; i>=0; i--) node[i] = min(node[2*i+1], node[2*i+2]);

    }

   

    voidupdate(intx, intval) {

        // 最下段のノードにアクセスする

        x += (n- 1);

       

        // 最下段のノードを更新したら、あとは親に上って更新していく

        node[x] = val;

        while(x > 0) {

            x = (x - 1) / 2;

            node[x] = min(node[2*x+1], node[2*x+2]);

        }

    }

    // 要求区間 [a, b) 中の要素の最小値を答える

    // k := 自分がいるノードのインデックス

    // 対象区間は [l, r) にあたる

   

    intgetmin(inta, intb, intk=0, intl=0, intr=-1) {

        // 最初に呼び出されたときの対象区間は [0, n)

        if(r < 0) r = n;

       

        // 要求区間と対象区間が交わらない -> 適当に返す

        if(r <= a || b <= l) returnINF;

       

        // 要求区間が対象区間を完全に被覆 -> 対象区間を答えの計算に使う

        if(a <= l && r <= b) returnnode[k];

       

        // 要求区間が対象区間の一部を被覆 -> 子について探索を行う

        // 左側の子を vl ・ 右側の子を vr としている

        // 新しい対象区間は、現在の対象区間を半分に割ったもの

        intvl = getmin(a, b, 2*k+1, l, (l+r)/2);

        intvr = getmin(a, b, 2*k+2, (l+r)/2, r);

        returnmin(vl, vr);

    }

};

 

 

 

セグ木の特徴として覚えておくべきこと(RMQ)

要素数以上となる最小の2冪をnとするとき

・最下段の要素数は n

・それより上段のノードの総数は n-1

二分ヒープとして 0-indexedで実現する場合、

・parent k に対して left child = 2k+1, right child = 2k+2

・node xに対して parent = (x-1)/2

セグ木への操作について、

・i 番目の要素の葉は node[i + n -1]でアクセスできる。

・要素をアップデートしたら、関連するノードを親方向に更新していく。

・RMQは上から。要求区間と対象区間の関係性を使って再帰的にやる。

対象区間 = ノードkについてkを根とする部分木の葉の集合

対象区間は初期値 [0, n)で、その範囲内の最小値はnode[0]。

・要求区間[a,b]が対象区間と交わらない -> 適当にINFを返しておけば勝手に無視される。

・要求区間が対象区間を包含する  -> node[k]の値を返す

・要求区間と対象区間が交わる    ->対象区間を[l, middle), [middle, right)に分割して潜る->小さい方取る

遅延セグ木の特徴として覚えておくべきこと(RAQ)

・セグ木に加えて、lazyメンバ変数(vector<ll>)

・クエリで参照したノードについてeval = 「それが葉でなければlazyを子に伝搬させる」

・range sumでは 対象区間[l, r)に対して val * (r-l)をlazyに入れてeval

・要求区間と対象区間が交わる場合、子にそれぞれ再帰でaddをかける。

・getsumでは、evalしたあと要求区間が対象区間を被覆するまで降ろしていく。

 

 

 

 

 

 

各種アルゴリズムの実装、特にグラフ関係については、この人のコードが勉強になる　

https://ei1333.github.io/luzhiled/

 

 

グラフ関係のコードを読んでいて得られたTips

 

・(a,b)の大小が知りたいときは minmax(a, b) -> pair<T, T> (min, max)が便利

 

・vector<hoge> vecにhogeクラスの要素を追加したい時、hogeに適切なコンストラクタが定義されていれば emplace_back()が便利:

 

template< typename T >

struct edge{

    int src, to; T cost;

    edge(int to,T cost) :src(-1),to(to),cost(cost){}

    edge(int src, int to, T cost) :src(src),to(to),cost(cost){}

    edge &operator=(const int &x){

        to =x;

        return *this;

    }

    operator int() const{ return to;}

};

 

Edges< int> es; 

for(inti = 0; i < E; i++) {

    inta, b, c;

    scanf("%d %d %d", &a, &b, &c);

    es.emplace_back(a, b, c); // ココ

}

 

・データ構造をクラス化しておくと各種操作を行う関数の引数がグロくならない