【C++】D - Base n (ABC192)

問題概要
ポイント
解説
サンプルコード
参考

問題概要

0 ～ 9 からなる文字列 $X$ と，整数 $M$ が与えられる． $X$ に含まれる最も大きい数字を $d$ とする． $d+1$ 以上の整数 $n$ を選んで $X$ を $n$ 進法表記の数とみなして得られる値のうち， $M$ 以下であるようなものは何種類あるか？

f:id:katakori3:20210221232103j:plain — 問題

https://atcoder.jp/contests/abc188/tasks/abc192_d

ポイント

$n$ 進数から 10 進数への変換
二分探索
オーバーフローへの対処
コーナーケースを考える

解説

$n$ 進数から 10 進数への変換

そもそも $n$ 進数とは，「n の累乗を位取りの基本とする」ものです．こんな感じで10進数から $n$ 進数へ変換することができます．

f:id:katakori3:20210221232519j:plain — 10 進数から 3 進数への変換

10¹⁸ という数字を見たら二分探索を使うことを考える．

$d+1$ から $M$ 進数まで判定していくと，時間が足りません．ここで， $x$ の $n$ 進数への変換を $f(n)$ とすると，単調増加であることが分かるので，二分探索が使用できることに気が付きます．

二分探索に関する詳しい説明は書籍やこちら（二分探索アルゴリズムを一般化〜めぐる式二分探索法のススメ〜 - Qiita）などにお任せするとして，二分探索を簡単に以下の図で説明します．

簡単に言うと，二分探索は全探索のようにすべてを探索するのではなく，探索する幅を狭めていく方法です．これにより $O(\log M)$ の計算量で探索することができます．

f:id:katakori3:20210221234101j:plain — 二分探索

f:id:katakori3:20210221234058j:plain — 二分探索

オーバーフローへの対処

今回， $n$ が大きくなっていくと， $n$ 進数へ変換したときにオーバーフローが発生する可能性があります．つまり， $M$ 以上であるかの判定を愚直に行うことができません．ここで，判定のために以下の式を使用します．ただし，この式が成立するのは $v$ が整数のときのみです．

$v >\mathrm{floor}{\dfrac{M}{x}}$ が成立するときは， $v > \dfrac{M}{x}$ が成立する

なぜこの式が成り立つのかの詳細な証明は省きますが，イメージ的には以下の図で示した通りです．これでオーバーフローを防ぐことができました．

f:id:katakori3:20210221231803j:plain — 数直線上で考える

コーナーケース

今回のコーナーケースは $X$ が一桁のときです．この時は任意の $n$ 進数で $X$ になります．

コーナーケース
進数変換の実装の説明

$value = value * n + int(c - '0')$ は何をしているのかを図解しました．

f:id:katakori3:20210222163059j:plain — 進数変換の実装

サンプルコード

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
 
int main(){
    string x; cin >> x;
    ll m; cin >> m;

    // x が 1 桁だと，任意の n 進数で x のみ（1種類しかない）
    if (x.size() == 1) {
        if (stoi(x) <= m) cout << 1;
        else cout << 0;
        return 0;
    }

    int d = 0;
    for (char c : x) d = max(d, int(c-'0'));
    // 下限を d にしたのは，最終的に知りたい値が ac - (d+1) - 1 なので
    // 下限を ac, 上限を wa とおくと良いらしい
    ll ac = d, wa = m + 1;

    // 二分探索は上限と下限（閾値）が隣り合うまで行われる
    while(wa - ac > 1){
        ll wj = (ac + wa) / 2; // (waithing judge: wj 進数)で表した時に m 以下かどうか
        ll value = 0;
        for (char c : x){
            // オーバーフローを避けるためにこちら
            if (value > m / wj) value = m + 1; 
            // 進数変換
            else value = value * wj + (c - '0');
        } 
        if (value <= m) ac = wj;
        else wa = wj;
    }
    cout << ac - d;
    return 0;

}

参考

進数法の解説にはこちらの記事を参考にさせていただきました．

examist.jp

実装に関しては公式解説のものです．（勉強のために写経させていただきました．）

www.youtube.com

2021-02-14

【C++】A - B = C (ARC112)

AtCoder AtCoder-300点問題 C++

問題概要
ポイント
解説
サンプルコード

問題概要

$L$ 以上 $R$ 以下の整数 $(A, B, C)$ の組であって， $A - B = C$ を満たすものは何通りか？

A - B = C

ポイント

計算量の推定
等差数列の和

解説

考え方

引き算が何となく嫌なので，移項して $B + C = A$ を考えます．

