ひらめの日常

プログラミングと読書と

ABC134-E Sequence Decomposing (500)

Sequence Decomposing

問題はこちら atcoder.jp

問題文は次のように言い換えることができる。すなわち、「数列  A が与えられた時に、その数列を狭義単調増加部分列に分ける。その分け方の最小値を求めなさい」という問題と同値になる。

考え方

sample1について、配列をイテレートする時の様子は以下のようになる。

具体的には、現在有効な部分列の右端(=最大の値)を保持する集合  S を持っておく。各要素  A_i を見た時に、 A _ i > s_j となるものが  S の中に存在するならば、 s _ j = A_i と更新する(以下の図で見ると、赤丸のものが  S に含まれるものになる)。

f:id:thescript1210:20190721071519j:plain
sample1

なお、更新できるものが複数あるときは、貪欲になるべく大きい値を更新するとよい。なぜなら、小さい値を残しておいたほうが、後々に更新可能な値の範囲が広がるためである。

解答

実装方法には、multisetを使った解法、dequeを使った解法、vectorを使った解法があるのでそれぞれの実装とその注意点を見ていく。

1. multisetを使う

今回は同じ値が複数個  A に含まれる可能性があるので、 multisetを使う。multisetに入っているものの中から、lower_boundを使って  A_i 以上の場所を取得。その一個前が  A_i 以下で最大の値になるので、それを更新する。

注意点としては以下の通り。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

/* ------------- ANSWER ------------- */
/* ---------------------------------- */

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

    for (ll i = 0; i < n; ++i) {
        ll now = a[i];
        auto itr = s.lower_bound(now);
        if (itr != s.begin()) s.erase(--itr);
        s.insert(now);
    }
    cout << s.size() << endl;
    return 0;
}

Submission #6482597 - AtCoder Beginner Contest 134

2. dequeを使う

 A_i が集合に入っているもの全てより小さい値の時、配列の先頭に追加する」という操作をしたい。また、それとは別にランダムアクセスをして更新作業もできるようにしたい。dequeはこれを満たしてくれる。

dequeとはdouble-ended-queueの略で、末尾と先頭への要素追加・削除が  O(1) で行える。さらにindexを指定してのランダムアクセスも  O(1) で行える。 C++ 両端キュー std::deque 入門

やっていることはmultisetの時と基本的に同じだが、注意点としては以下の通り。

  • dequeはランダムアクセスはできるが、連続したメモリ領域を確保するとは限らない。なので、イテレーターをデクリメントして値を参照するのではなく、一回indexに直してから値を更新する必要がある。

  • 常にsort済みであるようにdequeに入れていくので、lower_boundが使える。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

/* ------------- ANSWER ------------- */
/* ---------------------------------- */

int main() {
    ll n;
    cin >> n;
    vector<ll> a(n);

    rep(i, n) cin >> a[i];

    deque<ll> dq;
    rep(i, n) {
        ll idx = lower_bound(dq.begin(), dq.end(), a[i]) - dq.begin();
        if (idx == 0) dq.push_front(a[i]);
        else dq[idx - 1] = a[i];
    }
    cout << dq.size() << endl;
    return 0;
}

Submission #6482641 - AtCoder Beginner Contest 134

3. vectorを使う

2の時に、先頭に追加することを考えたため、vectorでは不適となった。しかし、値を降順に保持しておいて、末尾に追加することを行えばvectorでも実現が可能。

そもそも先ほどまで昇順にこだわっていたのは、lower_boundなどを使って高速に更新する値を求めたいからであったので、高順の時にも lower_boundが使えれば良い...(実は使える!!!)。

これもやっていることは他の手法と同じ。注意点としては以下の通り。

  • 降順にsortされたvectorに対しては、lower_bound(v.rbegin(), v.rend(), x) とすることで既存ライブラリを使って二分探索ができる。これで得られる reverse_iteretorはrbegin()からrend()の方へインクリメントしていく形になる。

  • アドレスの比較は、全て reverse_iteretor同士で行うこと。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

/* ------------- ANSWER ------------- */
/* ---------------------------------- */

