2012-10-13

rspec-mock broken by `scope :public` in ActiveRecord::Base

dev
class Foo < ActiveRecord::Base
  scope :public, -> { … } # this overrides Module#public
end

class FoosController < ApplicationController
  def create
    @foo = Foo.new(params[:foo])

    respond_to do |format|
      if @foo.save
        format.html { redirect_to @foo, notice: 'foo was successfully created.' }
        format.json { render json: @foo, status: :created, location: @foo }
      else
        format.html { render action: "new" }
        format.json { render json: @foo.errors, status: :unprocessable_entity }
      end
    end
  end
end

describe FoosController do
  describe "POST create" do
    describe "with invalid params" do
      it "re-renders the 'new' template" do
        # rspec-mock expects Foo.public to `Module#public`
        Foo.any_instance.stub(:save).and_return(false)

        post :create, {:foo => {}}, valid_session
        response.should render_template("new")
      end
    end
end

scope :public overrides Module#public method in the model, but rspec-mock expects Foo.public to be Module#public. rspec-mock calls Foo.public with arguments, so it raises ArgumentError on line scope :public. :/

 ArgumentError:
   wrong number of arguments (1 for 0)

こんな感じで scope :public, -> {…} していると、rspec-mock が Module#public(*name) を期待して引数付きで public を呼んで崩壊する模様。

Foo を stub ってるせいでテストがコケるみたいです。

Published at 2012-10-13 01:06:17 +0900 | Permalink
2012-10-06

rspec-rails は Gemfile で development グループにも入れてあげよう

dev

なんか rspec-rails でテストが生成されないなーと思ってたらこういう事だった。ちゃんとREADME読めっていう話ですね!

https://github.com/rspec/rspec-rails#configure

It needs to be in the :development group to expose generators and rake tasks without having to type RAILS_ENV=test.

group :test, :development do
  gem "rspec-rails"
end
Published at 2012-10-06 18:58:06 +0900 | Permalink
2012-09-09

socket.io で任意のeventを一つのlistenerで受け取る

dev

https://gist.github.com/3683181

無理っぽいのでこういうhackをするしかない。 Eventのinvoke周りは node.js 由来の EventEmitter を使っていて、その emit メソッドをラップして、本物のemitを実際に渡された引数で渡した後、別のeventとしてemitに飛んできた引数をargsとして渡しているだけ。

EventEmitter の emit は $emit に姿を変えていた

しかし socket.io がドキュメント無いのは驚いた。こういう知名度があって便利なライブラリ、わりとドキュメント無いのが多い。ドキュメントが、無い。人のこと言えないけど。

小さいコードなら今回のように自分で読んで解決できるけど、Rails のように巨大なライブラリがドキュメントなかったら絶望(デデドン) だと思う。

利用例

こんなふうに使います。

public domain なのでお好きにどうぞ。

Published at 2012-09-09 16:46:37 +0900 | Permalink
2012-05-10

Show response time in Rack app (Sinatra)

dev

Sinatra::Base + Thin doesn't show request path and response time.

You can show response time by writing this class and modifying your run line in your config.ru

日本語

Sinatra と Thin 使うと、レスポンスタイム出してくれないから、Rack の run に渡すクラスに、一つオブジェクトを挟めてレスポンス返すまでの秒数を計測するクラスを書いた。

config.ruStats クラスを書き込んで、run の行をちょっといじれば表示してくれます。

Published at 2012-05-10 00:32:07 +0900 | Permalink
2012-05-06

Ruby から iTunes DJ の次の曲を指定する

dev

play に対抗する物を作っていて、同じように iTunes DJ を使おうとして play 氏がどうやって iTunes DJ に次の曲として指定してるのか みたら、Add to queue で次の曲ではなくキューの最後に追加するだけ、という仕様で全く参考にならなかった。

自分は単純にボタンを押したら次に再生されるようにしたかったので、頑張って次の曲に追加するスクリプトを rb-appscript 使って書いた。

iTunes の Applescript インターフェース、プレイリストに曲を追加するのは末尾に追加しかできなくて、要するに以下の手順を踏まないと間に曲を差し込むことができない:

  1. 末尾に追加したい曲を入れる: [曲1, 曲2, 曲3, 追加したい曲]
  2. 末尾に既存の曲を入れる: [曲1, 曲2, 曲3, 追加したい曲, 曲1*, 曲2*, 曲3*]
  3. 先頭にある既存の曲を消す: [追加したい曲, 曲1*, 曲2*, 曲3*]

