{"id":1639,"date":"2010-03-08T14:36:15","date_gmt":"2010-03-08T05:36:15","guid":{"rendered":"http:\/\/blog.bitmeister.jp\/?p=1639"},"modified":"2010-03-08T14:43:30","modified_gmt":"2010-03-08T05:43:30","slug":"google-devfest-quiz%e3%82%92%e3%82%84%e3%81%a3%e3%81%a6%e3%81%bf%e3%81%be%e3%81%97%e3%81%9f%e3%80%82%ef%bc%88%e3%83%91%e3%83%83%e3%83%81%e3%83%af%e3%83%bc%e3%82%af%e5%95%8f%e9%a1%8c%e3%81%ae%e5%9b%9e","status":"publish","type":"post","link":"https:\/\/blog.bitmeister.jp\/?p=1639","title":{"rendered":"Google DevFest Quiz\u3092\u3084\u3063\u3066\u307f\u307e\u3057\u305f\u3002\uff08\u30d1\u30c3\u30c1\u30ef\u30fc\u30af\u554f\u984c\u306e\u56de\u7b54\uff09"},"content":{"rendered":"

\u3059\u3067\u306b\u65e7\u805e\u306b\u5c5e\u3059\u308b\u30cd\u30bf\u3067\u3059\u304c\u3001\u8a71\u984c\u306eGoogle DevFest\u306eQuiz<\/a>\u306e\u79c1\u306e\u56de\u7b54\uff08\u306b\u4f7f\u3063\u305f\u30d7\u30ed\u30b0\u30e9\u30e0\uff09\u3092\u6652\u3057\u3066\u307f\u307e\u3059\u3002\u9593\u9055\u3044\u306a\u3069\u306e\u3054\u6307\u6458\u304c\u3042\u308c\u3070\u30b3\u30e1\u30f3\u30c8\u3092\u304a\u9858\u3044\u3057\u307e\u3059\u3002
\n\u3061\u306a\u307f\u306b\u3001\u3053\u3061\u3089<\/a>\u306b\u306f\u4ed6\u306e\u65b9\u306e\u56de\u7b54\uff08\u30d7\u30ed\u30b0\u30e9\u30e0\uff09\u304c\u307e\u3068\u3081\u3089\u308c\u3066\u3044\u307e\u3059\u3002
\n\u3044\u308d\u3093\u306a\u89e3\u304d\u65b9\u304c\u3042\u308a\u307e\u3059\u306d\u3002
\n<\/p>\n

\u3068\u308a\u3042\u3048\u305a\u30d1\u30c3\u30c1\u30ef\u30fc\u30af\u554f\u984c\u306e\u56de\u7b54\u3060\u3051\u3002
\n\u554f\u984c\u6587\u306e\u4e00\u90e8\u3092\u5f15\u7528\u3057\u307e\u3059\u3002<\/p>\n

\n
\n“A” \u307e\u305f\u306f “B” \u3068\u3044\u3046\u6587\u5b57\u306e\u307f\u3092\u542b\u3080 600 \u6841\u3001600 \u884c\u306e\u30c6\u30ad\u30b9\u30c8\u304c\u3042\u308a\u307e\u3059\u3002
\n\u3053\u308c\u3092 600 x 600 \u306e\u5347\u76ee\u72b6\u306b\u4e26\u3079\u3001\u4e0a\u4e0b\u5de6\u53f3\u306b\u540c\u3058\u6587\u5b57\u304c\u3042\u308b\u90e8\u5206\u3092\u3064\u306a\u304c\u3063\u3066\u3044\u308b\u3068\u307f\u306a\u3057\u307e\u3059\u3002\n<\/div>\n
\n\u307e\u305a\u3001\u6700\u3082\u591a\u304f\u306e\u6587\u5b57\u304c\u3064\u306a\u304c\u3063\u3066\u3044\u308b\u9818\u57df\u3092\u3059\u3079\u3066 “_” \u3067\u5857\u308a\u3064\u3076\u3057\u3066\u304f\u3060\u3055\u3044\u3002
\n \u6700\u3082\u591a\u304f\u306e\u6587\u5b57\u304c\u3064\u306a\u304c\u3063\u3066\u3044\u308b\u9818\u57df\u304c\u8907\u6570\u5b58\u5728\u3059\u308b\u306a\u3089\u3070\u3001\u305d\u308c\u3089\u3059\u3079\u3066\u306e\u9818\u57df\u3092 “_”\u3067\u5857\u308a\u3064\u3076\u3059\u3053\u3068\u3068\u3057\u307e\u3059\u3002\n<\/div>\n
\n\u305d\u3057\u3066\u3001\u5404\u884c\u3054\u3068\u306b “_” \u304c\u4f55\u500b\u542b\u307e\u308c\u3066\u3044\u308b\u304b\u3092\u6570\u3048\u3001\u305d\u308c\u3089\u306e\u6570\u5024\u3092\u6539\u884c\u533a\u5207\u308a\u306e\u30c6\u30ad\u30b9\u30c8\uff08600 \u884c\uff09\u3068\u3057\u3066\u7b54\u3048\u3066\u304f\u3060\u3055\u3044\u3002\n<\/div>\n
\n\u4ee5\u4e0b\u306e\u4f8b1\u3092\u898b\u3066\u304f\u3060\u3055\u3044\u3002\u3053\u306e\u5165\u529b\u306b\u306f\u5358\u4e00\u306e\u6587\u5b574\u3064\u3067\u3064\u306a\u304c\u3063\u305f\u9818\u57df\u304c3\u7b87\u6240\u3042\u308a\u307e\u3059\u3002\u3053\u308c\u3089\u3059\u3079\u3066\u304c\u300c\u6700\u3082\u591a\u304f\u306e\u6587\u5b57\u304c\u3064\u306a\u304c\u3063\u3066\u3044\u308b\u9818\u57df\u300d\u306a\u306e\u3067\u3001\u5168\u3066”_”\u3067\u5857\u308a\u3064\u3076\u3057\u3001\u305d\u306e\u6570\u3092\u6570\u3048\u3066\u3044\u307e\u3059\u3002\n<\/div>\n<\/div>\n

\u4f8b1:
\n\u5165\u529b<\/p>\n

\n
ABAAB\r\nBABAA\r\nBAABB\r\nABABB\r\nBABAA\r\n<\/pre>\n<\/blockquote>\n
\u5857\u308a\u3064\u3076\u3057\u305f\u3068\u3053\u308d. <\/p>\n
\n
AB__B\r\nB_B__\r\nB____\r\nAB___\r\nBABAA\r\n<\/pre>\n<\/blockquote>\n
\u7b54\u3048<\/p>\n
\n
2\r\n3\r\n4\r\n3\r\n0\r\n<\/pre>\n<\/blockquote>\n<\/blockquote>\n
\u79c1\u306e\u56de\u7b54<\/h2>\n
\u30d7\u30ed\u30b0\u30e9\u30e0\u3092\u7d39\u4ecb\u3059\u308b\u524d\u306b\u307e\u305a\u89e3\u304d\u65b9\u3092\u8aac\u660e\u3057\u307e\u3059\u3002
\nA\u3084B\u3068\u3042\u308b\u3072\u3068\u3064\u3072\u3068\u3064\u306e\u6587\u5b57\u3092”Block”\u3068\u3057\u307e\u3059\u3002
\n\u4e0a\u4e0b\u5de6\u53f3\u306eBlock\u304c\u540c\u3058\u6587\u5b57\u306e\u9818\u57df\u3092”Region”\u3068\u3057\u307e\u3059\u3002
\nBlock\u306f\u81ea\u5206\u304c\u6240\u5c5e\u3059\u308bRegion\u3092\u6700\u59271\u3064\u4fdd\u6301\uff08\u53c2\u7167\uff09\u3057\u3001Region\u306f\u540c\u3058Region\u306b\u5c5e\u3059\u308b\u3059\u3079\u3066\u306eBlock\u3092\u4fdd\u6301\uff08\u53c2\u7167\uff09\u3057\u307e\u3059\u3002
\n
\"Block\u3068Region\"<\/a>
Block\u3068Region<\/p><\/div><\/p>\n
\u5165\u529b\u30c7\u30fc\u30bf\u3092\u8aad\u307f\u8fbc\u3080\u3068\u304d\u306f\u3001\u5de6\u4e0a\u304b\u3089\u9806\u306b\u4e00\u884c\u4e00\u884c\u8aad\u3080\u3053\u3068\u306b\u306a\u308b\u306e\u3067\u3001\u3072\u3068\u3064Block\u3092\u4f5c\u308b\u305f\u3073\u306b\u3001\u4e0a\u307e\u305f\u306f\u5de6\u306b\u3042\u308bBlock\u304c\u540c\u3058\u6587\u5b57\u306a\u3089\u3070\u3001\u305d\u308c\u3089\u3092\u304f\u3063\u3064\u3051\u3066(Connect\u3057\u3066)\u3072\u3068\u3064\u306eRegion\u3068\u3059\u308b\u51e6\u7406\u3092\u884c\u3044\u307e\u3059\u3002
\n
\"e38391e38383e38381e383afe383bce382af2\"<\/a>
Connect<\/p><\/div><\/p>\n
\u307e\u305f\u305d\u306e\u3068\u304d\u306b\u540c\u3058Region\u306b\u5c5e\u3059\u308bBlock\u306e\u6570\u3092\u53d6\u5f97\u3057\u3001\u3055\u3089\u306b\u6700\u5927\u306eBlock\u6570\u3092\u6301\u3064Region\u3082\uff08\u8907\u6570\uff09\u4fdd\u6301\u3059\u308b\u3088\u3046\u306b\u3057\u307e\u3059\u3002
\n\u5165\u529b\u30c7\u30fc\u30bf\u3092\u8aad\u307f\u7d42\u308f\u3063\u305f\u3068\u304d\u306b\u3001\u3082\u3046\u4e00\u5ea6\u5de6\u4e0a\u304b\u3089\u6700\u5927\u306eBlock\u6570\u3092\u6301\u3064Region\u306b\u5c5e\u3059\u308bBlock\u306e\u6570\u3092\u884c\u6bce\u306b\u30ab\u30a6\u30f3\u30c8\u3059\u308c\u3070\u3001\u56de\u7b54\u304c\u5f97\u3089\u308c\u307e\u3059\u3002<\/p>\n
\u30d7\u30ed\u30b0\u30e9\u30e0\u306fJava\u3067\u66f8\u304d\u307e\u3057\u305f\u3002
\n\uff08A\u3001B\u306e2\u7a2e\u985e\u3060\u3051\u3067\u306a\u304fchar\u306b\u53ce\u307e\u308b\u7bc4\u56f2\u3067\u3042\u308c\u3070\u3069\u3093\u306a\u6587\u5b57\u3067\u3082\u5927\u4e08\u592b\u306a\u306f\u305a\u3067\u3059\uff09<\/p>\n
PatchWork.java
\n[Java]
\nimport java.io.BufferedReader;
\nimport java.io.FileReader;
\nimport java.io.IOException;
\nimport java.util.ArrayList;
\nimport java.util.HashSet;<\/p>\n
public class PatchWork {<\/p>\n
\tpublic class Region {
\n\t\tpublic HashSet region = new HashSet();
\n\t\tpublic Region() {
\n\t\t}
\n\t\tpublic void add(Block block) {
\n\t\t\tregion.add(block);
\n\t\t}
\n\t\tpublic int size() {
\n\t\t\treturn region.size();
\n\t\t}
\n\t}
\n\tpublic class Block {
\n\t\tprivate Region region = null;
\n\t\tprivate char type = 0;
\n\t\tpublic Block(char type) {
\n\t\t\tthis.type = type;
\n\t\t}
\n\t\tpublic int Connect(Block neighbor) {
\n\t\t\tif (neighbor.type == this.type) {
\n\t\t\t\tif (neighbor.region != null) {
\n\t\t\t\t\t\/\/ \u304a\u96a3\u304c\u3059\u3067\u306b\u8ab0\u304b\u306e\u9818\u5730\u3060\u3063\u305f\u5834\u5408
\n\t\t\t\t\tif (region == null) {
\n\t\t\t\t\t\t\/\/ \u81ea\u5206\u304c\u8ab0\u306e\u9818\u5730\u3067\u3082\u306a\u3051\u308c\u3070\u3001\u76f8\u624b\u8272\u306b\u67d3\u307e\u308b\u3002
\n\t\t\t\t\t\tregion = neighbor.region;
\n\t\t\t\t\t}
\n\t\t\t\t\telse {
\n\t\t\t\t\t\t\/\/ \u81ea\u5206\u306b\u3059\u3067\u306b\u9818\u5730\u304c\u3042\u308c\u3070\u3001\u76f8\u624b\u3092\u81ea\u5206\u8272\u306b\u67d3\u3081\u308b\u3002
\n\t\t\t\t\t\tfor (Block block : neighbor.region.region) {
\n\t\t\t\t\t\t\tthis.region.add(block);
\n\t\t\t\t\t\t}
\n\t\t\t\t\t\tfor (Block block : neighbor.region.region) {
\n\t\t\t\t\t\t\tblock.region = this.region;
\n\t\t\t\t\t\t}
\n\t\t\t\t\t}
\n\t\t\t\t}
\n\t\t\t\telse {
\n\t\t\t\t\t\/\/ \u304a\u96a3\u304c\u8ab0\u306e\u9818\u5730\u3067\u3082\u306a\u3044\u5834\u5408
\n\t\t\t\t\tif (this.region == null) {
\n\t\t\t\t\t\tregion = new Region();
\n\t\t\t\t\t}
\n\t\t\t\t\t\/\/ \u304a\u96a3\u3092\u81ea\u5206\u306e\u9818\u5730\u306b\u3059\u308b
\n\t\t\t\t\tneighbor.region = region;
\n\t\t\t\t\tregion.add(neighbor);
\n\t\t\t\t}
\n\t\t\t\tregion.add(this);
\n\t\t\t\treturn region.size();
\n\t\t\t}
\n\t\t\treturn 0;
\n\t\t}
\n\t}<\/p>\n
\t\/\/ \u3059\u3079\u3066\u306e\u30d6\u30ed\u30c3\u30af
\n\tprivate ArrayList< ArrayList > blocks = new ArrayList< ArrayList >();
\n\t\/\/ \u6700\u5927\u306e\u9818\u57df\u306e\u5927\u304d\u3055
\n\tprivate int maxCount=0;
\n\t\/\/ \u6700\u5927\u306e\u9818\u57df\uff08\u540c\u3058\u5927\u304d\u3055\u306e\u9818\u57df\u3092\u8907\u6570\u6301\u3066\u308b\u3088\u3046\u306bHashSet\u3067\uff09
\n\tprivate HashSet regions = new HashSet();<\/p>\n
\tpublic void addString(String str) {
\n\t\tArrayList rowBlocks = new ArrayList();
\n\t\tfor (int col=0; col < str.length(); col++) {\n\t\t\tBlock block = new PatchWork.Block(str.charAt(col));\n\t\t\tint thisCount = 0;\n\t\t\tif (blocks.size() > 0) {
\n\t\t\t\t\/\/ \u771f\u4e0a\uff08\u3072\u3068\u3064\u524d\u306e\u884c\u306e\u540c\u3058\u5217\uff09\u306b\u3042\u308b\u30d6\u30ed\u30c3\u30af\u3068\u63a5\u7d9a
\n\t\t\t\tArrayList preRow = blocks.get(blocks.size()-1);
\n\t\t\t\tBlock preBlock = preRow.get(col);
\n\t\t\t\tthisCount = block.Connect(preBlock);
\n \t\t\t}
\n\t\t\tif (col > 0) {
\n\t\t\t\t\/\/ \u624b\u524d(\u3072\u3068\u3064\u524d\u306e\u5217)\u306b\u3042\u308b\u30d6\u30ed\u30c3\u30af\u3068\u63a5\u7d9a
\n\t\t\t\tBlock preBlock = rowBlocks.get(col-1);
\n\t\t\t\tthisCount = block.Connect(preBlock);
\n\t\t\t}
\n\t\t\tif (thisCount > maxCount) {
\n\t\t\t\t\/\/ \u9818\u57df\u306e\u30b5\u30a4\u30ba\u304c\u4eca\u307e\u3067\u306e\u6700\u5927\u3088\u308a\u5927\u304d\u3051\u308c\u3070\u8a18\u9332\u66f4\u65b0
\n\t\t\t\tmaxCount = thisCount;
\n\t\t\t\tregions.clear();
\n\t\t\t\tregions.add(block.region);
\n\t\t\t}
\n\t\t\telse if (thisCount == maxCount) {
\n\t\t\t\t\/\/ \u9818\u57df\u306e\u30b5\u30a4\u30ba\u304c\u4eca\u307e\u3067\u306e\u6700\u5927\u3068\u540c\u3058\u306a\u3089\u8ffd\u52a0
\n\t\t\t\tregions.add(block.region);
\n\t\t\t}
\n\/\/\t\t\tSystem.out.println(“row=”+rowBlocks.size()+” col=”+col+” count=”+maxCount);
\n\t\t\trowBlocks.add(block);
\n\t\t}
\n\t\tblocks.add(rowBlocks);
\n\t}<\/p>\n
\tpublic String getResult() {
\n\t\tStringBuffer sb = new StringBuffer();
\n\t\tfor (int row=0; row < blocks.size(); row++) {\n\t\t\tArrayList blocks = this.blocks.get(row);
\n\t\t\tint count = 0;
\n\t\t\tfor (int col=0; col < blocks.size(); col++) {\n\t\t\t\tBlock block = blocks.get(col);\n\/\/\t\t\t\tboolean isHit = false;\n\t\t\t\tfor (Region region : regions) {\n\t\t\t\t\tif (block.region == region) {\n\t\t\t\t\t\tcount++;\n\/\/\t\t\t\t\t\tsb.append('_');\n\/\/\t\t\t\t\t\tisHit = true;\n\t\t\t\t\t\tbreak;\n\t\t\t\t\t}\n\t\t\t\t}\n\/\/\t\t\t\tif (!isHit) {\n\/\/\t\t\t\t\tsb.append(block.type);\n\/\/\t\t\t\t}\n\t\t\t}\n\t\t\tsb.append(\"\"+count+\"\\n\");\n\/\/\t\t\tsb.append('\\n');\n\t\t}\n\t\treturn sb.toString();\n\t}\n\n\t\/**\n\t * @param args\n\t *\/\n\tpublic static void main(String[] args) {\n\/\/\t\tString[] tbl = {\n\/\/\t\t\t\t\"aaabbbccc\",\n\/\/\t\t\t\t\"aaacccbbg\",\n\/\/\t\t\t\t\"eeefccbbb\",\n\/\/\t\t};\n\t\ttry {\n\t\t\tBufferedReader reader = new BufferedReader(new FileReader(\"D:\\\\patchworkinput.txt\"));\n\t\t\tPatchWork pw = new PatchWork();\n\t\t\tString line;\n\t\t\twhile ((line = reader.readLine()) != null) {\n\t\t\t\tpw.addString(line);\n\t\t\t}\n\t\t\tSystem.out.println(pw.getResult());\n\n\t\t} catch (IOException e) {\n\t\t\t\/\/ TODO \u81ea\u52d5\u751f\u6210\u3055\u308c\u305f catch \u30d6\u30ed\u30c3\u30af\n\t\t\te.printStackTrace();\n\t\t}\n\t}\n}\n[\/Java]\n<\/p>\n
\u611f\u60f3<\/h2>\n
\u4ed5\u4e8b\u306e\u7d0d\u671f\u76f4\u524d\u3060\u3063\u305f\u306e\u3067\u3001\u3084\u3063\u3064\u3051\u3067\u4f5c\u308d\u3046\u3068\u601d\u3063\u305f\u306e\u3067\u3059\u304c\u3001\u601d\u3063\u305f\u3088\u308a\u96e3\u3057\u304f\u3066\u7d50\u5c40\u3061\u3083\u3093\u3068\u8a2d\u8a08\u3057\u3066\u4f5c\u308a\u307e\u3057\u305f\u3002
\n\u554f\u984c\u306f\u9762\u767d\u304b\u3063\u305f\u306e\u3067\u3059\u304c\u3001\u304a\u304b\u3052\u3055\u307e\u3067\u7761\u7720\u6642\u9593\u304c\u3060\u3044\u3076\u524a\u3089\u308c\u307e\u3057\u305f\u3002\u3002\u3002
\n\u3061\u306a\u307f\u306b\u3001\u3053\u3046\u3044\u3046\u30d1\u30ba\u30eb\u7684\u306a\u30d7\u30ed\u30b0\u30e9\u30df\u30f3\u30b0\u306e\u554f\u984c\u3068\u3044\u3048\u3070\u3001C Magazine\u3092\u601d\u3044\u51fa\u3057\u307e\u3059\u306d\u3002
\n\u691c\u7d22\u3057\u305f\u3089\u3053\u3046\u3044\u3046\u30b5\u30a4\u30c8\u3092\u898b\u3064\u3051\u307e\u3057\u305f\u3002
\n\u548c\u7530\u7dad\u4f5c\u3055\u3093\u306eC\u30de\u30ac\u96fb\u8133\u30af\u30e9\u30d6<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
\u3059\u3067\u306b\u65e7\u805e\u306b\u5c5e\u3059\u308b\u30cd\u30bf\u3067\u3059\u304c\u3001\u8a71\u984c\u306eGoogle DevFest\u306eQuiz\u306e\u79c1\u306e\u56de\u7b54\uff08\u306b\u4f7f\u3063\u305f\u30d7\u30ed\u30b0\u30e9\u30e0\uff09\u3092\u6652\u3057\u3066\u307f\u307e\u3059\u3002\u9593\u9055\u3044\u306a\u3069\u306e\u3054\u6307\u6458\u304c\u3042\u308c\u3070\u30b3\u30e1\u30f3\u30c8\u3092\u304a\u9858\u3044\u3057\u307e\u3059\u3002 \u3061\u306a\u307f\u306b\u3001\u3053\u3061\u3089\u306b\u306f\u4ed6\u306e\u65b9\u306e\u56de\u7b54\uff08\u30d7\u30ed\u30b0\u30e9\u30e0\uff09 […]<\/p>\n","protected":false},"author":7,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[17],"tags":[19,23,46,40],"class_list":["post-1639","post","type-post","status-publish","format-standard","hentry","category-tech","tag-google","tag-java","tag-46","tag-40"],"_links":{"self":[{"href":"https:\/\/blog.bitmeister.jp\/index.php?rest_route=\/wp\/v2\/posts\/1639","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.bitmeister.jp\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.bitmeister.jp\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.bitmeister.jp\/index.php?rest_route=\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.bitmeister.jp\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1639"}],"version-history":[{"count":9,"href":"https:\/\/blog.bitmeister.jp\/index.php?rest_route=\/wp\/v2\/posts\/1639\/revisions"}],"predecessor-version":[{"id":2447,"href":"https:\/\/blog.bitmeister.jp\/index.php?rest_route=\/wp\/v2\/posts\/1639\/revisions\/2447"}],"wp:attachment":[{"href":"https:\/\/blog.bitmeister.jp\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1639"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.bitmeister.jp\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1639"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.bitmeister.jp\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1639"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}