ひらめの日常

日常のメモをつらつらと

AtCoder: ABC123-D Cake 123 (400)

問題はこちら

atcoder.jp

美味しさは以下のように表される。

  •  X 種類のケーキ  A _ 1, A _ 2, ..., A _ X
  •  Y 種類のケーキ  B _ 1, B _ 2, ..., B _ Y
  •  Z 種類のケーキ  C _ 1, C _ 2, ..., C _ Z

この時、それぞれのケーキ美味しさの合計として大きい順に  K 個出力しなさい。

 \begin{array}{l}{1 \leq X \leq 1000}, \ {1 \leq Y \leq 1000}, \ {1 \leq Z \leq 1000}, \ {1 \leq K \leq \min (3000, X \times Y \times Z)}\end{array}

考え方

 X \times Y \times Z の全探索をすると  O(10 ^ 9) のループが周り、さらに大きい順に出力するので間に合わない。そこで、計算量を落とすことを考える。

いろんな解法があり、勉強になったので3つほど載せておく。元となる考え方は K が最大で3000 というところに注目するところにある。

解答1 - 解の候補を絞る

 A B の組み合わせを  X \times Y 分だけ全列挙すると、 O(10 ^ 6) となるので、sortしても大丈夫。この配列を  A \times B とおく。

大きい方から  K 個ということは、以下が成り立つ。

  •  A \times B からは最大でも  K 個使われる。
  •  C からは最大でも  K 個使われる。

よって、それぞれの配列の大きい方から  K ずつだけループを回して、大きい順に値を保持し、最後にsortして  K 個分出力すれば良い。計算量はここのsortがボトルネックとなって、  O(K ^ 2 \log(K))

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using vl = vector<ll>;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define all(obj) (obj).begin(), (obj).end()

int main() {
    ll x, y, z, k;
    cin >> x >> y >> z >> k;
    vl a(x), b(y), c(z);
    rep(i, x) cin >> a[i];
    rep(i, y) cin >> b[i];
    rep(i, z) cin >> c[i];

    vl ab;
    rep(i, x) rep(j, y) ab.emplace_back(a[i] + b[j]);
    sort(all(ab), greater<>());
    sort(all(c), greater<>());

    vl ans;
    rep(i, min(k, x * y)) rep(j, min(k, z)) ans.emplace_back(ab[i] + c[j]);
    sort(all(ans), greater<>());

    rep(i, k) cout << ans[i] << '\n';

    return 0;
}

Submission #7171632 - AtCoder Beginner Contest 123

解答2 - 貪欲とpriority_queueを使う

 A, B, C をそれぞれ大きい順にsortしておくとする。

最大値は  A _ 0 + B _ 0 + C _ 0 である。この次に大きいのはどれかということを考える。しかし、一意に定まりそうではないので候補を絞ることにする。すると、次の候補は以下の3つであるということがわかる。

  •  A _ 1 + B _ 0 + C _ 0 A のindexを一つだけ進めた。
  •  A _ 0 + B _ 1 + C _ 0 B のindexを一つだけ進めた。
  •  A _ 0 + B _ 0 + C _ 1 C のindexを一つだけ進めた。

なので、現在の最大値をpopした上で、これらを全て priority_queue にpushする。すると、次はtopにあるものが2番目に大きいものとなり、順に大きいものをpopしていくことができる。計算量は、priority_queue からpopする回数が  K 回、上記のように候補を3つpushする回数が  3K 回なので、 O(K log(K)) で間に合う。

ここで実装上の注意点は以下のようになる。

  • priority_queue にそれぞれのindexも含めて管理する。なぜなら、popした後にindexを一つ進める作業が必要になるため、和の値とそれぞれのindexの情報が必要。
  • 一度見たindexの和の値は priority_queue にpushしないように気をつける。例えば  A _ 1 + B _ 0 + C _ 1 は以下の二つのものから到達可能であり、重複して出力してしまう可能性があるからだ。
    •  A _ 1 + B _ 0 + C _ 0 から、 C のindexを増やした時。
    •  A _ 0 + B _ 0 + C _ 1 から、 A のindexを増やした時。

この辺の実装は以下の記事を参考にして実装させていただいた。

drken1215.hatenablog.com

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vl = vector<ll>;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define all(obj) (obj).begin(), (obj).end()

using data = pair<ll, vl>;

