CodeChef Snackdown Onsite 旅行記

4年半ぶりにここに書くっぽい。旅行記はQiitaには載せづらいのでこういうところにしか書けないかもしれない。

CodeChef Snackdown 2016の決勝にインドまで行ってきました。同じ組織の人で2人までチームを組んで行うコンテストです。去年はteamlabとして出ていたのですが、今年はRCOとして@kenkoooo君と組んで出ました。

あらまし

予選では42位で、実質決勝に行ける25位以上には程遠かったのですが、15位以上は全額支給されるのに対し残り10チームは航空券は自費負担になっていて、それで行かない選択をするチームが多く出て自分たちにまわってきました。
正直奮わない順位だったので自分としては行っても行かなくてもどちらでも良いかなと思ってたんですが、kenkoooo君がぜひ行きたいとの事だったので、RCOパワーを借りて出張名義で行くことになりました。航空券は会社持ちです。本当申し訳ないです。

準備

決まってから出発するまで2週間弱しかなかったので、パスポートを持っていないとこの時点でアウトです。
e-tourist visaというネットで申請できるビザがあり、ちゃんと申請できると一晩で発行されます。結構な量のフォーム入力がありますが、何を書けばいいかを示してくれるサイトが割りとあったので助かりました。
航空券はkenkoooo君が買ってくれました。感謝。海外用保険も会社が用意してくれました。死んだら2500万。バングラデシュのテロもあったのでビビってました。
持ち物に関してはあとでまとめてかきます。

1日目(7/7)

前日に朝食用のパンを買っておいたんですが、例によって寝不足でとても食べる気になれず結局空港に持ってきてしまいました。乳製品等はどこの入国審査でも引っかかると聞いていたのでやばいと思い急いで詰め込んでました(実は問題ない)。パンを頬張った直後に機内ランチが出たので悲しくなりました。これから何度も悲しくなる。
席が3人席の最後尾の2人席だったので、空間があいていてかなり良かったです。コースが関東から九州まで横断する感じで、結構天気も良かったので、窓から写真を撮りまくっていました。日本を抜けた後は雲ばかりで何も見えなかったんじゃ。
機内ではテトリスや麻雀をやってマシンをフリーズさせたりズートピアを見てたりしました。

チャトラパティ・シヴァージー国際空港に着いてインドの湿気を感じました。温度は東京より少し低いけど湿度がとにかく高くて、持っていた紙がどんどん湿気っていきました。ムンバイの入国審査は割りとスムーズにいけました。ホテル名・場所を控えておかないと悲惨な目にあうのはロンドンで経験済みだったのでそこはぬかりなく・・

ホテルに着いたら日本勢で夕食にしました。最初外でとろうという話だったんですが、ホテルの外には道路しかなかったのであきらめました。夕食はバイキングで、カレーをはじめイタリアンとかタイ料理とかカリフォルニア寿司とか色々並んでました。Egorがやたら巡回していたのが印象的でした。
このあとのホテルの食事もコンテストの食事もそうなんですが、給仕がとっかえひっかえ来て食べ物を勧めてくるのが印象に残ってます。
それから、電気で蚊を殺すラケットを持っている係員がいて、コバエをバチバチしていたのが印象的でした。
食べ物のバラエティは結構あるのですが、飲み物のバラエティはほとんどなく、ほとんどが水(3日目のディナーは水しかなかった)で、たまに謎の野菜ジュースとかチャイ・紅茶・コーヒーがあったりする感じでした。
ホテルの部屋については、トイレと他を仕切る扉がガバガバで、音がモロに漏れる以外は問題ありませんでした。

2日目(7/8)

5時間程度しか寝られませんでした。もちろんテンション低かったんですが、そのあと特に眠くならなかったのが不思議。
朝食もバイキングでした。スモークサーモンが常時あったので必ず食べる。イギリスで味わったのとほとんどかわらず、美味しい朝食でした。

16:00までは予定がなかったので、日本勢で観光しようという話になり、タクシーに乗ってまわっていました。インドでは列をつくるという意識がなく、車線に容量以上の車がひしめきあい、ドライバーは他の車を追い抜くレベルでもクラクションを鳴らしていて(多分自分の存在を知らせているんだと思うが)、常時どこかでクラクションが鳴っている感じでした。
Mahalaxmi Dhobi GhatとMarine DriveとGateway of Indiaに寄ったと思います。
Mahalaxmi Dhobi Ghatが巨大洗濯場とかいわれているところでタクシーから降りて散策したんですが、それっぽいのはあまりなく、湿気と臭いとゴミと、露店の野菜に群がる無数のハエに参ってしまい、命の危険を感じておびえていました。インド最大の都市の都市部でこんななのか・・という感じでした。さすがにここで物を買おうとか食べようとかいう気には到底なれませんでした。
Marine Driveはテトラポットがひたすら並んでいる海岸線で、カニがいました。
Gateway of Indiaはムンバイの代表的な観光地で、人がたくさんいました。門の窓の模様が窓ごとに違っていたのが気になりました。眺めはいいのですが、客引きとかゴミもたくさんあって、大丈夫かコレってなってました。
インド人は結構あっちこっちにゴミを投げるっぽいです。これは文化だししょうがないのかなーとも思いました。
帰りに謎のおみやげ屋に連れて行かれました。hogloidとsugim48は何か買ったみたいです。店先に食べ物とかなにもないのにハエが無数にいたのが印象的でした。
帰りにみたのですが、モノレールが走っていました。通常の列車はドアはついてないですが、モノレールはついていました。

ホテルに帰ってから、17:00くらいに開会式的なのがあって、そのあと3時間activities/gamesというものがあってteam dinnerという感じでした。イギリスにいたときは聞ける人の英語は聞き取れたのですが、インドの英語はなぜか聞き取りづらくて、ほとんど何を言っているのかわからなかったです・・英語力なのか・・。なおここでもドーナツ等を勧められました
activities/gamesは、ビンゴカードを各自渡されて、adminの出す課題に複数人で協力して最初に正解したグループが壇上に上がって何かもらえる・・というものでした。ビンゴじゃないです。これ以後もそうなんですが、課題が基本口頭でしか発表されない上に、他の話と違い厳密さが要求される文脈なので、聞き取れない英語弱者は完全に置いてけぼりでした。本当に部屋に帰りたかったです。帰りたそうにしているとスタッフが参加を激しく促してきます。なんか1個の課題に自分のビンゴカードがマッチしていたっぽく一度だけ壇上に上がれて中国製の四面体ルービックキューブをもらえたんですが、あっはいという感じでした。
この時点ではユニフォームとかなく、有名人以外はどんな名前かすらもわからないし、別にプログラミングで解かせるような問題でもないし、なぜこんなゲームにしたのか本当に意味がわからなかったです。
あまりにつまらなかったのでビンゴが終わってすぐにatcoderが始まったので適当に解いていました。
ビンゴのあとは偉い人の指示に従いみんなでひたすら太鼓をたたく催しでした。みんなで太鼓を叩いてシンパシーを感じればそりゃ盛り上がるだろ、って感じでした。ずっと昔にオーケストラ出てた時のことを思い出してました。

