2020年 6月 19日

まえがき

やばい、priority_queueになってしまいそう…

実は実家がpriority_queueで…いっつも家を出るのは僕が最後だったんですよね…

しかも、何が面白いってさ、家に他の家族構成員がいると俺が外にでれないんだよねｗｗｗ（ギャハハwwwww

ちょっと待って、俺テンションやばくね？何？

健康管理

大学の課題はやりたくなければやらなければいいってことに気がついたので気が楽です。
最近は布団に入ってyoutubeの動画をただひたすら見てたら１，２時間経ってるってことが多いです。

何した

今日はね、中間試験があったよ。あとは、（今から行くんだけど)大学に行ってフランス語の授業を受けてくるよ。夜は友人と油そばを食べに行くよ。

具体的に

今日解いた問題

AGC002 C-Knot Puzzle

[天才パズル,未証明貪欲,dequeではない,達成可否]

この問題、dequeで端から小さい方を取る。みたいな感じでやると死にます。

L = 8
3 5 2 4 4 1
をかんがえて小さい方から取ると　L(left) RRR となって、5,2が残ります。すると、もうほどけません。でも、4 4 を残してやればほどけます。

これがdequeでやった時死ぬコード。

では、どうすれば良かったか、それは、　a[i] + a[i+1] の最大となる二点を残して上げるのが一番良いです。
これがL以上であれば、絶対に達成出来ます。

a[i] + a[i+1] = K >= L として、そのようなi番目の結び目を最後にほどくことをかんがえます。
まず、最初にほどく結び目は1かN-1番目の結び目で、iでなければどっちでも良いです。

1かN-1番目の結び目をほどきます。
結び目の無くなった0番目（もしくはN-1番目)の紐は、以後かんがえなくて良くて、残りの結び目をほどかなければならない紐を見ます。

この紐は、i番目の結び目をほどかないようにしていたので、当然長さはK以上あります。　よって、まだほどけます。

同様にもう一回i番目以外で端っこの結び目をほどきます。

まだi番目の結び目は結んだままなので、長さはK以上です…

繰り返し。

i番目の結び目だけ残っています。 a[i]+a[i+1] = k >= Lです。
ほどきます。

結び目が全てなくなりました。あなたは自由です。 You are free.

天才のコードをさげておきますね。

int main()
{
    ll n, l;
    cin >> n >> l;
    vector<ll> a(n);
    rep(i, n)cin>>a[i];
    ll M = 0; // a[i] + a[i+1] の最大値
    int index = 0;
    rep(i,n-1){
        // a[i]+a[i+1]が最大となるような結び目iを見つける
        if(chmax(M, a[i]+a[i+1])) index = i;
    }
    if(M < l){
        cout << "Impossible" << endl;
        return 0;
    }
    cout << "Possible" << endl;
    rep(i,index){
        cout << i + 1 << endl;
    }
    for(int i = n - 1; i > index; i--){
        cout << i << endl;
    }
}

ABC075 D-Axis-Parallel Rectangle

[五重ループ,点を含む個数,二次元累積和っぽさ]
AtCoderExpress2この問題にニているものを感じたが、制約で二次元累積和出来ない…ってなった。
解説を見ると、二次元累積和が使えるらしい。(まじか)
採用する長方形の xの左端、右端,yの上端下端を全探索(候補はそれぞれ点の数だけ)。賢いなああああああ・・・・

AGC003 C-BBuBBBlesort!

[天才パズル,偶奇,操作の最小化]

天才とは1%の努力と99%の努力である
まずはこちらのツイートをご覧ください

f:id:niboshi_bisyoujo:20200618173102p:plain

みた？　ソート操作、隣と要素を入れ替える操作って,最大でも要素数-1回のSwapで任意の数列に並び替えることができるっていうのは有名な話だね。

あ、ごめん、これ嘘だ。

仕切り直しってことで仕切りいれとくね

はい、何回要素の反転行っても良いんだって。
まず、Aの偶数番目の要素を取り出して考えると、これは操作2だけで任意の順番に並び替えることが出来ます。
3つの順番を反転とあるが、1つ目と3つ目だけに着目すると、ただこの2つの要素が入れ替わっているだけなため、偶数番目の要素が2つswapされるだけです。
数列はswap操作だけでソート出来るので、偶数番目だけを昇順に並び替えることは操作1を一回も行わずに行うことが出来ます。
奇数番目も同様です。