int main() {

    ll n;
    cin >> n;
    vector<ll> a(n);

    rep(i, n) cin >> a[i];
    vector<ll> d;

    rep(i, n) {
        auto itr = lower_bound(d.rbegin(), d.rend(), a[i]);
        if (itr == d.rbegin()) {
            d.emplace_back(a[i]);
        } else {
            itr--;
            *itr = a[i];
        }
    }
    cout << d.size() << endl;
    return 0;
}

Submission #6482661 - AtCoder Beginner Contest 134

就活を終えました

はじめに

この記事は僕の就活体験記です。新卒の就活体験記をいくつか参考にさせていただいたので、僕も誰かの役に立てばいいなと思い書きました。結論から言うと、インターン先の教育系ベンチャーに行くのですが、ちゃんと就活をしたので残しておきます。

使った内容としては競プロとそれ以外が半々くらいの就活だったと思います。時期的には、2月頃から就活を始めて7月に終わった形になります。

どんな人?

勉強

工学部の情報系?みたいな学科の4年生です。途中からコンピュータサイエンスに興味が湧いてきたので、他学部や他学科の授業をたくさん取りに行きました。就活の段階では研究室配属が決まるくらいの時期だったので、就活中に研究については話していません。

競技プログラミング

段違いに強いというわけではないですが、最初は茶色適正だったので個人的には割と1年間、楽しみながら頑張っていました。レートは水色で、AtCoderの上位15%くらいです。就活中に緑色から水色になりました。

hiramekun - AtCoder

f:id:thescript1210:20190720031541p:plain:w500
レート

レートに関してはこちらを見るとどの程度かイメージしやすいと思います。

chokudai.hatenablog.com

就業経験

Android開発

1年間休学して、ベンチャーAndroid用のSNSアプリ開発をしていました。プログラミング経験がほぼ0かつ、いきなりのチーム開発を始めたのでかなり大変でした。ソフトウェア工学の基礎的なところを学んだり、チーム開発する上でのコードのお作法や設計思想などをたくさん勉強しました。

Java/KotlinでGithubを使ってチーム開発をしたり、アーキテクチャを考えたりしました。

ここで情報工学の基礎的な部分を大学で勉強し直したいという思いが強くなり、復学後に勉強を頑張るきっかけになりました。

物体検出

深層学習に興味を持ったので、半年弱のバイトでも物体検出の実装をしました。とは言っても、Chainerを使って自分が用意した新しいデータセットに対してモデルを再学習するだけなので、実装の中では割と簡単な部類に入るかもしれません。

音声認識

1年ほどR&Dチームでインターンをしました。そこはでMySQL叩いて簡単なデータ分析もしていましたが、主に音声認識をやりました。C言語で書かれたOSSの実装を追って、認識ロジックを実装してモバイル開発チームにライブラリとして提供したりしました。

機械学習アルゴリズム的な側面はもちろん、論文を読んで参考になる研究がないか調べたり、その論文を実装にどのようにして落とし込むのかを考え、上司から自分の考えに対してフィードバックがもらえる環境はとても刺激的で楽しかったです。

戦略

自分の経験を話す必要がある際は、上記のステータスを踏まえて以下のようなものを中心に話しました。割と会社や面接官によって、突っ込んで聞かれるところが異なったように思います。

  • インターンなどでチーム開発を経験したり、プロダクションのコードをたくさん書いてきた。
  • 競技プログラミングで計算量やメモリ量を意識したコードが書けるようになった。
  • 企業での研究開発を長めにやってきた。
  • 情報工学のレイヤー低いところや統計の理論的な面の勉強も頑張った。

自分のアウトプットとしては、ブログとAtCoderのユーザーページとGithubあたりを見せてました。 例えばGithubには授業などでやった機械学習系の授業のコードをまとめてあったりします(多分コードは汚いけどREADMEだけ整えた)。 github.com

あとはやりたいこととか、やりたい事業についての思いをきちんと言語化することくらいでしょうか。

体験記

割と多かったので、他にも内定やお祈りはいただきましたが適当に抜粋して書きます。別にここに書いてないから適当な気持ちで受けたとかそう言うわけではないです(念のため)。

