格子状に座標が分けられてDFS,BFSするとき

絶対既存(調べ方がわからない)

なんかよくわからないタイトルになってしまったけど()

ちょっとしたテクも書いていこうかなみたいな備忘録

問題

codeforces.com

問題概要

W * Hの大きさの板チョコがあり、格子に沿って切ろうとしている

(xi1,yi1)から(xi2,yi2)に切り、必ず一つのピースが2つのピースに分かれるように切る

N回切ったときに存在するN + 1個のピースの大きさをソートして出力する

見られた解法

進む方向に切った部分があるのか、無いのかを判定して進む方法

O(WHn)なので十分間に合うけど...

判定めんどい(これが実装力のなさ)ので

2 * 2 の

oo
oo

のような板チョコを

+++++
+o+o+
+++++
+o+o+
+++++

のようにしてやると、

+は辺

oはチョコみたいにできるので、カットがかんたんにできますね(+の対応する部分を通れないようにする)

あとは座標(x,y)の2つの値がどちらも奇数のところがチョコの部分なので、それをカウントすればOKですね

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)

int W,H;
int N;
vector<vector<int>> fie;
using P = pair<int,int>;

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

int bfs(int sx,int sy){
    int ans = 0;
    queue<P> que;
    que.emplace(sx,sy);
    fie[sx][sy] = 0;
    while(!que.empty()){
        int x = que.front().first;
        int y = que.front().second;
        que.pop();

        if((x % 2 == 1) && (y % 2 == 1)) {
            ans++;
        }
        for(int i = 0;i < 4;i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(!(1 <= nx && nx <= W * 2 - 1)) continue;
            if(!(1 <= ny && ny <= H * 2 - 1)) continue;
            if(!fie[nx][ny]) continue;
            fie[nx][ny] = 0;
            que.emplace(nx,ny);
        }
    }
    return ans;
}

int main(){
    cin >> W >> H >> N;
    fie.resize(W * 2 + 1,vector<int>(H * 2 + 1,1));
    rep(i,0,N - 1){
        int x1,y1,x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if(x1 == x2){
            rep(y,y1 * 2,y2 * 2){
                fie[x1 * 2][y] = 0;
            }
        }
        else{
            rep(x,x1 * 2 ,x2 * 2){
                fie[x][y1 * 2] = 0;
            }
        }
    }
    vector<int> ans;
    rep(i,1,2 * W - 1){
        rep(j,1,2 * H - 1) {
            if (fie[i][j]) {
                ans.push_back(bfs(i, j));
            }
        }
    }

    sort(ans.begin(),ans.end());

    for(int i = 0;i < ans.size();i++){
        cout << ans[i] << " \n"[i + 1 == ans.size()];
    }
}

(実はもっとうまくかける(外枠を通れないようにしておけば、範囲の指定なんて要らない))

ICPCのこの問題も同じようにして解いてますねー

Amazing Mazes | Aizu Online Judge

僕のコード

AIZU ONLINE JUDGE: Code Review

ARC038-C 茶碗と豆 -Segment Tree上の二分探索-

才能がないね。悔しい

https://beta.atcoder.jp/contests/arc038/tasks/arc038_c

100点解法

grundy数を使い、遷移は i - C[i] ~ i - 1だけ注目すればOK

104点解法

高速化すべきは遷移にO(N)かかる部分である

ここでseg[i]を「grundy数がiである茶碗の番号の最大値」とする

そして、†Segment Tree上の二分探索†を行う

わけがわからないので、概略を言うと

seg[k * 2 + 1]とseg[k * 2 + 2]の値を見て、深く進んでいく

というイメージです(は?)

seg[i]を求めたいとします

grundy数は[0,N)の中にあるので順番に絞っていきます

もしこのようなgrundy数が[0,N / 2)の範囲にあるとすれば,どのような条件を満たすでしょうか

それは

[0,N / 2)の範囲でのseg最小値がi-C[i]より小さい

です

grundy数の求め方を考えると、範囲に無い数で最も小さい数がgrundy数になるので、この条件になります

これを繰り返し,l + 1 == r を満たしたら終了です

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)

vector<int> grundy;


struct Segment{
    vector<int> node;
    int n = 1;