team dinnerは何か特別なものかと思ったら前日のバイキングと同じものが出てきました。

3日目(7/9)

finalsの日がやって来ました。3位以内でなければ賞金を貰えないし、予選の順位(決勝メンバーの中では19位相当)を上回ればいいやーと考えていました。
朝に部屋の前にユニフォーム等を入れているリュックが置かれているらしく、みんなユニフォームを着ていましたが、僕等のチームの部屋の前にそれが届くことはありませんでした。疎外感を感じたままバスに乗りdirectiplexへ。ユニフォーム一式は到着時にもらいました。
出発の数日前に知ったのですが、このコンテストはネット閲覧が許されない(ただし事前に送ったデータはPCに入っている)ICPC形式に近いものなので、ICPC勢以外には基本的に不利です。ネット閲覧が許されないのでiphoneは没収されました。環境はOSがUbuntuで、当然ですが英語キーボードです。どちらもほぼ使ったことないレベルだったので、Ubuntuの操作はkenkoooo君に頼りっきりでした
し、はじまるまでfor文をひたすら打っていました。ディスプレイ2台にキーボード・マウス1台、マスターとなるノートPCがあって、これらにさらに持込のキーボードやマウスを付ける感じでしたが、ノートPCのキーボードが一番しっくりきたので、結局それでずっとやっていました。
練習コンテストは去年の決勝の問題で、無理ゲーだろってなってました。チームアカウントはなぜかprofileが設定できなく、デフォルト言語が常にAdaになるというトラップがあるのがいやらしかったです。
あとEclipseを使ったんですが、Eclipseのバージョンが3.8でした(最新は4.5か4.6)。3系はJava8のラムダ式まわりが基本ダメで、ラムダ式を書こうとすると怒られます。実質的finalもエラーでした。だから実質Java8封印したまま出る感じです。ただしJava8で加わったLong.unsigned系等の関数は通ります。テンプレとライブラリはちゃんと入ったのでそこはうまくいきました。
後述するんですが、会場は冷房がきいていて、いつものRCOのオフィスぐらい寒かったです。なんとなく暑いだろうと思って長袖を一着も持ってこなかったのが仇でした。寒がっていたら某スタッフがパーカーをくれました。本当にありがたい！
本番中やたら飲み物食べ物をテーブルの上に置いて行かれました。水が美味しかったです。りんごとバナナを置かれた時は、絵でも描けというのか、という感じでした。

(問題それぞれについては後述)

コンテストが終わったら解説会をして下の階で結果発表・ディナーをやりました。解説はwriterのKevinsogoが現れて何か解説していましたが、まわりが冷たかったです。
結果発表は、適当に誂えた舞台でやるのですが、肝心の発表の前に長いご高説やらよくわからない表彰やらあってgdgdでした(もちろん口頭オンリーなので余計に何やっているのかわからず)。都知事みたいな人がいたんですがあれがDirectiの偉い人かもしれません。順位表を凍結したにもかかわらず、動く順位表もyes/noおじさんも出ることはなく、普通に3,2,1位が発表されていました。kussoooooooooおめでとうございます(ｸｯｽｰと呼ばれてました)。発表後に参加賞的なものをもらいました。ディナーはカレー中心のバイキングでした。割りとおいしかった。バタチキとタンドリーチキンが無限に食べられるのは幸せだと思います。
どうでもいいけど順位は11位でした。

4日目(7/10)

3日目にHackerRankでいつも窓口になっているShashankという人に会う約束をしていたので会いました。ここでも自分のつたない英語が炸裂して意思疎通の限界を感じていました。
2日目の観光でだいぶ観光というものに嫌気がさしていたのか、本来この日に観光する予定だったのにみんなあまり乗り気じゃなかったのでさてどうするかってなっていたところ、adminがfacebookに、午前中に自然公園をハイキングするから希望者は来いと言っていました。kenkoooo君は眠っていてｸｯｽｰチームは蒸し蒸し嫌いとのことだったので、日本人としては僕だけ行ってきました。
地図で空港の北東にある緑色の塊が自然公園です。これの外縁までバスで行ってから、歩いてKanheri Cavesを目指しました。Kanheri Cavesの入り口まで道路が続いていたんですが、なぜかみんな歩くノリになっていたので歩くことになりました。地図上で測ったら5kmありますね。そりゃ時間かかるわけだ。
バスの中に10匹くらい蚊がいて、かなりやばかったです。どこから湧いたんだろう・・潰しまくっていました。
道中は1.5〜1.8台分の幅の濡れた路面と、そのわきのぬかるんだ道をひたすら歩いていました。道路には車がひたすらきてクラクションを鳴らしていきます。自然公園のなかには白い鳥(フラミンゴなんだろうか)とか猿とかスラム街がありました。
Kanheri Cavesに着いたら入場料を払って入場して小高いところに登っていきます。入り口には猿がたくさんいました。特に人間に危害を加えるわけでもないし、人間にビビったりしている様子もなさそうでした。
小高いところから周囲を一望できました。確かtwitterにtweetしたところだとおもいます。結構な時間ゆっくりしたあと嵐がきて強風と強い雨にうたれながら下山しました。
時間を大幅にオーバーしたようですが、これはこれで楽しかったです。

夜はホテルでディナーを食べてから空港に向かいました。帰りはデリー経由で東京に行くんですが、これが結構厳しかったです。まずチェックイン時の係員と話が通じなかったです・・そしてタグをつけてもらえず出国審査で引っ掛かり余計に時間を食うことに・・出発2時間前に空港に着いたにもかかわらず、11分前にようやく出国審査を抜けられました。なぜか予約時の席がうまっていたのでエコノミークラスの1個上のクラスに座ることになりました。まさか1時間半くらいの便のなかで機内ディナーが出るとは思っていなかったです・・つらい。

デリーでも2時間くらい余裕があったにもかかわらず、乗り継ぎするには一旦空港の外に出なければならず、したがってふたたび出国審査を受けなければいけませんでした。どうなってるんだこれ。これも結局残り時間10分くらいでようやく乗れた感じでした。

5日目(7/11)

今回の席は普通の席だったのでかなり狭く、寝る姿勢をとるのに難儀しました。着陸前は窓の外が晴れていたので写真を撮っていました。日本の風景は綺麗ですね。
そして帰国しました。せっかくなのでスカイライナーに乗りました。結構スカスカだったので何で安くしないんだろうなーとか考えていました。

天気について