最終的に今インターンをしている会社に行く意思決定をしたので、実はここに実際行く会社が載ってません(あれれ)。

a社

逆求人→面接→面接→辞退

AtCoderでもコンテストを開いていたりして、面白いアルゴリズムを扱っており面白そうだったので選考を受けました。二回面接をしていますが、雑談のような形で話しやすい雰囲気でした。人事の方や技術職の方も丁寧に進路について向き合ってくれているのを感じましたし、やってる内容もチャレンジングでとても面白いと感じました。

正式に内定というものをいただく前に意思決定をして辞退しました。

b社

逆求人→技術テスト→技術面接*2→(落ちて別チームの選考へ)→技術テスト→面接→面接*2→お祈り

正直逆求人に行くまでは名前も知らなかったのですが、大企業のグループ会社でありながらシリコンバレー気質な社風と、自動運転の研究開発という分野が非常に面白そうだったので選考を受けました。「学部生でも実力があれば全然いける」というお話も聞いたのも後押しになりました。

最初のチームでの面接は、割とテクニカルな部分を聞かれ、それに加えて一人とホワイトボードプログラミング、もう一人とシステムデザインをしました。システムデザインが英語かつGoogleハングアウトでホワイトボードもろくに使えずボロボロでした。そのあとに「他のチームが興味を持っている」という連絡があり、再びコーディングテストと面接を受けて落ちました。

落ちた理由が「修士進んでいないこともあり〜」と言われたのにはちょっと首を傾げましたが、そのように落ちた理由も教えてくださり、メールの返信も早くて終始真摯な印象を受けました。

c社

Paiza→面接→技術テスト→面接→最終面接→最終面接(2回目)→内定

会計ソフトを扱っている会社。会社の文化が好きだったので選考を受けました。テクニカルな質問はほとんどなかったように感じます。向こうがこちらに不安な部分があったらしく、最終面接の二回目が通知された時はびっくりしました。

内定後は、自分の行きたいポジションの人と面談をアレンジしてくれたりと、意思決定のための判断材料を用意してくれました。

内定をいただいた後に他の選考結果を待っていただけないか何回か相談しましたが、あちらの事情もあり、どうしても一ヶ月以上は伸ばせないとのことだったので残念ながらお断りしました。

d社

書類→技術テスト→電話面接→技術面接*4→お祈り

有名な検索エンジン作ってるところです。緑コーダーで入った方がいるという記事を目にして、自分もチャレンジしてみたいと思い選考を受けました。オンラインでの技術テストは日頃の競プロに比べたら簡単だった気がします。電話面接、技術面接に向けては割と対策してから臨みました。

話題のお昼ご飯を食べたいなと思ってましたが、午後からになってしまいました(残念...!)。技術面接はホワイトボードプログラミングでしたが、面接官4人中2人とは英語でやりとりしました。解けなかった問題もあったので、手応えはあまり良くなく、帰りの電車で自分の解答のミスに気づいて落ち込んでた覚えがあります。

ただ、受けた感想としてはレートが低くても全然チャレンジする意義はあると思ったし、自分との距離が少し掴めた気がして受けてよかったなと思いました。

e社

書類→技術テスト→英語テスト→適性検査→技術面接→お祈り

求人サイトをやってるところです。普通に待遇が良かったのと、youtubeで働いてる様子とかみて、純粋に働いてみたい!と思ったので選考を受けました。

オンラインでの技術テストは自分にとって難しかったですがAtCoder力と気合いで通しました。面接ではホワイトボードプログラミングを英語でやりました。英語は割と話せました。開始20分間違った方向で回答を書いていて、気づいて修正しましたがタイムロスが多かったので、向こうが用意していた最後まで到達できなかったのかなと思ってたら案の定落ちました。

面接官の人がとってもフレンドリーでいい人でした。(ちょっと眠いかもって言ったら、一緒にカフェテリアでコーヒーを淹れに連れて行ってくれたりしました。)

f社

書類→面接→面接→面接→面接→辞退

ゲーム作ってたりAI事業に力入れてたりしてるメガベンチャーです。単純に技術的に強くなれそうだなーって思って受けました。基本的にはどんなことをどうやって頑張ってきたかということにフォーカスされてました。が、Androidアプリをどんな構成で作ってどんなところを工夫したか、とか、競技プログラミングをなぜやっていてどんなことを学んだか、とかは聞かれました。