次に、操作1を行わなければいけない場合をかんがえます。
{2,1,5,4,3}この数列は{1,2,3,4,5}にしたいです。
縦に並べてみます
{2,1,5,4,3}
{1,2,3,4,5}
こうしてみてみると、1は偶数番目(0-indexed)に欲しいのに奇数番目にある、2は奇数番目に欲しいのに偶数番目にある。
これを入れ替えるためには操作1をする必要があります。
つまり、操作1は、偶数番目と奇数番目を入れ替えることが出来る操作。

ちなみに、3と5は同じ偶数番目を入れ替える操作なので、操作2だけで出来ます。

要するに、この問題は、奇数番目になければいけないのに偶数番目にあるもの、偶数番目にあるのに奇数番目になければいけないものの数を数えてあげれば答えが求まります。

ちなみに、ちょっと考えれば分かりますが（僕はわからないけど）、偶数番目になきゃいけないのに奇数番目にあるものと、奇数番目になきゃいけないのにぐうす番目にある物の数は等しいので、どちらを数えて出力してもいいです。

並び替えのイメージは、操作2を行うことで、偶数番目と奇数番目が狂ってるやつを隣に持ってきます。隣に持ってきたら操作1で其の2つの位置を入れ替えることで、偶数番目になきゃいけないやつを偶数番目に持ってきます。

先程ちらっと言いましたが、偶数番目になきゃいけないのに奇数番目にあるものの個数と、奇数番目になきゃいけないのに偶数番目にあるものの個数は一緒だから、ある1個だけ偶数番目になきゃいけないのに奇数番目にあって、他は正しいってことにはなりません。

ABC144 E-Gluttony

[二分探索のプロ,内積の最小化]

最初、i番目の人が食べ終わってからi+1番目の人が食べ始めるものだと思って勘違いしていました。
蟻本の中級序盤ぐらいに書いてあったような気がするのですが、内積の最小化って知ってますか、 a[i] * f[i] の和を最小化したいときには、aを昇順、fを降順にしてかけ合わせたものを足せばいいってやつ。
ソレだと思って解いてました。そしたらWA,なるほどね、f[i] * a[i] の最大を最小化すればいいのね。(最大の最小ってそれSmart Infantsじゃん)

でも違った。さて手詰まりだ、どうしよう。俺は何も出来ない。何者にもなれない（お前らと一緒で)

だが違う、僕はなんにでもなれる。そうだ。考えるんだ。諦めるな。

ひらめいた。 伝家の宝刀二分探索!!! a[i] * f[i] をある値に出来るかを計算するコストはO(N)。 a[i] * f[i] であり得る値は最大でも10¹²　、log(10¹²) は40ぐらい、これなら行けるぞ。

まず、前提として、数列aとfがあって、a[i] * f[i] の最大を最小にしようってしたとき、aは昇順、fは降順（逆でもいい）っていうのは使えそうだ。
ちなみにこれは、a[i]に修行させた時、減るコストはf[i]なので、f[i]が大きいものに大して修行させたときのありがたみがでかいよね。的なかんがえ（あとで解説読む)

それで、a[i] * f[i] の最大値をMに出来るかっていう時、其の判定をどうするかをかんがえます
先程これはO(N)で出来ると言いましたね？
どういうことかと言うと、各iについてa[i] * f[i] = Mにするための修行回数を数えます。このとき、(iの修行した後の消化コスト) * f[i] が Mを下回るとき、其の値はMを下回る（＝もおっけ)最大のf[i]の倍数です。
よって、iが修行する回数は max(0,a[i] - M / f[i])として求められます。
例えば、a[i] = 3, f[i] = 9 のとき、M = 15を目指すとすると、修行する回数はmax(0, ai - M(15) / fi) = max(0, 3-1) = max(0,2) = 2となって、二回修行すればいい。
これをN人全員見てあげて、必要な修行回数がK以下だったら、Mは達成可能ということになります。よって、Mが達成可能化はO(N)で判別出来ることが分かりました（やったね)

ってことで天才のコードを見てくれ

int main()
{
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n), f(n);
    rep(i,n) cin >> a[i];
    rep(i,n) cin >> f[i];

    sort(a.begin(),a.end()); //消化コストを昇順
    sort(f.rbegin(),f.rend()); // 食べにくさを降順にソートした

    ll ng = -1, ok = 1e13;
    while(ok - ng > 1){
        ll mid = ok + ng; mid /= 2;
        ll count = 0;
        rep(i,n){
            // midを下回るまで修行する
            ll ob = mid / f[i]; //obは、midを達成できるときの消化コストの値
            count += max(0ll, a[i] - ob);
        }
        if(count <= k) ok = mid;
        else ng = mid;
    }
    cout << ok << endl;
}