この方法しか無いんじゃないかと思ってググってたらやっぱりこれしか方法がなくて、 しかしググったおかげか、ループを使って消してくのかと思ったらたった 3 行で実現できるぽくて、ループでやると滅茶苦茶遅い事が判明した。

http://hints.macworld.com/article.php?story=20040830035448525

Applescript 本当に面白い仕様だと思う。

iTunes の設定

iTunes DJ で voting を有効にしてるとダメなので設定をオフにしましょう。

Voting を有効にしてると、プレイリストが曲の重複を許さなくなり、上述の方法が通用しなくなり道が閉ざされる。

Published at 2012-05-06 11:37:38 +0900 | Permalink
2012-05-01

Building mruby for android

dev

android-ndk を standalone に使えるようにした のはこのためなのだけれど、

mruby (a.k.a. RiteVM, 軽量 Ruby) を動かせるかと思ってセットアップした。結果的には普通に動きました。

ただ、ビルドするときに mrbc をホストで実行できる必要があるみたいなので、ちょっと弄った。

make-standalone-toolchain.sh で作られた gcc 等 に PATH が通ってる事を前提として、以下の手順でビルドできました:

$ git clone https://github.com/mruby/mruby.git
$ cd mruby
$ make
$ cp bin/mrbc .
$ make clean && rm **/*.o

$ make CC=arm-linux-androideabi-gcc LL=arm-linux-androideabi-gcc
...
/bin/sh: ../bin/mrbc: cannot execute binary file

$ cp ./mrbc bin/mrbc

$ make CC=arm-linux-androideabi-gcc LL=arm-linux-androideabi-gcc 
# ↑ will fail at building mrubysample. you can just ignore because it's not needed.

$ file bin/mruby
bin/mruby: ELF 32-bit LSB executable, ARM, version 1 (SYSV), dynamically linked (uses shared libs), not stripped

あとは ./bin/mrubyadb push 等で Android に転送して実行できるようにしてあげればいいと思います。

Have fun!

Published at 2012-05-01 23:52:08 +0900 | Permalink
2012-05-01

Using toolchains standalone in android-ndk

dev

Android には NDK (Native Development Tools) がある。要するに C とか C++ でちょっと高速なアプリケーションを書いたりできるらしい。まぁ、察せるとおりクロスコンパイラが入っている。

Android で動くバイナリとかを吐く一番速い手段がたぶんコレ。

OS X だと homebrew を使って

$ brew install android-ndk

のようにしてインストールする事ができる。

homebrew だと brew --cellar android-ndk で表示されるディレクトリの下にバージョン名のディレクトリがあり、その下の toolchains/arm-linux-androideabi-4.4.3/prebuilt/darwin-x86/bin とかに gcc が転がっている。

が、これを普通に叩いてもちゃんと動いてくれない。インクルードパスとか。

しかしパッケージ内にちゃんと standalone に gcc とかを使えるようにしてくれるスクリプトがあったのでメモ:

# r7c はインストールされているバージョンに置き換えること
$ cd `brew --cellar android-ndk`/r7c
$ ./build/tools/make-standalone-toolchain.sh --ndk-dir=`pwd` --install-dir=$HOME/opt/android-ndk-standalone

これで ~/opt/android-ndk-standalone/bin にちゃんと単体で動く gcc 等が入るので、$PATH を通したりすれば OK.

Published at 2012-05-01 23:36:50 +0900 | Permalink
2012-04-24

OS X 上での tmux 上での nohup 事情

dev
sorah@americano /tmp $ nohup echo hi
appending output to nohup.out
sorah@americano /tmp $ cat nohup.out 
nohup: can't detach from console: Undefined error: 0

OS X 上の tmuxnohup を叩いても期待通りに動いてくれない。

OS X 上でしか再現しなかったので、pbpaste とか pbcopy が動かないのと同じ 原因と仮定して、tmux-MacOSX-pasteboard を設定したら動くようになりました。

めでたしめでたし。

Published at 2012-04-24 00:27:35 +0900 | Permalink
2012-04-21

sorah の開発環境まとめ 2012 年春号

dev

自分の開発環境等についてまとめておきます。あまりすごくない。

目次

  • エディタ
  • シェル
  • ホームディレクトリの構造
  • アプリケーション類
  • 構築方法

ふろく

github - sorah/config に sorah の使っている dotfiles などが置いてあります。

エディタ

Vim を使っています。OS X だと MacVim.

プラグイン

NeoBundle.vim を使って管理しています。

.vimrc を見ると、主に以下のプラグインを使っているようです。 全部書くのは面倒なので一部だけ。

  • metarw-simplenote.vim - Simplenote を metarw インターフェースで読み書きするプラグイン (拙作)
  • rails.vim - Vim is forever. Rails 周りの補助。
  • sudo.vim - sudo でファイルを保存したり読み込んだり。
  • quickrun.vim - <leader>r でそのファイルを即座に vim 上で実行できます。TopCoder でテストコードも入れてくれるプラグインとかと組み合わせてよく使います。
  • neocomplcache - 強力な自動補完を提供してくれます。
  • metarw - ファイルを編集するような感じでプラグインが提供する文字列などを編集できるようにできるようにするライブラリ。
  • vimproc - 非同期実行のサポートをするライブラリ。quickrun や vimshell 等で無いと困る。
  • vimshell - vim 上で vim script で実装されたシェル。たまにつかう。

vimrc

.vimrc にある。戦闘力は 505 程度だしまだまだですね。

シェル

zsh を使っています。

zshrc はこれ: .zshrc

~/.zshrc_global_env~/.zshrc_env を読み込むようにしていて、前者はそのプラットフォーム向けの固有設定、後者は端末毎の固有設定という扱いで global_env は適当に config リポジトリからシンボリックリンクを貼ったりします。

.zshrc がやっていることは簡単で、$PATH をあちこちに通して、~/git/*/*/bin にも $PATH を通したりし、