最終面接前に自分の意思が固まったので辞退しましたが、開発の進め方だったりとか、平均的な技術レベルの高さとか、素敵な会社だなと思いました。

感想とか

院進か就職か?

僕はてっきり院進すると思ってました。分野としては教育情報学をやりたくて、かなり前から院試についての情報を調べていたりしました。

hiramekun.hatenablog.com

hiramekun.hatenablog.com

2月頃に関連する研究室を見学をして、ちょっと自分のイメージと違うな...となりました。やはり自分がやりたいのは社会実装的な側面で、現存する問題を研究や実装によって早いサイクルで解決できるのは企業なんじゃないかと。かなり工学的思想が強いねとも言われて、確かにそうかもと思いました。(コンピュータサイエンスとかの勉強もとっても好きなのですが、大学で何か自分の好きな研究をしようというまでの熱意はありませんでした。)

就活の軸について

最初は自己分析とか正直やらなくてもいいと思ってました。ですが結局自分が意思決定をするときに、何かしらの軸で決めなければいけないので、ここを明確にしておくことは面接だけのためではなく、自分のためにも大事だと感じました。

  1. 興味のある事業をやっているか?
  2. 技術的に強くなれそうか?
  3. 文化が自分に合っていそうか?

このそれぞれの軸の優先順位をはっきりさせるところに時間がかかりました(半年くらい…)が、最終的には自分のやりたい教育という分野に新卒から関わりたい思いを最優先して意思決定をすることにしました。

あと、技術的に強くなれそうか?という点については、割と自分のすぐ近く(メンターとか)が優秀な人か?という尺度がとても重要だと思いました。「新卒ではベンチャーに行くよりもメガベンチャーに行った方が、伸び伸びと自分の実力をつけることができるかなー」と思っていましたが、先ほどの観点を重視して「会社の規模よりは近くで働く人たち」を大事にしようと決めました。

競プロは役に立つか

よく話題になりますね。正直自分の場合は、競プロをしていなかったら受けた会社の半分以上で面接まで行けなかったと思います。それほどまでに自分はアルゴリズムが苦手でした。就活のために競プロを始めたのではないのですが、こんなに自分の役に立つと思ってませんでした。

その一方で、日本企業の多くの面接ではアルゴリズムの能力よりも、「インターンや何かアプリを作った経験」とか、「その人がどんな人であるか」にスポットを当てることが多かったです。その人を表す指標の一つとして、なぜ競技プログラミングに出ているのか、どの辺が好きなのか、などはたまに聞かれました(が、他の経験についての方が深く聞かれました)。

自分のツイートを見返すと、会社によって反応が違うのがわかって面白いですね。緑〜水色はコードテストは割と通過するけど、面接でメインに据えるにしては会社によって関心度が違いすぎるなあと感じました。

就活する意味

まず、本当に行きたい会社を選ぶプロセスが大事だと思いました。僕は目の前に選択肢が出てきて、究極的に選択を迫られないと、本当の自分の気持ちに気づけませんでした。そういった意味で、最終的にはインターン先を選んだわけですが、就活をして本当に良かったと思います。

これもありますね。

調べるだけではわからない、面接で話してみてようやく掴めることもあるなあと感じたからです

競プロ純粋培養水コーダーでも就職したい! - はるらるら

あと、とても有名な企業と自分の距離感をつかむことができました。正直競プロをするまで、自分には程遠い世界だと思っていましたが、実際に受けてみると「思っていたよりも身近な世界なのではないか?」と思えました。自分の知らなかった世界を少しだけ垣間見れた気がして、楽しい経験になりました(落ちましたが...)。

最後に

長い文章でしたがありがとうございました、質問とかあればなんでもDMとかで聞いてください。 しんどい時もありましたが、総じて見るとたくさんコードテストを受けたり、いろんな業界を観れて楽しかったです。

来年からはインターン先のベンチャーで働きます。最終的にいい意思決定ができたと思うので、社会人になるのも楽しみです。

