競プロ参戦記 #34 Lazy Faith | ABC 119 #C++

AtCoder のプログラミングコンテスト ABC 119 に参加しました。先週に引き続き ABC-only 回です。

競プロ参戦記

この連載記事では、着手した問題の考察を自分なりに書いていきます。

問題文はリンク先を参照してください。
筆者の回答は、特に断りがなければ Rust (1.15.1) で書いています。入力のパースに自作マクロを使っています。
前回: 競プロ参戦記 #33 Match Matching | ABC 118 - Qiita

AtCoder Beginner Contest 119

問題一覧: https://atcoder.jp/contests/abc119/tasks

A - Still TBD

問題概要: 日付が yyyy/mm/dd 形式で与えられる。この日付が 2019/04/30 以前なら "Heisei" を出力し、そうでなければ "TBD" を出力せよ。

考察: 日付を比較せよという問題ですが、文字列を単純に辞書式順序で比較すればいいです。

辞書式順序とは、辞書の中に単語を並べるときの順序のことですが、簡単にいうと文字列の大小関係を最初に異なる文字の大小で決めるものです。

例えば "2019/02/24" と "2019/04/30" では、最初に異なる文字は 2, 4 であり '2' < '4' なので全体としては "2019/02/24" < "2019/04/30" という関係になります。

また、 "2018/12/31" と "2019/04/30" なら '8' < '9' なので "2018/12/31" < "2019/04/30" と判定できます。年月が一致するケースも同様です。

筆者の回答 (AC): https://atcoder.jp/contests/abc119/submissions/4370948

// 抜粋

fn main() {
    let S = rl(); // 与えられる文字列

    println!("{}", if S.as_str() <= "2019/04/30" { "Heisei" } else { "TBD" })
}

B - Digital Gifts

問題概要: N 個のお年玉が与えられる。i 番目のお年玉は数 x と単位 u の組み合わせからなり、u は JPY または BTC である。ただし 1 BTC = 380000 JPY と換算できる。お年玉の総額を JPY 単位で求めよ。

考察: B問題にしばしばある「言われたとおりに書け」系の問題です。

筆者の回答 (AC): https://atcoder.jp/contests/abc119/submissions/4370545

C - Synthetic Kadomatsu

問題概要: N 本の竹がある。i 番目の竹の長さは l_i である。竹に以下の操作を適用して、長さが A, B, C である3本の竹を作るとき、かかるコストの最小値を求めよ。

延長 (コスト 1): 1つの竹の長さを 1 増やす。
短縮 (コスト 1): 1つの竹の長さを 1 減らす。
連結 (コスト 10): 2つの竹を連結して1本にする。(長さは和になる。)

考察: 問題文をざっと読むと、最終的に竹が3本になるまで連結しなければいけないように読めますが、入力例を見ると余った竹があってもいいそうです。

また、制約 N ≤ 8 を見ると、計算量が O(2^N) などの指数オーダーになるようなアルゴリズムが許されることが分かります。

操作をみると、3つ目の連結でどの竹とどの竹を連結すればいいのかの判断が難しそうですが、これは全探索できます。つまり、竹 A を作るためにどの竹の集合を使うのか、というのは O(2^N) 時間ですべて列挙できます。同様に B, C を構成する竹の集合もすべて列挙してしまえば、連結操作について考える必要はなくなります。

この探索には全体で O(8^N) 時間かかりますが、 8^8 ≒ 1600万回程度のループに2秒もかからないので大丈夫です。

1本の竹を特定の長さにするのは、長さの差だけ延長か短縮を繰り返すだけなので簡単です。

結局、疑似コードで書けばこういう手続きになります:

    N: 竹の本数
    T: 竹のリスト

    min_cost = ∞
    for each a: 竹の集合
        for each b: 竹の集合
            for each c: 竹の集合
                if 集合 a, b に共通部分がある: continue
                if 集合 b, c に共通部分がある: continue
                if 集合 c, a に共通部分がある: continue

                min_cost ← min(min_cost,
                    (a を長さ A の竹にするコスト)
                    + (b を長さ B の竹にするコスト)
                    + (c を長さ C の竹にするコスト))
    出力 min_cost

筆者の回答 (AC): https://atcoder.jp/contests/abc119/submissions/4369593

D - Lazy Faith

問題概要: 数直線上に A 個の神社と B 個の寺と Q 個の位置がある。i 番目の神社は位置 s_i にあり、i 番目の寺は t_i にあり、q 番目の位置は x_q にある。各位置 x_q につき、そこから移動していずれかの神社といずれかの寺に行くとき、最小の移動距離を求めよ。

考察: この問題だけは C++ で回答を書いています。はじめはいつもどおり Rust で書いていましたが、どうしても TLE が取れなかったので C++ で書き直しました。みたところ Rust で普通に通っているみたいなので、何かを書き間違えていたかもしれません(?)

問題文を読むと、開始位置の近くにある神社と寺に行くのがよさそうに思えます。実際、開始位置のすぐ左とすぐ右にある神社や寺以外に行く必要があるケースはありません。このことを以下に確認します。

仮に、開始位置の右にある2つ目の神社に行くことになったとします。(これが寺でも、左側でも、同様です。) このとき寺がどこにあっても、1つ目の神社にいけば十分です。

開始位置 → 神社 → 神社

寺が開始位置より左なら、右の1つ目の神社で引き返したほうがいい
開始位置と1つ目の神社の間なら、右の1つ目の神社で止まればいい
1つ目と2つ目の神社の間なら、寺で止まればいい
2つ目の神社より右なら、1つ目の神社を通ることになるので、2つ目の神社について考える必要はない

したがって、大筋としては以下のようにできます。

開始位置の左右にある神社と寺を計算する。(左側に神社がないケースに注意。)
2つの神社と2つの寺について、そこに行くときのコストを計算する。
最小のコストを答えとする。

この手続きを 10^5 回ぐらい繰り返すことになるので、「開始位置の左右にある神社と寺を探す」には二分探索などの方法で高速化する必要があります。

二分探索はバグりやすいので個人的に書きたくないんですが、開始位置のリストを事前にソートしておくと二分探索を書かなくて済みます。具体的にはこうします:

まず「開始位置の右にある神社の番号」(右に神社がなければ A)という値を si とおき、変数に入れます。1つ目の開始位置 (最左の開始位置) について、si は線型探索します。
ループが進んで2つ目の開始位置について考えるとき、si はいくらか大きくする必要があります。小さくする必要はないというのがポイントです。例えば位置 100 から見て右にある神社と、位置 200 から見て右にある神社なら、後者のほうが右にある (あるいは同じ) ということです。ここでも si は線型探索しますが、前のループでの si の値から探索を開始できます。
すべて開始位置について処理を行った後、変数 si は最大で 10^5 回変更されるだけなので、全体として「開始位置の近くにある神社」を 10^5 回程度の計算で列挙できたことになります。

筆者の回答 (AC, C++): https://atcoder.jp/contests/abc119/submissions/4376343

ちなみに TLE したのはこれ:

筆者の回答 (TLE, Rust): https://atcoder.jp/contests/abc119/submissions/4375879