$B + C = A$ にするには， $B$ （または $C$ ）の最大値は $R - L$ になる必要があります．このことを利用して， $B$ を固定してカウントしていくと以下のようなコードになります．

ll ans = 0;
int ma = R - L;
for(int b = L; b <= ma; ++b){
    ans += b - L + 1;
}
cout << ans << endl;

計算量について

問題は計算量についてです．今回， $T$ 個の $L, R$ があります．上の実装だと $T$ 個のケースを考える時間と， $B$ を固定して解を求めていくのとで $O(T+N)$ の時間がかかってしまいます．これではいけないので， for 文を 1 つにすることを考えます．

例えば $L = 2$ ， $R = 6$ で， $B$ を固定したときは以下のようになります． $B$ の値を大きくしていくと， $C$ の取りうる値の数は減っていきます．

以上より，等差数列の和を用いることで for 文を使わずに求めることができることがわかりました．

f:id:katakori3:20210214030749j:plain — Bを固定すると，取りうるCの場合の数が等差数列になっている

等差数列

等差数列の和は，初項を $a$ ，末項を $l$ ，項数を $n$ ，公差を $d$ とすると，

$S_n = n(a + l) / 2 = (2a + (n - 1)d) * n / 2$

で求められます．今回の問題では，公差が 1 なので，はじめの式を用いています．
存在しないときの条件

$B = C = L$ の時に， $A$ は最も小さくなります．これが $R$ よりも小さい場合，条件を満たす $A, B, C$ が存在しません．

サンプルコード

#include <bits/stdc++.h>
#include <algorithm>
#define rep(i, n) for (int i = 0; i < n; i++)
using ll = long long;

int main(){
    int T; cin >> T;
    vector<ll> ans(T, 0);

    rep(i, T){
        ll L, R; cin >> L >> R;
        ll mi = L + L;
        if (mi > R) ans[i] = 0;
        else{
            ll ma = R - L;
            ll num = ma - L + 1;
            ans[i] = num * (1 + num) / 2;
        }
    }

    rep(i, T) cout << ans[i] << endl;
}

2021-02-10

【C++】D - Snuke Prime (ABC188)

AtCoder-400点問題 AtCoder C++

問題概要
ポイント
解説
サンプルコード
参考

問題概要

$i$ のサービスの利用料は $c_i$ 円であり，それぞれ $a_i$ 日から $b_i$ 日まで利用するとき，全日程の利用料金を求める．

D - Snuke Prime

ポイント

いもす法 (imos 法)

解説

いもす法について

いもす法とは「累積和のアルゴリズムを多次元，多次数に拡張したもの」らしいです．今回の問題のように，足し合わせていくものの期間が定められている場合，累積和の考えを 2 次元に拡張します．

いもす法では，ある期間において値が増えたり減ったりします．この増えたり減ったりすることを「イベント」として扱います．

今回の問題では以下の 2 つがイベントです．
- $a_i$ : 料金が $c_i$ 円の支払いが開始するイベントが起こる（1日当たり払う金額が $c_i$ 増える）
- $b_i$ : 料金が $c_i$ 円の支払いが終了するイベントが起こる（1日当たり払う金額が $c_i$ 減る）
サンプル 1 の料金

はじめに，「いもす法とは『累積和のアルゴリズムを多次元，多次数に拡張したもの』」と言いました．この図で，なんとなく累積和が 2 次元に拡張されているのがわかると思います．
１日当たりの料金の算出

イベントが起こらない日は，前日と同じ料金を払うだけでよいです．「１日当たりの料金 (perday)」と，「計算済みの日 (day)」を保存しておき，合計料金に足し合わせるような実装をしています．今回の問題では，１日当たりの料金がある一定の金額を超えると，それ以上は増えません．なので，「利用するサービスそれぞれの料金すべてを合計したとき (charge)」と，最大値 (C_max) を比較しています．

まとめると，イベントが発生すると以下の処理が行われます．
1. 計算済みの日 (day) から，イベントが起こる日 (it.first) までの料金を合計金額に足し合わせる
2. イベントが発生し，料金 (charge) が変動
3. 計算済みの日 (day) を更新

f:id:katakori3:20210210220756j:plain — 2, 3 日目は同じ料金，4, 5 日目も同じ料金

サンプルコード

#include <bits/stdc++.h>
#include <algorithm>
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define rep(i, n) for (int i = 0; i < n; i++)
using ll = long long;
using namespace std;