ABC040-D 道路の老朽化対策について (500)

道路の老朽化対策について

タイトルだけ見ると政策の説明みたいだけど、競技プログラミングの問題。

問題はこちら。 atcoder.jp

都市をつなぐ道路が与えられるので、都市を頂点、道路を辺としてみたグラフを考えることにする。

Unionfindを使ってクエリごとに構築して、大きさを調べようと思ったが、これだとTLEするので工夫が求められる。

考え方

1クエリごとに木を再構築していると、 O(QM) かかるので間に合わない。そこで、クエリを先に読んでおいて、 wが大きい順にクエリを処理する。こうすることで、既に存在する木に新たに条件を満たす辺を加えていくだけでよくなる。

計算量は、各辺を見る回数が高々1回なので、操作回数が O(Q + M)になる。

解答

答えを出力するときには元の順番で出力しなければいけないので、クエリのindexを保持しておく必要がある。

また、sortがしやすくなるようにpairの順番を指定している。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

/* ------------- ANSWER ------------- */
/* ---------------------------------- */
class UnionFind {
private:
    vector<ll> size; // グループに属する物の数.
public:
    vector<ll> par; // 親
    vector<ll> rank; // 木の深さ

    explicit UnionFind(unsigned int n) {
        par.resize(n);
        rank.resize(n);
        size.resize(n);
        rep(i, n) {
            par[i] = i;
            rank[i] = 0;
            size[i] = 1;
        }
    }

    // 木の根を求める
    ll find(ll x) {
        if (par[x] == x) {
            return x;
        } else {
            return par[x] = find(par[x]);
        }
    }

    // グループのサイズを求める.
    ll calc_size(ll x) {
        return size[find(x)];
    }

    // xとyの属する集合を併合
    void unite(ll x, ll y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (rank[x] < rank[y]) {
            par[x] = y;
        } else {
            par[y] = x;
            if (rank[x] == rank[y])rank[x]++;
        }
        size[x] = size[y] = size[x] + size[y];
    }

    // xとyが同じ集合に属するか否か
    bool is_same(ll x, ll y) {
        return find(x) == find(y);
    }
};


int main() {
    ll n, m;
    cin >> n >> m;
    // yab[i].first: y
    // yab[i].second.first: a
    // yab[i].second.second: b
    priority_queue<pair<ll, pair<ll, ll>>> yab;
    rep(i, m) {
        ll a, b, y;
        cin >> a >> b >> y;
        a--, b--;
        yab.push({y, {a, b}});
    }

    ll q;
    cin >> q;
    // wvi[i].first.first: w
    // wvi[i].first.second: v
    // wvi[i].second: index
    vector<pair<pair<ll, ll>, ll>> wvi(q);
    rep(i, q) {
        ll v, w;
        cin >> v >> w;
        v--;
        wvi[i] = {{w, v}, i};
    }
    sort(wvi.begin(), wvi.end(), greater<>());

    UnionFind uf(n);

    vector<ll> ans(q);
    rep(i, q) {
        while (!yab.empty() && yab.top().first > wvi[i].first.first) {
            pair<ll, ll> ab = yab.top().second;
            uf.unite(ab.first, ab.second);
            yab.pop();
        }
        ans[wvi[i].second] = uf.calc_size(wvi[i].first.second);
    }
    rep(i, q) cout << ans[i] << endl;
    return 0;
}

Submission #6310485 - AtCoder Beginner Contest 040

ABC127-E Cell Distance (500)

Cell Distance

問題はこちら atcoder.jp

数式があるので、それを文章にする。

NM 列のマス目のうち、K マスに駒をおく。このコストは全ての駒のペアのx座標の差 + y座標の差の和で計算される。これを全ての配置について和を取りなさい。」

考え方

愚直にやると、以下のようになり到底間に合わない。

  1. 全てのペアについて距離の合計を求める:O((NM)^{2})
  2. 全ての配置について試す: O(_ {NM} \mathrm{C} _ {K})(指数時間)

よって、それぞれについて高速化が必要である。