雨季というから雨が毎日ドバーッと降り続いているんだろうなーと思っていたんですが、そんなことはなかったです。基本的に曇りで、2時間に10分ぐらい雨が適当にザーッと降る感じでした。

インドについて

人がたくさん、ハエもカラスもたくさん、ときどき野犬という感じです。野犬は狂犬病にかかる恐れがあるのであまり近づけませんでした。
湿度が高く、路面が常時濡れていて、その上にゴミが転がって、その上にハエがたかって、その上にカラスがいて・・という感じでした。インドの写真をネットで拾うと結構綺麗そうに見えますが、下を見ると割りとゴミだらけだとおもいます。唾吐きや立ち小便、ポイ捨てなど、東京で見かける負の部分が増幅している感じでした。こんだけ汚いのにネズミやGはいなかったのもまた不思議でした。
カラスの首筋が灰色になっていて、日本より退廃的な、ゲームでよく聞くような鳴き声で鳴きます。
あとあっちこっちにスラム街があります。青いビニールシートの屋根で、下が家のようにみえないものは全部スラム街だと思います。

持って行ったもの

ホテルがかなり良いホテルだったようで、ほとんどのものは結果的に要らない感じになってしまいました。

• 傘

7月は雨季らしく雨対策してねと書かれていたので傘を2本持って行きました。ホテルの出口に貸し傘があったのと、あんまり外に出歩くことがなかったので基本的に使いませんでした。

• 蚊対策

自分は蚊に刺されやすい(出発前に5,6箇所刺されてた)ので、蚊対策用に部屋に撒くのと肌にふきつけるのを用意していきました。毎日出発前につけていたのですが、基本的に蚊に刺されなかったみたいです。

• 水(お茶)

ロンドンのときも持って行って結局使わなかった水ですが、今回も使いませんでした。ホテルが毎日1人あたり1リットルの水を置いていってくれます。

• 非常食

メシマズのときの非常食もメシマズじゃなかったので使いませんでした。

• トイレットペーパー・ウェットティッシュ

"インド トイレ"でぐぐって戦慄していたので、絶対こうならないようにトイレットペーパーとウェットティッシュを持って行きました。ホテルのトイレはトイレットペーパーが付いているので基本的にこの目的で使うことはありませんでしたが、給仕に提供される食べ物は本当に食べ物しかなく、手を拭くものは一切あたえられなかったので、その目的で大いに役立ちました。また寒さで鼻水が出た時にも役に立ちました。

• モバイルバッテリー

ロンドンに行った時、iphoneがしょぼかったのもありますが電池が一瞬で切れて満足に写真を撮ることができなかったので、今回はバッテリーを持って行きました。モバイルバッテリーは機内持ち込みしかできないので注意。結果的には残量を気にせず撮影できてとても良かったです。

• モバイルwifi

会社から間接支給されたのですが、外に出歩くことは基本なく、adminからSIMが提供されたのでそちらを使っていました。SIMを抜き差しするためのクリップを持って行ったのは良かったです。

• サンダル

サンダルを持って行きました。これにより靴下がなくとも歩き回れてよかったと思います。あと丸洗いもできたので10日のハイキングの後も問題ありませんでした。

• 扇子

最初うちわを持って行こうと思っていたんですが、サイズ的な問題で扇子にしました。たまに使っていましたが、ホテル内は暑いことはないのであまり出番がありませんでした。

• 名札

名札を下げていったからといって人に話しかけられると思うな。

• 偽財布

スリが怖かったのでやっすい財布を1個買ってみました。ただ買い物すること自体がなかったので結局使わずじまい。総評ですが、インドの人たちはそんなにあくどそうにはみえませんでした。

• マウス

会場のが割りとよかったので使いませんでした。

• e-tourist visaのgrantedメール
• e-ticketを印刷したもの
• ホテル名
• codechefのチームアカウントの認証情報
• 日程表を印刷したもの
• テンプレ
• SA-ISの論文

主に紙媒体。上4個はほぼ必須です。5番目はあってもなくてもiPhoneから確認できたけれど、ちゃんと使ったので良し。6番目はライブラリがちゃんと入っていなかった場合の最終手段です。使わなくてよかった。7番目は途中で読むかなと思って入れたんですが読みませんでした・・。

問題について

結構どうでもいいことにハマっていたり、後でわかるんですが、虚仮威しだったものもいくつかあったりでなんか釈然としていないです。

Tree Cake

正しい漸化式をつくって法則を見つけ出す問題。セットの中では解いたチームが一番多かったんですが、一番ハマったと思います。クソミスを繰り返してWA3してしまいました。

Equalize

中央値の最大値を求める問題。クソ問。最初の提出の実装であっていたのにTLEしてしまい、ウ〜ンとなって終了直前まで悩んでいました。ソートをradix sortにしたら通ったけれど、正直ジャッジの気まぐれレベルだと思います。

Segment Tree

問題文に書かれていることを忠実に実装して、あとは分割可能な条件を自力で導ければ解けます。これは割とすんなりいけました。

Xortest Path

XOR回廊。ただ気づくまでに30分かかってしまったのは本当に情けない。森になっているが、1頂点でまとめて木にすると少し扱いやすい。

Beautiful Sandwich

解いたなかではこれが一番おもしろかったです。区間の長さの2乗はその長さ2以上の部分区間と長さ1の部分区間の個数で表されることを使ってNGパターンをぽちぽち追加したあと、高速ゼータ変換を使って一気に片付ける感じ。

Rain vs City

コードを書いてすらいなかったけど、kenkoooo君の解法で良かったらしい。これdoubleの3.2*10^8のDPでそして整数に近い値の扱いが謎なんですけど普通通ると思わない・・(追記)通しました。これはひどい。

Provinces of ChefLand

これはまだ通してないけど、普通のセルを追加していくBitDPで良いっぽい？連結成分が小さいのでRedelmeierで列挙すればいけたか・・もったいない。(追記)通しました。Redelmeierで連結成分を全列挙してずらすだけ・・

Catch Spider-Chef

簡単な幾何。なぜこんなに解かれていないのか不思議。にぶたんやるだけ。

Counting Games

kenkoooo君から問題解釈を説明されたが、あとで読んだものとだいぶ違う理解をしていた。もったいない。いったんgrundy数を決めてしまえばあとは高速アダマール変換で行けそう。 (追記)ました。細かいミスたくさんしたけれど。

TreeLand Journey

Weird Queries

Big Search Trees

読んでないです。

これから

リスニング力が致命的にダメだったことを再認識しました。スピーキングも。こういうのはどうしたら鍛えられるんだろうか・・kenkoooo君とか他のメンバーに頼りっきりでした。感謝感謝。
他の国の参加者とも意思疎通したかったんですが、これではとてもとても・・という感じでした。
あとはコンテストの最初1時間固まっててあまり進捗が出せなかったのも問題です。このスロースターターっぷりをなんとかしたい。