int main(){
    int N, C_max;
    cin >> N >> C_max;

    vector<ll> A(N), B(N), C(N);
    rep(i, N) cin >> A[i] >> B[i] >> C[i];

    vector<pair<ll, ll>> event;

    // イベントの作成
    rep(i, N){
        // 0-index にする
        event.push_back({A[i] - 1, C[i]});
        event.push_back({B[i], -C[i]});
    }

    // イベントが起こる日を昇順に並べる
    sort(event.begin(), event.end());

    ll ans = 0;
    ll day = 0; // 現在何日目か
    ll charge = 0; // その日に必要な料金

    for (auto &it : event){
        ll perday = min(C_max, charge);
        ans += perday * (it.first - day);
        day = it.first;
        charge += it.second;
    }

    cout << ans;
}

参考

こちらの記事を参考にさせていただきました．

imoz.jp

2021-02-09

【C++】D - Wandering (ABC182)

AtCoder C++ AtCoder-400点問題

問題概要
ポイント
解説
サンプルコード
参考

問題概要

座標を移動していくときの最大位置を求める

正の向きに $A_1$ 進む
正の向きに $A_1$ + $A_ 2$ 進む

　　　　　　　　：

正の向きに $A_1$ + $A_2$ ...... $A_N$ 進む

D - Wandering

ポイント

累積和
変位（差分）を考える癖をつける

解説

累積和について

累積和については，ほかの方が詳しく説明していると思いますので，ここでは概要だけを説明します．

累積和とは，ある範囲の和を求めるときに重宝する手法です．簡単に言うと，「ある範囲の和を求めるときに，2 重 for 文を使わなくても済む方法！！」という感じです．

f:id:katakori3:20210209232949j:plain — 累積和の概念

実装はこんな感じでできます．私は 0-index を使用しています．

for (int i = 0; i < N + 1; ++i){
    s[i + 1] = s[i] + A[i];
}

累積和を使用して「変位」と「変位の最大値」を保存する

$N$ $\leq$ 2 $\times$ 10⁵ なので，2 重 for 文で累積和を使用していては間に合いません．（2 秒でできる for 文は 10⁸ くらいまでということを頭に入れておくといいと思います．）

こういう時は，「変位」を考えるとうまくいくことが多いそうです．
- d[N + 1]: 1 回の移動で動く距離
- m[N + 1]: 1 回の移動の中で，正の方向に最も動く距離
わかりにくいのでサンプル 1 で説明します． $p$ は現在の座標です．
サンプル 1 の動き

ここで， $m$ がなにを示しているかですが，つまりは「1 回の移動で最も大きく右に移動するときの変位」です．数式で示すと以下のようになります． $m_i = max(A_1, A_1+A_2, A_1+A_2+A_3, ........ , A_1+A_2+ ........ A_i )$

これを求めておくことで， $i$ 回目の移動では，今の座標位置から $m_i$ だけ進んだら最大値にいることがわかります．
座標の移動

現在の座標 $p_i$ を計算し，そこから $m_i$ だけ進めた座標が， $i$ 回目の移動で最も正方向に移動したときの座標となります．

最後に，実際に動く距離 ( $d_i$ ) を足し合わせることで $p$ を進めます．

サンプルコード

#include <bits/stdc++.h>
#include <algorithm>
#define rep(i, n) for (int i = 0; i < n; i++)

int main(){
    int N; cin >> N;
    vector<int> A(N); 
    // p: 移動が終わった後の座標になる （累積和）
    // m: 変位の最大値を保存しておく
    vector<ll> d(N + 1, 0), m(N + 1, 0);

    rep (i, N) cin >> A[i];
    
    rep (i, N + 1) {
        d[i + 1] = d[i] + A[i];
        m[i + 1] = max(ma[i], d[i + 1]);
    }

    ll res = 0;ll p = 0;
    rep(i, N){
        res = max(res, p + m[i + 1]);
        p += d[i + 1];
    }
    cout << res;
}

参考

2021-02-09

【C++】D - Hachi (ABC181)

AtCoder C++ AtCoder-300点問題

問題概要
ポイント
解説
サンプルコード

問題概要

ある文字列が与えられたとき，文字を入れ替えることで 8 の倍数を作れるかどうかの判定

D - Hachi

ポイント

下 3 桁が 8 の倍数であるとその数は 8 の倍数になる
桁数による場合分け
計算量の推定

解説

この問題，解き方はすぐ思い浮かびましたがなかなか実装に手こずりました．

探索は全探索で間に合いそう！

どうやって下 3 桁を探索するかですが，0 を含まず，8 の倍数だけを見ていけば良いので，111 ~ 999 の全探索でも十分間に合うことが分かります．（8 の倍数を見ていくので 112 から探索を始めます．）ちなみに，1，2 桁の時は文字列のまま判定した方が早いので場合分けをしています．
1~9 のそれぞれがどれだけ含まれているかを保存