alias をいろいろ設定して (ホスト名の入力で tmux で新規ウィンドウ開いて ssh 接続しにいったりできるようにしたりとか)

precmd 等で tmux 側のウィンドウタイトルにコマンド名やカレントディレクトリなどを表示するフックなどを設定しています。

あと、ssh の agent forwarding を tmux 内でもうまいこと使えるようにする hack 等もいれています。

そして最後に tmux を起動。

ホームディレクトリの構造

こんな感じです:

  • ~/git - git リポジトリの working copy を入れるところ。さらに一階層言語毎におおまかにディレクトリを掘って入れています。実態は Dropbox 内のディレクトリへのシンボリックリンクで、全て Dropbox に同期されるようにしています。

    • 言語名 (ruby とか) - ruby 等の場合は zshrc の方で lib ディレクトリを RUBYLIB 環境変数に入れたりしています。
    • リポジトリ名
  • ~/work - 仕事関係のリポジトリの working copy を入れる。 Dropbox に同期されないようにするため。

  • ~/sandbox - リポジトリにするまでもない単発のコードを入れる。~/git と同じように下にさらに一階層言語毎にディレクトリを掘ってある。最近あまり使わなくなった。

アプリケーション類

YoruFukurou, Limechat, Chrome (dev) があれば生きていける。

環境構築方法

OS X の場合。

  1. iTunes ライブラリを外付け HDD 等から引っ張ってくる。
  2. USB メモリ等に ~/Library/Preferences/com.apple.Terminal.plist を入れておいてそれをコピーしてくる。
  3. USB メモリに ~/Library/Application\ Support/YoruFukurou~/Library/Preferences/com.YoruFukurouProject.YoruFukurou.plist を入れてそれをコピーしてくる。
  4. USB メモリに ~/Library/Preferences/net.limechat.LimeChat.plist を入れておいてそれをコピーしてくる。
  5. YoruFukurou, Limechat, Chrome (dev) をいれる。
  6. XCode を入れる。
  7. Dropbox を入れて同期が終わるのを待つ。
  8. ln -s $HOME/Dropbox/.../git $HOME/git; ln -s $HOME/Dropbox/.../sandbox $HOME/sandbox を実行する。
  9. cd ~/git/config && source memo する。これで dotfiles がホームディレクトリにシンボリックリンクされる。
  10. chsh で zsh をログインシェルにする
  11. MacVim を入れて、:NeoBundleInstall をした後に cd ~/.bundle/vimproc && make -f make_mac.mak する。

