AtCoder Beginner Contest 119 振り返り

A - Still TBD
B - Digital Gifts
C - Synthetic Kadomatsu
- 反省点
- 解法
D - Lazy Faith
- 解法
  - 汚い解法（汚いのでちゃんとした解法を見たい方は綺麗な解法へ）
  - 綺麗な解法
知見
- 問題を解く上での気持ち的な面
- 技術的な面
終わりに

　一週間前の ABC119 の振り返り．ABC120 が終わったばかりで今更感満載だが，ちゃんと復習できてなかったので書いた（ABC120 の UnionFind 木もいずれまとめたい）．解けなかった問題の反省点，思考過程を綴った．

A - Still TBD

A - Still TBD

　入力文字列を受け取り月を抽出し，4 以下なら Heisei，それ以外なら TBDを出力．

int y, m, d;
scanf("%d/%d/%d", &y, &m, &d)

とすると入力が楽だが，単に input <= "2019/04/30" と文字列を比較するだけでも答えが出せる．また，標準出力の関数 cout と二項演算子を組み合わせ，

cout << (y <= 4 ? "Heisei": "TBD") << endl;

という書き方ができることを初めて知った．

　月だけを見れば良いのに，本番は焦りで日にちまで比較して余計なコーディングをしてしまったので，焦らず冷静に解かないと緑，水色が見えてこないなと思った．

B - Digital Gifts

B - Digital Gifts

　本番では，一度 std::pair を要素とする std::vector で入力を受け取ってしまったが，その必要はなかった．単純に整数型と文字列型の変数を用意しておきそれで入力を受け取り，入力文字列が JPY かどうかを判定すれば良いだけだった．A，B を速く解こうとするあまり，思いつきで余計なコードを書いてしまうことが多いので反省点として挙げておく．解答は以下．

#include <iostream>
#include <string>
#include <vector>
using namespace std;
using ll = long long;

#define REP(i, n) for (ll i=0; i < n; i++)  // 0 ~ n-1

int main() {
    // input
    ll N;
    cin >> N;

    double res = 0, yen;
    string moji;

    REP(i, N) {
        cin >> yen >> moji;
        if (moji=="JPY") res += yen;
        else res += 380000.0*yen;
    }
    
    // 表示桁は多めに取っておく
    cout << setprecision(20) << res << "\n";

    return 0;
}

C - Synthetic Kadomatsu

　解けなかった問題．前半部分はただのポエムなので解答見たい方はこちらへ．

　制約が小さい問題は基本全探索，ということは分かっていたつもりだったが，その全探索の仕方が分からなかった．本番では竹をソートしたり大きい方・小さい方から貪欲法で目標を作ったり（これは違うと分かりつつも他に何をすれば良いか分からなかった），組み合わせを考えたが上手く答えを出せなかった．コンテストの最後らへんに使う使わないの bit 全探索？，DFS？と考えたが，書き方が分からず空っぽの dfs と書いた関数が残って終了した．

　最も反省？改善しなければいけないのは思考方法だと思ったので，以下では，本番中良くなかった思考過程を挙げていく．

反省点

「アルゴリズム，データ構造の知識を持っていなかった」以外の場合で，問題が解けなかったコンテストの思考過程は恐らく似通っている．そのため，

自分の思考過程を記録として残しておくことで同じ沼にはまる確率を少しでも下げる
問題に対する考え方の矯正を行う

ことを目的として反省点を列挙してみる（コンテスト後の TL を見ると参加者の思考過程（反省点）が言語化される．眺めながら共感したものも多くあったのでそれも参考にした）．

「制約が小さいから全探索だ」と頭では分かっていたつもりなのに，いつまでも貪欲法でなんとかしようとしていた（列挙の仕方がそもそも浮かばない，分からないというのも原因）．
目先の +1，-1 に囚われ，合成と伸縮のどちらを順番にやればいいのだろうかと考えていた（伸縮の順序は合成をやりきった後で良い）．
（上にも通づるが）問題文を素直に受け取りすぎ．C 問題以降は問題文を素直に読んでも問題は解けない．「結局どういう問題なのか」と落としこもうする思考が必要（これも頭では分かっているつもりだがコンテスト中に焦ると途端に俯瞰できなくなる）．
操作を限界まで行なった場合，最終的にどうなっているかを考える．

　結論，大局を見る，問題を単純な問題に落とし込む訓練をしていく必要がある（難しいことだけど練習しないことには）．反省点は以上．

解法

反省点を挙げたのであとは問題を解いていく．

問題のポイント