112 ~ 999 を調べていくときに，元の文字列でその 3 桁を作れるかを評価する必要があるので，元の文字列で 1~9 が出てきた回数をカウントして配列 $all$ に入れておきます． $num$ に評価する 3 桁の数に各数字 (1~9) がどれだけ含まれるかを保存し， $all$ と比較して，元の文字列で作れるかを判定します．

f:id:katakori3:20210209010323j:plain — 下 3 桁を作れるかの判定

char から int への変換

int n = char - '0' で変換できます．ちなみに string を int に変換するときは stoi を使うと楽です．

サンプルコード

#include <bits/stdc++.h>
#include <algorithm>
#define rep(i, n) for (int i = 0; i < n; i++)

int main(){
    string s; cin >> s;
    vector<int> all(10, 0);

    rep(i, s.size()) {
        int n = s[i] - '0'; ++all[n];
    }

    if (s.size() == 1){
        if (stoi(s) % 8 == 0){
            cout << "Yes";
            return 0;
        }
    }

    else if (s.size() == 2){
        int a = stoi(s);
        swap(s[1], s[0]);
        int b = stoi(s);
        if (a % 8 == 0 || b % 8 == 0){
            cout << "Yes";
            return 0;
        }
    }
    
    else{
        for (int i = 112; i < 1000; i += 8){
            vector<int> num(10, 0);
            int i2 = i;
            int a = i2 % 10; i2 /= 10; ++num[a];
            int b = i2 % 10; i2 /= 10; ++num[b];
            int c = i2 % 10; ++num[c];
            bool ok = true;
            for (int j = 0; j < 10; ++j) {
                if (num[j] > all[j]) ok = false;
            }
            if (ok){
                cout << "Yes";
                return 0;
            }
        }
    }
    cout << "No";
    return 0;

}

2021-02-08

理系大学院生の就活のこと

雑記

はじめに
推薦について
面接でよく聞かれたこと
大切だと思ったこと
まとめ

はじめに

私は修士時代，研究に力を入れていて忙しく，普通の就活生がするような就活はほとんどしませんでした．

理系大学院生は基本的に研究に追われており，1 月ごろから就活を始める人が多いと思います．私も就活を本気でやり始めたのは 2 月からでした．就活を始めたころ，「周りは夏ごろから就活を始めているのに...」とめちゃめちゃ焦りました．そんな理系大学生の方は多いと思います．

私も就活中は不安で，「理系　大学院生　就活　不安」とかで調べていましたが，なかなか記事がなくて落ち込んでました．そこで，修士で研究しかしていなかった私が，就活で「やっておいてよかった」とか「大事だな」と思ったことをまとめたいと思います．就活している方の不安が少しでもなくなれば嬉しいなと思います．

また，保険を掛けるようですが，以下に記すことはすべて私という 1 サンプルが思っていることなので，参考程度に受け取っていただければと思います．

面接でよく聞かれたこと

研究について
- どうしてその研究をしているのか（どうして始めたのか，どんなことが大切だと思って進めているのか）
- 研究内容について（技術的な話）
- その研究が進むとどんなことがうれしいのか（実用性的な面で）
- 技術的なことをどうやって乗り越えたか（実装とか）
困難をどう乗り越えたか
これからどんなことを研究していきたいか
なぜ研究職を志望するのか

大切だと思ったこと

☆自分なりに研究を頑張ること

理系職では，面接で必ずと言って研究内容を聞かれます．面接で感じたことは，研究内容と同じくらい，自分がその問題に対してどう考えて，どうやって問題を解決しようとしているのかが大切だということです．

私は TOEIC の点も平々凡々（むしろ低いかも）だし，サークルを頑張っていたわけでもないし，役に立つような資格も持っていません．趣味がプログラミングなわけでもなかったし，突出した才能も有りません．

でも，できたかどうかは置いておいて，研究だけは人並みに頑張ったと思います．苦しかったこと，嬉しかったこと，たくさんありました．

研究職だと，技術試験がある企業が少なく，面接がメインになると思います．私は「困難にぶつかったか？それをどう乗り越えたか」「生きてきた中でどんなことを達成したか」など，面接で定番の質問はすべて研究につなげました．

研究に力を入れたこと，自分の研究について深く考えたことは無駄にならないと思いました．

☆臆せず就活経験者に助けを求めること

私は，何社か ES を出した後に，添削してもらわなかったことを後悔しました． OB の方もいたし，研究室の先輩もいたのに，迷惑かけたくないという思いから添削のお願いができませんでした．

