1日9時間寝たい

本当は10時間寝たいです

ABC 141 D - Powerful Discount Tickets 解説

問題: D - Powerful Discount Tickets

問題概要

$N$ 個の商品の値段 $A_1, A_2, \dots, A_N$ と割引券の枚数 $ M $ が与えられる。$a$ 円の商品に $b$ 枚割引券を使うと $\lfloor a / 2^b \rfloor$ 円で買える。$N$ 個の商品をすべて買うために必要な金額の最小値を求めよ。

解法

まず、割引券をまとめて使うのと「$1$ 枚ずつ使う」のは同じです。つまり $\lfloor a / 2^b \rfloor = \lfloor \cdots \lfloor\lfloor\lfloor a / 2 \rfloor / 2 \rfloor \cdots \rfloor / 2 \rfloor$ です。これは任意の非負整数 $a$ と任意の正整数 $p, q$ に対して $\lfloor a / (pq) \rfloor = \lfloor \lfloor a / p \rfloor / q \rfloor$ が成り立つ *1 ことから帰納的にわかります。

そこで、次を $ M $ 回繰り返せば最適解を求められそうな気がします。

現時点で最高値の商品の値段を $1/2$ にする ($\diamond$)

実際にこれが最適であることを証明しましょう。

証明

なにはともあれ、求めたいものを式で表すことから始めます。
商品 $i$ に割引券を $Y_i$ 枚使うとします。このとき、$N$ 個の商品をすべて買うために必要な金額は $\sum_{i = 1}^N \lfloor A_i / 2^{Y_i}\rfloor$ です。これを $f(Y)$ とおきます。$Y$ が $\sum_{i = 1}^N Y_i = M $ を満たしながら動くときの $f(Y)$ の最小値を求めたいです。
($\diamond$) を実行した結果わかる割引券の配分を $B$ としましょう。商品 $i$ の値段を $B_i$ 回 $1/2$ にした、商品 $i$ に $B_i$ 枚割引券を使った、という意味です。$B$ が最適解であるとは、他のどんな割引券の配分よりも $f(B)$ が小さい (か同じである) ことです。

任意に割引券の配分をひとつ固定します。これを $C$ とします。 $f(C) \ge f(B)$ を示したいです。$C = B$ ならば明らかに成り立つので $C \not= B$ とします。
簡単のために

  • $B_1 > C_1$
  • $B_2 < C_2$

