Hatena::ブログ(Diary)

rambling talk RSSフィード Twitter

2013-05-01

Google Code Jam 2013 Round 1A

毎年恒例、今年もGoogle Code Jamに参加しています。

A-small, A-large, B-small, C-small-1を正解。
669位でRound 2進出です。

いつもRound 1Cまで粘って辛うじて通過しているので、
1Aで通過したのは初めてでテンションが上がりました。
A問題が得意分野でlargeを通せたのがよかったようです。

A. Bullseye

まずは法則を見つけるため、1本目、2本目、3本目…のリングの面積を求めてみます。
1本目(n=0): π(r+1)^2 - πr^2 = π(2r+1)
2本目(n=1): π(r+3)^2 - π(r+2)^2 = π(2r+5)
3本目(n=2): π(r+5)^2 - π(r+4)^2 = π(2r+9)

1,5,9...の部分をkとすると、k = (2n+1)^2 - (2n)^2 となる気がします。
(てか4n+1なのですが、競技中はこれで進めてました)

したがって、π(2r + (2n+1)^2 - (2n)^2)と一般化できます。
1mlで面積πを塗れるそうなので、πで割るとペンキの必要量になります。

n+1本のリングを塗ったときのペンキの必要量は、
Σ[x=0→n](2r + (2x+1)^2 - (2x)^2)
= 2r(n+1) + Σ[x=0→n]((2x+1)^2 - (2x)^2)
となり、後半のΣの部分をWolframAlphaに突っ込むと、
= 2r(n+1) + (n+1)(2n+1)
となります。

これで、n本の場合のペンキの量がO(1)で出せるようになりました。
あとは、ペンキの量がt以下になる最大のnを求めます。
tの範囲も大きいので、二分探索で求めます。
nの範囲は適当に0 〜 2*10^18としても2^60くらいなので、60回くらいのループで求まります。

ソースコード

B. Manage your Energy

smallは範囲が狭いので、使うエネルギーの組み合わせは5^10 = 1000万通りくらいです。
なので総当たりしました。

ソースコード

C. Good Luck

テストデータのすべてに正解する必要はなく、指定された個数以上合ってればいいという珍しい問題です。
去年の乱択といい、確率問題がよく出ますね。

small-1は、Maryamが選ぶのは2〜5の数字を3個なので、
組み合わせの数はH(4, 3) = C(4+3-1, 3) = 20通りです。
Hは重複組み合わせです。今回ググって初めて知りました。

で、3個の数の部分集合は2^3 = 8通りです。
なので、数の集合とその部分積をすべて列挙しても20 * 8 = 160要素のテーブルで済みます。

テーブルを作ったら、与えられた積になり得ない数を削除していきます。
例えば、積が10なら、3 3 3の部分積は10になり得ないので、3 3 3を削除します。
こうして残った数のうち、適当に1つを回答します。

この方法でsmall-1は通りました。small-2はテーブルを作り終わる前にタイムアウトでした。
ちなみにRubyだと、Array#repeated_combination, Array#combination, Array#injectで一瞬でテーブルが作れました。超便利。

ソースコード

2013-01-23

無断転載じゃないワロスbotを作ってみた → @1000favs_RT, @1000Retweets_RT

忙しい人へのまとめ

ワロスbot(@)は人気のツイートを無断転載して、フォロワー数を増やしています。
そして、ときどき広告を入れて広告費を稼いでいます。それを企業としてやっています
他にも、同様のbotは多数あります。

無断転載されると…

  • 感じ悪い
  • 公式リツイートじゃないので、原作者にたどり着くのが難しい
    • ツイートが気に入っても原作者をフォローしにくい
  • ツイートの反響が、本来受け取るべき原作者に届かない
  • 原作者がツイートを削除したくなっても、削除できない

また、Twitter利用規約に、「繰り返し他のユーザーのツイートを自分のものとして投稿した場合」は利用規約違反になると明記されています。

そこで、原作ツイートを自動で検索し、公式リツイートするbotを作りました。
このbotをフォローすれば、無断転載ではなく、原作のツイートを読むことができます。

詳しく知りたい人は最後まで読んでみてください。

コピペツイート

最近Twitterで、ツイートのコピペ行為を見かけます。
これは公式RT*1をせずに、他人のツイートをコピペして自分のツイートとして発信することです。

コピペ行為には、様々な問題点があります。

単純にパクリ

パクられた側はいい気はしないでしょう。よく練り込んだ渾身のツイートならなおさらです。

原作者にたどり着きにくい

