Google Code Jam 2011 (予選) 参加記録と新言語「Anko C++」

CommonLisp

Google Code Jam
ついった見てたらLISPで参加してる人がちらほら見えたので自分もやってみた。初参加。
結果はA,B,Cそれぞれsmall, large両方正解で70点。Dはsmallで弾かれて0点。

Problem A. Bot Trust

自分のターンでない時には行動ポイントを貯め、自分のターンが来たらポイントを消費して瞬間移動 & 足りなければ1歩ずつ移動、というルールに脳内変換して解いた。

(defmacro do-problems (&body body)
  `(loop for #0=#:i from 1 to (read)
     do (format t "~&Case #~D: " #0#)
     (progn ,@body)))

(defmacro n-of (n form)
  `(loop repeat ,n collect ,form))

(do-problems
 (let ((buttons (n-of #0=(read) `(,(position (read-char) "OB") ,#0#)))
       (pos (vector 1 1))     ;blue, orange
       (stock (vector 0 0))
       (ans 0))
   (loop for (r n) in buttons do
     (let ((d (max 0 (- (abs (- n (aref pos r)))
                        (aref stock r)))))
       (setf (aref stock r) 0
             (aref pos r) n)
       (incf (aref stock (- 1 r)) (1+ d))
       (incf ans (1+ d))
       ;(format t "~&  ~A:~A" pos stock)
       ))
   (princ ans)))

do-problemsはkozimaさんが呟いてたGCJ用テンプレートloopをありがたく流用させてもらった。

n-ofはarcから。
普通のループで書けたのでlarge-setでも計算は一瞬。

Problem B. Magicka

マギカとな。巡回セールスマン問題か、と思ったら全然違った。
D

(defmacro aif (test then else)
  `(let ((it ,test))
     (if it ,then ,else)))

(do-problems
 (let* ((combs #0=(n-of #1=(read) #2=(coerce (symbol-name #1#) 'list)))
	(oposes #0#)
	(els (and #1# #2#))
	(ans (list (pop els))))
   (dolist (e els)
;     (format t "~&  ~A <- ~A" ans e)
     (aif (find-if (lambda (c)
		     (let ((fact (subseq c 0 2)))
		       (or (equal fact `(,e ,(car ans)))
			   (equal fact `(,(car ans) ,e)))))
		   combs)
	 (setf (car ans) (car (last it)))
       (if (find-if (lambda (o)
		      (some (lambda (e2)
			      (or (equal o `(,e ,e2))
				  (equal o `(,e2 ,e))))
			    ans))
		    oposes)
	   (setq ans nil)
	 (push e ans))))
   (format t "[~{~A~^, ~}]" (nreverse ans))))

入力魔法リストから1つずつElementを取り出して回答用リストに合成or消去等しながら追加していく、という動作。
合成リストと消去リストは文字のリストのリストとして保持するよう書いたけど、hashtableにした方が楽だったな。

smallで引っ掛かるかなーと思ったけど1回で通った。引っ掛かりそうな所はsample inputで全部網羅されてたらしい。

Problem C. Candy Splitting

弟の足し算がxorだという事と、xorの性質を知っていればとっても簡単。
全キャンディの値をxorして0じゃなればNOだし、0だったら一番小さいのを弟に渡せばOK。酷い兄。

(do-problems
 (let ((p (sort (n-of (read) (read)) #'<)))
   (if (< 0 (apply #'logxor p))
       (princ "NO")
     (princ (apply #'+ (cdr p))))))

Problem D. GoroSort

3個以上同時に入れ替える意味はないんだろーなーと思ってしまって交換系ソートの事ばかり考えてしまい、駄目だった。
kozimaさんが布団に入った瞬間答えが分かって回答した、と呟いてたので真似してみたけど普通に8時間寝て終わってた。


感想

gcjって物凄く難しい問題が出る、っていうイメージがあったのだけど、予選だとそこまで大変じゃないという事が分かった。
本戦はやっぱり難しそう。というかこんな問題出てたんだ。凄いな東亜プラン(違う


あとついったの#gcj眺めてたら謎の難読言語「Anko C++」で参加してる人を発見。
Participant: kana.ikeda
↓(恐らく)第一発見者

C.ankoより抜粋

QB: Patrick、君もいつか自分の判断ミスに気づいて、Seanを恨む日が来るのかな。その絶望への相転移が発生させるエネルギーに僕は興味がなくはないけど、やっぱり女の子じゃないとね! まどか!
QB: void
まどか: int
さやさや: int
さやか: 1000000000
マミマミ: int
マミ: 0
あんあん: int
杏子: 0
ほむほむ: int
ほむらちゃほむほむ: cin >> まどか
ほむらちゃほむほむ: まどか
まどか: まどかさまどまど
さやか: ほむらちゃほむほむ
まどか: まどか-1
杏子あんあん: cin >> ほむら

以下30行略。これは酷い。
この風越の大将は何者だろうか。ソース冒頭にAnko C++のプロジェクトページURLが書いてあった、が作者が何者なのか分からない。
Anko C++ Project Homepage
とても若干気になる。