AtCoder: 第一回日本最強プログラマー学生選手権-予選- D Classified (600)

問題はこちら

atcoder.jp

今回はほぼ解説放送と解説ブログを参考にした自分用のメモ。

考え方

JSC2019予選 - D 「Classified」 (600) - Mister雑記

[AtCoder 参加感想] 2019/08/25:JSC2019予選 | maspyのHP

• 奇閉路が存在しないようにグラフを分割できれば良い。
• 奇閉路が存在しないことは、二部グラフが構成できることと同値。
• よって、完全グラフを二部グラフに分割することを考える。
• なるべくたくさんの辺を取り除いていきたいので、最大の完全二部グラフを取り除いていくことを考える。
• 完全グラフから完全二部グラフを取り除いていくと、残りの部分グラフはそれぞれ完全グラフを構成している。
• よって、再帰的に完全グラフから完全二部グラフを構成していくことを繰り返せば良い。

解答

ほぼ写経コード。

残っている頂点を半分ずつに分割して、完全二部グラフを構成していく。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;

int main() {
    ll n;
    cin >> n;

    vvl level(n, vl(n));
    auto dfs = [&](auto &&f, ll l, ll r, ll lev) -> void {
        if (l + 1 == r) return;
        ll mid = (l + r) / 2;
        for (ll i = l; i < mid; ++i) {
            for (ll j = mid; j < r; ++j) {
                level[i][j] = lev;
            }
        }
        f(f, l, mid, lev + 1);
        f(f, mid, r, lev + 1);
    };
    dfs(dfs, 0, n, 1);
    for (ll i = 0; i < n - 1; ++i) {
        for (ll j = i + 1; j < n; ++j) {
            cout << level[i][j] << ' ';
        }
    }
    return 0;
}

AtCoder: 第一回日本最強プログラマー学生選手権-予選- C Cell Inversion (500)

問題はこちら

atcoder.jp

考え方

なんか自分で書いててもあまり納得感がないかもしれない... 記事を書いた後に自分がわかりやすかったものを参考として載せておきます。

misteer.hatenablog.com

Cで僕が考えたこと
・累積的な何かを考えるとよさそう
・[L, R]の反転は、[0, R]の反転と[0, L-1]の反転に分解できる
・つまりそれぞれの頂点xは[0, x]の反転として使う(Rにする)か[0,x-1]の反転として使う(Lにする)かのどちらか

— てんぷら (@tempura_cpp) August 24, 2019

step1 - 反転する操作の言い換え

まず、操作の順番を変えても答えは変わらないことに注意する。

任意の を選んでその区間を逆にする操作は、とに対してそれぞれ操作をすることと等価であることに注目する。

step2 - それぞれの文字が影響を及ぼす範囲を整理

つまり、番目に存在する文字は、以下のように考えることができる。

• として使った時は 自分を含めた 左側に影響を及ぼす。
• として使った時は 自分を含めない 左側に影響を及ぼす。
• に影響を及ぼすのは、それよりも右側にある文字だがこれの数は一定。

=> 以上より、番目よりも右側に存在する文字によって反転させられたあと自分の文字を変更できるのは、自分を として使うか、として使うかのどちらかのみ ということになる。

すべての要素は個あり、自分よりも右側のものに影響を受ける場合のみ考えると、終了時には以下のような状態になる。

// 0-indexで考える

if index % 2 == 0 then 色が反対に
else 色はそのまま

上記の操作を終了した時に、色を全て "W" にするためには以下のように振り分ける。

• "B" になっているものは として使う（自分を反転させるため）。
• "W" になっているものは として使う（自分を反転させないため）。

step3 - 組み合わせ計算

は自分よりも左側にある使われていない の数分だけペアになる候補がある。 よって累積のの数を数えておけばよく、疑似言語書くとこのようになる。

count = 1

for i in 2N:
  if is_right[i] == true:
    count *= left_count  
    left_count--

  else:
    left_count++

ただしよりも左側にまだペアになっていないがない時や、最終的にが余ってしまう時は答えは0なので、実装時はそこにも注意する。

最後に、操作順だけの場合の数があるので、をかけて出力する。

解答

#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 ------------- */
/* ---------------------------------- */
ll factorial(ll n) {
    ll ans = 1;
    while (n > 1) {
        ans *= n;
        ans %= mod;
        n--;
    }
    return ans;
}


int main() {
    ll n;
    cin >> n;
    string s;
    cin >> s;

    n *= 2;

    vector<bool> is_right(n);
    rep(i, n) {
        if (i % 2 == 0 && s[i] == 'W') is_right[i] = true;
        if (i % 2 == 1 && s[i] == 'B') is_right[i] = true;
    }
    ll ans = 1;
    ll left_sum = 0;
    rep(i, n) {
        if (is_right[i]) {
            if (left_sum == 0) {
                cout << 0 << '\n';
                return 0;
            }
            ans *= left_sum;
            ans %= mod;
            left_sum--;
        } else {
            left_sum++;
        }
    }
    if (left_sum > 0) cout << 0 << '\n';
    else cout << ans * factorial(n / 2) % mod << '\n';
    return 0;
}