公式RTされたツイートには、原作者のホームへリンクが張られています。
原作者に興味を持ったら、過去のツイートを読んだりフォローしたりすることが自然にできます。

コピペツイートの場合、原作者を探すことが難しくなります。
ツイート内に原作者のアカウント名が書かれていることもありますが、それでも検索したりする手間がかかります。

原作者が受け取るべき反響を奪う

Twitterでは、価値のあるツイートにはリプライ・Fav(お気に入り)・RT(リツイート)などで反響が寄せられます。
思わぬ反響に驚くこともありますし、反響を狙って練り込んだツイートをする人もいます。

コピペツイートでは、コピペしたアカウントを発信者としてツイートが広がるため、
原作者が受け取るべき反響を、コピペしたアカウントが奪うことになります。
反響が原作者に伝わりにくいだけでなく、原作者の知名度が上がる機会なども自分のものにしていることになります。

原作者がツイートを削除できない

公式RTの場合、原作者がツイートを削除すると、公式RTで拡散したツイートも消滅する仕組みになっています。
ツイート内容に誤りがあった場合など、これ以上の拡散を望まないときに、原作者の判断でRTを止めることができます。
コピペツイートは原作者の意思で削除ができないため、意図に反して広がり続けてしまいます。

コピペbot

最近、ワロスbotを筆頭に、コピペツイートばかりを自動的に行うbotが多数存在しています。
これらのアカウントは、主に人気のツイートを対象としてコピペを繰り返しています。

ここで言う人気のツイートとは、FavやRTを多く集めたツイートのことです。
Favstar, ふぁぼったーなど、人気のツイートを集めたサイトがあるため、
これらのサイトをクロールすれば、機械的に大量に手に入れることができます。

コピペbotはフォロワー数が多いものが多く、これらのbotがコピペをすると大きな影響があります。
10000フォロワー程度のものは多数あり、中には300000〜500000フォロワーのものも存在します。

なぜそんなに成長するのでしょうか?
人気のツイートは注目を集めた実績から分かるように、コンテンツとしての価値が高いです。つまり、RTされやすいのです。
それをコピペすることで、そのツイートはコピペbotを発信者としてどんどんRTされていきます。
するとコピペbotに注目が集まり、フォロワー数が増えていきます。
フォロワー数が多くなれば、より多くRTされるようになり、さらにフォロワー数が増えやすくなるという循環が起きます。

実際悲しいことに、RTするよりコピペしたほうがフォロワー数が増えるという現実があります。

コピペbotの中には、アフィリエイトのリンクが入ったツイートを混ぜるものもいます。
パクリ行為で注目を集めた上に、金銭的な利益まで得ているのです。

動機と経緯

こうしてコピペbotは幅をきかせていて、私のTLにもときどきコピペツイートのRTが流れてきます。
私がフォローしている人の中にも、コピペbotを毛嫌いしている人がいました。

この状況を見ていて、やはり原作者にはフィードバックがあるべきだと考えるようになりました。
自分自身ときどきFavやRTをもらうことがあり、反響があるのは楽しいと感じています。

また、Fav, RTの数を競うことに強いこだわりがある人もいるようです。
彼らにとっては、コピペbotは目の敵でしょう。

少し抽象的な話ですが、1人の技術屋として、Twitterに限らずコピペは嫌いです。
情報のコピペは様々なデメリットがあり、極力行わないように普段から気をつけています。
コピペをせず、ソースを明示できる公式RTという手段があるのに、それを使わずわざわざコピペする行動に苛立ちを感じていました。
原作者へ飛ぶのが面倒など、1ユーザーとしてリアルに不便も感じていました。

そこで私はささやかな抵抗として、コピペbotのツイート内容が気にいったときは、
本文で検索してオリジナルのツイートをFav, RTするようにしました。
当然、面倒です。でもこれは意義のあることだと思います。
たまに面倒でそのままFavすることもありますが、少なくともRTはしないようにしています。
コピペbotの利益にさせたくはありません。

何度かこれを行っているうちに、自動化するのは技術的に可能そうで、面白そうだと思うようになりました。
本文で検索してオリジナルのツイートを見つけることができたり、
コピペ回数のランキングを作ってコピペbotをさらし者にするようなサイトの企画を考え始めました。

そう思っていたとき、ぱくったーが公開されました。
考えていたサービスとほぼ同じで、しかもサイトの文面が切れ味抜群。タイトルからしてキャッチーです。

出遅れた悔しさも加わって、テンションが上がってきました。
そこで、他のアイデアのひとつを急いでリリースすることにしました。