int main() {

    ll x, y, z, k;
    cin >> x >> y >> z >> k;
    vl a(x), b(y), c(z);
    rep(i, x) cin >> a[i];
    rep(i, y) cin >> b[i];
    rep(i, z) cin >> c[i];
    sort(all(a), greater<>()), sort(all(b), greater<>()), sort(all(c), greater<>());

    priority_queue<data> ans;
    set<data> used;
    ans.push(data(a[0] + b[0] + c[0], vl({0, 0, 0})));
    while (k-- > 0) {
        auto now = ans.top();
        ans.pop();
        cout << now.first << '\n';
        ll ia = now.second[0], ib = now.second[1], ic = now.second[2];

        data tmp;
        if (ia + 1 < a.size()) {
            tmp = data(a[ia + 1] + b[ib] + c[ic], vl({ia + 1, ib, ic}));
            if (used.find(tmp) == used.end()) {
                used.insert(tmp);
                ans.push(tmp);
            }
        }
        if (ib + 1 < b.size()) {
            tmp = data(a[ia] + b[ib + 1] + c[ic], vl({ia, ib + 1, ic}));
            if (used.find(tmp) == used.end()) {
                used.insert(tmp);
                ans.push(tmp);
            }
        }
        if (ic + 1 < c.size()) {
            tmp = data(a[ia] + b[ib] + c[ic + 1], vl({ia, ib, ic + 1}));
            if (used.find(tmp) == used.end()) {
                used.insert(tmp);
                ans.push(tmp);
            }
        }
    }
    return 0;
}

Submission #7171780 - AtCoder Beginner Contest 123

解答3 - K個以上になる境目の値を二分探索

ここでも  A, B, C をそれぞれ大きい順にsortしておくとする。

 K 個以上になる美味しさの合計の境目を二分探索で探索」し、二分探索内での判定方法として「美味しさの合計が  p 以上であるものが  K 個以上あるかどうか調べる」方法を考える。

まず後者は、以下のように枝刈りをすれば  O(K ^ 2) の計算量で抑えられる。

auto solve = [&](ll p) -> bool {
    ll cnt = 0;
    rep(i, x) { // ここは最大でK回ループがまわる
        rep(j, y) { // ここから下は最大でK回ループがまわる
            rep(l, z) {
                ll val = a[i] + b[j] + c[l];
                if (val < p) break;
                if (++cnt >= k) {
                    return true;
                }
            }
        }
    }
    return false;
};

なぜか???それは、 A, B, C をそれぞれ大きい順にsortしてあるので、以下の操作をすることにより  y, z の二重ループが高々  K 回しか回ることがないからだ。

  • 合計が  p より小さいなら一番ネストの深いループを抜ける。
  • 合計が  p 以上なら、カウントを一つ増やし、 K 以上になったら関数をreturnする。

よって、二分探索内での判定は可能になった。

最後に、境目がわかった後にどうすれば良いのかを考える。この境目を  Border とする。

  • 合計が   Border 以上のものは  K 個以上ある。(が、最大で何個あるかどうかはわからない...!)
  • 合計が  Border + 1 以上のものは  K 個より少ない。

よって、以下のようにして上位  K 個を求めることで間に合う。

  • 合計が  Border + 1 以上のものを全部列挙する。 これは先ほどの二分探索内での判定方法をほとんど同じ。
  • この個数が  K 個よりも少なければ、残りの美味しさは全て  Border であるので、それをpushする。

計算量は、二分探索に  O(log(A _ {max} + B _ {max} + C _ {max})) 、枝刈りに  O(K ^ 2 ) より、  O(K ^ 2 log(A _ {max} + B _ {max} + C _ {max})) で間に合う。

この考え方は公式の解説を参考にした。
https://img.atcoder.jp/abc123/editorial.pdf

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using vl = vector<ll>;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define all(obj) (obj).begin(), (obj).end()

int main() {
    ll x, y, z, k;
    cin >> x >> y >> z >> k;
    vl a(x), b(y), c(z);
    rep(i, x) cin >> a[i];
    rep(i, y) cin >> b[i];
    rep(i, z) cin >> c[i];

    sort(all(a), greater<>()), sort(all(b), greater<>()), sort(all(c), greater<>());

    auto solve = [&](ll p) -> bool {
        ll cnt = 0;
        rep(i, x) { // ここは最大でK回ループがまわる
            rep(j, y) { // ここから下は最大でK回ループがまわる
                rep(l, z) {
                    ll val = a[i] + b[j] + c[l];
                    if (val < p) break;
                    if (++cnt >= k) {
                        return true;
                    }
                }
            }
        }
        return false;
    };

    ll s = -1, e = a[0] + b[0] + c[0] + 1;
    while (e - s > 1) {
        ll mid = (s + e) / 2;
        if (solve(mid)) s = mid;
        else e = mid;
    }
    vl ans;
    rep(i, x) {
        rep(j, y) {
            rep(l, z) {
                ll val = a[i] + b[j] + c[l];
                if (val < s + 1) break;
                ans.emplace_back(val);
            }
        }
    }
    while (ans.size() < k) ans.emplace_back(s);
    sort(all(ans), greater<>());
    for (auto val: ans) cout << val << '\n';
    return 0;
}