就活を終えた先輩は，強く主張するべきことや，就活で大切なことを知っています．先輩や友人，先生など，ES の添削や面接対策はいろんな人に見てもらうことをお勧めします．

☆指導教員とたくさんコミュニケーションをとること

私は研究を指導してくださっていた先生にたくさん相談しました．（お忙しい中本当にありがとうございました...）

先生は企業の内情を知っていたり，OBのお話をしてくださったので，企業選びの参考になりました．

私は自由応募だったので，「全部落ちたらどうしよう」という不安が常に付きまとっていましたが，「最後には先生に土下座して博士に残らせてもらおう！」とか考えてました．（ダメだこりゃ）

研究職はベンチャーや一般職と比較して選考が遅いことが多いです．私の周りにも，私が就活を始めたころにはすでに内定をもらっていた友人が多くいました．不安になるだけだし，就活に必要な情報は SNS がなくても手に入るので，Twitter や Instagram はアカウントごと抹消しました．

☆自分の欠点も知ること

就活だと，自分の良いところを前面に出すことばかりに力を入れてしまいがちです．私もそうでした．でも，取り繕ってばかりでは自分がわからなくなるし，就活ではそれが顕著だと思いました． 自分の苦手なことや，精神的に弱いことを知ることも大切な気がします．欠点を克服しようと頑張っていることを伝えると，面接してくださっている方にも「私とはどんな人間か」をより知ってもらえると思ったし，マッチングにずれが無くなるかもしれません．

私は面接の際に自分の欠点を克服するように努力していることを伝えました．私の欠点は，仕事をするのに致命的なものですが，それでも受け入れてくれた企業の方にはとても感謝しています．少し自信が出ました．

まとめ

結論，私は，「しっかり研究しているなら心配はない！」と思っています．

私は，就活が終わった後も「私なんかが研究を続けていけるのか」「うまくやっていけるのか」で不安にいっぱいになる日が続きました．こんなことがないように，今就活している皆さんが後悔なく就活を終えることができるように願っています．☆彡

2021-02-08

【C++】D - Alter Altar (ABC174)

AtCoder C++ AtCoder-400点問題

問題概要
ポイント
解説
サンプルコード

問題概要

条件を満たすように石の場所を入れ替える

D - Alter Altar

ポイント

条件を満たす状態を推定する

解説

条件を満たす状態

今回の問題で大切なのは「赤 (R) の左に白 (W) があってはいけない」という条件を「すべての赤 (R) が左に集まっている」という条件に読み替えることができるかということだと思います．（私はしばらくできなかったです．）

f:id:katakori3:20210208182652j:plain — 赤はすべて左側に寄る

A: 赤を白に替える

B: 石の場所を入れ替える

とします．

例えば，サンプル 1 の「WWRR」については，条件を満たす並び方は以下の 2 通りです．

f:id:katakori3:20210208181305j:plain — 入れ替え例

考えたこと

初めに，赤の石と白の石が何個あるかをカウントします．そして左から赤の数だけ見ていきます．もし白ならば A または B の処理を行い，赤ならばそのまま置いておきます．

左側に白さえなくなればよいので，A の処理でも B の処理でも問題ないですが，なるべく少ない回数で終えたいので，B の側にある赤と左にある白を入れ替えた方がよさそうです．なので，白を見つけたら赤と取り換えていきます．サンプル 1 の図で言うと，右の処理を実行しています．

処理しなければならない赤がなくなったら処理を終了します．

サンプルコード

#include <bits/stdc++.h>
#include <algorithm>
#define rep(i, n) for (int i = 0; i < n; i++)

int main(){
    int n; cin >> n;
    string c; cin >> c;

    int red = 0;
    int white = 0;
    
    rep(i, n){
        if (c[i] == 'R') ++red;
        else ++white;
    }

    int res = 0;
    rep (i, n){
        if (red == 0) break;
        if (c[i] == 'W'){
            ++res;
            --red;
        }
        else --red;
    }
    cout << res;

}

問題概要

ポイント

解説

サンプルコード

参考

問題概要

ポイント

解説

サンプルコード

問題概要

ポイント

解説

サンプルコード

参考

問題概要

ポイント

解説

サンプルコード

参考

問題概要

ポイント

解説

サンプルコード

はじめに

推薦について

面接でよく聞かれたこと

大切だと思ったこと

☆自分なりに研究を頑張ること

☆臆せず就活経験者に助けを求めること

☆指導教員とたくさんコミュニケーションをとること

☆SNS を見ない

☆自分の欠点も知ること

まとめ

問題概要

ポイント

解説

サンプルコード