アンチコピペbot

コピペbotがコピペツイートをするたびに、そのオリジナルを自動で探して公式RTするbotを作りました。
一言で言えば、コピペbotの公式RT版です。「アンチコピペbot」と呼ぶことにしましょう。

詳しく説明すると、以下のように動作します。

  • コピペbotの新規ツイートを監視する
  • 新しいツイートが来たら、その本文をGoogleで検索し、オリジナルのツイートを見つける
  • オリジナルを公式RTする

コピペbot(@)とアンチコピペbot(@)を並べてみてください。
同じ内容のツイートが並びます。

しかし、かたやコピペで同じアイコンが並び、原作者にたどり着きにくい。
かたや公式RTで色とりどりのアイコンが並び、原作者のホームにすぐ移動できます。
この2つを見た人は、当然アンチコピペbotを選ぶでしょう。

おわりに

アンチコピペbotの裏話、いかがだったでしょうか?
既にご存じの方は今後とも、初めて知った方はこれをきっかけに、コピペ問題に関心を持っていただければと思います。

敢えてコピペbotを肯定的にとらえると、面白いツイートのまとめとしての価値があります。
コピペの問題を意識しない人にとっては、単純に「面白いツイートがどんどん流れてくる、便利なアカウント」です。
また、公式RTをするスタイルでは、おそらくここまで広まることはなかったでしょう。

Twitter社には結構な数のスパム報告が届いていると思うのですが、コピペbotがなかなか凍結されないのは、
こういった側面が理由になっているのかもしれません。

とはいえ私自身は反対の立場に変わりありません。
今後も、ほかのコピペbotの公式RT版を作っていく予定です。
また、他のアプローチでコピペ対策ができないか、アイデアを練っています。
みなさんも面白いアイデアがありましたら、ぜひお寄せください。共にコピペ行為と戦いましょう。

*1:公式リツイート。ソースを明示して、自分のフォロワーにツイートを広める仕組み

2012-11-03

Android 4.0 + IIJmioで常に圏外表示になる問題の対処法

Galaxy S2 LTE (SC-03D)にCyanogenMod 9をインストールした環境で行っています。

こちらの手順を参考に、自分の環境に合わせて少し変更しています。
http://bl.oov.ch/2012/01/android-sim.html

開発者向け設定で

端末をUSBで接続。ストレージは有効にしない

datasim_framework_jar_patcher_20120317.zip解凍
execute.batを実行

API Levelは

Android 4.0.3〜 :    15 : Ice Cream Sandwich MR1

モードは

99 : モード 0 でダメな場合

緊急通報は

0 : 変更しない

コマンドプロンプト

adb push C:\datasim_framework_jar_patcher_20120317\framework.jar /sdcard/framework.jar
adb shell

adb shell内で以下を実行
ここで失敗すると起動しなくなるかもしれません。自己責任で。

su
mount -o rw,remount /dev/block/mmcblk0p24 /system  # デバイス名は mount で確認してね

cd /system/framework
cp framework.jar framework.jar.bak
cp /sdcard/framework.jar framework.jar
chmod 644 framework.jar

ボリューム上下を押しながら起動し、ClockworkMod Recoveryに入る
「Wipe cache partition」と、「advanced」の中にある「Wipe Dalvik Cache」

再起動すると、アンテナピクトが正しく表示されているはずです。
セルスタンバイでバッテリー消費が激しい問題は、まだ確認していません。

Galaxy S2 LTE (SC-03D)にCyanogenMod 9をインストール

手順をまとめておきます。
ドコモアプリサムソンのダサいUIから解放され、ほとんど素の状態のAndroid 4.0が楽しめます。
詳しくないのですが、CyanogenMod独自の便利機能もいろいろ入っているようです。

もちろん自己責任でお願いします。
エリアメールが使えなくなるので、地震で逃げ遅れるかもしれません。

ファイルの入手

Check Fus Downloaderで、
Choose a firmwareを以下の設定に

  • Android
  • SC-03D
  • Japan - SGH-N034DANDCM

Check firmware → Download

https://github.com/kbc-developers/release/wiki/sc03d から

  • cm-9-20121101-UNOFFICIAL-celoxdcm.zip
  • SC03D-ICS-KBC-20121031-recovery-odin.tar

ダウンロード。前者はSDカードのルートに置く

http://goo.im/gapps/gapps-ics-20120429-signed.zip をダウンロード。SDカードのルートに置く

インストール

Odin3のPDA欄で

  • SC03DOMLPH_SC03DDCMLPH_SC03DOMLPH_HOME.tar.md5 を焼く
  • SC03D-ICS-KBC-20121031-recovery-odin.tar を焼く