step1 - 和の計算の分解

 \sum _ {i=1}^{K-1} \sum _ {j=i+1}^{K}\left(\left|x _ {i}-x _ {j}\right|+\left|y _ {i}-y _ {j}\right|\right) について、xyは分解して考えることができる。

 \sum _ {i=1}^{K-1} \sum _ {j=i+1}^{K}\left|x _ {i}-x _ {j}\right| + \sum _ {i=1}^{K-1} \sum _ {j=i+1}^{K}\left|y _ {i}-y _ {j}\right|

よって、 x座標についてのコストの総和を計算し、同様にして y座標のコスト総和を計算し、それぞれを足すことで答えを得ることができる。これからはx座標のコストのみを考えていくことにする。

step2 - 計算式の整理

2点間の距離 dを固定して考えてみる。 すると、「考え方」で述べた二つの過程は次のように言い換えることができる。

  1. 全てのペアについて距離の合計を求める -> 距離 d となるようなペアの個数
  2. 全ての配置について試す -> そのペアが使われるような配置の場合の数
  3. 上記を全ての距離について試す。

step3 - 距離dとなるようなペアの個数

距離 dとなるようなペアの個数は、以下のようにして求めることができる。

まず、距離 dとなるような列の取り方が、 (M - d) 通り。そして、各列においてどの行の座標を使うかの組み合わせが N^{2} 通り。以上より、 (M - d) N^{2} 通り。

step4 - そのペアが使われるような配置の場合の数

 NM 個の座標のうち、そのペア以外の  (NM - 2) 個の候補から、座標を  (K - 2) 個えらぶような場合の数なので、 _ {NM - 2} \mathrm{C} _ {K - 2} 通り。

step 5 - 全ての距離について計算する。

疑似言語で書くとこんな感じになる。

int sumx = 0
for d in 0 to M-1:
  sumx += d * (M - d) * N * N

sumx *= combination(N * M - 2,  K  - 2)

...
同様にしてN, Mを入れ替えてsumyも計算する
...
print(sumx + sumy)

解答

modを取ったり、combinationでmodの逆元をとることなどを忘れないようにする。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll mod = 1000000007;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

/* ------------- ANSWER ------------- */
/* ---------------------------------- */


const int MAX = 510000;
long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++) {
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}

// 二項係数計算
ll COM(int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}

int main() {

    ll n, m, k;
    cin >> n >> m >> k;
    COMinit();

    // sum for x
    ll sum_x = 0;
    rep(i, m) sum_x += i * (m - i) * n * n;
    sum_x %= mod;
    sum_x *= COM(n * m - 2, k - 2);
    sum_x %= mod;

    // sum for y
    ll sum_y = 0;
    rep(i, n) sum_y += i * (n - i) * m * m;
    sum_y %= mod;
    sum_y *= COM(n * m - 2, k - 2);
    sum_y %= mod;

    cout << (sum_y + sum_x) % mod << endl;
    return 0;
}

Submission #6260827 - AtCoder Beginner Contest 127

ABC131-F Must Be Rectangular! (600)

Must Be Rectangular!

問題はこちら

atcoder.jp

考え方

解説放送が一番わかりやすいと思うので、そちらを見ると良い。

www.youtube.com

座標を二部グラフで捉えるという考え方は典型らしい。

下記の座標を、x座標とy座標をそれぞれ頂点としてもつ二部グラフで考えてみると、長さ3のpathが存在する場合は、その始点と終点を結ぶことで新たな頂点が追加されることになる。

f:id:thescript1210:20190628082017j:plain:w300
座標
f:id:thescript1210:20190628082030j:plain:w300
二部グラフ

また、連結成分に関しては、その部分が完全二部グラフになるまで辺を追加することができる。これは長さが3より大きいところに関しては長さ3になるようにpathを調整することで新たに辺を追加することが可能になるから。

完全二部グラフを作るための辺の数は、それぞれのグループに属する頂点数を掛け算すれば良い。答えは新たに張ることのできる辺の数なので、答えは以下のようになる。

連結成分のx座標の個数 * 連結成分のy座標の個数 - もともと存在していた辺の数n

解答

