MIS.W新歓コンテスト2020 - SABAKAN FEVER
概要
東京23区の地図(とそれぞれの隣接情報を文字化したもの)が与えられる。
それぞれの区には「幸せ度」という数値が設定されている。いくつかのお互いに隣接しない区を選び、その「幸せ度」の和の最大値を求めよ。
解法
まず、みなさんについて質問ですが、どう解きましたか？
SABAKAN FEVERについての解法の調査です。ご協力を頂けると嬉しいです。#MISW新歓コンテスト2020
— Sen (@nonpro3) 2020年4月23日
この問題は、答えのみを提出する普段のAtcoder、Codeforcesのようなコンテストにはない形式です。答えのみを提出するので、プログラミングが得意ではない人も、コツコツやれば大変ですが、必ず正解できます。
しかし、後述の理由からコンピューターを使って計算することをお勧めします。
hackerrankにはペナルティ数に影響がありませんので、正解かな？と思うようなものがあったら積極的に提出するという手段を取れます。(あまりやりすぎるとサーバー堕ちると思うのでほどほどにしてください)
ではまず、パズルとして解くときのポイントをいくつか解説します。
パズル
まず最初に謝りたいことがあります。この地図の数値配置を作った時間の割にはかなり、貪欲的に解けないような配置、つまり罠だらけです。本当に申し訳ございませんでした。
答えです。
世田谷(19) 品川(15) 中野(15) 千代田(25) 江東(18) 板橋(13) 葛飾(15) 荒川(22) Ward Cnt == 8 total == 142
わかります。「クソパズルをさせるな本質コンテストをやれ」という声はもっともです。でもコンテストの時間自体は長いので、こういうのあってもいいじゃない。(圧倒的罵声)(投げ込まれるカッターナイフ)(家に届く怪しい白い粉)(連日要求される切腹)(Sen氏、人生から堂々と退場す)
パズルを解いた方々は、これから羅列する罠要素には十分共感できると思います。
海辺の20以上の4区(渋谷、新宿、千代田、中央)は1つしか使わない
着眼点としての海辺のハイスコア地域、そこからパズルを始めた方は多いのではないでしょうか？ハイスコア4区のうち2つを選んで、そこからと。
千代田区(25)しか使いません。
理由として、ハイスコア地域を2つ以上採用した場合、トータルでは合計で最大でも7区しかとれません。そしてこの数値設定では、絶妙ではありますが、区数優先のほうが強いのです(結果論)
ちなみにハイスコア地域2つ採用した時のベストアンサー
練馬(18) 世田谷(19) 品川(15) 新宿(24) 中央(22) 葛飾(15) 荒川(22) Ward Cnt == 7 total == 135
端から攻めるがほとんど通用しない
パズルの定番として選択肢の少ないところからスタートしていく、というのがありますが今回では攻める端については、
右端と下端以外は(結果論ですが)不確定要素にまみれていて、かといって
右端も確固たる理由を持って葛飾区、江東区と選べるというわけでもない。
ある程度明確的に選べるのは、大田区を明らかに除外できるとわかったときの世田谷区や品川区だけです。
こういう点からもクソパズルであることはわかります。とても反省しています。
頭を抱えたくなる局所最適解
こちらが少しパラメータ調整して作った局所最適解が以下です。
練馬(18) 世田谷(19) 品川(15) 新宿(24) 江東(18) 台東(14) 北(17) 葛飾(15) Ward Cnt == 8 total == 140
これに比べて正解はこれ。
世田谷(19) 品川(15) 中野(15) 千代田(25) 江東(18) 板橋(13) 葛飾(15) 荒川(22) Ward Cnt == 8 total == 142
なんとたったの2しか違いません。そして、この局所最適解は明らかに袋小路であることは次の図をご覧いただければわかります。
140局所最適解：
142正解：
は？
上端、左端を含みなんと4つも選び方に違いがあります。140の方を引いてしまった方、申し訳ありませんでした。答えは142なんです。
強烈に自己主張されてる港区は使わない
港区のサイトからの引用なので、仕方はありませんが、港区は使用しません。
なんなら次善策でも使用しません。
港区を必ず使った時のベストアンサーです。
杉並(16) 目黒(17) 港(18) 江東(18) 豊島(19) 葛飾(15) 荒川(22) Ward Cnt == 7 total == 125
以上の要素からわかる通り、このパズルを解こうとするのならば、かなりの労力を使わなければいけません。みなさん、誠に申し訳ありませんでした。
全探索
困ったときの全探索という言葉がある通り、これを全探索で解けないか？と考えてみましょう。まずは状態数を数えてみましょう。
まず、この地図をグラフとしてみなして、隣接してる区とは無向辺でつながるようにします。地図はグラフにモデリングしやすいものとしてよく知られています。
状態数は、多めに見積もっても(隣接してるならばダメを考えずに)、「それぞれの区について、選ぶor選ばないの2択」と考えると、最大でも通りになります。
それぞれの状態ごとに、隣接してるかどうか？の判定は、すべての辺について両端が使われているか？を判定して、1つでもあるのならば隣り合った区が使われている、ということになります。
これで、使われている状態が与えられたとき、辺の本数をとすると、
で隣接チェックを行えました。では、どのようにして
通りもの考えを実装するのでしょうか？
こちらのけんちょんさんの記事で紹介されている、このようにのパターンを全部列挙したいときにやる実装法としてbit演算を用いる、という手法があります。これは一般的にはbit全探索と呼ばれていて、ABC-Cでも出題済みです。
この時、計算量を見積もってみましょう。辺の本数(すなわち区の隣接情報の個数)は与えた地図では106本(無向辺を2本の有向辺で表現した)です。すると、全体ではおおよそ次の回数のループが回ります。
普段のコンテストならば、2秒の制約に間に合うのか非常に怪しいと言えます。実際、Writer解の実行時間は5000ms(Intel Core i5-6200U, 8GB)と1968ms(Intel Core i7-7500U 8GB)でした。これを20倍まで浮動すると考えても、現実的な時間ではあります。
しかし、この問題は、回答だけを提出するタイプの問題。多少長くても、現実的な時間ならば手元で計算すればいいだけです。
BitDP
さらに、全探索から高速化をすることができます。(Writer解は全探索、m_tsubasaさんから言われて気づきました)BitDPをわかってる人向けの解説です。
まず、集合Sについて、最上位の立ってる桁を除いた集合S'を考えます。bitで集合を表現するときに、0からfor文を回せば、Sについての計算をするときに、S'についての答えをメモしていれば、最上位の立ってる桁が表してる頂点と、それ以外の桁の立ってる頂点が隣接か？と隣接判定をする量を大幅に減らせます。これによって、全探索の計算量が何に対して、
になります。(
は辺の数、
は頂点の数)
実装
みなさん、大変申し訳ありませんでした。グラフに変換するのが面倒で申し訳ありません。ここでは、Writer解の実装を紹介します。
まず、与えられた区の隣接リストについて、
練馬区： 中野、杉並、豊島、板橋 杉並区： 練馬、中野、世田谷、渋谷 ...
を、競プロ風の入力に整形します。
4 中野 杉並 豊島 板橋 4 練馬 中野 世田谷 渋谷 ...
このとき、エディタに備わっている置換機能で
- 全角スペースと「、」->半角スペース
とすれば手間がだいぶ省けると思います。
そして、練馬、杉並、世田谷、太田...をそれぞれ番号で0, 1, 2, 3...と置換します。
4 8 1 17 18 4 0 8 2 7 ...
これで、隣接リストを数値化することができました。(Writer解はここまで変換していません)
あとは「幸せ度」のリストの変換ですが、同じようにデータを加工して(「：」は手動で消して、全角スペースを半角スペースに置き換えて、先ほどと同じルールで区を数字に変換する)
0 18 1 16 ...
のようにします。
ここまで述べたのは、あくまでグラフへの変換の一例です。この通りに行う必要はありません。
最終的には、Writer解は次のデータセットを読み込んで、実行するものです。
4 中野 杉並 豊島 板橋 4 練馬 中野 世田谷 渋谷 4 杉並 渋谷 目黒 大田 3 世田谷 目黒 品川 4 目黒 港 渋谷 大田 4 大田 世田谷 渋谷 品川 5 品川 渋谷 新宿 千代田 中央 7 品川 港 新宿 中野 杉並 世田谷 目黒 5 杉並 練馬 豊島 新宿 渋谷 6 豊島 中野 渋谷 港 千代田 文京 5 港 中央 台東 文京 新宿 5 港 千代田 台東 墨田 江東 3 中央 墨田 江戸川 3 江東 墨田 葛飾 7 江戸川 葛飾 足立 荒川 台東 中央 江東 5 墨田 中央 千代田 文京 荒川 6 北 荒川 台東 千代田 新宿 豊島 6 練馬 板橋 北 文京 新宿 中野 3 練馬 豊島 北 5 板橋 豊島 文京 荒川 足立 4 北 荒川 墨田 葛飾 3 足立 墨田 江戸川 5 北 足立 墨田 台東 文京 0 18 1 16 2 19 3 12 4 15 5 17 6 18 7 20 8 15 9 24 10 25 11 22 12 18 13 13 14 20 15 14 16 17 71 19 18 13 19 17 20 18 21 15 22 22
#include<iostream> #include<string> #include<map> #include<vector> #include<algorithm> using namespace std; typedef long long ll; map<string, int> taiou;//都市名-> string taiou_inv[23]; int v[23]; int main() { taiou["練馬"] = 0; taiou["杉並"] = 1; taiou["世田谷"] = 2; taiou["大田"] = 3; taiou["品川"] = 4; taiou["目黒"] = 5; taiou["港"] = 6; taiou["渋谷"] = 7; taiou["中野"] = 8; taiou["新宿"] = 9; taiou["千代田"] = 10; taiou["中央"] = 11; taiou["江東"] = 12; taiou["江戸川"] = 13; taiou["墨田"] = 14; taiou["台東"] = 15; taiou["文京"] = 16; taiou["豊島"] = 17; taiou["板橋"] = 18; taiou["北"] = 19; taiou["足立"] = 20; taiou["葛飾"] = 21; taiou["荒川"] = 22; for (auto it = taiou.begin(); it != taiou.end(); it++) { taiou_inv[(*it).second] = (*it).first; } vector<vector<int>> E(23); for (int i = 0; i < 23; i++) { int k; cin >> k; for (int j = 0; j < k; j++) { string buf; cin >> buf; E[i].push_back(taiou[buf]); } } bool L[23][23] = {}; for (int i = 0; i < 23; i++) { for (int j = 0; j < E[i].size(); j++) { L[i][E[i][j]] = true; } } for (int i = 0; i < 23; i++) { int a; cin >> a >> v[i];//最初の0, 1, 2の序数はいらない } int ans = 0; int Cnt = 0;//debug用 for (int bit = 0; bit < (1 << 23); bit++) { vector<bool> used(23); bool flg = true; int happiness = 0; for (int i = 0; i < 23; i++) { if ((bit >> i) & 1)used[i] = true;//i番目が使われていたのならば、usedに印をつける } for (int i = 0; i < 23; i++) { if (used[i])happiness += v[i]; for (int j = 0; j < E[i].size(); j++) { int neighbor = E[i][j]; if (used[i] && used[neighbor])flg = false;//隣接してる区を使ってしまっている } } // 半分debug用 if (happiness >= 142 && flg) { for (int i = 0; i < 23; i++) if(used[i])cout << taiou_inv[i] << "(" << v[i] << ") ", Cnt++; cout << endl; cout << "Ward Cnt == " << Cnt << endl; cout << "total == " << happiness << endl; Cnt = 0; } if (flg)ans = max(ans, happiness); } cout << ans << endl; return 0; }
これを実行した答えを指定の制約に整形して、提出するとACです。
142 arakawa itabasi katusika koutou nakano setagaya sinagawa tiyoda
統計＆講評
AC数: 15
正解率: 83.3%
First AC(All): kotatsugame(23:50)
First AC(MIS.W内): KKT89(205:01)
こたつがめさん早すぎませんか？これ前に別の問題も解いてる上でこの速度なのすごヨの一言しかありません。
主催してるサークル内でのFAはKKT89さんでした。みんなに敬遠されて解かれるのめちゃくちゃ最後になってしまいましたね。
普段コンテストに出せない、実際の地図上での最適化問題をコンピューターで解くというタイプの問題をやりたかったです。1日も時間あるしいっかｗと思って出しましたが、やはり面倒なのか敬遠する人が多かったです。地図からグラフデータへの加工という意味で手間がかかるのは性質上避けられませんが、ハードルを結果上げてしまいました。面倒なパズルになってしまったことも併せて、大変お詫び申し上げます。
ちなみに、提出する際に正解を出した方でも、最初の提出で区の順番を間違えてることが多々ありました。問題文までもわかりづらかったことを重ねてお詫び申し上げます。