　この問題で考えるべき重要なポイントの一つとして，「+1，-1 をする操作は，合成してから考えれば良い．」という点である．

x + y  ->  (x + y) +1  ->  (x + y + 1) + 1  ->  x + y + 2
x + 1  ->  y + 1  ->  (x + 1) + (y + 1)  ->  x + y + 2

　反省点にも書いたが，私はこういう問題のときどうしても愚直に操作を辿っていく傾向がある．伸縮前後に合成をしても結果は変わらないことに「気づけない」というよりは，そういう考え方に「慣れていない」のだと思う．対象に対して操作を行う問題に対するこのような考え方は引き出しとして持っておきたい．

上記のポイントが分かったら問題を解く方針は以下のようになる．

合成して 3 本を作る．その方法を全探索．
作った 3 本の合成後（合成していない場合も含まれる）の長さを a, b, c とすると，A ，B，C との差分を取って abs(a - A) + abs(b - B) + abs(c - C) が伸縮の総コストになる．
各合成の組み合わせごとにコストを計算し，その最小値を算出．

　結局，上記手順の 1 の全探索の方法を考えることがこの問題のポイントである．けんちょんさんの記事を参考にすると，2 通りの解法があるようだ．

再帰(DFS)による解法
bit 全探索による解法

　この記事では再帰による解法で解く．bit 全探索による解法はけんちょんさんの記事を参考にされたい．

再帰(DFS)による解法

N 本(3 <= n <= 8)の竹それぞれについて，

A の合成に使う
B の合成に使う
C の合成に使う
使わない

の 4 通りがあり，その組み合わせを全探索しコストを計算する．つまり，あらゆる方法で竹から A，B，C を作ってみてその中から最小のコストを算出するということである．これを再帰で実装する．

　全 $4^{N}$ 通り，計算量は $O(4^{N}) = O(4^{8}) = O(65536)$ で十分間に合う．ただし，無から竹は生み出せないため，その場合は棄却する必要があるので注意．

以降けんちょんさんの記事を追っていく．

http://drken1215.hatenablog.com/entry/2019/02/24/224100

再帰関数の大枠をけんちょんさんの記事から拝借．i を配列のインデックスとして，

int recursion(int i, ~~~) {
    // 終端処理
    if (i == n) return ~;

    // i を進めながら、分岐処理
    int res = INF;
    chmin(res, rec(i + 1, 分岐 1));
    chmin(res, rec(i + 1, 分岐 2));
    chmin(res, rec(i + 1, 分岐 3));
    chmin(res, rec(i + 1, 分岐 4));

    return res;
}

という感じの再帰関数を書く．この問題では，

一つ一つの竹をどれに使うかを配列の端から検討していき，
その過程で「合成」のコストを算出．
全ての竹をどれに割り当てるか決める（i == N-1 まで）．
それぞれの竹を「伸縮」させるコスト（絶対値の差）を算出

先述した問題のポイントがここで反映されていることに注意．竹を伸縮させるのは，どの竹を使う決まった（最後の）時点で行う．実装では，

recursion(int i, int a, int b, int c)

として，

a: その時点での A に採用した竹の長さの総和
b: その時点での B に採用した竹の長さの総和
c: その時点での C に採用した竹の長さの総和

とするとよい．合成の過程のコスト計算を同時に行うことも念頭に実装していく．

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
using ll = long long;

ll N, num, A, B, C, res = LLONG_MAX;
vector<ll> vec;

#define REP(i, N) for(ll i = 0; i < N; ++i)

ll recursion(ll i, ll a, ll b, ll c, ll cost) {
    // 終端処理
    if (i == N) {
        // 一つでも 0 があったらMAXを出力．
        if (!a || !b || !c) return LLONG_MAX;
        else return abs(a - A) + abs(b - B) + abs(c - C) + cost;
    }

    // 現在の竹 vec[i] を使用しない場合
    // 竹を合成しないままインデックスを進める．当然合成コストは 0 なので加算は無い．
    ll ret0 = recursion(i+1, a, b, c, cost);

    // vec[i] を A, B, C どれに使うか割り当てる
    // 0 のときは合成コストは 0 を表す
    // それぞれの分岐で min が帰ってくる
    ll ret1 = recursion(i + 1, a + vec[i], b, c, cost + ((a == 0) ? 0 : 10));
    ll ret2 = recursion(i + 1, a, b + vec[i], c, cost + ((b == 0) ? 0 : 10));
    ll ret3 = recursion(i + 1, a, b, c + vec[i], cost + ((c == 0) ? 0 : 10));

    return min({ret0, ret1, ret2, ret3});
}