Submission #7171934 - AtCoder Beginner Contest 123

AtCoder: ABC136-E Max GCD (500)

問題はこちら

atcoder.jp

 A_1, A_2, ..., A_N から  i \neq j となる  A_i, A_j を選び、 A_i = A _ i + 1, A_j = A _ j - 1 とする。この時、 K 以下の操作回数で  A の最大公約数として考えられるもののうち、最大のものを求めよ。

考え方

step1 - 解の候補

まず、 A_i に+1して、 A_j に-1するという操作は、 A_i の値を一つ  A_j に移動する操作と考えることができる。

次に大事なのは、答えの候補は  A の和の約数 となること。これはなぜかを考えてみる。今、答えとなる最大の最大公約数を  x とする。

  • 約数であるという性質から、 A _ 1 \% x = A _ 2 \% x =...= A _ N \% x = 0
  • modの性質から、 (A _ 1 + A _ 2 + ... + A _ N ) \% x = 0
  • 今回の操作は片方に+1, もう片方に-1するだけなので、総和は操作終了後にも変わらない。
  • 以上より、答えの候補は  A の和の約数となる。

なので、ある最大公約数  x K 回以下の操作によって達成されるかをすべて確かめ、達成されるものの中で最大のものが答えとなる。

step2 - 達成可能かを確認する

 x で割ったあまりが小さい方(=  A_i)から、大きい方(=  A_j)へと渡すのが操作方法が少なくて良い方法だとわかる。 A _ i \% x = a _ i ,  A _ j \% x = a _ j ,  a _ i \lt a _ j とおく。(簡単にするため、二つの数字でやり取りすることで割り切れる場合を考えてみる。)

  •  a_i から  a_j へ渡して  x で割り切れるようにする時。操作回数は  max(a _ i, x - a _ j)
  •  a_j から  a_i へ渡して  x で割り切れるようにする時。操作回数は  max(a _ j, x - a _ i)
  •  a _ i \lt a _ j より、  max(a _ i, x - a _ j) \lt max(a _ j, x - a _ i)

よって、 x で割った余りを小さい順でsortして、インデックス i より小さい側を渡す側。インデックス i 以上を渡される側として、必要な操作回数が K 以下であれば満たすと判定すれば良い。

解答

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = ll(n - 1); i >= 0; i--)
#define each(i, mp) for(auto& i:mp)
#define all(obj) (obj).begin(), (obj).end()

/* ------------- ANSWER ------------- */
/* ---------------------------------- */
// 約数列挙
vector<ll> divisor(ll n) {
    vector<ll> res;
    for (ll i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            res.emplace_back(i);
            if (i != n / i) res.emplace_back(n / i);
        }
    }
    return res;
}

int main() {

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

    vector<ll> divs = divisor(accumulate(all(a), 0LL));

    ll ans = 0;
    each(e, divs) {
        vector<ll> mods(n);
        rep(i, n) mods[i] = a[i] % e;
        sort(all(mods));

        vector<ll> minus(n + 1);
        rep(i, n) minus[i + 1] = minus[i] + mods[i];

        vector<ll> plus(n + 1);
        repr(i, n) plus[i] = plus[i + 1] + e - mods[i];

        for (ll i = 0; i <= n; ++i) {
            if (max(plus[i], minus[i]) <= k) ans = max(ans, e);
        }
    }
    cout << ans << '\n';
    return 0;
}

Submission #7148617 - AtCoder Beginner Contest 136

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

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

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

任意の  [l, r] を選んでその区間を逆にする操作は、 [0, l-1] [0, r]に対してそれぞれ操作をすることと等価であることに注目する。

f:id:thescript1210:20190825021430j:plain:w600

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

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

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

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

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

// 0-indexで考える

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

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

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

step3 - 組み合わせ計算

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

count = 1

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

  else:
    left_count++

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

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

解答

#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

問題文は次のように言い換えることができる。すなわち、「数列  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

レート

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

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社

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

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

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

感想とか

院進か就職か?

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

hiramekun.hatenablog.com

hiramekun.hatenablog.com

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

就活の軸について

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

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

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

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

競プロは役に立つか

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

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

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

大事だと思ったこと

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

就活する意味

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

これもありますね。

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

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

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

最後に

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

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

AtCoder: 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