競プロ参戦記 #80 Two Currencies | ABC 164 #AtCoder

AtCoder Beginner Contest 164 に参加したので、A-E問題の考察を書いていきます。結果はD完でした。

前回: 競プロ参戦記 #79 Active Infants | ABC 163
問題一覧: https://atcoder.jp/contests/abc164/tasks

A - Sheep and Wolves

問題概要: 狼の数が羊の数以上のとき、羊は狼に襲われる。いま、羊が S 匹、狼が W 匹いる。羊が狼に襲われるか判定せよ。

A: 考察

羊の数 S と狼の数 W を比較すればいいです。「以上」は「等しい、または大きい」という意味で、「＝」の場合も含みます。

    let is_unsafe = W >= S;
    println!("{}", if is_unsafe { "unsafe" } else { "safe" });

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc164/submissions/12342639

B - Battle

問題概要:

高橋君と青木君はそれぞれモンスターを1体持っている。
高橋君のモンスターは体力が A、攻撃力が B である。
青木君のモンスターは体力が C、攻撃力が D である。
一方のモンスターが攻撃すると、その攻撃力の分だけ、他方のモンスターの体力が減る。
自分のモンスターが相手より先に体力 0 以下になったら負けとする。
高橋君のモンスターから始めて、両者のモンスターが交互に攻撃しあうとき、どちらが勝つか判定せよ。

制約: 1≤A, B, C, D≤100

B: 考察

実際に各攻撃後のモンスターの体力を計算すればいいです。

    let takahashi_win;

    loop {
        // takahashi
        C -= B;
        if C <= 0 {
            takahashi_win = true;
            break;
        }

        // aoki
        A -= D;
        if A <= 0 {
            takahashi_win = false;
            break;
        }
    }

    println!("{}", if takahashi_win { "Yes" } else { "No" });

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc164/submissions/12339507

C - gacha

問題概要: くじ引きを N 回行った。i 回目に得られた景品の種類は S(i) である。得られた景品の種類数を求めよ。

制約: N≤2×10^5, |S|≤10

C: 考察

S の重複を除いて件数を数えればいいです。

重複を除くには、集合 std::collections::HashSet に入れる、ベクタに入れて sort + dedup する、などの方法があります。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc164/submissions/12332138

D - Multiple of 2019

問題概要:

1 から 9 の数字からなる長さ N の文字列 S がある。
整数のペア (l, r) (1≤l≤r≤N) で、S の l 文字目から r 文字目までを10進数の整数とみなした値が 2019 の倍数であるようなものの個数を求めよ。

制約: N≤2×10^5

D: 考察

この問題は ABC 158 E - Divisible String とほぼ同じです。「素数 P」が 2019 に置き換えられ、文字列 S に数字 0 が含まれないという制約が追加されています。

2019 は素数ではありませんが、10 と互いに素なので全く同じ考察が通用します。

筆者の提出 (Rust, AC): https://atcoder.jp/contests/abc164/submissions/12355837

E - Two Currencies

問題概要:

N 個の都市がある。x 番目の都市では、金貨1枚を C(x) 枚の銀貨に両替できて、両替には D(x) 分かかる。
鉄道路線が M 本ある。y 番目の路線は都市 U(y) と V(y) を双方向に結んでいて、銀貨 A(y) 枚の運賃で乗車でき、片道 B(y) 分かかる。列車の待ち時間はゼロとする。
各都市 t (2≤t≤N) に関して、次のクエリに答えよ:
- はじめ、あなたは都市 1 にいて、金貨を 10^100 枚、銀貨を S 枚持っている。
- 鉄道路線を使ってなるべく早く都市 t に移動するとき、かかる時間の最小値を求めよ。

制約:

2≤N≤50
0≤S≤10^9
1≤A(i)≤50
1≤B(i)≤10^9
1≤C(i)≤10^9
1≤D(i)≤10^9
都市を点、鉄道路線を辺とする無向グラフは連結であり、自己辺や多重辺を持たない。

E: 考察

かかる時間を距離と読み替えると「非負の距離からなる単一始点の最短経路問題」なので、ダイクストラ法で解けそうです。しかし両替システムがあるので、ダイクストラ法をそのまま使うことはできません。

というのも、経路には「どの都市に、どのくらいの時間で行けるか」だけでなく「その都市についた時点で、どのくらいの銀貨を所持しているか」というパラメータもあり、最短経路が1つに定まらないからです。

例えば都市 1 から別の都市に行く2つの経路があって、

片方は移動に 10 分かかって、所持銀貨が 0 枚になる (早い)
他方は移動に 20 分かかって、所持銀貨が 200 枚になる (安い)

とするとき、どちらが良いとはいえません。そのためダイクストラ法の「各都市への最短経路を短い順に確定していく」手法が通用しなくなります。

他の経路より明らかに劣る経路、つまり「かかる時間が長く、しかも所持銀貨が少ない」ような経路は捨てることができます。そのため、各都市への経路の最良は1つに決まらなくても、「この都市に、これだけの所持銀貨を持って到着する経路」の中での最良は1つに決まります。行き先と所持銀貨が同じなら、移動時間が短くなる経路が最良です。

そして実は「都市数」×「所持銀貨」はあまり大きくなりません。(50^3 ぐらいで抑えられます。)

1つの都市を2回訪れるような移動経路は無駄なので、移動回数は N-1 以下です。
制約 A(i)≤50 (= 運賃は銀貨50枚以下) から、運賃として支払う金額の最大は 50・(N-1) ≤ 50・49 = 2450 枚です。この上限を超える所持銀貨は最後まで余るので、途中で捨てても結果は変わりません。
そのため所持銀貨は 2450 枚以下としてよいです。

したがって、(都市, 所持銀貨) を頂点、路線を辺とするグラフを構築してダイクストラ法を使うことにより、各都市への最短経路を求めればよいです。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc164/submissions/12432756

ちなみに本番では A(i)≤50 に長いこと気づかず、どこで両替するかに注目していて、例えば Floyd-Warshall で u→w→v の最短経路を「u→w の良い経路を通って、w で両替して、v→w の良いを通る」のようなかたちで再構成できないかとか、問題設定が似ている Travel By Car の変形で解けないか、みたいな方針を考えていました。