素数列挙について

Competitive Programming Advent Calendar 3日目は、数学っぽい話をしたいと思います。

N以下の素数をすべて求めよ。
N以下の素数の個数を求めよ。
A以上B以下の素数の個数を求めよ。

こんな感じの問題を見たことがあると思います。また問題としてでなくても、解く過程にこのようなサブ問題を解かなければいけない場合もよくあると思います。素数については説明しなくてもいいですよね？
このような問題を素数列挙と呼ぶことにします。素数列挙ができれば、大きい数の素数判定や素因数分解をめっちゃ高速化したり、トーティエント関数、メビウス関数等、数学系のいろんな関数を求めたりできます。最近のもので素数列挙がほぼ必須のものだと

Codeforces Beta Round #86 (Div. 1 Only) C. Double Happiness
ICPC 国内予選 2011 A Chebyshev's Theorem
ProjectEuler Problem 351
ProjectEuler Problem 354
KUPC E Fox Number
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2286:RUPC F Farey Sequence
CodeChef April Cook-Off Challenge A Prime Conjecture
1000万個目の素数を超高速に出力せよ
interviewstreet EQUATIONS

あたりでしょうか。ProjectEulerではしょっちゅう使っている気がします。いろんなことの前提になるのであれば、当然高速に動くコードがあったほうが良いわけです。今回は素数列挙を高速に解く方法について語ります。10^8,10^9くらいまでの素数を高速に列挙orカウントすることを目標に。この野郎知ってるよという節はばんばん飛ばしてください。
今回有為さんはいっぱい○っぱいなので申し訳ないですがJavaで書きます。素数列挙コードは競技コーダーの方はよく書いている(蟻本にもちょろっとある)ので、ぐぐればそれなりに出てきます。

ぐちょく

まずナイーブな方法から書いて行きましょう。ある自然数Nが素数であることを愚直に判定するには2以上√N以下の整数で試し割って、どれも割り切れなければいいわけです。N以下の素数列挙はこれを1〜Nに対し行えばいいだけです。実行時間O(N√N) (定数係数は2/3程度), メモリO(N)です。もしもライブラリがなく、Nが10^5以下で早解き勝負になっているなら、僕は迷わずこれを書きます。素数の個数の上限はもっと抑えられますが、それは後述します。

	static int[] sieveNaively(int n)
	{
		int[] primes = new int[n];
		int p = 0;
		outer:
		for(int i = 2;i <= n;i++){
			for(int j = 2;j*j <= i;j++){
				if(i % j == 0)continue outer;
			}
			primes[p++] = i;
		}
		return Arrays.copyOf(primes, p);
	}

	static int countNaively(int n)
	{
		int ct = 0;
		outer:
		for(int i = 2;i <= n;i++){
			for(int j = 2;j*j <= i;j++){
				if(i % j == 0)continue outer;
			}
			ct++;
		}
		return ct;
	}

あんまりnが大きいとj*jのところでintの範囲を超えてしまう場合がありますがご愛嬌。
実行時間は以下のとおり。sieveもcountもほぼ同じ実行時間でした。

n	実行時間(ideone)
10^4	0.05s
10^5	0.11s
10^6	1.46s
10^7	>15s

Eratosthenesの篩(ふるい)

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
ただの試し割りでは空振り率が高いので、既に求まった素数の倍数を選んで撃ち落そうというのがEratosthenesの篩です。2〜Nの整数を整列してフラグを立てます。これに、

列の先頭から見て行って、フラグが立っている数qに対し、q^2以上のqの倍数のフラグを全部消す。

