Never Ending Journey [第七回 アルゴリズム実技検定 J]

https://atcoder.jp/contests/past202107-open/tasks/past202107_j

前提知識

• DAG判定、トポロジカルソート

解説

https://atcoder.jp/contests/past202107-open/submissions/24466589

問題を簡単化しよう

都市を頂点、道路を有向辺と捉えると、全体が有向グラフの形をとる。
このように変換して考えたときに、今回の問題はループの構造がどこかにあればいくらでも旅行できるし、
そうじゃないなら旅行できないことになる。

実はこのループを持つかという問題は有名問題である。

DAG判定

有向グラフがループを持つかという部分は結構色々な所で出てくる問題で、このあたりを掘ると関連問題は多い。
ここにも色々ありますが、DAG判定あたりは初級編として良い題材と思う。

DAGというのはループが無い有向グラフのことである。
Directed acyclic graphの略なのでそのまんま。
よって、DAGであるかどうかを判定できれば、それが問題で要求されていることそのままとなる。

どうやって判定するか

競技プログラミング的にはDAG判定だけできるよりも、トポロジカルソートを学ぶ方が一石二鳥だと思うので、
トポロジカルソートを学ぶことをお勧めする。

毎回アルゴリズムを詳解していくとしんどいので、どこかで学んできてと毎回書いているが、それだと本当に今回書くことがないので、
一応オススメ資料を紹介しておく。
https://www.slideshare.net/hcpc_hokudai/topological-sort-69581002

2手法紹介されていて、どちらでも良い。
自分はdfsで実装したものをライブラリ化している。
トポロジカルソートをする過程でDAGじゃないことが判明したらDAGじゃないですよと返す実装。

多分DAG判定でググるよりもトポロジカルソートでググるほうが、競技プログラミング的な記事は多いと思う。
その辺で学んでみてほしい。
その辺が分かれば、この問題はライブラリ整備確認の問題となる。

int N, M;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;

    TopologicalSort ts(N);
    rep(i, 0, M) {
        int a, b; cin >> a >> b;
        a--; b--;
        ts.add_edge(a, b);
    }
    
    vector<int> ord;
    rep(i, 0, N) ord.push_back(i);
    auto res = ts.sort(ord);

    cout << (res ? "No" : "Yes") << endl;
}

Line Chart [第七回 アルゴリズム実技検定 H]

https://atcoder.jp/contests/past202107-open/tasks/past202107_h

前提知識

• 動的計画法

解説

https://atcoder.jp/contests/past202107-open/submissions/24466156

多次元のDPをくみ上げていく。
問題設定的にはいかにもDPっぽいという感じではあるが、慣れないうちはDPテーブルの定義に戸惑うかもしれない。

なぜDPっぽい？

正直見た瞬間にDPを考え始めたので、類題を見たことがあるのだろうと思う。
と書いてもしょうがないので、すこし想像して書いてみる。

最小値を求めるという所からまずDPを考え始めた。
先頭から数を決めていくDP的な考え方をしてみると、まとめられそうな状態は総和の値と最後の値は何かという部分である。
ここでちょうど総和の上限が100であることに気が付く。
いかにもDPに収めるための条件のように見えるので、方針に自信がつき、答えとしてまとめ上げていく…

DPテーブル

DPはDPテーブルを作る所までが折り返し地点。
以下のようにテーブルを用意しよう。

dp[i][rest][lst] := i番目の要素まで確定していて、総和として残っている数がrestで、最後に選択された数がlstであるときの距離の総和の最小値

それぞれの状態数の上限が100なので、状態数だけで10⁶通りとなる。
遷移は総和の上限が100なので、選択できる数も最大100となり、遷移数は10²通りで済む。
よって、全体の計算回数は10⁸回くらいになるので、計算が軽くなりがちなDPにとっては全く問題ない計算となる。

ホントに間に合う？

実は、今回はdoubleの計算となるので、ちょっと気を付けないといけない気がする。
計算の一番深い所で距離計算をする必要があり、平方根の計算が必要になる。
この計算量で、平方根の計算が必要になるのはちょっと怖いので、この部分を前計算しておくことにする。

dist[from][to] := (i, from)と(i+1, to)の距離