だとします。このとき $C' := (C_1 + 1, C_2 - 1, C_3, \dots, C_N)$ とおくと $f(C) \ge f(C') $ ($\star$) です。$C' = B$ ならば $f(C) \ge f(B)$ となり終わりです。$C' \not= B$ ならば同様のことを繰り返して $f(C) \ge f(C') \ge f(C'') \ge \dots \ge f(C^{\prime\prime\cdots\prime}) = f(B)$ が得られるので OK です。

($\star$) の証明

おおよそ次のような感じです。

  • 商品 $1$ が最高値のときに使える割引券がない
  • → 商品 $2$ に使っていた分の割引券を $1$ 枚持ってきて代わりに使う
  • → そのとき最終的に支払う合計金額は悪化しない

割引券を使う順番を $(\diamond)$ に沿うようにしてみます。
すると $B_1 > C_1$ より、最高値の商品を半額にするのを見逃してしまうタイミングがあります。正確には、

  • 商品 $1$ が現時点で最高値
  • これまでで、商品 $1$ に割引券を $C_1$ 枚使った (もう使える割引券がない)

というタイミングがあります。これが $t$ 回目に割引券を使う機会だとします。また、このときの

  • 商品 $1$ の値段: $x$ 円
  • 商品 $2$ の値段: $y$ 円

だとします。$x \ge y$ です。$t$ 回目以降の割引券を使う順番は、基本的にてきとうでよいですが最後 ($M $ 回目) は商品 $2$ に割引券を使うようにします。$B_2 < C_2$ なので商品 $2$ に使える商品券は時刻 $t$ の時点で少なくとも $1$ 枚余っていますから、これを取っておきましょう。

商品 $2$ に対する割引券がたくさん余ってる ($C_2$ が大きい) 状況を考えると、最後の割引券を使う直前で、商品 $2$ の値段は $\lfloor y / 2^k \rfloor$ の形をしています。これを $z$ とします。$y \ge z$ です。$M $ 回目は商品 $2$ に割引券を使うので、最終的には $\lfloor z / 2\rfloor$ 円になります。

商品ごと・時刻ごとの値段を表にしました。

全商品合計で割引券を使った回数 \ 商品 $1$ $2$
$t - 1$ $x$ $y$
$M - 1$ $x$ $z$
$M $ $x$ $\lfloor z/2 \rfloor$

割引券の配分が $C$ のとき・$C'$ のときに支払う合計金額を比べましょう。配分が $C'$ のときは

  • $1$ 回目 ~ $M - 1$ 回目に使う割引券: 配分が $C$ のときと同じ商品に対して使う
  • $M $ 回目に使う割引券: 商品 $1$ に対して使う

とします。このとき

  • $f(C) = \sum_{i = 1}^N \lfloor A_i / C_i\rfloor = \sum_{i = 3}^N \lfloor A_i / C_i\rfloor + x + \lfloor z / 2 \rfloor$
  • $f(C') = \sum_{i = 1}^N \lfloor A_i / C'_i\rfloor = \sum_{i = 3}^N \lfloor A_i / C_i\rfloor + \lfloor x / 2 \rfloor + z$

ですから、$f(C) - f(C') = \lceil x / 2\rceil - \lceil z / 2 \rceil \ge \lceil x / 2\rceil - \lceil y / 2 \rceil \ge 0$ となり、$f(C) \ge f(C')$ がわかりました。

類題

この問題 も似た流れで証明できると思います。

*1:証明は AtCoder 公式の解説 PDF https://img.atcoder.jp/abc141/editorial.pdf を見てください

「2 色で塗り分けられる」⇔「奇数長の閉路がない」の証明

グラフの話です。

簡単のために、グラフは連結で、多重辺や自己ループがないものとします。

用語の説明
  • 2 色で塗り分けられるとは、次の条件を満たすようにグラフの頂点を 2 色で塗る方法が存在することをいいます。
    条件:u と v が辺でつながっている ⇒ u と v は違う色
    たとえば
    • 四角形のグラフ: 4 頂点で辺が (1, 2), (2, 3), (3, 4), (4, 1) のグラフ は 2 色で塗り分けられます。具体的には、頂点 1, 3 を黒に、頂点 2, 4 を白に塗ればいいです。
    • 三角形のグラフ: 3 頂点で辺が (1, 2), (2, 3), (3, 1) のグラフは 2 色で塗り分けられません。
  • 奇数長の閉路とは、長さ (= 辺の数 = 通る頂点の種類数) が奇数である閉路をいいます。
    • 閉路とは、ある頂点からスタートして同じ辺を使わずに元の頂点へ戻ってくる経路をいいます。
      たとえば
    • 四角形のグラフには 1 → 2 → 3 → 4 → 1 という閉路があります。
    • 三角形のグラフには 1 → 2 → 3 → 1 という閉路があります。奇数長の閉路です。
    • Y のグラフ: 4 頂点で辺が (1, 2), (2, 3), (2, 4) のグラフには閉路がありません。

f:id:poyopoyoyon:20200507140009p:plain
三角形, 四角形, Y

2 色で塗り分けられる ⇔ 奇数長の閉路がない の使いみちとして、
奇数長の閉路がないかどうかを判定するかわりに
2 色で塗り分けられるかどうかを判定すればいいことになります。

実装例は DFS (深さ優先探索) 超入門! 〜 グラフ・アルゴリズムの世界への入口 〜【後編】 - Qiita を見てください。

証明
2 色で塗り分けられる $\Rightarrow$ 奇数長の閉路がない

こちらはカンタンです。
任意の閉路を取ります。← ここで、閉路がひとつもなかった場合、偶数長の閉路も奇数長の閉路もないため証明終わりです。
この閉路が偶数長の閉路であることを示せばいいです。
頂点番号を適当に付け替えて、閉路が 1 → 2 → ... ... → n → 1 であると考えていいです。
仮定より、2 色で塗り分けられるため、閉路内の各頂点の色は ○ → ● → ... ... → ● → ○ または、これを白黒反転させたものです。
よって 1 から n までに白と黒が同じ個数ずつ現れるため n は偶数です。

2 色で塗り分けられる $\Leftarrow$ 奇数長の閉路がない

d[v]: 頂点 1 から頂点 v までの最短距離 (通る必要のある最小の辺数) とします。

  • d[v] が偶数 ⇒ v を白に塗る
  • d[v] が奇数 ⇒ v を黒に塗る

とすれば条件を満たす塗り方になっています。
これを確かめるには

  • u, v: 白 ⇒ u, v が辺でつながっていない (☆)
  • u, v: 黒 ⇒ u, v が辺でつながっていない (★)

を示せばいいです。
まず (☆) を示しましょう。
u, v が白だとして、辺でつながっていると仮定します。(背理法です)
すると 1 → ... ... → u → v → ... ... → 1 という閉路ができます。
そして、この閉路の長さは d[u] + 1 + d[v] です。
d[u] + d[v] は偶数なので d[u] + 1 + d[v] は奇数です。
これは奇数長の閉路がないことに矛盾します。
よって (☆) がわかりました。
(★) も同じようにして証明できます。

f:id:poyopoyoyon:20200507150619p:plain
(☆)

おわりです。

Slash Command に対して 3 秒以上かかる処理をする

はじめに

Slash Command は Slack の機能のひとつです。デフォルトでは /remind/invite などがあります。

このようなスラッシュ / から始まるコマンドは自作することもできます。たとえば、あいさつするコマンド:

  • /greet 太郎 と打つと
  • 「こんにちは、太郎。」と返ってくる

を作れます。

Slash Command は、たとえば HTTP をトリガーに起動する Google Cloud Functions を用意して、Slack からのリクエストが来たら適当にレスポンスを返せばいいです。イメージとしては下の図です。

f:id:poyopoyoyon:20200319191124p:plain

しかし、レスポンスは 3 秒以内にしなければいけません*1

それでは、Cloud Functions で時間のかかる処理を行うにはどうすればいいのでしょう?

結論

解決方法のひとつは Slack Tutorial - Slash Commands  |  Cloud Functions Documentation で言及されているように Google Cloud Pub/Sub を使うことです。Slack からのリクエストを受け取る関数とは別にもう一つ関数を用意して、重い処理をそちらに任せます。

この記事では、上の /greet コマンドを

  1. Cloud Functions のみで実装
  2. Cloud Functions + Cloud Pub/Sub を使って実装

します。

たかが /greet コマンドに (2) の方針を採るのは正直大げさすぎますが、ソースコードの例をシンプルにしたいので /greet コマンドで説明します。

この記事の内容は、以下の [1], [2], [3] から少しづつ拾い集めただけなので、お急ぎの人はリンク先を追ってください。

Cloud Functions

実装と言っても、ソースコードは以下の 4 行で終わりです。

exports.greet = (req, res) => {
    const name = req.body.text;
    res.status(200).send("こんにちは、" + name + "。");
}

マウスをカチカチするパートはだいたい次のような感じです。

ここまでで、Slack で /greet 太郎 と打つとすぐに「こんにちは、太郎。」と Bot が返信するようになりました。

Cloud Functions + Cloud Pub/Sub

図を示します。

f:id:poyopoyoyon:20200319193003p:plain

「わかった」と返信する部分は簡単です。

新しく知るべきことは主に次の 3 つでしょう。

  1. Cloud Pub/Sub にデータを送る方法
  2. Cloud Pub/Sub からデータを受け取る方法
  3. Slack にあいさつを投稿する方法

(a) と (b) は [3]Quickstart: Using Client Libraries  |  Cloud Pub/Sub Documentation を見るとわかります。

(b) のために Cloud Pub/Sub をトリガーとする Cloud Functions を新しく作りましょう。いえ、その前に topic を作る必要があります。それっぽい箇所を Google Cloud Platform のコンソールから探してください。ここでは my-topic と名前を付けました。

f:id:poyopoyoyon:20200319201301p:plain
topic を作る

Function を作ります。[トリガー] は Pub/Sub、[トピック] は my-topic とします。

f:id:poyopoyoyon:20200319201533p:plain
Pub/Sub をトリガーとした Function を作る

(c) は [3] を見ると、コマンドが実行されたときに Slack から /greet 太郎 と一緒に https://hooks.slack.com/commands/1234/5678 のような URL が送られてくるとわかります。この URL に対して POST リクエストをすればよいです*2

実装です。

  • Publisher
const {PubSub} = require("@google-cloud/pubsub");
exports.publish = (req, res) => {
    const pubsub = new PubSub();
    pubsub.topic("my-topic").publish(
        Buffer.from(JSON.stringify(req.body)));
    res.status(200).send("あとであいさつを返します。");
};
  • Subscriber
const fetch = require("node-fetch");
exports.subscribe = pubsubMessage => {
    const data = JSON.parse(Buffer.from(pubsubMessage.data, "base64"));
    fetch(data.response_url, {
        method: "POST",
        headers: {
            "Content-Type": "application/json"
        },
        body: JSON.stringify({
            text: "こんにちは、" + data.text + "。"
        })
    });
};

注意点として、@google-cloud/pubsub などの package を使うために package.jsondependencies のところを以下のように編集してください。

f:id:poyopoyoyon:20200320112229p:plain
package.json

動作例です。