2011-04-16
■Groongaの対話モードをラップするgrnwrap
Groongaには素敵なWebベースの管理画面が付属していますが、ターミナルから対話モードで動作を確かめたいことも（私は）けっこうあります。
がしかし、この対話モードでは履歴呼び出しやカーソル移動が使えません。それと結果のJSONが一行なのでたいへん見づらい。
困ったのでPythonで入出力をラップするスクリプトを書きました。動作環境として、Python 2.6以上（それ以前の場合はsimplejsonをインストール）がreadlineモジュールつきでコンパイルされていることが必要です。
michisu/grnwrap at master - GitHub
機能
- カーソル移動とか
- 履歴の保存
- タブキーでコマンド名、引数名、テーブル名、ファイルパスの補完
- JSONのインデント表示
- Gオプションでselectの結果をMySQLの\G風にフォーマット
- *.grnなファイルパスを入力するとファイルに書かれたGroongaコマンドを実行
引数名（--filterとか）の補完は環境によって動作が変わってしまうようなので、デフォルトでは無効の場合があります。無効になっているけど試したい場合は-cオプションをつけて起動してみてください。
使い方
$ grnwrap <groonga_db>
実行例
$ grnwrap -G /tmp/tutorial.db
> select --table Site --query title:@this
******************************* 1. row *******************************
_id: 1
_key: http://example.org/
title: This is test record 1!
1 records / 1 hits (0.000823 sec)
> select --table Site --query title:@test --output_columns _id,_score,title --sortby _score
******************************* 1. row *******************************
_id: 1
_score: 1
title: This is test record 1!
******************************* 2. row *******************************
_id: 2
_score: 1
title: test record 2.
******************************* 3. row *******************************
_id: 4
_score: 1
title: test record four.
******************************* 4. row *******************************
_id: 3
_score: 2
title: test test record three.
******************************* 5. row *******************************
_id: 9
_score: 2
title: test test record nine.
******************************* 6. row *******************************
_id: 8
_score: 2
title: test test record eight.
******************************* 7. row *******************************
_id: 7
_score: 3
title: test test test record seven.
******************************* 8. row *******************************
_id: 5
_score: 3
title: test test test record five.
******************************* 9. row *******************************
_id: 6
_score: 4
title: test test test test record six.
9 records / 9 hits (0.007133 sec)
2011-04-09 TopCoder SRM 502
■TopCoder SRM 502
Div2 Easy: TheProgrammingContestDivTwo
時間内に複数のタスクをこなさなければならない。順序は任意。一つのタスクをこなすと、そのタスクが終わった時点での経過時間がペナルティとして加算される。制限時間Tと各タスクの必要時間requiredTimeが与えられた時、こなせる最大のタスク数と累計のペナルティを答える。
import java.util.Arrays; public class TheProgrammingContestDivTwo { public int[] find(int T, int[] requiredTime) { int solved = 0; int passed = 0; int t = 0; Arrays.sort(requiredTime); for (int i = 0; i < requiredTime.length; i++) { if (T < passed + requiredTime[i]) break; solved++; passed += requiredTime[i]; t += passed; } int[] res = {solved, t}; return res; } }
テスト実行しながら何回か書き直しつつ正解。一発で書きたいなぁ。英語の問題文がぱっと頭に入ってこないのが問題。
Div2 Medium: TheLotteryBothDivs
くじを一枚持っている。くじは"000000000"から"999999999"までの10桁の数字からなる文字列で表されるとする。この時、1桁から10桁までの文字列（suffix）がいくつか与えられ、くじ番号の末尾にそのどれかが一致すれば当たりである。与えられた文字列配列から、当たりの確率を答える。ただし、浮動小数点演算による1e-9以下の誤差は許される。
import java.util.Arrays; import java.util.Comparator; import java.util.HashSet; import java.util.Set; class StringLengthComparator implements Comparator<String> { public int compare(String o1, String o2) { if (o1.length() < o2.length()) { return -1; } else if (o2.length() < o1.length()) { return 1; } else { return 0; } } } public class TheLotteryBothDivs { public double find(String[] goodSuffixes) { double res = 0.0; Set<String> set = new HashSet<String>(); Arrays.sort(goodSuffixes, new StringLengthComparator()); for (String suffix : goodSuffixes) { boolean ignore = false; for (int i = 1; i <= suffix.length(); i++) { String check = suffix.substring(suffix.length()-i, suffix.length()); ignore = set.contains(check); if (ignore) break; } if (!ignore) { set.add(suffix); res += Math.pow(0.1, suffix.length()); } } return res; } }
例えば {"1", "2"} が渡されると当たりの確率は0.2。 {"01", "02"} であれば0.02。{"1", "2", "01", "02"} だったら、長いほうの文字列は確率に影響を与えないので0.2のまま。
文字列を短い順に並び替えて、憶えておく。前に共通のサフィックスを使う文字列が現れていたら、確率には加算しない。文字列の種類は最大でも50と少ないから、トライ木のようなデータ構造を使わなくても一文字ずつ削りながら処理していけばOK。
Javaで比較処理のもっと簡単な書き方ってないっけ。。
Div2 Hard: TheCowDivTwo
飼っている牛の数と逃げ出した牛の数が渡される。逃げ出した牛の組み合わせは何通りあるか、という問題。
組み合わせの定義を調べてやってみたがうまく動かず、時間切れ。やっぱり中学数学からやり直しが必要だな。。
結果
EasyとMediumの二問正解で491.79pt。Div2 758人中143位。レーティングは922から979にアップ。次で4桁になれれば初回挑戦以来だ！
2011-04-05 Google Code Jam勉強会 第一回
■Google Code Jam勉強会 第一回
Google Code Jam（GCJ）の勉強会に参加しました。講師はおなじみ id:chokudai 先生。
簡単な説明の後で、二問実習し、問題の後にchokudaiさんのライブコーディング、という流れ。
ちなみに二回目が4/19 18:30〜に予定されていますよ。
説明と方針
以下、chokudaiさんの解説まとめ。
GCJ用の特別な対策は基本的には必要ない。TopCoderとの違いは、時間制限が長いこと、入出力がファイルであること、実行環境がローカルであること、使える言語が自由であること。言語は自由だが処理速度の差が出るので必ず計算量を意識するべし。
各問、SmallとLargeの二種類のデータセットがある。それぞれダウンロードして4分/8分以内に結果を提出しなければならない。Largeは実行に時間がかかるので、ナイーブな実装では間に合わないことがある。
Smallを正解すると10ポイント、Largeで23ポイントが与えられる。Smallは何回も試せるが、Largeは一回しかできないので注意。
33点が予選ラウンド通過スコアなので、Largeを一問解けば（Smallも解けるので）通過できる。逆にSmallが三問解けても点数が足りない。Largeをしっかり一問解けるかどうかが鍵。
そして実習へ。
GCJ Africa and Arabia 2011 Qualification Round A. Closing the Loop
赤と青のロープを交互に結び合わせて輪を作る。結び目の箇所には両方のロープ合わせて1cmを使う。与えられた長さと本数がまちまちのロープから最大何cmの輪を作れるか、という問題。
GCJの問題は初めてだったので入力の書き方をどうするか悩みながらも、問題自体は特に問題なく解けた。赤と青の本数の小さい方を取り、その本数分、長いロープから使っていく。
import sys def readline(): return sys.stdin.readline().strip() num_case = int(readline()) for i in range(num_case): red_lopes = [] blue_lopes = [] num_lope = int(readline()) lopes = readline().split() for lope in lopes: color = lope[-1] length = int(lope[:-1]) if color == 'R': red_lopes.append(length) else: blue_lopes.append(length) red_lopes = sorted(red_lopes) red_lopes.reverse() blue_lopes = sorted(blue_lopes) blue_lopes.reverse() num_used = min(len(red_lopes), len(blue_lopes)) len_knots = num_used * 2 len_lopes = sum(red_lopes[:num_used]) + sum(blue_lopes[:num_used]) print 'Case #%s: %s' % (i+1, len_lopes - len_knots)
GCJ 2010 Qualification Round C. Theme Park
ローラーコースターがR回運行する。一度に乗せられる人数はk人。乗客はN個のグループが並んでおり、同じグループの人はまとめて乗せなければならない。また、順番を飛ばすこともできない。つまり、k=5の時に、{2, 2, 3, 1}人ずつのグループがあったとすると、最初に乗せられるのは4人。乗り終わったグループはまた列の最後に並ぶことになる。R回運行した後の運賃合計（1人1ユーロ）を答える。
LargeではRが最大10の8乗。まともにR回シミュレーションをしていると、8分以内に終わることはできない。シミュレーション中にループする箇所が出てきて、その分をまとめてスキップしてあげれば最短の時間で処理できるだろう・・・というのはすぐに思いついた。
しかし残念ながら勉強会の時間内には解けなかった。帰宅してからやっと書けたが、一度で全グループを乗せられてしまうケースへの対処に苦労した。プログラム的に難しい問題だと思う。
import sys def rl(conv=str): return conv(sys.stdin.readline().strip()) num_cases = rl(int) for i in range(num_cases): R, k, N = map(int, rl().split()) groups = map(int, rl().split()) sum_r = 0 sum_p = 0 index = 0 start = 0 starts = {} skiped = False p = 0 while sum_r < R: g = groups[index] p += g index += 1 if len(groups) == index: index = 0 if k < p + groups[index] or index == start: sum_r += 1 sum_p += p if not skiped and index in starts: prev_p, prev_r = starts[index] jump_p = sum_p - prev_p jump_r = sum_r - prev_r num_jump = (R - sum_r) / jump_r sum_p += num_jump * jump_p sum_r += num_jump * jump_r skiped = True starts[start] = (sum_p - p, sum_r - 1) start = index p = 0 print 'Case #%s: %s' % (i + 1, sum_p)
（4/7）最初に載せたものは不要な変数やimport文が残っていたので、整理した。
ほぼ一発で動くライブコーディングはさすが。
2011-04-03 TopCoder SRM 501
■TopCoder SRM 501
Div2 Easy: FoxProgression（Java）
与えられた数列に追加すると、その数列が等差数列または等比数列になるような数は何種類あるか、という問題。
先頭に入れるのもありかと思って時間がかかったが、後ろにappendする場合だけを考慮すればいいらしい。
public class FoxProgression { public int theCount(int[] seq) { if (seq.length == 1) return -1; int last = 0; int[] diffs = new int[seq.length-1]; double[] ratios = new double[seq.length-1]; boolean ari = true; boolean geo = true; for (int i = 1; i < seq.length; i++) { diffs[i-1] = seq[i] - seq[i-1]; ratios[i-1] = (double)seq[i] / seq[i-1]; if (seq[i-1] * (int)ratios[i-1] != seq[i]) geo = false; last = seq[i]; } for (int i = 1; i < diffs.length; i++) { if (diffs[i] != diffs[i-1]) ari = false; } for (int i = 1; i < ratios.length; i++) { if (ratios[i] != ratios[i-1]) geo = false; } if (!ari && !geo) return 0; if (ari && geo) { if (last + diffs[0] == last * ratios[0]) { return 1; } else { return 2; } } return 1; } }
Div2 Medium: FoxPlayingGame（Java）
スコア0から始めて、任意の順序でparamA / 1000.0をnA回足し、paramB / 1000.0をnB回かけることができる。最大スコアは何点か。
最初の回答。いくつかのパターンを挙げてつぶしていく。。
public class FoxPlayingGame { public double theMax(int nA, int nB, int paramA, int paramB) { double scoreA = paramA / 1000.0; double scoreB = paramB / 1000.0; double ret = Math.max( 0 + (scoreA * nA) * Math.pow(scoreB, nB), 0 * Math.pow(scoreB, nB) + (scoreA * nA)); if (scoreB < 0) { if (nB % 2 == 0) { return Math.max(ret, 0 + (scoreA * nA) * Math.pow(scoreB, nB)); } else { return Math.max(ret, 0 * scoreB + (scoreA * nA) * Math.pow(scoreB, nB-1)); } } return ret; } }
あっさりと他の参加者に撃墜される。こういう方法ではだめですね。
後日の復習で、他の人のコードを見て書き直し。
つまるところ、 (paramA / 1000.0) * nA に、nB回以下で任意の回数 (paramB / 1000.0) をかけて、最大値をとれば良い。
public class FoxPlayingGame { public double theMax(int nA, int nB, int paramA, int paramB) { double scoreA = paramA / 1000.0; double scoreB = paramB / 1000.0; double ret = scoreA * nA; for (int i = 0; i <= nB; i++) { ret = Math.max(ret, (scoreA * nA) * Math.pow(scoreB, i)); } return ret; } }
二つ二次元配列を用意して動的計画法らしく更新していくやり方の人もいるので、そっちも後で確認。
結果
Hard問題には手が出ず。レーティングは912から922に微増。
