競プロ参戦記 #59 Coins Respawn | ABC 137

ABC-only 回です。E完でした。

珍しくEまで早く解けたのでFをやっていましたが、そもそも方針が間違っていたっぽくてダメでした。

AtCoder Beginner Contest 137

• この連載記事では、着手した問題の考察を自分なりに書いていきます。
  • 前回: 競プロ参戦記 #58 Max GCD | ABC 136
• 問題の詳細は問題一覧を参照してください。
  • 問題一覧: https://atcoder.jp/contests/abc137/tasks

A - +-x

問題概要: 整数 A, B が与えられる。A+B, A-B, A*B の中で最大の数を求めよ。

A: 考察

3つの式を実際に計算して比較すればよいです。std::cmp::max を使うと楽に書けます。

    max(A + B, max(A - B, A * B))

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

B - One Clue

問題概要: すべての整数 i に対して数直線上の i の位置に石が置かれている。ある連続する K 個の石は黒で塗られていて、それ以外は白で塗られている。座標 X の石は黒で塗られている。黒で塗られている可能性がある石の座標をすべて求めよ。

B: 考察

例えば K=3, X=4 のとき、石の塗り方の可能性は以下の3通りです。(B: 黒, _: 白)

    1 2 3 4 5 6 7 8
    _ B B B _ _ _ _
    _ _ B B B _ _ _
    _ _ _ B B B _ _

このとき黒である可能性があるのは 2, 3, 4, 5, 6 の5つ。

連続する K 個の石が黒で塗られているという条件から、X から距離 K 以上離れている石 (x≤X-K または X+K≤x) は白です。

逆にそれ以外の石 x (X-K < x < x + K) は、その石と X の間にある石をすべて黒に塗っても矛盾は生じないので、黒である可能性があります。

結局 X-K+1 以上 X+K-1 以下の範囲の座標を列挙すればよいです。

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

C - Green Bin

問題概要: N 個の文字列が与えられる。互いにアナグラムであるような文字列のペアを数えよ。

制約: N≤10^5

C: 考察

アナグラムは文字列が「文字の順番」を除いて等しいということなので、ソートすることで文字の順番も揃えてやれば普通の文字列の相等と同じになります。

具体的には、まず文字列を「ソートした結果が等しい」ものごとに分類します。ソートした結果が等しい文字列が n 個あるとき、どの2つもアナグラムとして等しいので、ペアは n(n-1)/2 個あります。

実装はマップを使うと楽です。ソートして分割するのも可。

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

ちなみに、わざわざ指摘されているにもかかわらずオーバーフローをやらかして1WAもらいました。0_i64 のように明記しなくても i64 か usize に推論されるケースがほとんどなので油断していた……

D - Summer Vacation

問題概要: N 件の日雇いアルバイトがある。i 番目のアルバイトを請けると、A(i) 日後に B(i) の報酬を得る。1日あたり最大1件のアルバイトを請けられる。1つのアルバイトは最大1回だけ請けられる。今日から M 日後 (M 日後も含む) までに得られる報酬の合計の最大値を求めよ。

D: 考察

直感的に、

• 報酬の受け取りが M+1 日後より後になるアルバイトは請けない
• A(i) が大きいアルバイトは後々請けられなくなるので先に請けたい
• なるべく報酬 B(i) が大きいアルバイトを請けたい

ということが分かります。

これは最終日から逆順に計画を立てると分かりやすいです。

• M-1 日後の時点では、A(i)≤1 のアルバイトのうち B(i) が最大のものを請けるのがベスト

他の日も同様です。「A(i)≤k のアルバイト」を B(i) に関して降順の優先度つきキューに入れて管理すると高速に処理できます。

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

E - Coins Respawn

問題概要: N 頂点 M 辺の有向グラフが与えられる。辺 i は C(i) の重みを持つ。頂点 1 から N に行くとき、通った辺の本数を T、重みの総和を S とするとき、max(0, S - T * P) のスコアを得る。スコアの最大値が存在するか判定し、存在するなら求めよ。

制約: N, M≤2500

E: 考察

最大値が存在しないというのがパット見ピンと来ませんが、以下のグラフで 2-3 のループを回れば回るほどスコアが大きくなるのであれば、最大のスコアというのは存在しません。

    1 --> 2 --> 3 --> 4
          ^     |
          |     |
          +-----+

はじめに、T * P の計算が厄介なので解消しましょう。通る辺を E(1), E(2), .., E(T) とおくと、S = ΣC(E(i))) と書けます。S - T * P = Σ(C(E(i)) - P) なので、C(i) からあらかじめ P を減じておけば T * P を消せます。

• C(E(i)) - P → C(E(i))
• S - T * P → S

いまスコアは max(0, S) です。スコアを求めるには、辺の重みの総和 S の最大値を求めればよいので、いまの問題は「最 長 経路問題」です。辺の重みを -1 倍すれば「最 短 経路問題」に変換できます。

重みが負である辺を含む単一始点の最短経路問題は Bellman-Ford アルゴリズムで解けます。

Bellman-Ford アルゴリズムは負閉路があるかどうかを検出できます。しかし入力例3で指摘されているように、頂点 1 から N までの経路上にない負閉路があっても、必ずしもスコア無限大にはならないので注意です。

この問題では頂点 1 から N への経路上にない頂点は使用されないので、そのような頂点をあらかじめ削除しておくことで対処できます。これは単純な BFS です。

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

ちなみに 本番で提出したコード は頂点 N に到達できない負閉路は削りましたが、頂点 1 から到達できない負閉路は削除してなかったので嘘解法でした。