ARC 009 (virtual) 解法

コンテストページ

AtCoder Regular Contest 009 - AtCoder

解法

✔A - 元気にお使い！高橋君

税抜価格を計算したら、105 を掛けて、100 で割ると良いです。

✔B - おとぎの国の高橋君

strig で管理します。数字の対応表と逆対応表を保持しておきます。これを用いて中身を書き換えたあと、サイズを push_front して辞書式比較でソートです。これが済んだらサイズは pop_front して、中身も戻しておきましょう。

✔C - 高橋君、24歳

お友達の集合 I に対して、I に属するお友達は全員ご配送がされてしまい、そうでないお友達には正しく届くような数を、a_I とおきます。すると答えは要素数が k であるような I に関する和です。

ここで、各 I に対して、その部分集合に関する a_I の和を、A_I と置きましょう。するとこれは、I に属さないようなお友達には正しく届き、I に属するお友達のことは知りませんの数ですから、階乗です。あとは、包除原理で足し合わせましょう。

お気持ち

mod = 1,777,777,777、これはなんですか？

私の mint がオーバーフローに十分に対応していませんでしたから、久々に職人が真心を込めて剰余を取りました。剰余に関しては普段からライブラリに頼り切りですから、いざ見放されてしまうと悲しくなってしまいます。

✖D - 覚醒ノ高橋君

考えたこと

全体が全域木である条件は、各市が全域木であることです。そこで、各市の全域木をすべて列挙しましょう。頂点数が 7 ですから、辺の数は 21 です。2 の 21 乗通り全探索です。これを市ごとに、別々の配列にソートして格納しておきましょう。

知りたいのは K 番目に大きい全域木ですから、最大のものから順に列挙していきましょう。各市が何番目に大きな全域木で出来ているかという配列を状態とするダイクストラ法で計算をします。K が 7,777,777 ですから、TL が 8 秒とはいえログが掛かると厄介です。しかし、キューに入る配列は高々市の数 A <= 77 ですから、ここにログは掛かりません。

しかし、すでに訪問した頂点はどのように管理をしましょう。ここに set を使っていたのですが、これでは間に合わなさそうです。