これは前計算しておくのは計算量的には全く問題ないので、距離計算を毎回するのではなくこの配列を使用することで、
高速化をしておこう。

注意点として、最初と最後は0になるので、その辺をうまいことやること。
DP作れるならば、このあたりはあまり問題ではない気もする。

int N, A[101];
double dp[101][101][101];
double dist[101][101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    int tot = 0;
    rep(i, 0, N) tot += A[i];

    rep(from, 0, tot + 1) rep(to, 0, tot + 1) dist[from][to] = sqrt((from - to) * (from - to) + 1);

    rep(i, 0, N + 1) rep(rest, 0, tot + 1) rep(lst, 0, tot + 1) dp[i][rest][lst] = inf;
    dp[1][tot][0] = 0;
    rep(i, 1, N - 1) rep(rest, 0, tot + 1) rep(lst, 0, tot + 1) if (dp[i][rest][lst] < inf) {
        rep(nxt, 0, rest + 1) {
            chmin(dp[i + 1][rest - nxt][nxt], dp[i][rest][lst] + dist[lst][nxt]);
        }
    }

    double ans = inf;
    rep(lst, 0, tot + 1) chmin(ans, dp[N - 1][0][lst] + dist[lst][0]);
    printf("%10f\n", ans);
}

Power Expression [第七回 アルゴリズム実技検定 G]

https://atcoder.jp/contests/past202107-open/tasks/past202107_g

解説

https://atcoder.jp/contests/past202107-open/submissions/24465845

何から始めるか

このような構築問題は、慣れないうちは何から始めていいか分からないと思う。
とりあえずいくつか方針を立ててみて、実験してみて、それっぽい方針を実装していくしかない。
…という説明も不親切なので、もう少し説明を試みる。

構築問題のテクの1つとして、ある一定のルールで構築していくという方針がある。
このときに定義するルールはなるべく簡単なルールで、実装しやすいものが望ましい。
この「ルール」というのも結構傾向があり、今回もよく見るようなルールで構築をしていく。

ルール

今回は、1, -1, 3, -3, 9, -9, 27, -27, ...といった数が使える。
この候補からどの数を最初に使うかという場面で「毎回、答えに最も近づくものを選択する」というルールで数を選んでいくことにしよう。
例えば、21を作りたい場合、0から21に最も近づくためには、一旦超えてしまうが、27を選択するのが最も良い。

0 -> 27

次に最も近づくのはどれだろう。

9 : 27 -> 36
-9 : 27 -> 18 差分が3
3 : 27 -> 30
-3 : 27 -> 24 差分が3
1 : 27 -> 28
-1 : 27 -> 26

2つ候補がある。どちらを使うべきだろうか？
条件に選択される数が被ってはいけないという条件がある。
答えとの数の差が狭くなっていくにつれて、絶対値が小さい数が重宝されそうなのは想像がつくので、なるべく大きい方を採用することにする。
今回は-9を使う

0 -> 27 -> 18

あとは、+3を使えば21が、差分が最も小さくなって達成。

0 -> 27 -> 18 -> 21

振り返ると、正確にルールを定義すると以下のようになる。

• 毎回、答えに最も近づくものを選択する
• 同着になった場合は絶対値が大きい方を採用する

これで本当に大丈夫？

自分は証明スキルを持ってないので証明してないのですが、強い人は証明してるらしいので、するのがオススメです。
再帰的帰納法とかで証明できるんじゃないかな？
競プロ的には未証明でも、確度が高ければ突っ込む戦略もありかなと思います（俗にいうACをもってQ.E.D.とする証明AC）

実装時は

実装時には0からNを目指すのではなく、Nから足し引きをして0を目指すように実装している。
なので、答えとして採用するときは逆から計算しているので、正負が逆になって答えとして記録している。

あと、ルールの性質上選択される数は絶対値が単調減少していくので、候補をすべて確認するのではなくて、
候補を絶対値が大きい方から見ていって、使うことで答えに近づくなら使うという方針で実装している。
このような方針と実装は構築問題では、ある種の貪欲法としてよく見られるので、覚えておくといい。

なお…

