2011-09-12

ひさびさの投稿ですね。

ようやっとGoogle Developer Day 2011のDevQuizが終わったのでいろいろ考えていたことを書きたいと思います。この記事ではスライドパズル以外の問題等々について書きます。

去年TwitterのTLにGDD2010の話題がよく流れていて、指をくわえて見ていたのですが、今年は情報を早めにキャッチできたので即参加しました。参加時点では、実はGDDが何をするものなのかよくわかってませんでした。

ウォームアップクイズ

いくらか意地悪な問題がある以外は適当にやってればできました。ヨセミテがぐぐらずともわかったのが良かったです。

Web Game

最初にWebGameから手をつけました。user.jsは何度かつくったことがあったのですが、最初カードの色を取得するもんだとおもって少々手こずりました。色の取得なんてしなくてもscriptの内容を読めば一発ですね。eventをdispatchしてからclickイベントで受け取ってもらえるように短めのタイマーで繰り返しクリックをdispatchしていました。
明らかに手で解けないほどの数でもサクサク進んでたのが面白かったです。

// ==UserScript==
// @name           osimasu2
// @namespace      uwi
// @description    おしまーす
// @version        0.1.0
// @author         uwi
// @copyright      uwi
// @include        http://gdd-2011-quiz-japan.appspot.com/webgame/problem
// ==/UserScript==

//(function(){
	var ar = [];
	
	window.setInterval(function(event){
		if(ar.length > 0)return;
	
		var e = document.getElementsByTagName("script");
		var t = e[2].innerText;
		var ind = t.indexOf("conc.setup([");
		var inde = t.indexOf("]);");
		var ss = t.substring(ind + "conc.setup([".length, inde);
		var sp = ss.split(",");
		var n = sp.length;
		for(var i = 0;i < n;i++){
			for(var j = i+1;j < n;j++){
				if(sp[i] == sp[j]){
					ar.push([i, j]);
					break;
				}
			}
		}
	}, 500);
	window.setInterval(function(event){
		if(ar.length == 0)return;
	var ev = document.createEvent("MouseEvents");
	ev.initEvent("click", false, true);
		var y = ar.pop();
		document.getElementById("card"+y[0]).dispatchEvent(ev);
		document.getElementById("card"+y[1]).dispatchEvent(ev);
	}, 50);
//})();

一人ゲーム

競技コーダーなら楽勝のBitDPの典型問でした。数の個数が高々10なのでその時々で消せる5の倍数の数たちは2^10通りのビットで表せます。dp[i][j]=(i回半分にする操作を行ったとき、消されているパターンがjになるための操作回数の最小値), erase[i]=(i回半分にする操作を行ったあと消せる5の倍数の数のパターン)として
dp[i][j|erase[i] ] = min(dp[i][j|erase[i] ], dp[i][j]+1) // 5の倍数消去の操作
dp[i+1][j] = min(dp[i+1][j], dp[i][j]+1) // 半分にする操作
の漸化式で配るDPを行い、最後にdp[*][(1<

package gdd2011;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

public class E {
	static Scanner in;
	static PrintWriter out;
	
	static void solve()
	{
		for(int t = ni();t >= 1;t--){
			int n = ni();
			int[] a = new int[n];
			for(int i = 0;i < n;i++)a[i] = ni();
			
			int[][] dp = new int[23][1<<n];
			for(int i = 0;i < 23;i++){
				Arrays.fill(dp[i], 999);
			}
			dp[0][0] = 0;
			for(int i = 0;i < 22;i++){
				int erase = 0;
				for(int j = 0;j < n;j++){
					if(a[j] % 5 == 0){
						erase |= 1<<j;
					}
					a[j] /= 2;
				}
				
				for(int j = 0;j < 1<<n;j++){
					dp[i][j|erase] = Math.min(dp[i][j|erase], dp[i][j] + 1);
					dp[i+1][j] = Math.min(dp[i+1][j], dp[i][j] + 1);
				}
			}
			
			int min = 999;
			for(int i = 0;i < 23;i++){
				min = Math.min(min, dp[i][(1<<n)-1]);
			}
			out.println(min);
		}
	}
	
	public static void main(String[] args) throws Exception
	{
		in = INPUT.isEmpty() ? new Scanner(System.in) : new Scanner(INPUT);
		out = new PrintWriter(System.out);
		
		solve();
		out.flush();
	}
	
	static int ni() { return Integer.parseInt(in.next()); }
	static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
	
	static String INPUT = "4\r\n" + 
	"2\r\n" + 
	"10 21\r\n" + 
	"3\r\n" + 
	"0 9 9\r\n" + 
	"4\r\n" + 
	"81 67 83 86\r\n" + 
	"3\r\n" + 
	"11 22 30";
}

満点をとった後に解きました。ideoneにGoがあったので書いてみていたら、どうやらバージョンが古い様子・・リファレンスをみながらせこせこ書きました。最近の言語はひと通り必要なのが揃っていますね。あと未使用変数に厳しいのとメソッド名が大文字で始まるのが気に入らないですね・・
image/pngのメソッドを呼ぶときどうしたらいいかでハマってました。

package main
import (
"fmt"
"io"
"strings"
"image/png"
)

func CountColor(pn io.Reader) int {
	im, _ := png.Decode(pn)
	minx := im.Bounds().Min.X
	miny := im.Bounds().Min.Y
	maxx := im.Bounds().Max.X
	maxy := im.Bounds().Max.Y
	colmap := map[uint32] int {}
	
	for x:=minx;x < maxx;x++ {
	for y:=miny;y < maxy;y++ {
		r, g, b, _ := im.At(x,y).RGBA()
		colmap[r<<16|g<<8|b] = 1
	}
	}
	
	return len(sum)
}

Apps Script

これもリファレンスを読みながらせこせこ解いていました。不正解でも理由がちゃんと表示されるので良いですね。リファレンスには使える関数の詳細しか載っていなくて、基本的な文法のところがごっそり抜けてたので、どういうふうに書いたものだか悩んでました。

function myFunction() {
  var sps = SpreadsheetApp.getActiveSpreadsheet();
  var i,j;
  
  var response = UrlFetchApp.fetch("http://gdd-2011-quiz-japan.appspot.com/apps_script/data?param=2140114143949079677");
  var json = response.getContentText();
  var obj = Utilities.jsonParse(json);
  for(j in obj){
    var datum = obj[j];
    var sheet = sps.insertSheet(datum.city_name);
    var len = datum.data.length;
    for(i = 0;i < len;i++){
      var datum2 = datum.data[i];
      sheet.getRange(i+1, 1).setValue(datum2.capacity);
      sheet.getRange(i+1, 2).setValue(datum2.usage);
      sheet.getRange(i+1, 3).setValue((datum2.usage/datum2.capacity*100)+"%");
    }
  }
  Browser.msgBox("おたわ");
}

Android

解けませんでした・・エミュレータをいれてコード入力まではできたんですが、あのAIDLからどうやってアプリをつくれというんだ・・というのでうんうん唸っていました。締切前日になってEclipseにAndroid pluginを入れたらいいことがわかったのでいれようとしたら固まったままInstallできない→終了　でした。向いてないんでしょうか。

MugiCha

Google Developer Day DevQuiz 所感1