    Segment(int sz){
        while(n < sz) n <<= 1;

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

    void update(int i,int x){
        i += n - 1;
        node[i] = x;

        while(i > 0){
            i = (i - 1) / 2;
            node[i] = min(node[i * 2 + 1],node[i * 2 + 2]);
        }
    }

    int get(int limit,int k = 0,int l = 0,int r = -1){
        if(r == -1) r = n;
        if(l + 1 == r) return l;

        if(node[2 * k + 1] < limit){
            return get(limit,2 * k + 1,l,(l + r) / 2);
        }
        return get(limit,2 * k + 2,(l + r) / 2,r);
    }
};


int N;
vector<int> C;
vector<int> A;

int main(){
    cin >> N;
    C.resize(N);
    A.resize(N);

    rep(i,1,N - 1){
        cin >> C[i] >> A[i];
    }

    int gs = 0;
    Segment seg(N + 10);
    seg.update(0,0);
    rep(i,1,N - 1){

        int ok = seg.get(i - C[i]);

        if(A[i] & 1) gs ^= ok;


        seg.update(ok,i);
    }

    if(gs == 0){
        cout << "Second" << endl;
    }
    else{
        cout << "First" << endl;
    }

}

ほかの例題があったら練習したいねこれ

AtCoder青色になるまでにやったこと

ありがとうございます ありがとうございます ありがとうございます

f:id:Kutimoti:20180416000716p:plain

水色から青色になるまでにやったことメインで書きたいと思います

緑後半、水色前半の方に届いたらいいなーという気持ちです

終始適当なテンションなのでご了承下さい

絶望のJOI本選

100点台....ここで自分の無力さ、努力のしなさ、ゴミであることを知りました(無知の知)

このころからTwitterが病んできます

春休みの精進

一週間で約100ACを生やす精進生活を送っていました()

f:id:Kutimoti:20180416000753p:plain

AtCoderで精進するのも良いですが、CodeForcesICPCにも手を出しました

ライブラリ作成

すごくいい経験になります(C++が書けるようになる)

GitHubのいい練習です(これは嘘でpushしかしない)

どんなお気持ちで精進していたか

精進し始めは、コーディング力も何もかも足りない状態だった(緑、水色前半とか抱えてるかもしれない問題)ので、克服するべく、ABC-C,D,ARC-Bを埋めました

実装力も付いてきたところで、典型力のNASAを感じるようになりました

ここでCodeforcesに手を出します

すごくお勉強になります(問題を理解すると簡潔な問題になる=典型的な考察,テクの必要性)

ICPCにも取り掛かりました(実装問題は捨てて、考察問題を解きました)

何回も「考察を意識して」繰り返してくるうちに、考察力も付いてきて、AGCが解けるようになってきました(個人差、経験で頭を磨いた感じ)

そのうちに青になることが出来ました

正直、僕は周りに比べて「天才」じゃなかった

(ポエム要素)

僕のFFには「青になるまでに特にしたことが無いから記事書けねぇ」とか、「青は通過点」みたいな人がいて、そういう人が青になるのかと感じてはいました

正直、そういう人たちを見て悔しかったし、何回も病みました.

週末のARCの結果が悪いと、一週間病みっきりです()

「あーなんで解けるんだろう...」

そのたびに憧れて努力をし続けようと思い、今に至る感じです(要は嫉妬で強くなった)

まあ、「努力の量で実力が変わるなんて思うな」ってエアリプが来た時は正直萎えましたが((((

人から否定されても、それが未確定要素ならそれを自分で確かめたほうがいいです(親にPCの前で座っているだけとか言われても気にするんじゃないぞ)

これから

codeforces詰める

区間DPを勉強してみた

精進してるとやっぱり出てきた区間DP...

避けてきたけど、今回は少しコツをつかもうと思って勉強してみました

What's 区間DP?

区間についての動的計画法です。はい。

....

は?

訳がわからんから取り敢えず問題解いてみよう

だるま落としぃ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1611&lang=jp

どのようにブロックの対を取り出せばいいのか....っていうところなんですが...

まずはdpの保持する値を決めてしまいましょう

dp[l][r] := 区間[l , r)で取り除くことのできるブロックの数

どのように求めるか

2つパターンがあって、今見ている区間を[l,r)とすると

1.lのブロックとr - 1のブロックが対になれる
2.[l,mid) , [mid , r)に区間を分ける

1.が満たすのはどういう状況か...

それは

・w[l]とw[r - 1]の差が1
・[l + 1,r - 1)が完全に取り除ける
    -> dp[l + 1][r - 1] が r - l - 2 

という条件にあたりますね

[l] [......] [r]

という配置のとき

[......]

が弾き出すことができて,かつ

[l][r]

をはじき出せるかということになります

2.を考えると

//左側で取り除けた量 + 右側で取り除けた量
dp[l][r] = dp[l][mid] + dp[mid][r]

というふうに出来ます

これをDPすればできちゃいそう!

どうやって書こう

再帰で書く方法と,ボトムアップ(for文だけのやつ)で書く方法,

どちらもありますが、再帰で書いたほうがわかりやすいかも(個人差)

int rec(int l,int r){
    //既に計算済み?
    if(dp[l][r] != -1) return dp[l][r];

    //これ以上取り除けない?
    if(abs(l - r) <= 1) return 0;

    int res = 0;
    //パターン1.
    if(abs(w[l] - w[r - 1]) <= 1 && rec(l + 1,r - 1) == r - l - 2)
    {
        //[l , r)がはじき出せるので
        res = r - l;
    }

    //パターン2.区間を分ける
    for(int mid = l + 1;mid <= r - 1;mid++)
    {
        res = max(res , rec(l,mid) + rec(mid,r));
    }
    return dp[l][r] = res;
};

こんな感じ

あとはrec(0,n)で求められるね

ひゃい

ボトムアップはこんな感じです

for(int W = 2;W <= n;W++)
{
    //left
    for(int l = 0;l < n;l++)
    {
        int r = l + W;
        if(r > n) continue;

        if(dp[l + 1][r - 1] == W - 2 && abs(w[l] - w[r - 1]) <= 1)
            dp[l][r] = W;

        for(int mid = l;mid <= r;mid++)
        {
            dp[l][r] = max(dp[l][r] , dp[l][mid] + dp[mid][r]);
        }

    }

}

幅を広げていくイメージです

コツ??

結局、遷移が大事だったね(ア)

どのように小さな区間に遷移していくかが問題っぽい...

今回は基本的なことしか書いてないからまだわからないけど

また違う問題で書こう

ARC090-E Avoiding Collision

何するか分かるけど、どうしたらいいのか分からないことが多かったので 書いておく

解法

1.S から各頂点への距離をDijkstraで求める

2.S から各頂点への経路数

各頂点からTへの経路数を求める

3.(全経路の組み合わせ) - (すれ違ってしまう組み合わせ) が答え

計算方法が分からず

1.は分かる

最短経路は必ずDAGになる(これは分かる)

dpをすれば経路数が分かるのだが

簡単に計算する方法があり

vector<P> vec;
for(int i = 1;i <= n;i++) vec.push_back({dist[i] , i});
sort(vec.begin(),vec.end());

とすることで、Sから近い順に頂点を取り出すことができるので

この頂点順に沿って

for(int i = 0;i < n;i++)
{
    for(auto & e : edges[vec[i].second])
    {
        if(dist[e.to] == dist[vec[i].second] + e.cost)
            (dp_t[e.to] += dp_t[vec[i].second]) %= MOD;
    }
}

としてやれば経路数が分かる

また各頂点からTまでの経路数は逆からやっていけばいい

for(int i = n - 1;i >= 0;i--)
{
    for(auto & e : edges[vec[i].second])
    {
        if(dist[vec[i].second] == dist[e.to] + e.cost)
            (dp_s[e.to] += dp_s[vec[i].second]) %= MOD;
    }
}

全経路の組み合わせは

dp_t[t] * dp_s[s]

すれ違う可能性のあるのは

頂点か辺

頂点...

出会うタイミングのあるのは

dist[v] * 2 = dist[t];

となっている頂点v

経路の組み合わせの数は S -> v -> T と T -> v -> S の組み合わせなので

dp_t[v] * dp_s[v] * dp_s[v] * dp_t[v]

辺...

出会うタイミングは

辺の両端の頂点をu,vとすると

2 * dist[u] < dist[t] && dist[t] < 2 * dist[v]
    &&  dist[u] + cost == dist[v]

を満たす辺である

経路の君合わせの数は S -> u -> v -> T と T -> v -> u -> S の組み合わせなので

dp_t[u] * dp_s[v] * dp_s[v] * dp_t[u]

これらを引いてやればいいですね

初心忘れるべからず..

ARC083-E Bichrome Tree

dp解けなくて悲しいね...

解法

要するに、「根をそれぞれの色で塗った時の合計がX_i以下になる」を満たせば 頂点に重みをつけることで満たすことができる

じゃあどうやって求めるのか、ということですが...

根をどちらかに塗った時の値は

X_iの値(定義から自明)

片方の色の値

じゃあ、この「片方の色の値」を最小化していけば、

効率のいい塗り方が求められるのでは

となります

この値をdp[i]...(頂点iで片方の色で総和をX_iにした時のもう片方の色の総和)

とすれば

ナップサックで解けますね

たどり着けなくて悲しいね

Submission #2171065 - AtCoder Regular Contest 083

WindowsのVSCodeにC++を書く環境を作る

VSCodeC++の環境を作るのに手こずっている人をいっぱい観測して

このままじゃ広がらない(宗教的)と思ったので書いてみました

環境はSurface Pro 2017 , Windows10です

VSCodeインストール

code.visualstudio.com

ここから

f:id:Kutimoti:20180302095547p:plain

一番左を選択

インストーラーがダウンロードされるのでそれを実行

f:id:Kutimoti:20180302095634p:plain

気長に待ちましょう

f:id:Kutimoti:20180302095712p:plain

起動できました

MinGWLLVM-clangのインストール

MinGWC/C++コンパイル用に

LLVM-clangはVSCodeの補完に使います

こちらのページがとても参考になりますね

yohshiy.blog.fc2.com

ここからが本題です f:id:Kutimoti:20180302095908p:plain

まずMinGWです

MinGWのインストールについては情報がありふれまくっているので

そちらを参考にしたほうがいいと思います

C言語入門 - MinGW - gcc のインストール - Windows環境 - Webkaru

ここで、MinGWのbinフォルダにパスを通しておいてください

次にLLVM-clangです

ここに飛んで LLVM Download Page

windows 64bitの方はこれ f:id:Kutimoti:20180302100141p:plain

これもインストーラーがダウンロードされるので実行しましょう

インストールしたLLVM/binにパスを通しておいてください

VSCode拡張機能を入れる

とりあえずこれでも書けて実行できるのですが

補完欲しいじゃないですか...

拡張機能を入れます f:id:Kutimoti:20180302100535p:plain

検索欄に「C++」と入力すると

いろいろ出てきますが

f:id:Kutimoti:20180302100618p:plain f:id:Kutimoti:20180302100629p:plain

この二つを入れてVSCodeを再起動してください

次に、VSCodeでフォルダを開きます

f:id:Kutimoti:20180302100925p:plain

ここをクリックして

適当な自分の作業フォルダを開いてみてください(プログラムを書く場所とか)

開いたら新しいファイルを作ってみましょう

f:id:Kutimoti:20180302100953p:plain

適当にhello.cppとかでOKです

拡張機能の設定

設定を開きます

Ctrl+, でもいけます

f:id:Kutimoti:20180302101112p:plain

するとこんな画面が開きます

f:id:Kutimoti:20180302101158p:plain

これの右側が自分の設定ファイルで左側がデフォルトです

右側を編集して f:id:Kutimoti:20180302101424p:plain このように設定します

設定が書けたら保存して、 hello.cppに戻りましょう

書いてみてください f:id:Kutimoti:20180302101640p:plain

感動

おそらくまだ補完が出ない方もいらっしゃると思います

問題はインクルードパスのデフォルトの設定が

visual studioのインクルードパスになっているせいです

visual studioC++を入れていない方は多分補完が出ません

直しましょう

インクルードパスの設定

Ctrl+Shift+Pでコマンドパレットを開きます(これ便利)

「cpp」と入力すると

f:id:Kutimoti:20180302101955p:plain

「Edit Configurations」

というのがあるので選択

デフォルトの設定ファイルが出てきます

いじるのはここ(winなので) f:id:Kutimoti:20180302102142p:plain

ここにMinGWのインクルードパスを追加します

             ,
            "C:/MinGW/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/7.1.0/include/c++/x86_64-w64-mingw32",
            "C:/MinGW/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/7.1.0/include/c++/backward",
            "C:/MinGW/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/7.1.0/include",
            "C:/MinGW/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/7.1.0/include-fixed",
            "C:/MinGW/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/7.1.0/../../../../x86_64-w64-mingw32/include",
            "C:/MinGW/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/7.1.0/include/c++"

追記

keymoonさんからご指摘をもらいました!ありがとうございます

"/bin"から左のパスはmingwをインストールした場所に各自して下さい...

f:id:Kutimoti:20180302102707p:plain

これで補完が出ると思います

実行する

統合ターミナル(?)を起動して f:id:Kutimoti:20180302102511p:plain

コマンドを打てば

f:id:Kutimoti:20180302102550p:plain

できましたーー

お疲れ様ー