この問題は平衡3進法として有名ではあり、類題もいくつかあるので、練習してみよう。
競技プログラミングにおける数学的問題まとめ - はまやんはまやんはまやん

ll N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    vector<ll> cand;
    ll x = 1;
    while (x <= 2e15) {
        cand.push_back(x);
        x *= 3;
    }
    reverse(all(cand));

    vector<ll> ans;
    fore(a, cand) {
        if (abs(N + a) < abs(N)) {
            N += a;
            ans.push_back(-a);
        } else if (abs(N - a) < abs(N)) {
            N -= a;
            ans.push_back(a);
        }
    }

    int M = ans.size();
    printf("%d\n", M);
    rep(i, 0, M) {
        if(i) printf(" ");
        printf("%lld", ans[i]);
    }
    printf("\n");
}

Double Booking [第七回 アルゴリズム実技検定 F]

https://atcoder.jp/contests/past202107-open/tasks/past202107_f

解説

https://atcoder.jp/contests/past202107-open/submissions/24465658

判定を効率化する問題。
大変そうに見えるが、特に大きなひねりはなく、愚直に実装すれば間に合う。
慣れている人はimos法が思い浮かぶかと思うが、実際は必要ない。
（必要ないが、使えばそこそこ早くなる）

日付毎に判定していく

今回は、日付をまたいだ予定というのはない。
なので、日付毎に予定が被っているかを判定して、一つでもかぶっていればyesだし、1つもないならnoである。

まずは日付毎に予定を分ける作業が必要であるが、自分はこの部分をmapにvectorを載せることで実現した。

days[d] := d日目の予定であり、{開始時間,終了時間}の集合

というデータ構造を用意することにする。
ここで、{開始時間,終了時間}としているが、開始時間と終了時間が同じでも時間としてはかぶっていないように考えるので、
半開区間、つまり、「開始時間≦hour＜終了時間」、記号的には「[開始時間,終了時間)」のように考えることにする。
競技プログラミングではこのように半開区間にすると色々扱いやすい場合が多い。（慣れかもしれないけど）

このデータ構造が作れれば、イテレータで日付別に取り出せるので、各日について重複判定をして、重複しているならyesとする。

重複判定

日付はもう関係ないので、区間の集合があったときに重複しているかをcheckDuplication関数で判定していく。
区間が0～24の範囲しかないので、適当に実装すれば間に合う。
具体的には以下のような配列を用意して、使用されている区間を数え上げていく。

book[h] := 時間hが予約されている件数

普通にループで件数を足していき、最後に2件以上予約されていれば、被っていることになる。
これでAC。

int N, D[101010], S[101010], T[101010];
//---------------------------------------------------------------------------------------------------
#define yes "Yes"
#define no "No"
bool checkDuplication(vector<pair<int, int>> ranges) {
    vector<int> booked(24);
    fore(range, ranges) rep(h, range.first, range.second) booked[h]++;
    rep(h, 0, 24) if (1 < booked[h]) return true;
    return false;
}
//---------------------------------------------------------------------------------------------------
string solve() {
    map<int, vector<pair<int, int>>> days;
    rep(i, 0, N) days[D[i]].push_back({ S[i], T[i] });

    fore(p, days) if (checkDuplication(p.second)) return yes;
    return no;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> D[i] >> S[i] >> T[i];
    cout << solve() << endl;
}

Aoki's Trick [第七回 アルゴリズム実技検定 E]

https://atcoder.jp/contests/past202107-open/tasks/past202107_e

解説

https://atcoder.jp/contests/past202107-open/submissions/24461067

この問題は勘がいい人だと3進数を利用したような問題だなと感じるかもしれない。
それが見えてれば比較的見通しのいい問題になったかもしれない。
だが、3進数が分からなくても操作を逆から行えることに気が付けば、問題を同様に解くことができる。

操作を逆から行う

足し算も掛け算も逆操作が行えるので、以下のように操作を逆に見ていくことにしよう。

Nという値に対して30回3で割るという操作を行う。
操作前に1度だけ1で引くということが行えるとしたときに、適切に1で引いて最終的に1にできるか確認する。

これをやっていこう。