解説放送を聞いて実装上のテクニック

  • 二部グラフの表現の方法。x座標: xy座標: y + MAXV とすることでいつものグラフ構造を用いながら、二部グラフを表現することができる。
  • 連結成分の数の保持の方法。大きさ2のvectorを用意し、cnt[e / MAXV]++ とすることで、今見ている頂点がx座標に属するかかy座標に属するかを場合分けしている。

抜粋部分

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define each(i, mp) for(auto& i:mp)

const ll MAXV = 1e5 + 5;
vector<ll> xy[MAXV * 2];
vector<ll> cnt;
bool visited[MAXV * 2];

void dfs(ll now) {
    visited[now] = true;
    each(e, xy[now]) {
        if (visited[e]) continue;
        cnt[e / MAXV]++;
        dfs(e);
    }
}

int main() {
    ll n;
    cin >> n;
    rep(i, n) {
        ll x, y;
        cin >> x >> y;
        xy[x].emplace_back(y + MAXV);
        xy[y + MAXV].emplace_back(x);
    }
    ll ans = 0;
    rep(i, MAXV * 2) {
        if (visited[i]) continue;
        cnt = vector<ll>(2);
        cnt[i / MAXV]++;
        dfs(i);
        ans += cnt[0] * cnt[1];
    }
    cout << ans - n << endl;
    return 0;
}

Submission #6142912 - AtCoder Beginner Contest 131

ABC128-E Roadwork (500)

Roadwork

問題はこちら

atcoder.jp

考え方

まずは、 d_j に出発した人がどのような条件を満たした時に  x_i の地点で通行止に引っかかるかを考えてみる。すると、1秒ごとに1進むので、以下の条件を満たしているときに通行止に引っかかるということが分かる。

  •  s_i - x_i \leq d_j \lt t_i - x_i

これを愚直にやると、 N 箇所の通行止について、 Q 人の出発時間を調べるので  N \times Q のオーダーになり制限時間に間に合わない。

そこで、 各々の通行止区間について、そこで止まるものを取り除く という風に考えてみる。具体的には、一番手前で止まった場合はもうそれ以降の区間について考える必要がないので、調べる集合から取り除くことができるという考え。

なぜこれを行うと間に合うのか?

  • setでスタート時間  d_1, ..., d_j, ..., d_Q を管理する。
  • まず通行止区間を全て調べるので、ここに  O(N)
  • 各通行止区間について、 s_i - x_i \leq d_j となるような  d_jlower_bound で見つける。ここに  O(log(Q))
  •  d_j \lt t_i - x_i となっている限り、set からスタート時間を削除し、 d_j にスタートした人の答えは  x_i となる。ここは最大でも Q 回までしか回ることはない。要素の削除には  O(log(Q))

以上より、合計の計算量は  Nlog(Q) + Qlog(Q) = (N+Q)log(Q) になる。

具体的な実装

  • structのvectorとして、 s, t, x を管理。 x の昇順にsortする。
  • 各スタート時間とindexのpairを、setにいれて管理。
  • それぞれの通行止区間について、 s_i - x_i \leq d_j \lt t_i - x_i を満たすような  d_j があれば、setからeraseする。
    • この時、別に答え出力用のanswer配列を用意しておき、answer[index] x_j を代入する。
  • answerを出力する。

解答

抜粋部分

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

struct stx {
    ll s, t, x;

    stx(ll s, ll t, ll x) : s(s), t(t), x(x) {}
};

int main() {
    ll n, q;
    cin >> n >> q;
    vector<stx> v;
    rep(i, n) {
        ll s, t, x;
        cin >> s >> t >> x;
        stx temp(s, t, x);
        v.emplace_back(temp);
    }
    set<pair<ll, ll>> set1;
    rep(i, q) {
        ll d;
        cin >> d;
        set1.insert(pair<ll, ll>(d, i));
    }
    auto comp = [](stx &a, stx &b) {
        if (a.x == b.x) {
            if (a.s == b.s) return a.t < b.t;
            return a.s < b.s;
        }
        return a.x < b.x;
    };
    sort(v.begin(), v.end(), comp);

    vector<ll> ans(q, -1);
    rep(i, n) {
        ll s = v[i].s, x = v[i].x, t = v[i].t;
        auto it = set1.lower_bound(pair<ll, ll>(s - x, -1));
        while (it != set1.end()) {
            if (t - x <= it->first) break;
            ans[it->second] = x;
            set1.erase(it++);
        }
    }
    rep(i, q) cout << ans[i] << endl;
    return 0;
}