CODE FESTIVAL 2016 Final C-Interpretation

[通訳,UnionFind,集合の管理]

Aが言語(1,2,3)を話せる、みたいなのをA(1,2,3)と表記して、AとBがコミュニケーションを取れるとき、 A(1,2,3) - B(2,3,4)みたいに書きます。

A(1) - B(1,2,3) -C(3,4)- D(4)
このようなとき、４人は全ての人とコミュニケーション可能です。
AとDがコミュニケーションを取れることについて説明します。

Bは言語3を話せる、Cは言語3を話せるので、B(1,2,3)-C(3,4)
Cは言語4を話せる、Dは言語4を話せるので,C(3,4) - D(4)
ある人Cが存在して,BとDの二人ともがCおコミュニケーションを取ることが出来る。
よって、BとDがコミュニケーションを取れる。次に、
AとBは共通して言語1を話せるのでA(1) - B(1,2,3)
ある人Bが存在して、AとDの二人共がBとコミュニケーションを取ることが出来るよってAとDもコミュニケーションを取れる。

これは、友達の友達は友達理論です。
A-BでB-Dなとき、BとDは共通して喋れる言語が無いからA-Dにはならないんじゃないか〜って思っちゃうけど、A-Dな条件はA - hoge - D でhogeがAもDも喋れる言語を持っていることではなくて、コミュニケーションを取れるかどうかなので、条件がゆるくなるイメージを感じますね（僕はそんなイメージを持った)

ところで、今回の問題では重要ではありませんが、現実世界では共通する言語を話してもコミュニケーションが取れるとは限りませんね

さて、本文はUnionFinで解けますね。
A(1) - B(1,2,3)のとき、Cがなんの言語を喋れたらAともBともコミュニケーションを取れるでしょうか。

答えは、1,2,3のいずれかを話せれば良い、です。
Cが3を話せるとき、Bを媒介してAとコミュニケーションを取ることが出来ます。
さらに言うと、一度コミュニケーションが取れるようになってしまった集合に対しては、Aは1を話せて、Bは1,2,3を話せる、などと区別しなくて良い。

これは今思いついた表現なんだけど、Aが1を話せる、Bが1,2,3を話せるではなくて、 AとBがいるグループaが言語1,2,3を話せる。と解釈すると楽そうです。
そうしてやると、Cは、グループaと共通する言語を持っていればグループaにいる人間と話せる。と捉えれるようになります。

さらにここで、C(3,4,6)である時、グループaは言語1,2,3,4,6の5つを話せるようになります。

以上は僕の気持ちです、受け取ってください。
次に解法、 1. 各i人目について,Ki個の言語Li1,Li2, ... , LiKiをユニオンファインドで合併する.

0人目が話せる言語をXとする
各i人について、iが話せる言語を一つ持ってきて、Xとiが同じ集合にあれば,とりあえずok
Xとiが同じ集合になければNOを出力して終わり。
とりあえずokがN人全員について言えたらYES

int main()
    int n, m;
    cin >> n >> m;
    vector<int> K(n);
    vector<int> L(n); // それぞれが喋れる言語を一人一つだけ保持しておく。
    UnionFind uf(m+1); // 言語をUnionfind
    rep(i,n){
        int k;
        cin >> k;
        K[i] = k;
        rep(j,k){
            int lan;
            cin >> lan;
            if(j==0){
                L[i] = lan; //iは言語lanを喋れる。(保持しておく)
            } else {
                uf.unite(L[i],lan);
            }
        }
    }
    rep(i,n){
        if(uf.same(L[0],L[i])){ // iが0と繋がってるか。
        } else {
            // i と 0が繋がってなければダメ
            puts("NO");
            return 0;
        }
    }
    puts("YES");
}

ARC090 D- People on a Line

[有向重み付きグラフ,矛盾判定]

難しいですね。(何をコメントしたらいいかわからない)
とりあえず、数式で繋がっている頂点（人の位置)は相互に関係しているので、一つ決めた時もう一つも決まる。そこから派生してもう一つも決まる。みたいなのはグラフで管理していけばいいみたいです。
A - B間の距離が3の時,Aから右に3行けばB、とともに、Bから左に3行けばA、っていう辺を2つ作ります。
これでうまく行くっぽいです、難しいですね。とりあえず人の写経コード貼っときます（こら)

struct edge {
    int to;
    long long cost;
};

