RELAX NG
XMLスキーマ
ということです。
XMLやSGML等で文書を作成する際、その文書構造を定義する言語を言う。
Document Type Definition
略してDTD。スキーマ言語のひとつ。元々SGMLのスキーマ言語として開発され、SGMLから派生したXMLにおいても、スキーマ言語として採用されていました。しかし現在では、XMLのスキーマ言語としてDTDを利用するケースは少なくなっているようです。XMLが勧告された後、DTDに対して
などの問題が指摘されてきました。
RELAX NG
リラクシング。DTDに代わるXMLの新たなスキーマ言語のひとつ。RELAX NGで記述されたスキーマは、それ自身がXML文書となっています。RELAX NGでスキーマをXML文書として記述する方法を、XML構文といいます。RELAX NGでは、スキーマを簡潔な短縮構文(Compact Syntax)で記述することもできます。
たとえば、電子メールのアドレス帳を表現した簡単なXML文書を考えます。
<addressBook> <card> <name>John Smith</name> <email>js@example.com</email> </card> <card> <name>Fred Bloggs</name> <email>fb@example.net</email> </card> </addressBook>
これに対応するRELAX NGのXML構文は次のように書くことができます。
<element name="addressBook" xmlns="http://relaxng.org/ns/structure/0.9"> <zeroOrMore> <element name="card"> <element name="name"> <text/> </element> <element name="email"> <text/> </element> </element> </zeroOrMore> </element>
一方、これに対応するRELAX NGの短縮構文は次のように書くことができます。
element addressBook { element card { element name { text }, element email { text } }* }
短縮構文の方が見通しが良いですね。
Google XML Document Format Style Guide（日本語訳はこちら）ではXMLのスキーマ言語としてRELAX NGのcompact syntaxを使うべきであるとしています。
Validator
XMLスキーマはただXMLの文書構造を定義するためのものではなく、Validator（妥当性検証器）への入力とすることで作成したXML文書の妥当性を検証することができます。
RELAX NGのValidatorには次のようなものがあります。
- Jing
- RELAX NGの設計者のひとりであるジェームズ・クラーク氏が開発したValidator。XML syntax、compact syntaxの両方に対応している。
- RNV
- ANSI Cによる実装。compact syntaxにのみ対応している。
- Libxml2
- GNOMEプロジェクト。XML syntaxのみ対応。
Jing
で検証してみます。
今回は一冊の書籍を記述するための簡単なXML文書のためのスキーマを例に行います。一冊の書籍を記述するXML文書インスタンスは以下の通り。これをsomebook.xmlとします。
<?xml version="1.0" encoding="UTF-8"?> <book> <page>これは1ページです。</page> <page>これは2ページです。</page> </book>
XML syntaxによるスキーマは以下の通り。これをbook.rngとします。
<element name="book" xmlns="http://relaxng.org/ns/structure/1.0"> <oneOrMore> <element name="page"> <text/> </element> </oneOrMore> </element>
compact syntaxによるスキーマは以下の通り。これをbook.rncとします。
element book { element page { text }+ }
こちらから適当なバージョンのJingをダウンロードします。展開したディレクトリのbinの中にjing.jarがあるので以下のように検証します。
$ java -jar jing.jar book.rng somebook.xml
何も出力がなければ妥当だということです。
$ java -jar jing.jar -c book.rnc somebook.xml
compact syntaxによるスキーマで検証する場合は-cオプションが必要なので注意。
試しにスキーマは変えずに、以下のようなotherbook.xmlを検証してみた。
<?xml version="1.0" encoding="UTF-8"?> <!-- Invalid book instance --> <book> <title>これはタイトルです。</title> <page>これは1ページです。</page> <page>これは2ページです。</page> </book>
titletという要素はスキーマで定義されていません。これを検証すると次のようにエラーが出ました。
$ java -jar jing.jar book.rng otherbook.xml
otherbook.xml:4:10: error: element "title" not allowed anywhere; expected element "page"
うむ！
iPhoneデバイスの方向入力インタフェースについて考える
iPhoneデバイスにおける方向入力の歴史
App StoreからゲームをダウンロードしてiPhoneやiPod touchの上で遊べるようになってから久しいですが、その間iPhoneデバイスにおける方向入力の方法は様々なものが考案されてきました。
今日は、その歴史（と言ってもiPhoneを購入して１年未満。大してiPhoneでゲームをしない私の知っている範囲なので薄いですが）を振り返りつつ、最も良さそうなものを自作アプリに導入してみます。
ボンバーマンTOUCH
往年の名作ボンバーマンのiOS版。2008年の7月にリリースされました。ボンバーマンといえば上下左右の十字の動きですが、このゲームでは移動したい方向に左下にあるボンバーマンをスライドさせることで移動します（きっと。恐らく。多分そうでした・・・）。友人のiPhoneに入っていたのでやらせてもらったことがあるのですが、かなり操作し辛かった記憶があります。
このゲームの方向入力インタフェースは、据え置きゲーム機や携帯ゲーム気の十字キーに近いものです。しかし、十字キーは例えば上方向から右方向に入力を切り替える時に、十字キーの中心を軸にして指を移動させることで指を離さずに入力を切り替えること、所謂ドラッグができますが、当時の「擬似十字キー」を扱ったゲームではこういったことはできませんでした（maybe）。
ストリートファイターIV for iPhone/iPod touch
往年の（ｒｙストリートファイターの（ｒｙ。2010年の3月にリリースされました。ただでさえ難しい複雑なコマンド入力を要求される格闘ゲームをどうやってiPhoneでプレイするのよJKと思っていたらとても画期的な方向入力インタフェースが用意されていました。
画面にはゲームセンターの筐体にあるレバーが表示されており、これをドラッグすることによって滑らかな方向入力が可能になりました。また、入力値はデジタルではなくアナログなのでより細かい操作をすることができます。ボンバーマンのインタフェースが十字キーに似ていたのに対して、ストIVは任：3Dスティック/GK：アナログスティックに似ています。
今年の3月にこのゲームをプレイするまでiPhone上で本格的なゲームをやってこなかったのでボンバーマンからの進化に感動しました。
※ちなみに先ほどのボンバーマンも現在バージョン2.5になり、同様の方向入力インタフェースを採用しています。
FINAL FANTASY III
往ｎ（ｒｙFF3（ｒｙ。2011年の3月にリリースされました。リサイクル品です。FF3と言えばフィールド音楽の悠久の風がいいですね。iPhone/iPod touch版が1,800円、iPad版が2,000円というとんでもなく高いゲームです。
実際にiPhoneでプレイしたことはないのですが、ストIVのレバーに感動していた私にid:halwhiteが「FF3の方がすごいよ！」と教えてくれました。
このゲームではストIVのアナログスティックを更に進化させ、好きなところにアナログスティックを出現させることができます（らしいです）。なるほど素晴らしいアイディアだと思いました。さすが公式HPで「これまでのスクウェア・エニックスのiPhone用RPGタイトルのノウハウをいかし、直感的でプレイしやすい操作性を実現しています。」と公言するだけあります。ただのリサイクルではないのです。
FlexibleLeverView
ここまで見てきて一番素晴らしかったFINAL FANTASY IIIの拡張アナログスティックを自作アプリに導入してみます。どこにでも出現させることのできる柔軟性からFlexibleLeverと名づけ、このレバーを表示させることができるViewをFlexibleLeverViewとしました。
サンプル
どこかで見た戦車を操作するサンプル。
FlexibleLeverViewは滅びぬ、何処へでもあらわれるさ。
仕様
- ビューのどこかをタッチするとレバーが現れる
- 指を離すとレバーが消える
- レバーが現れている間はドラッグすることでレバーを操作できる
- レバーは土台を中心に一定距離しか移動できない（可動範囲は土台を中心とした円の内部になる）
- FlexibleLeverViewDelegateプロトコルはrequiredメソッド- leverInclined:を持ち、これはデリゲートにレバーの傾きを通知するものである
- FlexibleLeverViewはインスタンス変数id
delegate_を持つ
実装
これは非常に残念なのですが、マルチタッチイベントを受信するメソッドに「移動はしていないがタッチされ続けている」ことを受信するものはありません（「移動している」ことを受信する- touchesMoved:withEvent:メソッドはあります）。そのため、開発者が自分でインスタンス変数（e.g. BOOL beingTouched_）を用意して、- touchesBegan:withEvent:メソッドでこれをYESに、- touchesEnded:withEvent:メソッドでこれをNOにすることで「移動はしていないがタッチされ続けている」ことを知る手段を確保する必要があります。
なぜこんなことをするのかというと、アナログスティックの操作ではスティックが少しでも傾いていれば、移動していなくても入力されていることになるからです。本実装では指定イニシャライザである- initWithFrame:メソッドの中でNSTimerによって- notifyメソッドを定期的に呼び出すようにしています。- notifyメソッドではif (beingTouched)という条件で- leverInclined:メソッドを呼び出すことで、デリゲートにレバーの入力値を通知しています。
FlexibleLeverViewのインタフェース
@interface FlexibleLeverView : UIView { @private BOOL beingTouched_; CGPoint inputVector_; CGPoint baseLocation_; UIImageView *baseImageView_; UIImageView *ballImageView_; id<FlexibleLeverViewDelegate> delegate_; } @property (nonatomic, assign, readonly) CGPoint inputVector; @property (nonatomic, assign) id<FlexibleLeverViewDelegate> delegate; @end
inputVector_はレバーの土台からの入力量と向きを表すためのベクトルです。デリゲートでは- leverInclined:メソッドの中でこの値を読むことによって入力値を得、適当な処理をします。
baseLocation_は土台の位置を表します。
baseImageView_とballImageView_はそれぞれレバーの土台の画像とレバーの球体（？）の画像を扱うビューです。
FlexibleLeverViewはデリゲートメソッド- (void)leverInclined:(FlexibleLeverView *)flexibleLeverViewで自身をデリゲートに渡すので、勝手にインスタンス変数が変更されないようにinputVector_以外は公開せず、inputVector_もreadonlyにしてあります。
FlexibleLeverViewDelegateプロトコル
@class FlexibleLeverView; @protocol FlexibleLeverViewDelegate - (void)leverInclined:(FlexibleLeverView *)flexibleLeverView; @end
- touchesBegan:withEvent
タッチ開始を処理する- touchesBegan:withEvent:メソッドではbeingTouched_をYESにしてタッチされ続けている状態にし、タッチ開始場所を土台の位置としてセットします。また、土台の画像と球体の画像を表示させます。- (void)touchesBegan:(NSSet *)touches withEvent:(UIEvent *)event { UITouch *touch = [touches anyObject]; CGPoint location = [touch locationInView:self]; // Set |beingTouched_| |YES| beingTouched_ = YES; // Set |baseLocation_| baseLocation_ = location; // Add |baseImageView_| to self baseImageView_.layer.position = CGPointMake(location.x, location.y); [self addSubview:baseImageView_]; // Add |ballImageView_| to self ballImageView_.layer.position = CGPointMake(location.x, location.y); [self addSubview:ballImageView_]; }
- touchesMoved:withEvent:
ドラッグを処理する- touchesMoved:withEvent:メソッドでは土台からタッチしている位置へのベクトル（入力ベクトル）を計算します。この入力ベクトルの長さがレバーの可動範囲（土台を中心とした半径kValidLengthの円の内部）に収まっているかどうか調べます。収まっていない場合は、入力ベクトルの単位ベクトルを求めてkValidLength倍することで円周上を指すようにします。最後に土台へのベクトルと入力ベクトルを合成したベクトルの指す位置に球体を移動します。こうすることでレバーの可動範囲外までドラッグしても、それにつられてレバーの頭がもげてしまうことはありません。また、メソッドの最後でinputVector_の値を正規化しています。これにより、レバーからの入力値は(x, y) (-1.0<=x, y<=1.0)というベクトルでデリゲートに通知されます。
- (void)touchesMoved:(NSSet *)touches withEvent:(UIEvent *)event { UITouch *touch = [touches anyObject]; CGPoint location = [touch locationInView:self]; inputVector_ = CGPointMake(location.x - baseLocation_.x, location.y - baseLocation_.y); CGFloat length = sqrtf(powf(inputVector_.x, 2) + powf(inputVector_.y, 2)); if (length > kValidLength) { // Fit length of |vector| to |kValidLength| inputVector_.x = (inputVector_.x / length) * kValidLength; inputVector_.y = (inputVector_.y / length) * kValidLength; } ballImageView_.layer.position = CGPointMake(baseLocation_.x + inputVector_.x, baseLocation_.y + inputVector_.y); // Normalize |inputVector| inputVector_.x /= kValidLength; inputVector_.y /= kValidLength; }
- touchesEnded:withEvent:
タッチが終了したことを処理する- touchesEnded:withEvent:メソッドではbeingTouched_をNOにしてタッチされていない状態にし、土台の画像と球体の画像を消します。- (void)touchesEnded:(NSSet *)touches withEvent:(UIEvent *)event { // Set |beingTouched_| |NO| beingTouched_ = NO; // Remove |baseImageView_| and |ballImageView_| from superview [baseImageView_ removeFromSuperview]; [ballImageView_ removeFromSuperview]; }
- leverInclined:
最後にデリゲートで実装する- leverInclined:です。- (void)leverInclined:(FlexibleLeverView *)flexibleLeverView { CGPoint vector = flexibleLeverView.inputVector; NSLog(@"レバーを (%f, %f) 方向に入力中", vector.x, vector.y); // Move tank CGFloat dx = vector.x * kMaxTankVelocity; CGFloat dy = vector.y * kMaxTankVelocity; tankImageView_.layer.position = CGPointMake(tankImageView_.layer.position.x + dx, tankImageView_.layer.position.y + dy); // Rotate tank CGFloat angle = atan(vector.y / vector.x); if (vector.x < 0.0f) angle += M_PI; tankImageView_.transform = CGAffineTransformMakeRotation(angle); }
戦車をレバーが傾いている方向に移動させます。移動量として（入力値）×（戦車の速さの最大値）を計算することでレバーの傾きに応じて速さが変化します。こういったアナログな値を扱いやすくするために、レバーの入力値を正規化しました。また、進行方向に向かって戦車を回転させています。
複数のFlexibleLeverViewを配置したい場合（そんなことあるだろうか）は、- leverInclined:メソッドの中でif (flexibleLeverView == hogeFlexibleLeverView)などとして処理を分けてあげれば良いです。
[追記] 超信地旋回
戦車が超信地旋回をできるようになりました。
オレンジの領域が前進後退をするレバーのためのビューで、ブルーの領域が超信地旋回をするレバーのためのビューになっています。オレンジのレバーを上に入力すると前進、下に入力すると後退、ブルーのレバーを左に入力すると反時計回りに超信地旋回、右に入力すると時計回りに超信地旋回します。
- (void)leverInclined:(FlexibleLeverView *)flexibleLeverView { CGPoint vector = flexibleLeverView.inputVector; if (flexibleLeverView == leftLeverView_) { CGFloat dx = -vector.y * kMaxTankVelocity * cosf(tankDirection_); CGFloat dy = -vector.y * kMaxTankVelocity * sinf(tankDirection_); tankImageView_.layer.position = CGPointMake(tankImageView_.layer.position.x + dx, tankImageView_.layer.position.y + dy); } else if (flexibleLeverView == rightLeverView_) { tankDirection_ += vector.x * kMaxTankAngleRate; if (tankDirection_ < 0.0f) { tankDirection_ += (2.0f * M_PI); } else if (tankDirection_ > (2.0f * M_PI)) { tankDirection_ -= (2.0f * M_PI); } tankImageView_.transform = CGAffineTransformMakeRotation(tankDirection_); } }
本当は左のレバーで左の履帯を、右のレバーで右の履帯を動かすようにした方が本物感が増すのですが、面倒なので実装していません。去年のICPCアジア地区予選の模擬練習会でこんな問題あったなぁｗ
忍法壁抜けの術
スーパーメリオ
重力操作で天井から地面に落下する時、低い位置にある1ブロック分（16x16ピクセル）の厚さのレンガやブロックをすり抜けてしまうバグを発見しました。
めり込む男、メリオ。
原因と解決法
まず、垂直方向にマリオを移動させるメソッドは次のようになっていました。
// Verlet法によるジャンプの実装。 CGPoint tmpOrigin = self.origin; self.y += (self.y - prevOrigin_.y) + gravityAcceleration_; prevOrigin_ = tmpOrigin;
このように、現在いる位置に現在の垂直方向の速度を足し合わせて垂直方向に移動します。
そして、このコードの下の部分で当たり判定を行い、当たっていたら当たる直前の座標まで戻す、というやり方をしていました。
あまり高くない所からの落下ならば、このやり方でも問題はないのですが、このゲームでは重力操作による天井から地面までの急降下が頻繁に起こります。滞空時間が長くなる分、重力加速度を受ける時間も長くなり、落下速度がどんどん速くなります。その速度が一定値を超えた時、上記のやり方では当たり判定をし損ねてしまうということです。
これを解決するにはループを1つ設けて、単位速度（1ピクセル）ずつ移動させながら当たり判定を行うことです。
// Verlet法によるジャンプの実装。 CGPoint tmpOrigin = self.origin; float verticalVelocity = (self.y - prevOrigin_.y) + gravityAcceleration_; float unitVelocity = (verticalVelocity>0.0)?1.0:-1.0; prevOrigin_ = tmpOrigin; for (int i = 0; i < abs(verticalVelocity); ++i) { self.y += unitVelocity; // ここで当たり判定 }
ビームとブロックとの当たり判定でも同様のバグがあり、ブロックに対してゼロ距離射撃をするとビームが通り抜けてしまっていましたが、同じ修正を施すことで解決しました。
Google Code Jam 2011 Qualification Round
Qualification Round
Google Code Jam 2011の予選に参加しました。
24時間かけて4つの問題に挑戦し、25点以上獲得で次のラウンドに進むことができます。各問題には単純なアルゴリズムで十分間に合うsmallと、工夫したアルゴリズムでないとTLEになってしまうlargeの2種類の入力があり、largeの方が得点が高くなっています。また、smallは何度でも挑戦でき、その場で正否が判定されますが、largeはコンテスト中一回しか提出できず、コンテスト終了まで正否がわかりません。
昨年は3つの問題があり33点が予選通過のボーダーラインで、smallは各10点、largeは各23点だったので、少なくとも1問はlargeまで解かなければ予選通過はできなかったのですが、今年はsmallを3つ通せば予選通過できるように設定されていました。
予選通過できたかどうかコンテスト終了までわからない緊張感がなくなったのが残念のような、精神衛生上良かったような・・・。
また、競技者数も昨年より少し増えていたようです。
無事！
予選通過できました！
昨年はA問題とB問題でlargeを間違えて、C問題で何とかlargeを通して辛くも予選通過だったのですが、今年は全問largeまで解くことができました。
AとBは言われた通りに実装する問題で、特に高速化などは意識せずに解けましたが、C-largeとDに大きく時間を取られてしまいました。
A. Bot Trust
秒数でループを回してしまうとlargeで落ちてしまうのかもしれないです。順番の何番目か、すなわちターンでループを回せばO(N)（1≦N≦100）で解けます。
ブルーとオレンジのロボットがそれぞれ廊下の上に置かれておりテストをする。
廊下には100個のボタンが一列に1メートル間隔で並んでいて、1から100までラベリングされている。
ブルーとオレンジは廊下のボタン1の位置からスタートする。
1秒間の中でロボットは
・どちらかの方向に1メートル歩く
・今いる場所のボタンを押す
・ボタンを押さずにその場に留まる
のどれかの行動をすることができる。
テストというのは決められた順番でボタンを押すことである。
例えば、
O 2, B 1, B 2, O 4
という順番が与えられたら、まずオレンジがボタン2を押し、その次にブルーがボタン1を押し、・・・という風に実行される。
ブルーとオレンジは最短何秒でテストをクリアできるか？
次にボタンを押すべきロボットは次のボタンの位置まで移動させてボタンを押させ、その間にもう一方のロボットは次に自分が押すべきボタンの位置まで出来る限り移動します。
#include <cstdio> #include <vector> #include <map> using namespace std; const int kInf = 1 << 20; int main() { int T; scanf("%d", &T); for (int t = 1; t <= T; ++t) { int N; scanf("%d", &N); vector<pair<int, int> > blue_seq; vector<pair<int, int> > orange_seq; for (int i = 0; i < N; ++i) { char R; int P; scanf(" %c %d", &R, &P); if (R == 'B') { blue_seq.push_back(make_pair(P, i)); } else { orange_seq.push_back(make_pair(P, i)); } } blue_seq.push_back(make_pair(-1, kInf)); orange_seq.push_back(make_pair(-1, kInf)); int ans = 0; int blue_turn = 0, orange_turn = 0; int blue_pos = 1, orange_pos = 1; for (int turn = 0; turn < N; ++turn) { pair<int, int> blue_button = blue_seq[blue_turn]; pair<int, int> orange_button = orange_seq[orange_turn]; if (blue_button.second == turn) { int distance = abs(blue_button.first - blue_pos); int delta = orange_button.first - orange_pos; blue_pos = blue_button.first; if (abs(delta) < (distance)+1) { orange_pos += delta; } else { orange_pos += (delta>0?1:-1) * (distance+1); } ans += distance+1; ++blue_turn; } else if (orange_button.second == turn) { int distance = abs(orange_button.first - orange_pos); int delta = blue_button.first - blue_pos; orange_pos = orange_button.first; if (abs(delta) < (distance)+1) { blue_pos += delta; } else { blue_pos += (delta>0?1:-1) * (distance+1); } ans += distance+1; ++orange_turn; } } printf("Case #%d: %d\n", t, ans); } }
B. Magicka
Twitterでキーワード「gcj」のタイムラインを見ていたら、問題の読解で詰まっている人が多かったようです。
魔法使い（wizardは男。故に魔法少女ではない）であるあなたは、8種類のベースエレメント、すなわちQ、W、E、R、A、S、D、Fを生み出すことができる。
生み出したエレメントはエレメントリストに追加される。
ある特定のベースエレメントのペアは結合し、18種類のノンベースエレメントとなる。
結合ペアがエレメントリストの後ろにある時、2つのエレメントはすぐさまノンベースエレメントになる。
また、ある特定のエレメントのペアは反発し合っている。
あなたがベースエレメントを生み出した後、すぐに結合が起こらない時、エレメントリストに反発ペアが含まれている場合、エレメントリストの全てのエレメントが消えてしまう。
生み出すエレメントのリストが与えられ、すべてのエレメントを生み出し終わった時のエレメントリストはどうなっているか？
問題文だけで十分に理解できなくても、サンプルケースがどのようになっているかしっかり確認すれば、問題文と照らし合わせつつ題意がつかめる気がします。
私は結合ペア、反発ペアをそれぞれ26x26の二次元配列に格納して、エレメントリストを操作していきました。
注意すべき点、というほどでもないですが、反発ペアを見つける時はO(N^2)で毎回すべてのエレメントのペアを確認する必要はなくて、新しく末尾に追加されたエレメントとその他のエレメントのペアをO(N)でチェックすれば良いです。仮に全てチェックしても全体のオーダーはO(N^3)（2≦N≦1000）なので、特に問題ないはずです。
#include <iostream> #include <string> using namespace std; char combine_rules[26][26]; bool opposed_rules[26][26]; int main() { int T; cin >> T; for (int t = 1; t <= T; ++t) { int C; cin >> C; memset(combine_rules, '\0', sizeof(combine_rules)); for (int i = 0; i < C; ++i) { string combine_rule; cin >> combine_rule; int tx = combine_rule[0]-'A'; int ty = combine_rule[1]-'A'; char tc = combine_rule[2]; combine_rules[ty][tx] = tc; combine_rules[tx][ty] = tc; } int D; cin >> D; memset(opposed_rules, false, sizeof(opposed_rules)); for (int i = 0; i < D; ++i) { string opposed_rule; cin >> opposed_rule; int tx = opposed_rule[0]-'A'; int ty = opposed_rule[1]-'A'; opposed_rules[ty][tx] = true; opposed_rules[tx][ty] = true; } int N; string elements; cin >> N; cin >> elements; string element_list = ""; for (int n = 0; n < N; ++n) { element_list += elements[n]; int len = element_list.length(); if (len < 2) continue; int tx = element_list[len-2]-'A'; int ty = element_list[len-1]-'A'; if (combine_rules[tx][ty] != '\0') { element_list = element_list.substr(0, len-2); element_list += combine_rules[tx][ty]; } len = element_list.length(); if (len < 2) continue; tx = element_list[len-1]-'A'; for (int i = len-2; i >= 0; --i) { int ty = element_list[i]-'A'; if (opposed_rules[tx][ty]) { element_list = ""; break; } } } printf("Case #%d: [", t); int len = element_list.length(); for (int i = 0; i < len; ++i) { printf("%c", element_list[i]); if (i != len-1) printf(", "); } printf("]\n"); } }
C. Candy Splitting
パトリックの加算の仕方は排他的論理和（XOR）です。C言語やC++ではこれを行う演算子^があるので、パトリック加算はこれを使えば良いです。
ショーンとパトリックの兄弟が両親からキャンディーの袋詰めをもらった。
キャンディーにはその価値を表す正の整数が書かれており、兄弟はこのキャンディーを2人で分ける。
まず、兄であるショーンがキャンディーを2つの山に分ける。そして、どちらか1つの山を弟パトリックに渡す。
次に、パトリックがそれぞれの山のキャンディーの価値を足し合わせる。もしそこで2つの山の合計が等しくなければパトリックは泣き出してしまう。不幸なことにパトリックは幼いため、正確に足し算をすることができない。彼は数を二進数で加算することができるのだが、桁上がりを忘れてしまう。例えば、12（二進数で1100）と5（二進数で101）を足し合わせると
1100
＋ 0101
- -
1001
で、9になってしまう。ショーンは正確に足し算ができ、弟を泣かせずにできるだけ多くのキャンディーを取りたい。
もし可能なら、ショーンはキャンディーの山をパトリックが価値が同じだと思うように2つに分けたい。
すべてのキャンディーの価値が与えられた時、価値が同じように分けることが可能かどうか判定し、もし可能ならショーンが得られるの山の価値の最大値を求めよ。
キャンディー山を2人で分けるのは分割問題で、2^N通りの分け方があり、これは指数オーダーなのでN=20くらいがまでが限界です。
smallでは2≦N≦15なので、愚直に全通り試す解法でも恐らく通すことができます。
本番では実際に愚直な方法で通したのですが、なぜ「恐らく」かということは後ほど。
愚直な解法
愚直な方法で2つの分割を全通り生成するには、ビット演算を使うことができます。
例えば、2^N通りだったら次のようになります。
for (int bits = 0; bits < (1<<N)-1; ++bits) { for (int i = 0; i < N; ++i) { int bit = (bits>>i)&1; if (bit == 1) { SomeFunc(); } else { TheOtherFunc(); } } }
すべての分け方を試してみて、条件を満たす分け方がなかった場合にNOと出力する方法だとO(2^N)になります。
しかし、この問題ではNOの判定はもっと簡単にできるのです。
ある分け方が条件を満たしているならば、ショーン山のパトリック加算での価値の合計false_sean_sumとパトリック山のパトリック加算での価値の合計false_patrick_sumはすべて同じビットが立っているので、それらの排他的論理和、すなわちfalse_sean_sum ^ false_patrick_sumは0になります。・・・（＊）
ここで、ショーン山のキャンディーの数をNs、それぞれのキャンディーの価値をCs1, Cs2, ..., CsNs、パトリック山のキャンディーの数をNp、それぞれのキャンディーの価値をCp1, Cp2, ..., CpNpとすると、false_sean_sumとfalse_patrick_sumはそれぞれ、
となります。
false_sean_sum = Cs1 ^ Cs2 ^ ... ^ CsNs
false_patrick_sum = Cp1 ^ Cp2 ^ ... ^ CpNp
したがって、（＊）と合わせて考えると、ある分け方が条件を満たしているならば、
となることがわかります。
C1 ^ C2 ^ ... ^ CN = (Cs1 ^ Cs2 ^ ... ^ CsNs) ^ (Cp1 ^ Cp2 ^ ... ^ CpNp) = false_sean_sum ^ false_patrick_sum = 0
よって、C1からCNの排他的論理和を計算することによって、条件を満たす分け方が存在するかどうかを判定することができます。
話が長くなりましたが、先ほど「恐らく」と言った理由の1つは、愚直な解法の中でこの判定法を使っていたことです。これにより、2^N通りの分け方を最後まで調べることはなくなりました。
更にもう1つの理由としては、キャンディーの価値を予めソートしておいて、ショーンがより多くの価値の山を得られる分け方から調べていったことです。
もちろんこの方法を使ったところでO(2^N)は変わりませんが、多少の高速化を期待してこうしました。
結局
- XORを使った判定法を利用した
- キャンディーの価値をソートしておいた
というところで、smallを提出しました。
スマートな解法
smallを提出した後でlargeの解法が思いつかなかったので放置して、DのGoroSortに取り組みましたが、パッと思いついた解法に飛びついてsmallでincorrectを出してしまったので戻ってきました。
O(2^N)という状況を打破してくれるスーパーな解法はDPなのかなぁと思いつつ（DPが苦手です。と同時に、何やらとんでもない計算量の解法しか思いつかない時は、DPが正解なのではないかと思ってしまいます）、ノートに色々な組み合わせで二進数を書いていたら閃きました。
先程のXOR判定法を使って、条件を満たす分け方が存在すると判明したキャンディー山は、どんな分け方をしても条件を満たすのです。（普通の人は判定法を思いついたら、すぐにここまでたどり着くのではないだろうか・・・）
ということで、条件を満たす分け方が存在すると分かったら、あとは1番価値の低いキャンディーをパトリックにあげるだけです。（ひどい）
#include <cstdio> #include <vector> #include <algorithm> using namespace std; const int kInf = 1 << 20; int main() { int T; scanf("%d", &T); for (int t = 1; t <= T; ++t) { int N; scanf("%d", &N); vector<int> candies(N); for (int i = 0; i < N; ++i) { scanf("%d", &candies[i]); } int candies_sum = 0; int true_candies_sum = 0; int min_value = kInf; for (int i = 0; i < N; ++i) { candies_sum ^= candies[i]; true_candies_sum += candies[i]; min_value = min(min_value, candies[i]); } if (candies_sum != 0) { printf("Case #%d: NO\n", t); } else { printf("Case #%d: %d\n", t, true_candies_sum - min_value); } } }
D. GoroSort
まずGoroって誰？ってなる問題。頭の中で操作をシミュレートし続けたせいで、4本腕のロボットが力強くテーブルを叩き続ける絵が頭に焼き付いてしまった。
吾郎は4本の腕を持っている。
テーブルの上にN個の異なる数字が書かれたエレメント（何だ？）が置かれておりこれをソートしなければならない。
吾郎はアルゴリズムに強くないが、腕っ節には自身がある。
吾郎はまず、2つの手でいくつかのエレメントを押えつける。そして、残りの2つの拳で力いっぱいテーブルを叩く。
すると押さえつけていなかったエレメントがランダムにシャッフルされる。
この操作を繰り返してソートする時、吾郎がテーブルを叩く回数の期待値を求めよ。
まず初めにCのlargeから逃げてきて考えたのは、バブルソートの回数を数えればいいんだということ。そしてincorrect。
次にCのlargeを終えて考え直したのは、何も隣接する2つのエレメントを交換しなくてもいいんだということで、ループの度に最もWin-Winの関係になれる2つのエレメントをO(N^2)で探してスワップするという方法。そしてincorrect。
これに微調整を加えて提出。そしてincorrect。
悩みあぐねること数時間。やっと気づいた。
それまでは2つより多いn個のエレメントをシャッフルすると、全てが適切な位置になるのにn!回叩く必要があるので、堅実に2つずつやるべきだと思っていたのですが、正しい位置にないエレメントを残して盛大にテーブルを叩くと、平均して毎回1つは正しい位置に移動するのではないか。
そして正しい位置に移動したエレメントを押さえて、また叩く。すると平均毎回1つずつ正しい位置に収まるので、元の並びの内で正しい位置にない要素の数が求める期待値になるのではないか。
証明をしたわけではないので確証はなかったですが、既に3回incorrectを出しているのでダメもとで提出してみるとcorrect。
仮説は正しかったようで、Contest Analysisを見るとしっかりとした証明が書かれています。
#include <cstdio> #include <vector> using namespace std; int main() { int T; scanf("%d", &T); for (int t = 1; t <= T; ++t) { int N; scanf("%d", &N); vector<int> elems(N); for (int i = 0; i < N; ++i) { scanf("%d", &elems[i]); } double ans = 0.0; for (int i = 0; i < N; ++i) { if (elems[i] != i+1) ++ans; } printf("Case #%d: %lf\n", t, ans); } }
感想
初の満点を取れたのは嬉しい。ですが、
- 解法を思いつくまで、思いついた解法を実装するまで、と全体的に時間がかかり過ぎ
- Cは正しい解法の直前まで行ったのに、そこから悩んでしまった
- Dは閃き、勘に依るところが大きかった。強引に実装できたかもしれない
という反省点があります。
Round 1まで2週間弱あるので過去問で練習をしたいと思います。
と反省も多いけれど、やっぱり楽しかった！scoreboardで自分の順位が変動するのはワクワクするし、卒業してしばらく会っていない（というほど会ってなくもなかった）先輩方をFriendsで見つけてやっぱりすごいなぁと感心したり、競技プログラミングに興味を持ち始めて初参戦した後輩がいたり、Twitterのタイムラインで知らない人が同じ気持ちになっていたり。
なんかいいよね！
儚く消ゆる
プチ更新
iPhoneで2Dアクションゲームを開発中。
前回の記事では、
まで完成していました。
今回はプチ更新で「ビームとターゲットとの当たり判定」を実装しました。
ターゲットをこわせ
開発予定のゲームは複数のデバイスで通信対戦を想定しているので、キャラクターの出すビームは他のキャラクターに当たらなければなりません。
ですが通信部分が未実装なので、今回は他のキャラクターに見立てたターゲットを用意し、ビームとキャラクターとの当たり判定を実装しました。
CollisionDetection
Fighterクラスは自分の撃った弾（ビームや弾丸）をNSMutableArrayのインスタンスとして持っています。引数として当たり判定されるオブジェクトを受け取るメソッドcollisionDetectionは以下のようになっています。
- (BOOL)collisionDetection:(Widget *)widget { for (int i = 0; i < [shotsArray_ count]; ++i) { Shot *shot = [shotsArray_ objectAtIndex:i]; if ([shot hasCollidedWithWidget:widget]) { [shotsArray_ removeObjectAtIndex:i]; [shot disappear]; [widget disappear]; return YES; } } return NO; }
shosArray_に自分の撃った弾が格納されているので、全ての弾についてオブジェクトとの当たり判定を行います。もし当たっていれば当たった弾はshotsArray_から削除し、弾とオブジェクトを画面から消します。
弾を表すShotクラスのメソッドhasCollidedWithWidgetは以下のようになっています。
- (BOOL)hasCollidedWithWidget:(Widget *)widget { return CGRectIntersectsRect(self.frame, widget.frame); }
CGRectIntersectsRectメソッドはCGRectの変数２つを引数として受け取り、２つの矩形が交わっていれば真を返してくれます。
儚く消ゆる
ビームに当たったターゲットにはパッと消えるのではなく、パリーンと儚く消えて欲しい。
そこで、Targetクラスのメソッドdisappearではアニメーションを使ってこれを実現しています。
- (void)disappear { [UIView beginAnimations:nil context:NULL]; [UIView setAnimationDelegate:self]; [UIView setAnimationDidStopSelector:@selector(didFinishAnimation:)]; [UIView setAnimationDuration:1.0]; self.alpha = 1.0; self.image = [UIImage imageNamed:kBrokenTargetImageName]; self.alpha = 0.0; [UIView commitAnimations]; }
今までUIImageViewのanimationImagesプロパティに複数の画像をセットするアニメーションは使ったことがあったのですが、今回はアニメーション実行→UIImageViewを親ビューから削除ということをしたかったので、アニメーションの終了を通知してもらう必要がありました。方法を探していたらこちらの記事（「プログラミングノート UIViewで手軽にアニメーションを実行する方法」）で発見！
UIViewのクラスメソッドを使ってアニメーションの細かな設定を行えるようです。
アニメーションの終了を通知してもらうには、setAnimationDelegateで通知を受け取るオブジェクトを指定し、setAnimationDidStopSelectorで終了を通知してもらうメソッドを指定してやればOKです。
終了通知を受け取るメソッドdidFinishAnimationでは自身を親ビューから削除しています。
- (void)didFinishAnimation:(id)sender { [self removeFromSuperview]; }
こんな感じになります！
2Dアクションゲームの当たり判定と当たらない判定
iPhoneで2Dアクションゲーム
CEDEC 2011にiPhoneで2Dアクションゲームを出展予定。
それの練習ということで2Dアクションゲームの当たり判定について学ぶなど。
実はまだ審査中なのでこの努力は水泡に帰すかもしれないけれど、人生に無駄なことなどないと信じよう。
プロトタイプアプリ「1-2」
何かに似てるけど他人の空似。
配管工のおっさんがレンガや文字の書かれたブロックが配置されたステージで縦横無尽に飛び回る。
開発予定のゲームはiPhoneの加速度センサーを利用した「重力の操作」が肝になっているのでその部分も実装。デバイスを反転させると重力も反転しておっさんが落下する。
UIDeviceOrientationLandscapeRight（ホームボタンが右側に来る向き）の時はいつも通り地面に立っている。
iPhoneをひっくり返すと・・・
天井が地面に、地面が天井に。
ビームも出るよ！
ちなみに画面右下に表示されている半透明の円はジャンプボタン（赤色）とアタックボタン（黄色）です。
ジャンプの実装
なめらかなジャンプを実装することは2Dアクションゲームを作る上で必須。以前「iPhoneで横スクロールアクションゲームを作りたい」でジャンプゲームを実装した時は、キャラクターに垂直方向の速度と加速度を持たせて計算していました。これでも間違いではないのですが、ジャンプゲームの元祖「マリオ」のジャンプはVerlet積分という計算法で実装しているようなので、今回はこちらで実装してみました。
こちらのブログを参考にさせて頂きました。「Gemmaの日記 マリオのジャンプ実装法とVerlet積分」
当たり判定
やっぱり2Dアクションゲームを作る上でまず苦労するのはフィールドにあるオブジェクトとの当たり判定です。
フィールドに斜面などを作ってしまうとかなりの高等技術が必要になる（に違いない！）ので、まずはフィールドを16x16ピクセル単位で区切って、ブロック（レンガやハテナブロック）の有無を二次元配列で確保しました。
// フィールドデータ extern int gField[kFieldHeight][kFieldWidth];
厳密にはブロックがない場所は0に、ブロックがある場所は1以上の数字にしてあり、ブロックの種類毎に数字を変えて描画するときに役立てています。
おっさんを左に移動するメソッドmoveLeftの中では、おっさんの左側のブロックとの当たり判定を行います。おっさんの位置データはfloat型なので、これをフィールド情報を格納した二次元配列のインデックスに変換します。
// 左方向のブロックとの当たり判定 int fieldX = floor(self.x / kBlockWidth); int fieldY = floor((self.y+self.height/2) / kBlockHeight); if (gField[fieldY][fieldX]) { self.x = kBlockWidth * fieldX + kBlockWidth; [self stopRunning]; return; }
おっさんを垂直方向に移動するメソッドmoveVertical（ずっとmoveVerticallyの方が良かった気がしている）の中では、上方向に速度がある時はおっさんの上側のブロックとの、下方向に速度がある時はおっさんの下側のブロックとの当たり判定を行います。
// 半身の当たり判定をするために、はみ出している部分を計算し（protrusion）、 // はみ出している側に合わせて補正値|offset|を計算する。 double protrusion = (self.x+self.width/2.0) - kBlockWidth * floor((self.x+self.width/2.0) / kBlockWidth); int offset = 0; if (protrusion <= (0.3*kBlockWidth)) { offset = -1; } else if (protrusion >= (0.7*kBlockWidth)) { offset = 1; } // 上方向に速度があるならば、上方向のブロックとの当たり判定 // 下方向に速度があるならば、下方向のブロックとの当たり判定 if (self.y - prevOrigin_.y < 0) { int fieldX = floor((self.x+self.width/2.0) / kBlockWidth); int fieldY = floor(self.y / kBlockHeight); if (gField[fieldY][fieldX] || gField[fieldY][fieldX+offset]) { self.y = fieldY * kBlockHeight + kBlockHeight; if (status_.isUpsideDown) { status_.isJumping = NO; } } } else if (self.y - prevOrigin_.y > 0) { int fieldX = floor((self.x+self.width/2.0) / kBlockWidth); int fieldY = floor((self.y+self.height) / kBlockHeight); if (gField[fieldY][fieldX] || gField[fieldY][fieldX+offset]) { self.y = fieldY * kBlockHeight - kBlockHeight; if (!status_.isUpsideDown) { status_.isJumping = NO; } } }
大事なのはコードの最初の方で準備している「半身の当たり判定」です。
そもそも仕様ではおっさんは半身でブロックに立つことができます。
ですが、半身の当たり判定をしない、すなわち自分の真下（真上）のブロックとしか当たり判定をしないと、ちょっと足が掛かっているだけではすり抜けてしまいます。
しっかり２ブロック分の当たり判定をしておくことですり抜けを防止することができます。
当たらない判定
もう１つ大事なのは「当たらない判定」です。
ジャンプしていない時でも常に重力は受けているので、ブロックの上で足を踏み外したらおっさんは落下しなければなりません。
そうしないとこんなファンタスティックスなことに・・・
このような空中歩行をさせないために「当たらない判定」が必要なのです。
moveVerticalの中ではジャンプ中でない時は当たらない判定をして足下にブロックがない場合は落下状態に移行します（実装の上では落下状態とジャンプ状態は区別していません）。
// ジャンプ中ではない場合は当たらない判定をする // 上下さかさまなら上方向のブロックと当たらない判定 // そうでないなら下方向のブロックと当たらない判定 if (!status_.isJumping) { if (status_.isUpsideDown) { int fieldX = floor((self.x+self.width/2.0) / kBlockWidth); int fieldY = floor(self.y / kBlockHeight); if (gField[fieldY][fieldX] == 0) { prevOrigin_ = self.origin; status_.isJumping = YES; } } else { int fieldX = floor((self.x+self.width/2.0) / kBlockWidth); int fieldY = floor((self.y+self.height) / kBlockHeight); if (gField[fieldY][fieldX] == 0) { prevOrigin_ = self.origin; status_.isJumping = YES; } } }
「当たってない判定」の方がいいかな、と思ったりした。
Google Code Jam 2011に登録完了
Google Code Jam 2011
昨年に続いてGoogle Code Jamに参加します。昨年はQualification Roundは突破できましたが、Round 1ではSub-Round AからCまで全て参加しましたが尽く敗退し、苦い経験となっています。
昨年は競技プログラミングに出会い、PKU Online Judgeで鍛え、ACM-ICPCにも参加しました。最近はというと、チームでのシステム開発プロジェクトを経験したり、iPhoneアプリの開発をしたりと実務的なプログラミングが多く、競技プログラミングはご無沙汰気味でしたが、今回のGCJを機に少しずつ再開できたらと思います。プログラミングを好きになった原点なので！
過去問
GCJの公式サイトから過去問に取り組むことができます。少しでも競技プログラミングのカンを取り戻すために昨年のQualification Roundの問題に取り組みました。
Snapper Chain
指パッチンでON/OFFが切り替わるデバイスSnapperを使って電球を点灯させる問題。昨年は律儀にSnapperの動作をシュミレーションし、見事にLargeで落ちてしまいました。実は電源から連結されたSnapperのON/OFFの動作は二進数のビットそのもので、これに気づくとすごく簡単に、かつ高速なプログラムを書くことができます。実にGCJらしい問題だと思います。
昨年も載せましたがソースコードを再掲。
#include <cstdio> using namespace std; int T, N, K; int main() { scanf("%d", &T); for (int t = 1; t <= T; ++t) { scanf("%d %d", &N, &K); int mask = (1<<N)-1; printf("Case #%d: %s\n", t, (mask&K)==mask?"ON":"OFF"); } }
Fair Warning
未だに問題の意味がわかりません。"slarboseconds"をググッても意味がわからずにパニクった記憶があります。どうやら最大公約数がポイントらしいということはわかるのですが、Largeでは10^50まで扱わなければならないため、私の場合はJavaでBigIntegerを使わなければなりませんでした。そういうこともあり手を付けていなかった問題。
Javaも良く分からないので今年は多倍長整数をどうしようと思っていたのですが、GCJでは使用するプログラミング言語に制約がないのでRubyを使ってみることにしました。Rubyも基礎程度しか知らないのですが、Javaよりも多倍長整数を扱いやすいので今年はこちらで行ってみます。
def calc_gcd(a, b) return b!=0?calc_gcd(b, a%b):a end class FairWarning def initialize @C = gets.chop.to_i puts @C for c in 1..@C a = gets.chop.split @N = a[0].to_i ts = [] for i in 1..@N ts << a[i].to_i end result = solve(ts) print "Case ##{c}: #{result}\n" end end def solve ts ts = ts.sort ds = [] for i in 0..ts.size-2 d = ts[i+1]-ts[i] unless d == 0 ds << d end end gcd = ds[0] for i in ds gcd = calc_gcd(gcd, i) end ret = ts[0] % gcd unless ret == 0 ret = gcd - ret end return ret end end FairWarning.new
Theme Park
ジェットコースター大好きグループがN組いて、各グループはg1, ..., gN人。ジェットコースターの定員はk人で、同じグループの人がバラバラに乗るのは嫌がるし、順番を抜かされるのも嫌がる。乗り終わったグループは列の後ろに並ぶ。一日R回ジェットコースターを運行するとして、一日の売上は何ユーロか？（１ユーロ/人）
これも単純にシュミレーションをするとLargeでTLEになってしまう。グループの数は高々10^3なので、全グループについてそのグループを先頭としたときに乗れる人数とグループ数を予め計算しておけば良い。
#include <cstdio> using namespace std; int T, R, k, N; int main() { scanf("%d", &T); for (int t = 1; t <= T; ++t) { scanf("%d %d %d", &R, &k, &N); int gs[N]; for (int i = 0; i < N; ++i) { scanf("%d", &gs[i]); } int nps[N]; int ngs[N]; for (int i = 0; i < N; ++i) { int np = 0, ng = 0; for (int j = 0; j < N; ++j) { if (np + gs[(i+j)%N] > k) break; np += gs[(i+j)%N]; ++ng; } nps[i] = np; ngs[i] = ng; } int pos = 0; long euros = 0; for (int r = 0; r < R; ++r) { euros += nps[pos]; pos = (pos+ngs[pos])%N; } printf("Case #%d: %ld\n", t, euros); } }昨年よりも圧倒的に練習が足りないですが、とりあえず予選通過はしたいと思います！