おわり。

Published at 2012-04-21 14:11:58 +0900 | Permalink
2012-03-14

rails/strong_parameter

dev

https://github.com/rails/strong_parameters

Action Controller parameter attributes are now tainted by default and Active Model has been extended to check for tainted on mass assignment. This means you’ll have to make a conscious choice about which attributes to allow for mass updating and this prevent accidentally exposing that which shouldn’t be exposed.

先日の mass assignment 脆弱性の件 への対応策と見られるレポジトリが github の rails organization に push されたようです。

params を保護する方向らしい。この方がコントローラ毎に設定できて確かに良いなあ。

params.required[:person].permit(:name, :age)

params に :person パラメータを必須としてそこの中で :name, :age パラメータも安全とするという感じなのかな。

https://github.com/rails/strong_parameters/blob/master/lib/action_controller/parameters.rb

主な実装はこの辺だな。

Published at 2012-03-14 12:39:29 +0900 | Permalink
2012-03-05

github の mass assignment 脆弱性が突かれた件

dev

気になって調べたのでメモ。自分も気をつけないとなー。

github に脆弱性があってそれが突かれたらしい。 Rails アプリにありがちな脆弱性の一つ、Mass assignment とかいうタイプの脆弱性である。

mass assignment 脆弱性とは

mass assignment 脆弱性とは何か、というのは以下の記事が詳しい:

Rails 3.1 の新機能解説の記事だが、機能拡張の解説であって attr_accessible などは 3.1 より前からある。 要するに、モデルのメソッド update_attributesnewHash でデータを渡した時 attr_accessible (attr_protected) で指定した カラムについては無視されるようにするという機能である。

update_attributes とは: ActiveRecord のモデルで、カラム名がキーとなった Hash を渡す事でデータを更新できるメソッド。foo.update_attributes(:title => "New Title") のように使います。 scaffold で生成されたコントローラの update アクションなどで使われていて、scaffold では update_attributes(params[:foo]) のようにパラメータが直接渡されています。

そして、update_attributes に HTTP のパラメータ params (Hash) を特にチェックせず直接渡して、 その params に本来更新されるべきではないカラムのパラメータが含まれていても更新されないようにするために attr_accessible, attr_protected をモデルで定義しておく事によって、update_attributes 等のメソッドにパラメータを渡しても、attr_accessible (attr_protected) で保護指定したカラムについては渡した Hash で指定されていても無視されるようになります。

上記のこの記事での例を引用すると、

attr_accessible :name とした事によって, ホワイトリスト方式で :name カラム以外は無視されるようになるため、 User.new:group_id を指定していてもそれは無視されている事がわかるかと思います。

さて、この機能を使っておらず保護されていないカラムがあると何故脆弱性になるかはもう分かると思いますが、

たとえば実際にこのモデルを用いた Web アプリケーションがある時に、Web のインターフェースでは更新時に update_attributes を特にパラメータをチェックせず直接 params を渡していて、 ユーザー (Web インターフェース) からは group_id を変更できないという事にします。

すると、 もし attr_accessible :name が無い場合 、Web インターフェースの update_attributes を呼んでいる所が、 Web インターフェースでは更新できるべきではない group_id を含んだパラメータを受け取ると 更新できるべきではない group_id が更新できてしまいます。

しかし attr_accessible :name がある事によって、update_attributes:group_id を含んだ Hash (パラメータ) が来ても無視されるので変更される事は無いのです。

そのため、attr_accessible で明示的に「変更可能なカラム」を指定しておくのは重要で、これを指定していない事によって 更新されるべきではないカラムも更新することができる 脆弱性が mass assignment 脆弱性です。

しっかりホワイトリスト方式の attr_accessible で指定する事が一番安全でしょう。

update_attributes はいちいち user.name = params[:user][:name] 等としなくても Hash のキー・値でデータ (レコード)を更新できる 機能で便利なため、

update_attributes 以外にも new, create でもその保護は働くという事もあり、attr_accessible, attr_protected で保護するのが安全だと思います。

