# 都道府県 人口(人) 面積(km2)
strData =<<_EOT_
北海道 5,248,552 83,424.39
青森県 1,246,138 9,645.64
岩手県 1,226,430 15,275.01
宮城県 2,303,160 7,282.29
秋田県 965,968 11,637.52
山形県 1,077,057 9,323.15
福島県 1,847,950 13,783.90
茨城県 2,868,041 6,097.39
栃木県 1,942,312 6,408.09
群馬県 1,937,626 6,362.28
埼玉県 7,337,330 3,797.75
千葉県 6,279,026 5,157.60
東京都 13,942,856 2,194.07
神奈川県 9,200,166 2,416.30
新潟県 2,222,004 12,584.24
富山県 1,042,998 4,247.59
石川県 1,137,181 4,186.05
福井県 767,742 4,190.52
山梨県 812,056 4,465.27
長野県 2,049,023 13,561.56
岐阜県 1,988,931 10,621.29
静岡県 3,639,226 7,777.35
愛知県 7,552,873 5,173.06
三重県 1,779,770 5,774.45
滋賀県 1,413,959 4,017.38
京都府 2,583,140 4,612.20
大阪府 8,823,453 1,905.29
兵庫県 5,463,609 8,400.94
奈良県 1,331,330 3,690.94
和歌山県 923,721 4,724.65
鳥取県 555,663 3,507.14
島根県 673,891 6,708.27
岡山県 1,891,346 7,114.33
広島県 2,807,987 8,479.64
山口県 1,355,495 6,112.53
徳島県 728,633 4,146.75
香川県 956,069 1,876.79
愛媛県 1,338,811 5,676.16
高知県 697,674 7,103.64
福岡県 5,110,113 4,986.51
佐賀県 814,211 2,440.70
長崎県 1,325,205 4,131.00
熊本県 1,746,740 7,409.45
大分県 1,134,431 6,340.76
宮崎県 1,072,077 7,735.33
鹿児島県 1,599,984 9,187.08
沖縄県 1,454,184 2,281.00
_EOT_
arr = []
strData.split("\n").each{|line|
dat = line.split("\t")
dat[1] = dat[1].tr( ',', '' ).to_i # 人口(人)
dat[2] = dat[2].tr( ',', '' ).to_f # 面積(km2)
arr << dat
}
def bcut( arr, mx )
w = arr.dup
w.sort_by{|x| x[2] }.each_with_index{|x,i| x[3] = i > mx }
w.sort_by{|x| -x[1]/x[2] }.each_with_index{|x,i| x[3] = x[3] && i > mx }
w.delete_if{|x| x[3]}
end
def solver( arr )
ans_max = 0
ans = []
arr.combination( 20 ){|x|
ps = x.inject(0){|r, i| r + i[1] } / x.inject(0){|r, i| r + i[2] }
next if ans_max > ps
ans_max = ps
ans = x
}
[ ans, ans_max ]
end
ansmap = []
12.upto(19){|mx|
wrk = bcut( arr, mx )
ans, ans_max = solver( wrk )
puts "# #{mx} : #{wrk.size} #{'%12.6f' % ans_max} 人/km2"
puts "[#{ans.map{|a| a[0]}.join(",")}]" if ansmap != ans # 前回と同じ解は出力を省略
ansmap = ans
}
=begin
959 デフォルトの名無しさん 2020/02/24(月) 20:48:14.13 ID:D8qhYUus
[お題]
URLのページに都道府県別の人口と面積が載っている。
今回使用するのは、2019.10.1のデータ
URL: https://u...content-available-to-author-only...b.jp/pjn/pb.html
異なる20都道府県を選んで人口密度(人/km2)を最大化する。
人口密度は、少数6桁程度表示
選んだ都道府県名を 20個表示する(表示されてる順 ← 県コード順)。
例えば、3都道府県なら、
4906.099305 人/km2
[東京都, 神奈川県, 大阪府]
※入力はwebページから(工夫して)コピペで、スクレイピングの問題じゃない。
-------
人口密度と面積の順位で枝刈り
14位..22位まで結果が同じだったので多分
1008.245481 人/km2
[茨城県,埼玉県,千葉県,東京都,神奈川県,富山県,石川県,愛知県,滋賀県,京都府,大阪府,兵庫県,奈良県,鳥取県,徳島県,香川県,福岡県,佐賀県,長崎県,沖縄県]
=end
IyDpg73pgZPlupznnIwJ5Lq65Y+j77yI5Lq677yJCemdouepje+8iGttMu+8iQoJc3RyRGF0YSA9PDxfRU9UXwrljJfmtbfpgZMJNSwyNDgsNTUyCTgzLDQyNC4zOQrpnZLmo67nnIwJMSwyNDYsMTM4CTksNjQ1LjY0CuWyqeaJi+ecjAkxLDIyNiw0MzAJMTUsMjc1LjAxCuWuruWfjuecjAkyLDMwMywxNjAJNywyODIuMjkK56eL55Sw55yMCTk2NSw5NjgJMTEsNjM3LjUyCuWxseW9ouecjAkxLDA3NywwNTcJOSwzMjMuMTUK56aP5bO255yMCTEsODQ3LDk1MAkxMyw3ODMuOTAK6Iyo5Z+O55yMCTIsODY4LDA0MQk2LDA5Ny4zOQrmoIPmnKjnnIwJMSw5NDIsMzEyCTYsNDA4LjA5Cue+pOmmrOecjAkxLDkzNyw2MjYJNiwzNjIuMjgK5Z+8546J55yMCTcsMzM3LDMzMAkzLDc5Ny43NQrljYPokYnnnIwJNiwyNzksMDI2CTUsMTU3LjYwCuadseS6rOmDvQkxMyw5NDIsODU2CTIsMTk0LjA3CuelnuWliOW3neecjAk5LDIwMCwxNjYJMiw0MTYuMzAK5paw5r2f55yMCTIsMjIyLDAwNAkxMiw1ODQuMjQK5a+M5bGx55yMCTEsMDQyLDk5OAk0LDI0Ny41OQrnn7Plt53nnIwJMSwxMzcsMTgxCTQsMTg2LjA1Cuemj+S6leecjAk3NjcsNzQyCTQsMTkwLjUyCuWxseaiqOecjAk4MTIsMDU2CTQsNDY1LjI3CumVt+mHjuecjAkyLDA0OSwwMjMJMTMsNTYxLjU2CuWykOmYnOecjAkxLDk4OCw5MzEJMTAsNjIxLjI5CumdmeWyoeecjAkzLDYzOSwyMjYJNyw3NzcuMzUK5oSb55+l55yMCTcsNTUyLDg3Mwk1LDE3My4wNgrkuInph43nnIwJMSw3NzksNzcwCTUsNzc0LjQ1Cua7i+izgOecjAkxLDQxMyw5NTkJNCwwMTcuMzgK5Lqs6YO95bqcCTIsNTgzLDE0MAk0LDYxMi4yMArlpKfpmKrlupwJOCw4MjMsNDUzCTEsOTA1LjI5CuWFteW6q+ecjAk1LDQ2Myw2MDkJOCw0MDAuOTQK5aWI6Imv55yMCTEsMzMxLDMzMAkzLDY5MC45NArlkozmrYzlsbHnnIwJOTIzLDcyMQk0LDcyNC42NQrps6Xlj5bnnIwJNTU1LDY2MwkzLDUwNy4xNArls7bmoLnnnIwJNjczLDg5MQk2LDcwOC4yNwrlsqHlsbHnnIwJMSw4OTEsMzQ2CTcsMTE0LjMzCuW6g+WztuecjAkyLDgwNyw5ODcJOCw0NzkuNjQK5bGx5Y+j55yMCTEsMzU1LDQ5NQk2LDExMi41MwrlvrPls7bnnIwJNzI4LDYzMwk0LDE0Ni43NQrpppnlt53nnIwJOTU2LDA2OQkxLDg3Ni43OQrmhJvlqpvnnIwJMSwzMzgsODExCTUsNjc2LjE2CumrmOefpeecjAk2OTcsNjc0CTcsMTAzLjY0Cuemj+WyoeecjAk1LDExMCwxMTMJNCw5ODYuNTEK5L2Q6LOA55yMCTgxNCwyMTEJMiw0NDAuNzAK6ZW35bSO55yMCTEsMzI1LDIwNQk0LDEzMS4wMArnhormnKznnIwJMSw3NDYsNzQwCTcsNDA5LjQ1CuWkp+WIhuecjAkxLDEzNCw0MzEJNiwzNDAuNzYK5a6u5bSO55yMCTEsMDcyLDA3Nwk3LDczNS4zMwrpub/lhZDls7bnnIwJMSw1OTksOTg0CTksMTg3LjA4Cuaylue4hOecjAkxLDQ1NCwxODQJMiwyODEuMDAKX0VPVF8KCglhcnIgPSBbXQoJc3RyRGF0YS5zcGxpdCgiXG4iKS5lYWNoe3xsaW5lfAoJCWRhdCA9IGxpbmUuc3BsaXQoIlx0IikKCQlkYXRbMV0gPSBkYXRbMV0udHIoICcsJywgJycgKS50b19pCSMg5Lq65Y+j77yI5Lq677yJCgkJZGF0WzJdID0gZGF0WzJdLnRyKCAnLCcsICcnICkudG9fZgkjIOmdouepje+8iGttMu+8iQoJCWFyciA8PCBkYXQKCX0KCmRlZiBiY3V0KCBhcnIsIG14ICkKCXcgPSBhcnIuZHVwCgl3LnNvcnRfYnl7fHh8IHhbMl0gfS5lYWNoX3dpdGhfaW5kZXh7fHgsaXwgeFszXSA9IGkgPiBteCB9Cgl3LnNvcnRfYnl7fHh8IC14WzFdL3hbMl0gfS5lYWNoX3dpdGhfaW5kZXh7fHgsaXwgeFszXSA9IHhbM10gJiYgaSA+IG14IH0KCXcuZGVsZXRlX2lme3x4fCB4WzNdfQplbmQKCmRlZiBzb2x2ZXIoIGFyciApCglhbnNfbWF4ID0gMAoJYW5zID0gW10KCWFyci5jb21iaW5hdGlvbiggMjAgKXt8eHwKCQlwcyA9IHguaW5qZWN0KDApe3xyLCBpfCByICsgaVsxXSB9IC8geC5pbmplY3QoMCl7fHIsIGl8IHIgKyBpWzJdIH0KCQluZXh0CWlmIGFuc19tYXggPiBwcwoJCWFuc19tYXggPSBwcwoJCWFucyA9IHgKCX0KCVsgYW5zLCBhbnNfbWF4IF0KZW5kCgoJYW5zbWFwID0gW10KCTEyLnVwdG8oMTkpe3xteHwKCQl3cmsgPSBiY3V0KCBhcnIsIG14ICkKCQlhbnMsIGFuc19tYXggPSBzb2x2ZXIoIHdyayApCgkJcHV0cyAiIyAje214fSA6ICN7d3JrLnNpemV9ICN7JyUxMi42ZicgJSBhbnNfbWF4fSDkurova20yIgoJCXB1dHMgIlsje2Fucy5tYXB7fGF8IGFbMF19LmpvaW4oIiwiKX1dIglpZiBhbnNtYXAgIT0gYW5zCSMg5YmN5Zue44Go5ZCM44GY6Kej44Gv5Ye65Yqb44KS55yB55WlCgkJYW5zbWFwID0gYW5zCgl9CgoKPWJlZ2luCgo5NTkg44OH44OV44Kp44Or44OI44Gu5ZCN54Sh44GX44GV44KTIDIwMjAvMDIvMjQo5pyIKSAyMDo0ODoxNC4xMyBJRDpEOHFoWVV1cwogICAgW+OBiumhjF0KICAgIFVSTOOBruODmuODvOOCuOOBq+mDvemBk+W6nOecjOWIpeOBruS6uuWPo+OBqOmdouepjeOBjOi8ieOBo+OBpuOBhOOCi+OAggogICAg44CA5LuK5Zue5L2/55So44GZ44KL44Gu44Gv44CBMjAxOS4xMC4x44Gu44OH44O844K/CiAgICDjgIBVUkw6IGh0dHBzOi8vdS4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4uYi5qcC9wam4vcGIuaHRtbAoKICAgIOOAgOeVsOOBquOCizIw6YO96YGT5bqc55yM44KS6YG444KT44Gn5Lq65Y+j5a+G5bqmKOS6ui9rbTIp44KS5pyA5aSn5YyW44GZ44KL44CCCiAgICDjgIDkurrlj6Plr4bluqbjga/jgIHlsJHmlbA25qGB56iL5bqm6KGo56S6CiAgICDjgIDpgbjjgpPjgaDpg73pgZPlupznnIzlkI3jgpIgMjDlgIvooajnpLrjgZnjgoso6KGo56S644GV44KM44Gm44KL6aCGIOKGkCDnnIzjgrPjg7zjg4npoIYp44CCCgogICAg44CA5L6L44GI44Gw44CBM+mDvemBk+W6nOecjOOBquOCieOAgQogICAg44CA44CANDkwNi4wOTkzMDUg5Lq6L2ttMgogICAg44CA44CAW+adseS6rOmDvSwg56We5aWI5bed55yMLCDlpKfpmKrlupxdCgogICAg4oC75YWl5Yqb44Gvd2Vi44Oa44O844K444GL44KJKOW3peWkq+OBl+OBpinjgrPjg5Tjg5rjgafjgIHjgrnjgq/jg6zjgqTjg5Tjg7PjgrDjga7llY/poYzjgZjjgoPjgarjgYTjgIIgCgotLS0tLS0tCgoJ5Lq65Y+j5a+G5bqm44Go6Z2i56mN44Gu6aCG5L2N44Gn5p6d5YiI44KKCgkxNOS9jS4uMjLkvY3jgb7jgafntZDmnpzjgYzlkIzjgZjjgaDjgaPjgZ/jga7jgaflpJrliIYKCgkxMDA4LjI0NTQ4MSDkurova20yCglb6Iyo5Z+O55yMLOWfvOeOieecjCzljYPokYnnnIws5p2x5Lqs6YO9LOelnuWliOW3neecjCzlr4zlsbHnnIws55+z5bed55yMLOaEm+efpeecjCzmu4vos4DnnIws5Lqs6YO95bqcLOWkp+mYquW6nCzlhbXluqvnnIws5aWI6Imv55yMLOmzpeWPluecjCzlvrPls7bnnIws6aaZ5bed55yMLOemj+WyoeecjCzkvZDos4DnnIws6ZW35bSO55yMLOaylue4hOecjF0KCj1lbmQK
# 12 : 20 996.618903 人/km2
[茨城県,埼玉県,千葉県,東京都,神奈川県,石川県,静岡県,愛知県,滋賀県,京都府,大阪府,兵庫県,奈良県,鳥取県,徳島県,香川県,福岡県,佐賀県,長崎県,沖縄県]
# 13 : 21 1005.496874 人/km2
[茨城県,埼玉県,千葉県,東京都,神奈川県,石川県,福井県,愛知県,滋賀県,京都府,大阪府,兵庫県,奈良県,鳥取県,徳島県,香川県,福岡県,佐賀県,長崎県,沖縄県]
# 14 : 22 1008.245481 人/km2
[茨城県,埼玉県,千葉県,東京都,神奈川県,富山県,石川県,愛知県,滋賀県,京都府,大阪府,兵庫県,奈良県,鳥取県,徳島県,香川県,福岡県,佐賀県,長崎県,沖縄県]
# 15 : 23 1008.245481 人/km2
# 16 : 24 1008.245481 人/km2
# 17 : 25 1008.245481 人/km2
# 18 : 26 1008.245481 人/km2
# 19 : 27 1008.245481 人/km2