ボリューム上下を押しながら電源ON

ClockworkModで

  • wipe data/factory reset
  • wipe cache
  • cm-9-20121101-UNOFFICIAL-celoxdcm.zip をインストール
  • gapps-ics-20120429-signed.zip をインストール

参考文献

http://anago.2ch.net/test/read.cgi/smartphone/1332415484/
http://cielsomer.blog.fc2.com/blog-entry-67.html
http://cielsomer.blog.fc2.com/blog-entry-198.html

既知の問題

IIJmioのSIMでは、アンテナピクトが常に圏外になる。3G通信は可能。バッテリーの消費が激しいかは確認中
http://techlog.iij.ad.jp/archives/487

2012-05-01

ニコニコ超会議 2日目

行ってきました。

あたり。

入場待機列とエンジニアミーティングではいろいろつぶやいてたのでこちらを。
ニコニコ超会議 2日目 - Togetter

ニコニコ学会は、頭の下がり具合で聴衆の関心度合いをデータ化したり、
網戸にミクを投影して立体映像っぽく見せていたのが面白かったですね。

ニコつくでは技術部が出展していました。作品の実物を見るとインパクトが全然違います。
トイレットペーパーにタコメーターを搭載してたのがアホでよかったです。
ニキシー管の巨大スペアナもインパクトがありました。

なかでも、最後に見た人力3Dがすごかった。
赤青メガネで立体模型の影絵を見るのですが、光源が赤と青の2点あることで3Dに見えます。
ドームスクリーンに投影していて、上から迫ってくるのが迫力ありました。
アバターより飛び出すとの前置きでしたが、けっこうガチです。
中の人も話し慣れている感じで、大道芸の経験がありそうでした。

全体的にウワサ通り混んでいましたが、がんばった甲斐はありました。
次があるならビッグサイトだとうれしい。

Google Code Jam 2012 Round 1A

A-small, Bを正解。1251位でした。
A-largeはほぼ解けていたのですが、ケアレスミスで落としてしまいました。
合っていれば余裕で通過だったのですが…Round 1Bをがんばります。

A. Password Problem

指示通り計算するだけです。
ただし、backspaceの場合を素直に実装するとO(n^2)になり、
ワーストケースで100000^2なので間に合いません。
これに気付かずlargeを実行してしまい、慌てて直したのですが配列のindexがひとつずれていてwrong。残念な結果でした。

バグ修正後の、largeが通るコードです。
GCJ 2012 Round 1A - A. Password Problem ? GitHub

B. Kingdom Rush

サンプルを眺めてると、Greedyでいけることに気付きます。

下記の繰り返しで解けます。

  1. 現状で、2-starでクリアできるレベルを選びます。複数ある場合はどれでもかまいません。
  2. 現状で、1-starでクリアできるレベルを選びます。複数ある場合は、2-starの条件が最も厳しいものを選びます。
    • 例: サンプルのCase #4で、0 5, 0 1の2択になったら、0 5を先にクリアします。
    • そうすることで、次に0 1の1-starを飛ばして2-starに挑戦でき、1回節約できます。
  3. どちらも不可能で、未クリアのレベルが残っている場合はToo Badです。

サンプルがヒントになっているあたり親切ですね。
GCJ 2012 Round 1A - B. Kingdom Rush ? GitHub

C. Cruise Control

レーンチェンジが必要なのは、前後の車との間隔が0mになった瞬間だけです。たぶん。
事前にレーンチェンジしないと間に合わない場合はないと思います。

それなら、その瞬間の時刻を2分探索で求めればいいのかな。
…くらいまで考えたところで気力と時間が尽きてしまいました。

2012-04-27

明日はGoogle Code Jam Round 1A

明日はGCJですね。みなさん準備はいいですか?

私はソースコードテンプレートと、bash関数をいくつか用意しているところです。
後者は問題ごとのソースファイルの作成・実行を手早く行うためです。
ヒューマンエラーを防ぐ意味も大きいです。競技中は慌てやすいので、
うっかり違うデータで実行したりファイルを上書きしたりしたら大惨事。

ということで、作った物を晒してみます。
大して実力もない人間の、しかもRuby用ですが、よかったら参考にしてみてください。
軽くデバッグしてありますが、手元での確認も忘れずに。

GCJ ruby template ? GitHub
GCJ bash aliases ? GitHub

自分用のバックアップの意味もあります(去年も作ったのですが、なくしました…)

Connection: close