Submission #7126826 - Japanese Student Championship 2019 Qualification

AtCoder: ABC134-E Sequence Decomposing (500)

Sequence Decomposing

問題はこちら atcoder.jp

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

考え方

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

具体的には、現在有効な部分列の右端（＝最大の値）を保持する集合 を持っておく。各要素 を見た時に、 となるものが の中に存在するならば、 と更新する（以下の図で見ると、赤丸のものが に含まれるものになる）。

sample1

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

解答

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

1. multisetを使う

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

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

• multiset::erase を使うとき、引数にイテレーターを指定すると一つだけ削除してくれる。逆に値を指定すると、その値が入った全てを削除する。今回は一つだけ削除したいのでイテレーターを指定して削除する。
  multiset::erase - cpprefjp C++日本語リファレンス

• lower_bound(mulsiset.begin(), multiset.end(), x)の計算量は 、multiset::lower_boundの計算量は 。
  競プロ覚書：二分探索，std::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];
    
    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を使う

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

dequeとはdouble-ended-queueの略で、末尾と先頭への要素追加・削除が で行える。さらにindexを指定してのランダムアクセスも で行える。 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

レート

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

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ハングアウトでホワイトボードもろくに使えずボロボロでした。そのあとに「他のチームが興味を持っている」という連絡があり、再びコーディングテストと面接を受けて落ちました。

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

「コーディングスキルはあるのですが、修士に進まれていないこともあり専門領域が他の方と比べて足りないと感じました」

— ひらめくん🐟 (@hiramekun1995) May 8, 2019

C社

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

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

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

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

他の企業の選考始まる前に内定承諾か決めるの難しすぎないか？

— ひらめくん🐟 (@hiramekun1995) March 29, 2019

D社

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

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

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

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

落ちた人なのであんまり参考にならないと思うけど、レートが低い人でも全然チャレンジする価値があると思った

— ひらめくん🐟 (@hiramekun1995) July 1, 2019

E社

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

待遇が良かったのと、youtubeで働いてる様子とかみて、純粋に働いてみたい！と思ったので選考を受けました。

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

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

F社

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

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

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

感想とか

院進か就職か？

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

hiramekun.hatenablog.com

hiramekun.hatenablog.com

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

就活の軸について

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

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

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

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

競プロは役に立つか

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

就活のために競プロを始めたわけではないけど、結果的に就活にとっても役立ってる

— ひらめくん🐟 (@hiramekun1995) May 4, 2019

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

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

僕は AtCoder で緑なんだけど，就活では割と「緑なんですか？すごいですね」と言われること多いよ．自信持って言い切ること大事な気がする． https://t.co/SYnYSXQdHX

— ひらめくん🐟 (@hiramekun1995) March 4, 2019

僕「趣味で競技プログラミングをしてます」
面接官「レッドコーダーとかですか？」

— ひらめくん🐟 (@hiramekun1995) June 17, 2019

大事だと思ったこと

• 面接にたどり着くためのコーディング，アルゴリズム力．
• 自分の意思決定に関して明確に言語化すること．またそれを的確に伝えること．

就活する意味

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

これもありますね。

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

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

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

最後に

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

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

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

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

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

問題はこちら。 atcoder.jp

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

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

考え方

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

計算量は、各辺を見る回数が高々1回なので、操作回数がになる。

解答

答えを出力するときには元の順番で出力しなければいけないので、クエリの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

AtCoder: ABC127-E Cell Distance (500)

Cell Distance

問題はこちら atcoder.jp

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

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

考え方

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

1. 全てのペアについて距離の合計を求める：
2. 全ての配置について試す：（指数時間）

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

step1 - 和の計算の分解

について、とは分解して考えることができる。

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

step2 - 計算式の整理

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

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

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

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

まず、距離となるような列の取り方が、 通り。そして、各列においてどの行の座標を使うかの組み合わせが 通り。以上より、 通り。

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

個の座標のうち、そのペア以外の 個の候補から、座標を 個えらぶような場合の数なので、 通り。

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

AtCoder: ABC131-F Must Be Rectangular! (600)

Must Be Rectangular!

問題はこちら

atcoder.jp

考え方

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

https://www.youtube.com/watch?v=XI8exXVxZ-Qwww.youtube.com

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

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

座標

二部グラフ

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

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

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

解答

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

• 二部グラフの表現の方法。x座標: x、y座標: 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