という操作を行うと、残ったフラグの立っている数はすべて素数になります。先頭から見て行って出会うqは必ず素数になっていて、この素数で他の数を試し割りします。r*q(r

	static int[] sieveEratos(int n)
	{
		BitSet primeset = new BitSet();
		primeset.flip(2, n+1);
		for(int q = primeset.nextSetBit(2);q != -1 && q*q <= n;q = primeset.nextSetBit(q+1)){
			for(int i = q*q;i <= n;i += q){
				primeset.clear(i);
			}
		}
		
		int[] primes = new int[primeset.cardinality()];
		int p = 0;
		for(int q = primeset.nextSetBit(2);q != -1;q = primeset.nextSetBit(q+1)){
			primes[p++] = q;
		}
		return primes;
	}

n	実行時間(ideone)
10^6	0.11s
10^7	0.66s
10^8	7.95s
10^9	MLE

BitSetが活躍します。nextSetBitで立っているビットだけを走査したり、cardinalityで立っているビットの個数を数えたりできます。countはcardinalityをただ返せばいいですね。

Wheel factorization

http://en.wikipedia.org/wiki/Wheel_factorization
見に行く整数の個数の式で、2,3,5といった小さい素数のところの値が大きくなるのに気づいたでしょうか。実際10^9までの素数の逆数の和は3程度ですが、その半分がこの3つの素数で占められています。これらをあらかじめ除いてから篩にかけちゃおう、というのがWheel factorizationです。
たとえば2,3,5を除くとすると、残るのは30m+1,7,11,13,17,19,23,29の8個になります。30個から8個に減らせたのでそのぶん定数倍高速化が見込めますが、30m+dがqで割り切れるようなmを求めなくてはいけません。これは拡張ユークリッド互除法を使ってO(log q)で求めることができます。
ここでは昔の僕の2だけ消したしょぼい篩を書くにとどめておきます。

	public static int[] sieveEratosthenesOld(int n)
	{
		int[] ret = new int[(int)(n / Math.log(n)) + (int)(n / (Math.log(n)*Math.log(n))*1.5)  ];
		ret[0] = 2;
		int pos = 1;
		
		// 0:3 1:5
		// 2x+3=n
		BitSet bs = new BitSet(n/2+1);
		int sup = (n - 3) / 2;
		for(int i = bs.nextClearBit(0);i <= sup; i = bs.nextClearBit(i+1)){
			int p = 2 * i + 3;
			ret[pos++] = p;
			for(int j = i + p;j <= sup;j += p){
				bs.set(j);
			}
		}
		
		return Arrays.copyOf(ret, pos);
	}

n	実行時間(ideone)
10^7	0.35s
10^8	4.76s
10^9	MLE

retの要素数のところにおぞましい式が出てきていますがこれは次節で。

素数の個数の概算

http://en.wikipedia.org/wiki/Prime_number_theorem
素数定理という有名なものがあります。素数の個数のだいたいの値はこれでわかりますが、あまり精度がよくないので、詳しい値は求められません。

対数積分Li(x)を1回部分積分すると、の項が出てきます。オーダー等を計算するにはだいたいこれで十分でしょう。前節のコードの式は2回部分積分したものの2項目に1ではなく1.5をかけて上限の個数を近似しています。1.5は実験で決めています。
1〜Nから一度に素数列挙しようとすると、やはりO(N/log N)以上のメモリは必要になってしまいます。N=10^9だと若干心配ですね。

自力高速化

BitSetではなくintでビットを持つことにすると、32bitを1単位として持つので、そのなかで複数出てきうるような小さい素数に対してはパターンが数種類程度で収まり、これをまとめて適用することで定数倍高速化できます。現在使っている篩はこのコードです。

	public static int[] sieveEratosthenes(int n)
	{
		if(n <= 32){
			int[] primes = {2,3,5,7,11,13,17,19,23,29,31};
			for(int i = 0;i < primes.length;i++){
				if(n < primes[i]){
					return Arrays.copyOf(primes, i);
				}
			}
			return primes;
		}
		
		int u = n+32;
		double lu = Math.log(u);
		int[] ret = new int[(int)(u/lu+u/lu/lu*1.5)];
		ret[0] = 2;
		int pos = 1;
		
		int[] isp = new int[(n+1)/32/2+1];
		int sup = (n+1)/32/2+1;
		
		int[] tprimes = {3,5,7,11,13,17,19,23,29,31};
		for(int tp : tprimes){
			ret[pos++] = tp;
			int[] ptn = new int[tp];
			for(int i = (tp-3)/2;i < tp<<5;i+=tp)ptn[i>>5] |= 1<<(i&31);
			for(int i = 0;i < tp;i++){
				for(int j = i;j < sup;j += tp)isp[j] |= ptn[i];
			}
		}
		
		// 3,5,7
		// 2x+3=n
		int[] magic = {0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4, 13, 31, 22, 28, 18, 26, 10, 7, 12, 21, 17, 9, 6, 16, 5, 15, 14};
		int h = n/2;
		for(int i = 0;i < sup;i++){
			for(int j = ~isp[i];j != 0;j &= j-1){
				int pp = i<<5|magic[(j&-j)*0x076be629>>>27];
				int p = 2*pp+3;
				if(p > n)break;
				ret[pos++] = p;
				for(int q = pp;q <= h;q += p)isp[q>>5] |= 1<<(q&31);
			}
		}
		
		return Arrays.copyOf(ret, pos);
	}

n	実行時間(ideone)
10^7	0.13s
10^8	1.72s
10^9	MLE

途中に出てくるmagicとかいうのは2^nからnを高速に得るための黒魔術です。
http://chessprogramming.wikispaces.com/De+Bruijn+sequence

区間篩

[L,L+B]の区間上での篩をしたいとき、√(L+B)までの素数が求まっていれば篩うことができます。Lが大きくて、Bが小さい場合に使えるテクニックです。区間篩自体はO(Bloglog(L+B))でしょうか。

	public static BitSet sieveBySegment(long l, int b){
		BitSet com = new BitSet();
		com.set(0, l+1);
		for(int p : primes){
			if((long)p*p > l+b)break;
			for(int i = (int)(p-1-(l-1)%p);i <= b;i+=p){
				com.clear(i);
			}
		}
		return com;
	}

さあ、これまでは前座、前座あかりです。

Atkinの篩

http://en.wikipedia.org/wiki/Sieve_of_Atkin
Eratosthenesより計算量の良いものとしてAtkinの篩があります。実行時間はO(N/loglogN)です。
これは次の事実を利用しています。nはsquarefree(同じ素因数を2個以上含まない)として、
が素数⇔の正の解(x,y)が奇数個存在する。
が素数⇔の正の解(x,y)が奇数個存在する。
が素数⇔の解(x,y) (x>y>0)が奇数個存在する。
これの証明は単項イデアル整域等出てきてお見せ出来なかったので端折ります。
つまりは、2,3,5以外、この(x,y)をN以下について全部列挙して、squarefreeなやつだけ選べばいいのです。(x,y)の個数は高々O(N).
Spaghetti Sourceまんまですが、Atkinの篩にはあまり思い入れはないのでいいでしょう。

	public static BitSet sieveAtkin(int n)
	{
		int sqn = (int)Math.sqrt(n);
		BitSet isp = new BitSet(n);
		int b;
		for (int z = 1; z <= 5; z += 4) {
			for (int y = z; y <= sqn; y += 6) {
				for (int x = 1; x <= sqn && (b = 4 * x * x + y * y) <= n; ++x)isp.flip(b);
				for (int x = y + 1; x <= sqn && (b = 3 * x * x - y * y) <= n; x += 2)isp.flip(b);
			}
		}
		for (int z = 2; z <= 4; z += 2) {
			for (int y = z; y <= sqn; y += 6) {
				for (int x = 1; x <= sqn && (b = 3 * x * x + y * y) <= n; x += 2)isp.flip(b);
				for (int x = y + 1; x <= sqn && (b = 3 * x * x - y * y) <= n; x += 2)isp.flip(b);
			}
		}
		for (int y = 3; y <= sqn; y += 6) {
			for (int z = 1; z <= 2; ++z) {
				for (int x = z; x <= sqn && (b = 4 * x * x + y * y) <= n; x += 3)isp.flip(b);
			}
		}
		for(int i = isp.nextSetBit(5);i != -1 && i <= sqn;i = isp.nextSetBit(i+2)){
			int zz = i*i;
			for (int k = zz; k <= n; k += zz)isp.clear(k);
		}
		isp.set(2); isp.set(3);
		return isp;
	}

n	実行時間(ideone)
10^7	0.22s
10^8	3.39s
10^9	MLE

Atkinの篩進化形

http://scholar.google.co.jp/scholar?cluster=17579060183460050316&hl=ja&as_sdt=0,5
前節のAtkinの篩は10^9でMLEしてしまいました。前にも書いたように1〜Nを一度に篩おうとするとそれなりのメモリが必要なのです。これから書くものは実行時間のオーダーそのままで、メモリがなんとO(√N)でできる篩です。メモリだけ減っても速くならないというわけではなく、既存のものもL1,L2キャッシュに乗りやすくなるので高速化が期待できます。
区間[60L,60(L+B))の素数をAtkinの篩で篩うことを考えます。当然、の解を求めることになりますが、xy平面上でみると、これらは2次曲線の軌跡からなる帯のような形をしています。この中を、特殊解から、なら(-15,0)または(0,30)のステップ幅で移動して解を列挙していきます。これで使用するメモリはO(B). B=60√Nとして選び、[60,60(1+B)),[60(1+B),60(1+2B)),..について区間篩を繰り返すと、全体での実行時間オーダーがちょうどO(N/loglogN)に、メモリオーダーがになるようです。
特殊解はあらかじめ計算できておくのでその辺は埋め込みです。でもあまり実行速度には影響ありませんでした。

また、squarefreeの判定のために√Nまでの素数が必要なので、別にsieveしておきます。これは自分自身を呼んでも構いません。

  // 4x^2+y^2=d(mod 60)の特殊解(x,y)=(f,g)
	static final int[][] DFG1 = {{1,0,1},{1,0,11},{1,0,19},{1,0,29},{1,2,15},{1,3,5},{1,3,25},{1,5,9},{1,5,21},{1,7,15},{1,8,15},{1,10,9},{1,10,21},{1,12,5},{1,12,25},{1,13,15},{13,1,3},{13,1,27},{13,4,3},{13,4,27},{13,6,7},{13,6,13},{13,6,17},{13,6,23},{13,9,7},{13,9,13},{13,9,17},{13,9,23},{13,11,3},{13,11,27},{13,14,3},{13,14,27},{17,2,1},{17,2,11},{17,2,19},{17,2,29},{17,7,1},{17,7,11},{17,7,19},{17,7,29},{17,8,1},{17,8,11},{17,8,19},{17,8,29},{17,13,1},{17,13,11},{17,13,19},{17,13,29},{29,1,5},{29,1,25},{29,4,5},{29,4,25},{29,5,7},{29,5,13},{29,5,17},{29,5,23},{29,10,7},{29,10,13},{29,10,17},{29,10,23},{29,11,5},{29,11,25},{29,14,5},{29,14,25},{37,2,9},{37,2,21},{37,3,1},{37,3,11},{37,3,19},{37,3,29},{37,7,9},{37,7,21},{37,8,9},{37,8,21},{37,12,1},{37,12,11},{37,12,19},{37,12,29},{37,13,9},{37,13,21},{41,2,5},{41,2,25},{41,5,1},{41,5,11},{41,5,19},{41,5,29},{41,7,5},{41,7,25},{41,8,5},{41,8,25},{41,10,1},{41,10,11},{41,10,19},{41,10,29},{41,13,5},{41,13,25},{49,0,7},{49,0,13},{49,0,17},{49,0,23},{49,1,15},{49,4,15},{49,5,3},{49,5,27},{49,6,5},{49,6,25},{49,9,5},{49,9,25},{49,10,3},{49,10,27},{49,11,15},{49,14,15},{53,1,7},{53,1,13},{53,1,17},{53,1,23},{53,4,7},{53,4,13},{53,4,17},{53,4,23},{53,11,7},{53,11,13},{53,11,17},{53,11,23},{53,14,7},{53,14,13},{53,14,17},{53,14,23}};
  // 3x^2+y^2=d(mod 60)の特殊解(x,y)=(f,g)
	static final int[][] DFG2 = {{7,1,2},{7,1,8},{7,1,22},{7,1,28},{7,3,10},{7,3,20},{7,7,10},{7,7,20},{7,9,2},{7,9,8},{7,9,22},{7,9,28},{19,1,4},{19,1,14},{19,1,16},{19,1,26},{19,5,2},{19,5,8},{19,5,22},{19,5,28},{19,9,4},{19,9,14},{19,9,16},{19,9,26},{31,3,2},{31,3,8},{31,3,22},{31,3,28},{31,5,4},{31,5,14},{31,5,16},{31,5,26},{31,7,2},{31,7,8},{31,7,22},{31,7,28},{43,1,10},{43,1,20},{43,3,4},{43,3,14},{43,3,16},{43,3,26},{43,7,4},{43,7,14},{43,7,16},{43,7,26},{43,9,10},{43,9,20}};
  // 3x^2-y^2=d(mod 60)の特殊解(x,y)=(f,g)
	static final int[][] DFG3 = {{11,0,7},{11,0,13},{11,0,17},{11,0,23},{11,2,1},{11,2,11},{11,2,19},{11,2,29},{11,3,4},{11,3,14},{11,3,16},{11,3,26},{11,5,2},{11,5,8},{11,5,22},{11,5,28},{11,7,4},{11,7,14},{11,7,16},{11,7,26},{11,8,1},{11,8,11},{11,8,19},{11,8,29},{23,1,10},{23,1,20},{23,2,7},{23,2,13},{23,2,17},{23,2,23},{23,3,2},{23,3,8},{23,3,22},{23,3,28},{23,4,5},{23,4,25},{23,6,5},{23,6,25},{23,7,2},{23,7,8},{23,7,22},{23,7,28},{23,8,7},{23,8,13},{23,8,17},{23,8,23},{23,9,10},{23,9,20},{47,1,4},{47,1,14},{47,1,16},{47,1,26},{47,2,5},{47,2,25},{47,3,10},{47,3,20},{47,4,1},{47,4,11},{47,4,19},{47,4,29},{47,6,1},{47,6,11},{47,6,19},{47,6,29},{47,7,10},{47,7,20},{47,8,5},{47,8,25},{47,9,4},{47,9,14},{47,9,16},{47,9,26},{59,0,1},{59,0,11},{59,0,19},{59,0,29},{59,1,2},{59,1,8},{59,1,22},{59,1,28},{59,4,7},{59,4,13},{59,4,17},{59,4,23},{59,5,4},{59,5,14},{59,5,16},{59,5,26},{59,6,7},{59,6,13},{59,6,17},{59,6,23},{59,9,2},{59,9,8},{59,9,22},{59,9,28}};
	static final int[] DALL = {1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59};
	static final int[] D1 = {1,13,17,29,37,41,49,53};
	static final int[] D2 = {7,19,31,43};
	static final int[] D3 = {11,23,47,59};
	static final int[] U60 = new int[]{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};
	
	static int[][] segs = new int[60][];
	
	public static int[] sieveOfAtkinBernstain(int N)
	{
		if(N <= 60){
			int ind = Arrays.binarySearch(U60, N);
			if(ind < 0)ind = -ind-2;
			return Arrays.copyOf(U60, ind+1);
		}
		
		int B = 60*(int)Math.sqrt(N);
		int[] primes = sieveOfAtkinBernstain((int)Math.sqrt(N));
		
		int u = N+32;
		double lu = Math.log(u);
		int[] ret = new int[(int)(u/lu+u/lu/lu*1.5)];
		
		int r = U60.length;
		System.arraycopy(U60, 0, ret, 0, U60.length);
		
		for(int d : DALL)segs[d] = new int[(B>>>5)+1];
		
		for(int L = 1;L <= N/60;L+=B){
			for(int d : DALL)Arrays.fill(segs[d], 0);
			
			// sieve!
			for(int[] D : DFG1)enum1(D[1], D[2], D[0], L, B);
			for(int[] D : DFG2)enum2(D[1], D[2], D[0], L, B);
			for(int[] D : DFG3)enum3(D[1], D[2], D[0], L, B);
			
			// sieve non-squarefree
			for(int p : primes){
				if((long)p*p > 60*(L+B))break;
				if(p >= 7){
					// kp^2=60(L+x)+d
					// A*p^2-X*60=60L+d
					long b = -exGCDSimple(p*p, 60);
					int p2 = p*p;
					if(b < 0)b += p2;
					for(int d : DALL){
						int x = (int)(b*(60*L+d)%p2);
						for(;x < B;x += p2){
							segs[d][x>>>5] &= ~(1<<(x&31));
						}
					}
				}
			}
			
			// arrange primes
			inner:
			for(int j = 0;j < (B>>>5)+1;j++){
				for(int x = 0;x < 32;x++){
					long base = 60*(L+x+(j<<5));
					for(int d : DALL){
						if(base+d > N)break inner;
						if(segs[d][j]<<31-x<0){
							ret[r++] = 60*(L+x+(j<<5))+d;
						}
					}
				}
			}
		}
		ret = Arrays.copyOf(ret, r);
		return ret;
	}
	
	public static int countOfAtkinBernstain(int N)
	{
		if(N <= 60){
			int ind = Arrays.binarySearch(U60, N);
			return ind < 0 ? -ind-1 : ind;
		}
		
		int B = 60*(int)Math.sqrt(N);
		int[] primes = sieveOfAtkinBernstain((int)Math.sqrt(N));
		int r = U60.length;
		
		for(int d : DALL)segs[d] = new int[(B>>>5)+1];
		
		for(long L = 1;60*L <= N;L+=B){
			for(int d : DALL)Arrays.fill(segs[d], 0);
			
			// sieve!
			for(int[] D : DFG1)enum1(D[1], D[2], D[0], L, B);
			for(int[] D : DFG2)enum2(D[1], D[2], D[0], L, B);
			for(int[] D : DFG3)enum3(D[1], D[2], D[0], L, B);
			
			// sieve non-squarefree
			for(int p : primes){
				if((long)p*p > 60*(L+B))break;
				if(p >= 7){
					// kp^2=60(L+x)+d
					// A*p^2-X*60=60L+d
					long b = -exGCD(p*p, 60);
					int p2 = p*p;
					if(b < 0)b += p2;
					for(int d : DALL){
						int x = (int)(b*(60*L+d)%p2);
						for(;x < B;x += p2){
							segs[d][x>>>5] &= ~(1<<(x&31));
						}
					}
				}
			}
			
			// count primes
			for(int j = 0;j < (B>>>5)+1;j++){
				long base = 60*(L+(j<<5)+31);
				for(int d : DALL){
					if(base+d > N){
						// 60(L+32j+x)+d <= N
						// x <= (N-d)/60-L-32j
						int sup = (int)((N-d)/60-L-(j<<5)+1);
						if(sup <= 0)break;
						r += Integer.bitCount(segs[d][j]&(1<<sup)-1);
					}else{
						r += Integer.bitCount(segs[d][j]);
					}
				}
			}
		}
		return r;
	}
	
	public static long exGCDSimple(long a, long b)
	{
		long r = 0, s = 1;
		while(b > 0){
			long c = a / b;
			long d;
			d = a; a = b; b = d % b;
			d = r; r = s; s = d - c * s;
		}
		return r;
	}
	
	static void enum1(int f, int g, int d, long L, int B)
	{
		int x = f, y0 = g;
		int k0 = (4*f*f+g*g-d)/60;
		while(k0<L+B){
			k0 += 2*x + 15;
			x += 15;
		}
		while(true){
			x -= 15;
			k0 -= 2*x+15;
			if(x <= 0)break;
			while(k0 < L){
				k0 += y0+15;
				y0 += 30;
			}
			int k = k0, y = y0;
			while(k < L+B){
				segs[d][(int)(k-L)>>>5] ^= 1<<((k-L)&31);
				k += y+15;
				y += 30;
			}
		}
	}
	
	static void enum2(int f, int g, int d, long L, int B)
	{
		int x = f, y0 = g;
		int k0 = (3*f*f+g*g-d)/60;
		while(k0<L+B){
			k0 += x + 5;
			x += 10;
		}
		while(true){
			x -= 10;
			k0 -= x+5;
			if(x <= 0)break;
			while(k0 < L){
				k0 += y0+15;
				y0 += 30;
			}
			int k = k0, y = y0;
			while(k < L+B){
				segs[d][(int)(k-L)>>>5] ^= 1<<((k-L)&31);
				k += y+15;
				y += 30;
			}
		}
	}
	
	static void enum3(int f, int g, int d, long L, int B)
	{
		int x = f, y0 = g;
		int k0 = (3*f*f-g*g-d)/60;
		outer:
		while(true){
			while(k0 >= L+B){
				if(x <= y0)break outer;
				k0 -= y0 + 15;
				y0 += 30;
			}
			int k = k0, y = y0;
			while(k>=L && y<x){
				segs[d][(int)(k-L)>>>5] ^= 1<<((k-L)&31);
				k -= y+15;
				y += 30;
			}
			k0 += x+5;
			x += 10;
		}
	}

sieve

n	実行時間(ideone)
10^7	0.15s
10^8	0.76s
10^9	MLE

digest(結果を格納せず、何も書き出さないWriterに逐次書きだす)

n	実行時間(ideone)
10^7	0.15s
10^8	0.75s
10^9	6.76s

count

n	実行時間(ideone)
10^7	0.09s
10^8	0.33s
10^9	2.83s

こんな感じです。論文を見て自前で実装したので、もっと高速化できると思います。

2次式の篩

呼び方がよくわからないので・・ProjectEulerで稀に、2次式の形の篩を要求されることがあります。これはO(NloglogN)でできます。考えてみてくださいね。
http://projecteuler.net/problem=216

Google Developer Day DevQuiz 所感1

ひさびさの投稿ですね。

ようやっとGoogle Developer Day 2011のDevQuizが終わったのでいろいろ考えていたことを書きたいと思います。この記事ではスライドパズル以外の問題等々について書きます。

去年TwitterのTLにGDD2010の話題がよく流れていて、指をくわえて見ていたのですが、今年は情報を早めにキャッチできたので即参加しました。参加時点では、実はGDDが何をするものなのかよくわかってませんでした。

• ウォームアップクイズ

いくらか意地悪な問題がある以外は適当にやってればできました。ヨセミテがぐぐらずともわかったのが良かったです。

• Web Game

最初にWebGameから手をつけました。user.jsは何度かつくったことがあったのですが、最初カードの色を取得するもんだとおもって少々手こずりました。色の取得なんてしなくてもscriptの内容を読めば一発ですね。eventをdispatchしてからclickイベントで受け取ってもらえるように短めのタイマーで繰り返しクリックをdispatchしていました。
明らかに手で解けないほどの数でもサクサク進んでたのが面白かったです。

// ==UserScript==
// @name           osimasu2
// @namespace      uwi
// @description    おしまーす
// @version        0.1.0
// @author         uwi
// @copyright      uwi
// @include        http://gdd-2011-quiz-japan.appspot.com/webgame/problem
// ==/UserScript==

//(function(){
	var ar = [];
	
	window.setInterval(function(event){
		if(ar.length > 0)return;
	
		var e = document.getElementsByTagName("script");
		var t = e[2].innerText;
		var ind = t.indexOf("conc.setup([");
		var inde = t.indexOf("]);");
		var ss = t.substring(ind + "conc.setup([".length, inde);
		var sp = ss.split(",");
		var n = sp.length;
		for(var i = 0;i < n;i++){
			for(var j = i+1;j < n;j++){
				if(sp[i] == sp[j]){
					ar.push([i, j]);
					break;
				}
			}
		}
	}, 500);
	window.setInterval(function(event){
		if(ar.length == 0)return;
	var ev = document.createEvent("MouseEvents");
	ev.initEvent("click", false, true);
		var y = ar.pop();
		document.getElementById("card"+y[0]).dispatchEvent(ev);
		document.getElementById("card"+y[1]).dispatchEvent(ev);
	}, 50);
//})();

• 一人ゲーム

競技コーダーなら楽勝のBitDPの典型問でした。数の個数が高々10なのでその時々で消せる5の倍数の数たちは2^10通りのビットで表せます。dp[i][j]=(i回半分にする操作を行ったとき、消されているパターンがjになるための操作回数の最小値), erase[i]=(i回半分にする操作を行ったあと消せる5の倍数の数のパターン)として
dp[i][j|erase[i] ] = min(dp[i][j|erase[i] ], dp[i][j]+1) // 5の倍数消去の操作
dp[i+1][j] = min(dp[i+1][j], dp[i][j]+1) // 半分にする操作
の漸化式で配るDPを行い、最後にdp[*][(1<

package gdd2011;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

public class E {
	static Scanner in;
	static PrintWriter out;
	
	static void solve()
	{
		for(int t = ni();t >= 1;t--){
			int n = ni();
			int[] a = new int[n];
			for(int i = 0;i < n;i++)a[i] = ni();
			
			int[][] dp = new int[23][1<<n];
			for(int i = 0;i < 23;i++){
				Arrays.fill(dp[i], 999);
			}
			dp[0][0] = 0;
			for(int i = 0;i < 22;i++){
				int erase = 0;
				for(int j = 0;j < n;j++){
					if(a[j] % 5 == 0){
						erase |= 1<<j;
					}
					a[j] /= 2;
				}
				
				for(int j = 0;j < 1<<n;j++){
					dp[i][j|erase] = Math.min(dp[i][j|erase], dp[i][j] + 1);
					dp[i+1][j] = Math.min(dp[i+1][j], dp[i][j] + 1);
				}
			}
			
			int min = 999;
			for(int i = 0;i < 23;i++){
				min = Math.min(min, dp[i][(1<<n)-1]);
			}
			out.println(min);
		}
	}
	
	public static void main(String[] args) throws Exception
	{
		in = INPUT.isEmpty() ? new Scanner(System.in) : new Scanner(INPUT);
		out = new PrintWriter(System.out);
		
		solve();
		out.flush();
	}
	
	static int ni() { return Integer.parseInt(in.next()); }
	static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
	
	static String INPUT = "4\r\n" + 
	"2\r\n" + 
	"10 21\r\n" + 
	"3\r\n" + 
	"0 9 9\r\n" + 
	"4\r\n" + 
	"81 67 83 86\r\n" + 
	"3\r\n" + 
	"11 22 30";
}

• Go!

満点をとった後に解きました。ideoneにGoがあったので書いてみていたら、どうやらバージョンが古い様子・・リファレンスをみながらせこせこ書きました。最近の言語はひと通り必要なのが揃っていますね。あと未使用変数に厳しいのとメソッド名が大文字で始まるのが気に入らないですね・・
image/pngのメソッドを呼ぶときどうしたらいいかでハマってました。

package main
import (
"fmt"
"io"
"strings"
"image/png"
)

func CountColor(pn io.Reader) int {
	im, _ := png.Decode(pn)
	minx := im.Bounds().Min.X
	miny := im.Bounds().Min.Y
	maxx := im.Bounds().Max.X
	maxy := im.Bounds().Max.Y
	colmap := map[uint32] int {}
	
	for x:=minx;x < maxx;x++ {
	for y:=miny;y < maxy;y++ {
		r, g, b, _ := im.At(x,y).RGBA()
		colmap[r<<16|g<<8|b] = 1
	}
	}
	
	return len(sum)
}

• Apps Script

これもリファレンスを読みながらせこせこ解いていました。不正解でも理由がちゃんと表示されるので良いですね。リファレンスには使える関数の詳細しか載っていなくて、基本的な文法のところがごっそり抜けてたので、どういうふうに書いたものだか悩んでました。

function myFunction() {
  var sps = SpreadsheetApp.getActiveSpreadsheet();
  var i,j;
  
  var response = UrlFetchApp.fetch("http://gdd-2011-quiz-japan.appspot.com/apps_script/data?param=2140114143949079677");
  var json = response.getContentText();
  var obj = Utilities.jsonParse(json);
  for(j in obj){
    var datum = obj[j];
    var sheet = sps.insertSheet(datum.city_name);
    var len = datum.data.length;
    for(i = 0;i < len;i++){
      var datum2 = datum.data[i];
      sheet.getRange(i+1, 1).setValue(datum2.capacity);
      sheet.getRange(i+1, 2).setValue(datum2.usage);
      sheet.getRange(i+1, 3).setValue((datum2.usage/datum2.capacity*100)+"%");
    }
  }
  Browser.msgBox("おたわ");
}

• Android

解けませんでした・・エミュレータをいれてコード入力まではできたんですが、あのAIDLからどうやってアプリをつくれというんだ・・というのでうんうん唸っていました。締切前日になってEclipseにAndroid pluginを入れたらいいことがわかったのでいれようとしたら固まったままInstallできない→終了　でした。向いてないんでしょうか。

BottomCoder SRM 367 div2

SRM 367 div2

points	result	time
250	AC	2.5m
500	AC	2m
1000	WA	17m

1000はケアレスミス・・なのか？どうすればいいんだこれ

BottomCoder SRM 369 div2

SRM 369 div2

points	result	time
250	AC	4.7m
500	WA
1000	AC	17.1m

あああ500みたいな問題苦手だ・・どうすればひらめくんだろう

BottomCoder SRM 370 div2

SRM 370 div2

points	result	time
250	AC	2.7m
500	AC	4.4m
1000	AC	46.5m

でたー！T9だー！

BottomCoder SRM 371 div2

SRM 371 div2

points	result	time
250	AC	6.5m
500	AC	5m
1000	AC	21m

SRMの有向グラフの問題はどうして方針を間違えまくるのだろう。