3で割る操作を行うときは、切り捨てを行ってしまうと逆計算として成立しないので、3の倍数のときに3で割る必要がある。
よって、操作を行うときに数を3で割った余りで見て、0なら何もせずに3で割って、1なら1を引く操作をして、2なら不正な状態と判定づけることができる。
これを判定しながら割りながら引きながらやっていけばいい。

ただ、1で引く操作は1回しかできないので複数回出てきたら-1と応答すべきだし、最終的に数が1にならなければ何かがおかしいので-1と応答する。
queryは最初が30回目となるので、30から1まで減らしていくようなループでやっていくと、そのまま回数を答えることができる。

ll N;
//---------------------------------------------------------------------------------------------------
int solve() {
    int ans = -1;
    rrep(query, 30, 1) {
        if (N % 3 == 0) N /= 3;
        else if (N % 3 == 1) {
            N /= 3;
            if (ans < 0) ans = query;
            else return -1;
        }
        else { // N % 3 == 2
            return -1;
        }
    }
    
    if (N != 1) return -1;
    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    cout << solve() << endl;
}

Replace [第七回 アルゴリズム実技検定 D]

https://atcoder.jp/contests/past202107-open/tasks/past202107_d

解説

https://atcoder.jp/contests/past202107-open/submissions/24466988

ちょっと考察、ちょっと実装の問題。

操作回数が最大となる操作

ここがまず1つ考察が必要な部分である。
今回は実は最適戦略があり、先頭から変換できるならば変換していくのが最も良い。
先頭から順にという部分が重要で例えば、axaxaxaの場合は真ん中で消すと損してしまうからである。
先頭から消せば最適なのかという問いについては、はっきりとした証明で答えることはできないのだが、
今回考慮するべき状況はaxaxaxa...のような?x?xの状況だけであり、この状況に限っては先頭を消さずに残すことで
それ以降有利になることはない、逆に言うと、先頭が残っている状態は消した場所を先頭に移すことでより良い状態に
遷移可能であるため、最適である。
（言葉を重ねた所でっぽいくらいの説得力しかないかも）

実装

よって、あとは消せるだけ消すを実装する。
stringから部分文字列を抜き出すときは、substrを使えばいい。
それでpatternと一致するものがあれば、3文字分を.に変換するという実装をしている。
一行で書いているので、見にくいかもしれないが、パターンに合致すれば...に変換するということをしているだけ。

int N; string S;
string patterns[] = { "axa","ixi","uxu","exe","oxo" };
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;
    rep(i, 0, N) fore(pattern, patterns) if (S.substr(i, 3) == pattern) S[i] = S[i + 1] = S[i + 2] = '.';
    cout << S << endl;
}

Validation [第七回 アルゴリズム実技検定 C]

https://atcoder.jp/contests/past202107-open/tasks/past202107_c

解説

https://atcoder.jp/contests/past202107-open/submissions/24460011

要求されている判定を行う実装問題。
自分の実装では色々な工夫をすることで、なるべく実装を減らしている。

まずSの長さの最大値が100であるが、Rの最大値が10⁹で、先頭の0も認められないので、
文字数は11文字以上であれば必ず条件を満たさないことが分かる。
よって、文字数が11文字以上ならばとりあえずNoとしていい。

そうすると、文字列Sを数値に変換するときにlong longに収まる範囲になるので、stoll関数を使って文字列を数に変換する。
数になっていると大小関係の比較がしやすいので、[L,R]の範囲にあるかどうかを効率よく判定できる。

面倒な判定が、先頭に不要な0があるかどうかである。
自分は数に変換した後改めて文字列に直したときに全く同じ文字列になれば先頭な0が無いと判断する実装を行った。
先頭が0であるかどうかを判定基準としてもいいのだが、S=0のときにちょっと場合分けが必要となるので注意。

string S;
int L, R;
//---------------------------------------------------------------------------------------------------
#define yes "Yes"
#define no "No"
string solve() {
    if (11 <= S.length()) return no;

    ll n = stoll(S);

    // 先頭に不要な0があったのでダメ
    if (to_string(n) != S) return no;

    if (L <= n && n <= R) return yes;
    return no;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S >> L >> R;
    cout << solve() << endl;
}