int main() {
    // input
    cin >> N >> A >> B >> C;
    // REP(i, N) {
    //     cin >> num;
    //     vec.push_back(num);
    // }
    // vec をグローバル変数にしているため，以下の受け取り方の方がスマート
    vec.resize(N);  // vec のメモリを確保
    for(ll  i = 0; i < N; i++) cin >> vec[i];

    // calculation
    cout << recursion(0, 0, 0, 0, 0) << "\n";

    return 0;
}

少し再帰の気持ちが分かってきたような分かってこないような．DFS については以下の記事にまとめてみたので良かったらどうぞ．

pyteyon.hatenablog.com

類題

再帰(DFS)を使って解ける類題を挙げておく．

D - Lazy Faith

　D 問題は解くまでに至らなかったので反省は無い．強いて言うなら C が解けないと分かった時に D 問題を一瞬でも良いから見てみる良いと言う教訓を得た．

　解き直しで AC はできたが，正直 TL で「二分探索」という言葉を見なかったら解けなかったなと思った．自力 AC した汚い解法と，解説等を見て書いた綺麗な解法，両方を残しておく（自分の思考過程を残すため）．解法のみに興味がある方は綺麗な解法に飛ぶことを推奨．

二分探索に関しては以下を参照．

pyteyon.hatenablog.com

解法

汚い解法（汚いのでちゃんとした解法を見たい方は綺麗な解法へ）

まず考えたことは，

制約が $10^{5}$ なので $O(N) \ or \ O(NlogN)$ 以下だろう
クエリを挿入して左右を調べる -> $O(Q*N)$ で $(10^{5})^{2}$ を超える
配列に s, t の情報を持たせて重ねる -> $(10^{5})^{2}$ を超える
Twitter で二分探索って言ってたけどどこで使うんだ... 使いどころが分からん...
上記を考え終えたところで，神社，寺の各配列に対して境目を二分探索すればいいじゃないか．そうすれば， $O(Q * (\log A + \log B))$ くらいに収まりそう．
直近の座標二つを見るだけで十分．それより外に行ってもすでに直近二つは必ず通っている．

　上記により，境目を二分探索することにしたが，最後の二つまで絞ったときにどちらを選べば良いのか分からなかったため，探索範囲が 2 つになったところでその範囲の配列（大きさ 2 の配列）を返すように二分探索の関数を書いた（二分探索に必要な前処理のソートは入力がソート済みなので考えなくて良い）．

よって一つのクエリに対しての操作は，

神社，寺の配列をそれぞれ二分探索
二分探索によって，クエリの座標と近い座標を持つ範囲を絞った配列を神社，寺それぞれから得る
それらの位置関係によって距離の最小値を全探索

　計算量は，恐らく $O(Q * (\log A + \log B + 4))$ 程度（+4 は範囲を絞った配列から神社と寺の組み合わせを全探索 2 × 2）．

実装は以下（見たい方はソースコード展開をクリック）．

▶︎ソースコード展開

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>  // LLONG_MAX
using namespace std;
using ll = long long;

#define REP(i, n) for (ll i=0; i < n; i++)  // 0 ~ n-1
#define vl vector<ll>

template <typename T>
vector<T> BinarySearch(vector<T> &vec, T key) {
    if (vec.size() == 1) return vec;
    // key: 検索対象の値
    // T left = 0, right = (T)vec.size(), mid, idx_res;
    T left = 0, right = (T)vec.size()-1, mid, idx_res;  // ほんとうは番兵を N とおく
    while (left < right) {
        mid = (left + right)/2;
        if (right - left == 1) {
            vector<T> res = {vec[left], vec[right]};
            return res;
        } else if (key < vec[mid]) {
            // 半分より下
            right = mid;
        } else if (vec[mid] < key) {
            // 半分より上
            // left = mid+1;
            left = mid;  // これだと永遠に2つ以下に絞れない
        }
    }
    return {-1, -1};
}