Submission #6087534 - AtCoder Beginner Contest 128

ABC130-E Common Subsequence (500)

Common Subsequence

問題はこちら

atcoder.jp

この問題はLCS(Longest common subsequence)と関わりが深いのでまずはそれから書いてみる。

LCS

最長の共通部分列の長さを求めてくださいというのが典型的な問題。次のような例を考えてみる。

s: abcd
t: acfed

 s_i = t_j (= x) の時、これまでの共通部分列の末尾にそれぞれ x を加えることで長さが+1された共通部分列を新しく作ることができる。 例でみると、 s_i = d, t_j = d の時、今までのLCSは "ac" なので、"acd" を作ることでより長いものを作ることができる。

よって、常にLCSを持ちながら遷移するdpを実装することで答えを求めることができる。遷移は次の通り。

  •  dp[i + 1][j + 1] :  s_i までと  t_j までの中のLCS
  •  s_i = t_j の時:  dp[i + 1][j + 1] = dp[i][j] + 1
  • それ以外:  dp[i + 1][j + 1]  = max(dp[i][j + 1], dp[i + 1][j])

今回の問題

それぞれちょうど s_i t_jで終わるものの共通部分列の数を数えてみる。

 s_i = t_j (= x) の時、これまでに存在していた全ての共通部分列に対して、末尾にそれぞれ  x を加えることで、新しい共通部分列を作ることができる。つまり、これまでに存在していた全ての共通部分列(=  s _ {i-1}までと t _ {j - 1}までに存在する全ての共通部分列)の数だけ増える。さらに、 x 一文字のみのものも増えるので、これに+1されることになる。

遷移テーブルのイメージは次のようになる。水色の部分を例とすると、"abc" までと "abcfe" までの共通部分列の数は水色で囲われた部分の和になっている。なので、 "abcd" までと "abcfed" までの共通部分列の数は水色で囲われた部分 + d自身のみの場合である。

f:id:thescript1210:20190618181932j:plain:w300
遷移テーブル

  •  sum[i + 1][j + 1]:  s_i までと  t_j までの共通部分列の個数の二次元累積和。
  •  dp[i + 1][j + 1] :  s_i までで ちょうど s_iで終わるもの と、 t_j までで ちょうど t_jで終わるもの の共通部分列の数。
  •  s_i = t_j の時:  dp[i + 1][j + 1] = sum[i][j] + 1
  • それ以外:  dp[i + 1][j + 1]  = 0
  • 累積和の更新:  sum[i + 1][j + 1] = sum[i][j + 1] + sum[i + 1][j] - sum[i][j] + dp[i + 1][j + 1]

解答

抜粋部分

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
const ll mod = 1e9 + 7;

int main() {
    ll n, m;
    cin >> n >> m;
    vector<ll> s(n), t(m);
    rep(i, n) cin >> s[i];
    rep(i, m) cin >> t[i];

    vector<vector<ll>> dp(n + 1, vector<ll>(m + 1, 0));
    vector<vector<ll>> sum(n + 1, vector<ll>(m + 1, 0));
    rep(i, n) {
        rep(j, m) {
            if (s[i] == t[j]) {
                dp[i + 1][j + 1] = sum[i][j] + 1;
            } else {
                dp[i + 1][j + 1] = 0;
            }
            dp[i + 1][j + 1] %= mod;
            sum[i + 1][j + 1] = sum[i][j + 1] + sum[i + 1][j] + dp[i + 1][j + 1];
            sum[i + 1][j + 1] %= mod;
            sum[i + 1][j + 1] = (sum[i + 1][j + 1] + mod - sum[i][j]) % mod;
        }
    }

    ll ans = 1;
    rep(i, n + 1) rep(j, m + 1) ans += dp[i][j], ans %= mod;
    cout << ans << endl;
    return 0;
}

Submission #6008512 - AtCoder Beginner Contest 130

参考

betrue12.hateblo.jp

qiita.com