これは ActiveRecord を使ったアプリケーション (大半の Rails アプリケーション) は多く存在する可能性がありますが、 Mongoid でも同様の脆弱性が発生することがある そうです。

重要: これは Rails の脆弱性 ではなく Rails の問題 である。mass assignment 脆弱性に関しては Rails アプリケーション (もしくは ActiveRecord を使ったアプリケーション) において開発者が作りやすい脆弱性であるから。すぐ後述する Issue #5228 についたコメント (2段落目) にも書いてある。__Rails の問題__ というのは、現在の scaffold generator や ActiveRecord がこの問題を発生させやすいため、Issue 5228 では発生しにくくなるような対策を検討している。

今回の発端

さて、そこでこの github/rails/rails に登録された issue を見てみよう。今回の問題の発端である。

この issue で問題に上げているのは、現在の Rails は、開発者が mass assignment 脆弱性を発生させやすい (attr_accessible 等の存在とこのような脆弱性を知らないと) ということ。

そのため、attr_accessible 等の指定を開発者に強制したりする等して、発生しにくくする案を探している。

(その後、いくつかの案が複数人によって挙げられているが今の議論、何が提案されているかまではこの記事では取り扱わない為、 issue ページを参照してください (それを見て、コメントするのも良いでしょう))

はじめは速攻で reject された。既にデフォルトで有効にする pull request があり (Pull Request #4062) それが reject されているからだ。

もちろん homakov さんは反論している。「ホワイトリストを必須にするのではなく、たとえばデフォルトで foreign_key, primary_key をブラックリスト入りさせておくのはどうか」 と。

(メモ: 一度は reject されましたが、現在は議論が再開されています)

脆弱性の問題を例示

そして、reject が繰り返されるとこのような issue が open される:

what?

作成日時を示す部分を見て欲しい。"in 1001 years" とある。未来ですね。おそらく github が抱えている mass assignment 脆弱性をつついたのだろう。GitHub を使って例示してしまった。

たぶん created_at 等をパラメータに含ませて自分の指定した値に created_at を変更したのだろう。

そして彼はさらに別の所にある脆弱性もつつく:

hacked

一番最初に上げた github の blog の記事でメインに言及されている脆弱性がこれである。

At 8:49am Pacific Time this morning a GitHub user exploited a security vulnerability in the public key update form in order to add his public key to the rails organization. He was then able to push a new file to the project as a demonstration of this vulnerability.

(日本語訳: 8:49am (Pacific Time) に GitHub ユーザーは SSH 公開鍵の更新フォームに存在する脆弱性を攻撃し、彼の公開鍵は rails organization に登録された。そして彼は rails/rails プロジェクトに新しいファイルをコミットする事ができた、この脆弱性のデモとして。)

organization account も実は SSH 公開鍵を登録する事ができるので、たぶん SSH 公開鍵の更新のフォームで SSH 公開鍵のモデルにある user_id といったカラムを推測してパラメータに含ませ、pubkey を update したのだろう。どうやって account 側の primary key を取得したんだろう?

このように GitHub 等もうっかり mass assignment 脆弱性を抱えてしまう事から、デフォルトでいくつかの key をブラックリスト入りさせようと提案した訳である。まだこの issue は議論が続けられている: Issue #5228: Mass assignment vulnerability - how to force dev. define attr_accesible? · rails/rails

どのようにしてこの脆弱性の発生を防ぐか。現状だとユーザーが attr_accessible 等を手動で定義しないと、ユーザーがこの脆弱性の存在を知らない限り容易に発生させてしまうからね。rails だと。

GitHub のアクション

ちなみに今は解除されたが 彼の github アカウント は一時的に suspend された様である。何をしたかの調査、その間は害を及ぼした疑いがあるための suspend と見える。最初のアナウンス では単に suspend したとしか書いてないから誤解が多かったんだなぁ。Github, もちろん当初から疑いが晴れたら解除するつもりだったんだよね?

ちなみに誤解が多いと思われるのは そのアナウンス についたコメントでは「suspend を解除してやるべき」との声が多く上がっていた。

その suspend は実際に解除されたが、まぁ、解除すべきだよね。何か重大な損害を起こすような事はしてないものね。ただ、素直に報告せずに rails の所で実例を示してしまうというのはどうかと思うがw

まとめ

これだから rails は(キリッ, はやくなんとかしろ(キリッ

今後の動向が注目されますね。

追記 8: コントローラでみえる params に保護機能 ($SAFE な時の taint 的な感じで) をつける方向というのが DHH の考える一応の対応策? 別記事に詳細を書いた: rails/strong_parameters

あわせてよみたい: GitHub and Rails: You have let us all down. - Code Space

ところで、PHP は?

"register_globals?そんなのデフォルトでオフですよ" という記事より。

何年も前に指摘されていた脆弱性に今頃慌てふためいている愚かでコンピュータサイエンスを学ぶには無能すぎてRailsくらいしか使えないくせにPHPerだなんだと他人の尻馬に乗って調子こいてたボケナス共は、土下座してmodelの修正に取りかかるがよい。わっはっは。

だそうです。

PHP: グローバル変数の登録機能の使用法 - Manual」… これはひどい。

あと、PHP の Web フレームワークの一つ Symfony にも似たような問題があるっぽい: Security must be taken seriously - Symfony (はてブコメントより)

はてブコメントを見て思ったこと

  • attr_accessible はバリデータの一種なのかなぁ。
  • 自動生成で中身を把握してないというのも問題だが、これは自動生成じゃなくても update_attributes とか普通に使うメソッドだし自動生成関係無くないかなあ。自分は今回この記事で自動生成 (=scaffold) を取り上げたけど。

追記メモ

追記: suspend は解除されていたようだ (実害を及ぼしたかどうかの疑惑が解けたから?) https://github.com/blog/1069-responsible-disclosure-policy ので、文章を一部修正

追記2: これは Rails の脆弱性と言うよりは Rails の問題点である事を追記。 (重要: 〜 の段落を追加)

追記3: セクションごとに見出しをつけました

追記4: register_globals の事を言及

追記5: 前提知識が必要だとの言葉を受けて若干追記。まだ分からない部分があれば twitter 等で指摘ください。

追記6: mass assignment 脆弱性の説明を大幅に書き換え。わかりやすくなったと思う。

追記7: PHP の Symfony にあった似たような脆弱性のつくりを紹介

追記8: strong_parameters の事を追記

Published at 2012-03-05 09:35:58 +0900 | Permalink
2012-03-03

CTPC (College of Technology Programming Contest) 参加記

dev

高専生向け競技プログラミングコンテストらしい。 http://koj.cms.am/contest/index.html

起きたら twitter の TL で話題になっていたので寝起きで参加しました。

結果: 400/1100点 (39/65位), 2 WA.

といた順番は A→C→B→E. A の後 B は一見難しそうに見えて C を解き、その後他の問題を物色して E を解き始めたのだけど、 途中これはグラフ理論とか使うのかなあ、と思って物色を再開した所、実は B が簡単だった事に気づいて B を解き、時間が余った。E をもう一度見たら実は Time Limit 8 秒とか入力の制約を見るにシンプルな 探索でも通るだろうということで再度解き始めて、ギリギリで通した。

問題 A - Average

http://www.atcoder.jp/problem/detail/151

改行区切りで 4 つの数値が与えられるので、(それらの最高値+それらの合計)/5 を求め、60 以上であれば Yes, 60 未満であれば No を表示すれば良い。

Codeforces とかだと YES, NO (全て大文字) なのでそこで引っかかってる人が多かったイメージ。

コード

きたないですね。

問題 B - Macaron

http://www.atcoder.jp/problem/detail/152

W 高さ H の盤面 (自分は空白マスを false, 壁マスを true とした) を用意、その後 X, Y, L の 3 つの数値がスタンプとして与えられるので、 座標 (X,Y) 中心に L 間隔の正方形の形になるように盤面のマスを反転 (空白マスなら壁マスへ、壁マスなら空白マスへ) した。 自分は前述のように bool で管理したので ! つかって反転させるだけ。らくちん。

正方形の作り方は、n を任意の 1 以上の整数として、 頂点の座標は X, Y に下の式から求められる数値を足したり引いたりすれば求められる。(コードでは 27 行目の変数 s への代入)

s = L + (L+1)(n-1)

左上、右上、左下、右下の座標は以下のようになる:

  • 左上: (X-s,Y-s)
  • 左下: (X-s,Y+s)
  • 右上: (X+s,Y-s)
  • 右下: (X+s,Y+s)

処理は n を初期値 1 でループを回し、まず頂点を反転し頂点と頂点の間の線となるマスも反転、 一つの正方形の処理において反転させようとしたマスがすべて盤面の外ならループを打ち切り、 そのスタンプの適用を終了して次のスタンプの適用に入る。

そして与えられたスタンプを全部適用したらおわり。それを整形して表示するだけ。

もっと賢い方法あるのかなあ。

日本語が書けないのでうまく解説できないな。しかし。

コード

問題 C - Communication Tool

http://www.atcoder.jp/problem/detail/153

n つの文字列が改行区切りで2行目以降に入力されてくる。

それぞれの文字列は以下のルールに従ってカテゴリ分けできる。

  • その文字列は 1 文字以上 140 文字以下であるなら Tw○tter からの情報 であり、また:

    • @ で始まる文字列であるなら リプライ
    • @ で始まらない文字列である つぶやき
  • それ以外の文字列 (リプライでもつぶやきでもない) はすべて mix○ または gre○ からの情報となる。

表示するものは つぶやきリプライ の割合であるため、リプライでもつぶやきでもない文字列は無視して問題がない。 また文字列自体もどうでもよくただ個数だけ数えれば良い。

割合については以下のように求めて (C++ なのでつぶやきとリプライを数えた変数を double 型にしておく) 小数点以下を切り捨てたものを表示すれば良い (C++ だと普通に int にキャストしてしまえば良い)

つぶやき もしくは リプライ / (つぶやき+リプライ)

しかし入力によっては つぶやきもリプライも存在しない 事があるので、その場合は "NA" を割合の代わりに表示すれば良い。

この問題で Wrong Answer を唯一 2 回も出してしまって、理由はそれぞれ以下。非常にクズであると思います。

  1. NA を表示しなかった
  2. NA を表示する条件がどちらか片方が 0 以下だった (ひどい)。

|| から && に修正してやっと通った。

コード

問題 E - Airport

http://www.atcoder.jp/problem/detail/155

空港の名前と、空港同士の便 (出発地, 目的地) が与えられる。

与えられた空港と便を見て、以下の条件に当てはまれば Yes, 当てはまらなければ No を表示しろという問題。

  • すべての空港 A において、他全ての空港 B (A != B) との間に、便 AB もしくは BA が存在する事
  • 任意の空港 A, B (A != B) の間に、便 ABBA 両方が存在しない事
  • すべての空港 A は空港 A から出発する任意の便に搭乗し、他の空港の便と乗継、最初に搭乗した空港 A に戻ってくる事ができる事

最初 3 番目の条件をみて間違いなく自分のコードだと Time Limit Exceeded になってダメだろうと思ったがよく制約と time limit を見ると、 time limit は 8 秒だったり、空港は最大でも 17 個、つまり便は最大でも 272 個なので幅優先で挑戦してみた。

(メモ化再帰の深さ優先探索とどっちが良いのかは知らない)

コード

  1. map で空港名 (string) をキーに Flights* (実態は vector<string>, 空港名を格納) を保管。空港毎にその空港からの便の行き先を列挙しておく。
  2. 便を受け取って Flight flights (Flight は ↑の map<string,Flights*>) に格納していく課程で、同じ空港同士で逆方向の便がみつかれば即座に No を表示して終了
  3. 便を Flight flights に保存したらとりあえず総当たりで 1 番目の条件に当てはまるか確かめ、当てはまらない物があったらその場で No を表示して終了。
  4. 最後に全ての空港に対し check_loop を呼び出して、3 番目の条件に当てはまるかを確かめる。一つでも当てはまらなければ No を表示して終了。

check_loopqueue 使った幅優先探索。

あと、最初 typedef vector<Flights*> Flights しようと思ったけどできないのね。残念。

反省

くだらない 2 WA は酷かった。 もうちょっと問題の難易度を推定して自分の実力で時間以内に解けるかどうかの判断を迅速に間違いなく下したいなあ。

@kyuridenamida さん, @kagamiz さんへ: 面白いコンテストをありがとう。次回はありますか?

Published at 2012-03-03 18:43:55 +0900 | Permalink