int main() {
    // input
    ll A, B, Q;
    cin >> A >> B >> Q;
    vl Jin(A), Tera(B), Query(Q);
    REP(i, A) cin >> Jin[i];
    REP(i, B) cin >> Tera[i];
    REP(i, Q) cin >> Query[i];

    // calculation
    vector<ll> res_A, res_B;
    ll query, jin, ter, res;
    REP(i, Q) {
        query = Query[i];
        res_A = BinarySearch(Jin, query);  // size: 1 or 2
        res_B = BinarySearch(Tera, query);  // size: 1 or 2
        res = LLONG_MAX;
        REP(j, res_A.size()) {
            REP(k, res_B.size()) {
                jin = res_A[j];
                ter = res_B[k];
                if (query < jin && query < ter) {
                    // query が小さい
                    res = min(res, max(jin, ter) - query);
                } else if (query > jin && query > ter){
                    // query が大きい
                    res = min(res, query - min(jin, ter));
                } else {
                    // 間にあるとき
                    res = min(res, min(abs(query - jin), abs(query - ter)) + abs(jin - ter));
                }
            }
        }
        cout << res << "\n";
    }
    return 0;
}

　収束しない二分探索を書いてしまっている（範囲が二つまでしか絞れないため本来は無限ループに入るが，今回は探索範囲を絞るのは最後の二つまでで良いので都合が良い）ので良い解法ではないなと思ったけど，自力 AC できたので良かった．次に綺麗な解法でちゃんとした解法を学ぶ．

綺麗な解法

解説等を見ると，自分の解法も悪くない線だったということが分かった．ただ，

std::lower_bound を使う（クエリ以上の配列の要素のイテレータを返す）
配列外参照を見越し，神社，寺の左右に -INF，+INF の番兵を置くという考え方（自分は配列が参照が怖くて二分探索で一つに絞ることを避けた．結果的にふわっとした解法になった）

によりもっと簡潔にコードが書けることが分かった．以下綺麗()に書き直したコードを示す．

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
using ll = long long;

#define REP(i, n) for (ll i=0; i < n; i++)  // 0 ~ n-1
const ll INF = 1LL<<60;  // 10^8

int main() {
    // input
    ll A, B, Q, q;
    cin >> A >> B >> Q;
    vector<ll> Jin(A), Tera(B);
    REP(i, A) cin >> Jin[i];
    REP(i, B) cin >> Tera[i];
    Jin.push_back(INF); Jin.push_back(-INF);  // 番兵を追加してソート
    Tera.push_back(INF); Tera.push_back(-INF);
    sort(Jin.begin(), Jin.end());
    sort(Tera.begin(), Tera.end());

    // calculation
    REP(i, Q) {
        cin >> q;
        auto s = lower_bound(Jin.begin(), Jin.end(), q);
        auto t = lower_bound(Tera.begin(), Tera.end(), q);

        // 距離の最小値を求める
        vector<ll> ss = {*s, *prev(s)};
        vector<ll> tt = {*t, *prev(t)};
        ll res = INF;
        REP(j, 2) {
            REP(k, 2) {
                if (q < ss[j] && q < tt[k]) {
                    res = min(res, max(ss[j], tt[k]) - q);
                } else if (ss[j] < q && tt[k] < q) {
                    res = min(res, q - min(ss[j], tt[k]));
                } else {
                    // q が間にある
                    res = min(res, abs(tt[k]-ss[j]) + min(abs(tt[k]-q), abs(ss[j]-q)));
                }
            }
        }
        cout << res << "\n";
    }
    return 0;
}

　番兵を置くという考えは，正直解法を見た今も身についた気がしない．慣れが必要な気がする．とりあえず配列外参照が起こりそうな時に番兵を置くと良いことがある，ということはひとつここで覚えておきたい．

知見

問題を解く上での気持ち的な面

シミュレーションにおいて，操作を限界まで行なった後の状態がどうなっているかを考えると上手く解けることがある．
問題文を素直に受け取りすぎない．C 問題以降は問題文を素直に読んで愚直に実装しても問題は解けない．「結局どういう問題なのか」という落としこむ作業が大事．

技術的な面

x 以上，x より大きい数字を配列から探すときは二分探索で計算量を落とす
数値の境目を探すときは二分探索
配列外アクセスの可能性があるときは INF，-INF の番兵を置くと良い．
番兵を置く時のテクニックとして，無理に先頭，末尾に番兵を置こうとして配列のサイズを変えるのではなく，入力を終えてから vec.push_back(INF) として番兵を置いた後にソートすれば，入力のミスが減らせる（今回はソートされていたから気にしなくて良いがランダムに配列が与えられた時はこのテクが使える）（Python だとリストの連結が楽なので気にしなくて良い）．
n 個前のイテレータにアクセスする関数: std::prev(iter, n)（n を省略で一つ前のイテレータを返す）

などなど

std::prev

終わりに

ABC119 の C 問題は本当に苦しみました．精進あるのみ．

pyてよn日記

一寸先は闇が人生