vector<edge> G[100'100];

void bfs(int N, int v, vector<bool> &used, vector<long long> &dist, bool &good, long long cost){
    if (used[v]){
        if(dist[v] != cost) good = false;
    } else {
        used[v] = true;
        dist[v] = cost;
        for (int i = 0; i < G[v].size(); i++) bfs(N, G[v][i].to, used, dist, good, cost+G[v][i].cost);
    }
}
int main()
{
    int N, M;
    cin >> N >> M;

    for (int i = 0; i < M;i ++){
        int L, R, D;
        cin >> L >> R >> D;
        L--, R--;
        G[L].push_back((edge) {R,D});
        G[R].push_back((edge) {L,-D});
    }

    vector<bool> used(N, false);
    vector<long long> dist(N, -1);
    dist[0] = 0;
    bool good = true;

    for(int i = 0; i < N; i++){
        if(!used[i]){
            dist[i] = 0;
            bfs(N, i, used, dist, good, 0LL);
        }
    }
    if(good) cout << "Yes" << endl;
    else cout << "No" << endl;
}

コード野やってる事自体は明確でわかりやすいですね、流石です。

ABC040 C-柱柱柱柱柱

[動的計画法]

動的計画法の初級っぽい問題(バグらせたけど)
i本目の柱へ行くコストを最小化しながら更新していけばいい。綺麗なコードが書きたいな

ABC036 C-座圧

[ソート,連想配列]

実装頑張れの問題。
まず、aを昇順に整列したものが手に入れば、各値をどうしたいかが分かる。aを整列したとき一番小さいものが0,2番目が1ってなる。

よって、各値が何になってほしいかを連想配列で管理してやれば良い。

ABC035 C-オセロ

[優先度付きqueue,ノリと根性]

L~Rの区間をヒックリ返しますよ〜ってとき、何回ひっくり返している。っていうのを保持しておいて、で、Rを過ぎたら其の回数を減らす。。。みたいなことを…

int main()
{
    int n, q;
    cin >> n >> q;
    priority_queue<int, vector<int>, greater<int>> get; // Lを保持
    priority_queue<int, vector<int>, greater<int>> ret; // Rを保持
    rep(i,q){
        int l, r;
        cin >> l >> r;
        get.push(l);
        ret.push(r);
    }

    ll time = 0;
    rep(i,n){
        while(get.size() && get.top() == i+1){
            get.pop();
            time++;
        }
        if(time %2 == 0){
            cout << 0;
        } else {
            cout << 1;
        }
        while(ret.size() && ret.top() == i+1){
            ret.pop();
            time--;
        }
    }
    cout << endl;
}

Lが来るたびに何回ひっくり返してるかを+1して、Rをすぎるたびに-1する。

爆弾でモンスター倒すやつ。みたいな考え方を使って解きました。
あ、これ、配列でも解けるな。
気合で。あ、これ配列使ってやるのいもす法って言うらしい。（ってかそもそもpriority_queueも配列を使っているのでは) ちょっと実装してみるか.

int main()
{
    int n, q;
    cin >> n >> q;
    vector<int> plu(n,0);
    vector<int> diff(n,0);
    rep(i,q){
        int l, r;
        cin >> l >> r;
        --l, --r;
        plu[l]++;
        diff[r]++;
    }

    int count = 0;
    rep(i,n){
        count += plu[i];
        if(count % 2 == 0){
            cout << 0;
        } else {
            cout << 1;
        }
        count -= diff[i];
    }
    cout << endl;
}

出来た〜わ〜いわ〜い

ABC030 C-飛行機乗り

[うなぎってなんだよ,priority_queue]

N,Mが10⁵程度なので、2 * 10⁵ 回、それぞれ採用するかどうか見るぐらいなら余裕で間に合います。
どれぐらい余裕かって言うと、生まれたての子鹿を片手で捻り潰すぐらいには余裕です（こら)

飛行機に乗っている時間っていうのは短いので、乗れるなら速いうちに乗ったほうが良いよね。
だから、空港Aから乗れる一番速いのに乗る,空港Bにつく。Bから乗れる速いのに乗る。
(速いじゃなくて早いなんだけどね)
っていうのを実装してやれば行けるね。

提出コード
さすがに今日のブログの文量がえぐたぷにきあ君なのでURLだけ貼っておくね。

あとがき

以下は毎回記事に貼っているテンプレート

基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます - 瑞々しぃにぼしの自己紹介(自己紹介の記事です)

草体にぼ日記

だらだらと

2020年6月19日　日記