SRM613

R1372でDivに参戦。

Easy

x軸上のN匹の猫が左右にX回移動したときの移動後の両端の猫の差を求める問題。
プログラミングコンテストチャレンジブックに載ってるアリの問題と大体同じだけど自分で考えてサブミットした答えは全然間違っていた。500人以上も解いてる人がいるのに、、これが自分の実力か…。

Medium

問題の意味は直ぐ分かったけど糸口すらつかめず。

Hard

開いてない

所感

今回は自分に落ち着きがなく物凄く焦っていた。R1372->R1292. Easy問題が解けないと速攻でレーティングが落ちる。3月中のイエローコーダーは厳しくなってしまった。

メタ・ビッグデータ

すごく抽象的だけど面白い話。

いわゆるデータ爆発の時代に、データをどう管理するかはIT産業における大きな問題です。Hadoopをはじめとするビッグデータの蓄積保存と分析のためのツールも普及が進んでいますが、いっぽうでデータの検索や管理についてはまだまだ人手でカバーしている場面が多いのではないかと思います。

例えば、あなたはWebマーケティングマネージャでとあるWebキャンペーンのディレクションをしたとします。キャンペーン期間は1か月あり、キャンペーン後に告知サイトのWebアクセスログがエンジニアリングチームから渡されました。圧縮して100ギガ、展開して500ギガになり、圧縮状態と展開状態がそれぞれ社内のHadoop（HDFS）においてあります、とhdfs URIスキーマ形式でのアドレスが担当エンジニアからのメールに記載されています。
あなたはキャンペーンの目的に照らして、効果検証の項目を列挙し、部下に検証作業を依頼します。もろもろのレポートが出来上がり、経営層へのプレゼンを終えてプロジェクトは終了します。

さてこのとき、次のような課題が浮上すると思われます。

  • このキャンペーンの生ログはこの後もHDFSにずっととっておくのか？
  • 生ログは圧縮状態で保管するのか？それとも展開状態か？前処理は？
  • 効果検証に使ったプログラムはログのデータとは別にコードリポジトリで管理されているが、両者の対応（どのプログラムがどのデータに適用可能か、もしくは適用したのか）については誰が覚えておくのか？
  • 同様に、分析結果はどこにどのように保管するのか？
  • キャンペーンは繰り返し色んな対象物で行れていくが、過去の事例からデータや分析結果や分析プログラムを引っ張ってきて再利用するためのプロセスは人手で頑張るのか？

いまビッグデータと言われている話は、分析の手法や扱うデータの大きさへの対処を特に意識して語られることが多いと思われますが、実務上はこうした「管理」の側面がバカになりません。

上記の事例はある企業の「社内データ」において発生する課題についてのものですが、社外のデータにおいても、同様の課題は企業横断的に発生すると思います。とくに昨今のアドテクにおいては、メディアやテクノロジベンダやエージェンシーなどの各プレイヤがそれぞれ持つデータを統合するところに大きな付加価値があると思われるためです。とりあえずここではその話は置いといて、本記事では社内データについて考えます。

この課題への対処としてメジャーな手段として、「情報の一元化」がまず第一に挙げられます。つまり、「常にそこに集約される場所」を用意しておけば「何かあったらそこを見る」という対応が可能になるからです。分析プログラムとデータの対応関係等も、社内ポータルのようなものを立ててドキュメント化しておくわけです。するとこうした運用は、どの会社でも似たような構造になるのでテクノロジベンダーが登場し共通サービス（蓄積・管理・照会などの機能を提供）を提供する流れになりそうです。その代表格がトレジャーデータ社ではないでしょうか。

さて、上記課題は第二の対処方法も挙げられます。それは、Web2.0がブームとなった時代にさんざん研究された「メタ情報」を扱うという手段です。例えば、上記の例でしたら生ログに関して「xxというキャンペーンの、告知サイトでの、yyからxxまでにおける、Apache Log形式で書かれたWebアクセスログファイルを、zip圧縮したもの」というメタ情報を考慮することが出来るでしょう。分析プログラムや結果情報についても同様です。そのメタ情報を系統的に管理しておけば、データ分析をはじめとするさまざまなデータ利活用において利便性を飛躍的に高められると思います。

ここでメタ情報に含まれる「告知サイト」「Apache」といった知識情報は共通に利用できるため、知識表現のテクノロジをうまく使うことでシステムをどんどん賢くしていけそうです。そして知識表現のテクノロジは、ブームを終えた感のあるWeb2.0の時代にさんざん研究されて技術資産がパブリックに蓄積されています。

そう思って私はそんなメタ情報管理のWeb2.0標準技術について調べていたのですが、今ビッグデータ関連のコンテキストであまり語られない面白い視点があることに気づきました。それは何かというと（標準仕様書において直接述べられていない私の造語的な概念ですが）「名前」と「実体」の分離です。もう少し突っ込んで英語でいえば「mentionability（言及可能性）」と「accessibility（アクセス可能性）」の分離です。

簡単に言うと、「そういうデータが『ある』という知識」と「それを入手するための知識」は別々に管理したほうが色々と嬉しいことがある、ということです。たとえば、発生したデータや分析プログラムや分析結果に「名前」をつけることによって、まずそういうものの存在を意識することが出来ます。hadoopに入れるまでもない小さなデータや、かき捨てのスクリプトプログラムだとしても、何らかの社内リソースを投入して得られた成果物なので、「どっかのメールにそういうものが埋もれてるっていうことくらいは覚えといてもいいのではないか」みたいな落としどころがデータの管理コスト的にちょうどバランスのとれた話になってくると思うわけです。

なので「そりゃあきっちりと蓄積保管したほうがいいけどさ、面倒くさいしコスト的に見合わないからビッグデータだけは何とかしようよ」みたいな話で終始してるんじゃないかと思います。名前の管理と実体の管理を分離するビジネス的なメリットは、前者は後者よりもはるかに低コストで出来ることです。Web2.0関連仕様書には全然そんなこと書いてないけど、僕はそう感じます。

そういう意味でWeb2.0の技術はよく考えられていると思います。そういう面白いことは他にもあります。例えばXMLはWeb2.0技術の根幹ですが、XMLとJSONの大きな違いは何かといえば、XMLには「名前空間」があるということです。例えば次のメタ情報を見てください。

<rdf:RDF
  xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
  xmlns:dc="http://purl.org/dc/elements/1.1/"
  xml:lang="ja">
 <rdf:Description rdf:about="http://www.kanzaki.com/docs/sw/">
  <dc:creator>神崎正英</dc:creator>
  <dc:date>2001-09-04</dc:date>
 </rdf:Description>
</rdf:RDF>

(出典元：Dublin Core: メタデータを記述するボキャブラリ)

これはWebページ（ページじゃなくてもURIが付与できるものなら何でもいい。O2O的なURI、例えば「どこどこのイタリアンレストランの水曜日の日替わりランチ」みたいなものでもOK.）に意味を付与するRDFという仕様で使われる語彙を定義するDublin Coreという仕様ですが、XML全体はrdfという名前空間が付与されていますがそこで叙述されている名前や日付にはdcという名前空間のものが適用されています。つまり「ボキャブラリ」と「メタ情報」は別々の名前空間に属するというわけです。このあたりのセマンティクスの強さがWeb2.0関連仕様の特長だと思います。残念ながら流行ってないのはこれを使ったアプリケーションがあまりないからだと思われますが、上で検討したことに照らせば、こうした技術はうまく最新のビジネスに応用可能ではないかと思います。

データのメタ情報を管理することで出来ることはいっぱいあります。例えば、機械学習の世界では「Bag Of Words」というデータ表現方法がありますが、もしそのデータがBag Of Wordsだということをシステムが把握できていれば、機械学習タスクをシステムが暗黙裡に実行し、何らかの経営面への影響が見えた時だけユーザにアラートするという機能が実現できます。そしてそういった暗黙裡に行われるタスクについてもメタ情報を付与することによって、マーケティング担当者ドリブンで分析作業を行う場合にも似た分析が既に実行済みかどうかを簡単にバックトレース出来るようになります。新しい機械学習手法をシステムにアドインしたときも、即時に活用出来る状態まで持っていけそうです。

そうした諸々のことを、考えたので書いてみた次第です。

HaskellとClojureとF#で書き比べ

最近ClojureとF#が気になってしょうがないので、最近楽しませてもらってるPython練習コミュニティサイトCheckiOに掲載されている問題の一つ、words_finder をHaskellとClojureとF#で書き比べてみた。同じ問題の同じアルゴリズムでの解答をそれぞれの言語で解く事でコーディング感覚の違いを知ろうという趣旨。

まずはPythonでの解答 (ネタバレ注意：CheckiOは本来は自分が解答しないと他人の解答は見られない)

def checkio(text, words):
    span=[]
    for w in words.split():
        for i in range(len(text)):
            if text[i:i+len(w)].lower()==w.lower():
                span.append((i,len(w)))
    def check(i):
        return set(a for a,b in span if i>=a and i<a+b)
    ans=''
    for i in range(len(text)):
        c1,c2,c3=[check(j) for j in range(i-1,i+2)]
        if len(c2)>0 and len(c1&c2)==0: ans+='<span>'
        ans+=text[i]
        if len(c2)>0 and len(c2&c3)==0: ans+='</span>'
    return ans

Pythonはデフォルト言語という位置づけがしっくり来るくらい普通のコードが書ける。

  • Haskell
    • (個人的にHaskellは趣味でよく触っているので少し慣れている)
    • Listモナドと内包表現がやはり強力
  • Clojure
    • Javaライブラリとの接続はかなりスムーズに書けてよい
    • Clojureはリテラルが強力なのが便利だと思った
    • 括弧が増えてもインデントの位置で分かるので大丈夫そう
    • マクロのおかげでいろいろとすっきりする
    • Haskellより長くなる気がする（慣れてないせい？）
  • F#
    • .NETライブラリとの接続はClojureより複雑な感じがした
    • letが多くなりがちだが、パイプライン演算子でしのぐ感じ
    • リテラル記法が手薄く標準ライブラリで明示的に書く感じ
    • printfの"%A"が便利
    • Clojure, Haskellより長くなる気がする（慣れてないせい？）

CheckiOの問題は練習問題として良いので関数型言語で解く練習をつづけるつもり。(GitHubレポジトリ作った.)

早熟と大器晩成について

トラックバック＆感想

こういう話を読んで思うのは、プロ将棋の世界のことだ。トップ棋士の羽生さんは14歳でプロになり、以後ずっとトップを維持している。

仮にその羽生さんが

「一生は子供の頃からの才能で決まる。10代で既に才能がみえていなければ超一流になるのは難しい」

と言ったとする。そしてたぶん、それは事実だと思われる。

上記エントリのKAIZEN Platform須藤社長が書かれている事も、それと似たような話だと思う。そしてそれは事実そうだと思う。

しかし最大限のエネルギーを注げるかどうかは、その人に合った事をやっているかどうかだと思う。努力が続かないというのは、自分に合ってない事をやっているからであって、羽生さんや須藤さんのような成功者は合った事をやったひとなのだ。仮に須藤さんがプロ棋士を目指して奨励会にはいったとして、プロになれるだろうか。羽生さんがリクルートに入って20代で役員まで上り詰められるだろうか。

一流の人でさえ、自分に合わない事をやったら成果をだしにくくなってしまうことは想像に難くない。取り組むべき事が合ってないときに、それを気合いと根性のような資質でカバーしようとしても、それが好きで好きでたまらないという人には到底勝てない。

だから、須藤さんのいうことは正しいのだけれども、一般論としては役にはたたないと思われる。まぁ、須藤さんは勝利宣言をしているだけなんだろうけど。

一般論として役に立つ考え方というのは、世の中の人の「平均レベル」にとって役に立つ考え方である必要がある。それは、

  • 自分に合う事を見つけるまでは、うまくいかなくても自分を責めない
  • 自分に合いそうなことを見つけられるよう、いろいろと行動をおこす
  • それでも自分に合う事が一生見つからないかもしれないと覚悟しておく

ということではないだろうか。

自分に合う事が見つかったら、須藤さんの考え方を参考にして取り組んでいけばいいのだと思う。

プログラミング言語の使いわけ

私は色んなプログラミング言語を触るのが病的*1に好きで、どの言語をどういう場面で使うのが良いのか凄く興味があります。

そこで、今の私の知識範囲でのそれぞれのプログラミング言語の使いどころを（自分用の整理もかねて）書いてみます。

C/C++ - C＝OSやミドルウェア、C++＝効率化のための再実装

安直に「メモリとスピードが第一優先のとき」と思いたいところですが、同等程度のスピードでもっといい言語はいっぱいあります。計算集約的ならJuliaとか、オブジェクト指向で組むようなソフトならD言語とか。なのでまずC言語は、Swigみたいのを使って他の言語の拡張ライブラリを書いたり、システムコールを使ってOSやミドルウェアを書くときじゃないかと思います。C++はテンプレートを駆使したりして効率を維持しながら抽象度の高いコーディングをするような場面がしっくり来ると思います。既に他の言語で実装したソフトウェアのパフォーマンスを改善するためにC++で書き直すときとかがピッタリだと思います。

D - 仕様変更に強いC/C++

D言語はテンプレートのようなC++的な効率維持を持たせつつmixinなどのオブジェクト指向実践テクの面を合わせた言語だと思います。Dを使うのはメモリに読み込んで色々複雑な事をやるような普通だったらC/C++を使う場面で、コードの見通しを保ちながら抽象度を上げたいときじゃないでしょうか。つまり、Cで書いちゃうと要件が変わったときに書き直しが大変なのでもう少し変更が楽な言語が欲しいときにピッタリなんじゃないでしょうか。

Objective-C - Appleプラットフォーム

iOSやMAC用のアプリを作るときですね。他でそれがピッタリとなるような用途は無いと思います。

Perl - シェルの機能強化

PerlはWebアプリからバッチ処理まで何でも使えますが、言語の種類が豊富になった現在ではPerlを使う事が最もしっくり来る場面というのは少なくなっているかもしれません。シェルからコマンドとして使うようなソフト、リダイレクトやパイプを扱うような処理が一番の使いどころな気がします。Perlはもともとの出自がshやC言語やsed/awkなどの発展形なので、その部分では後発のスクリプト言語より優っているように思います。Perlでオブジェクト指向はちょっとハッキング的すぎるかなと。

Ruby - ドメイン特化処理

RubyはなんといってもRailsでしょう。Webアプリケーションを最も速く作れるフレームワークがRailsだと思います。「テキスト処理がメインでドメイン知識をいろいろと仕込んでいくようなアプリ」がぴったりだと思います。PythonはRubyとくらべると関数型の色が少しあるように思いますが、Rubyは純粋にオブジェクト指向を追求しているので、処理の一般化がしにくく差分を積み重ねながら組んでいくようなドメイン特化型のアプリにより適していると思います。

Python - データの加工

Pythonはいま最も「汎用性」が高い言語じゃ無いかと思います。特に理由がなければデフォルトでPythonというのはアリだと思います。その中で、Pythonを使うのが最もしっくりくるのは「データの加工、データ分析における前処理・後処理」じゃないかと思います。テキストや画像、音声、それらの入出力、ネットワーク通信といった機能がそろっています。それとデータ分析本体のアルゴリズムもScipyなどの便利なライブラリがありますが、それはたぶんもともとPythonが前処理と後処理に秀でていたからそういう分析本体の機能がどんどん追加されていったのであって、元々の強みは「加工」なんじゃないかと思います。

PHP - コモディティなWebアプリ

実は使った事が無いので分からないのですが、Webアプリケーションの開発でコモディティなカスタム開発にはぴったりなんじゃないでしょうか。

Javascript - リアルタイムWeb

JavascriptはHTML5を使ったリッチなクライアントアプリケーションはもちろんですが、強力なV8エンジンとNode.jsの登場のおかげで効率的なサーバサイドの処理にも使えます。そうした特長を一言で言えば「リアルタイムWeb」でしょう。DBアクセスがメインのアプリケーションはRailsやDjangoを使えばjavascriptの部分はそれほど書かなくてもすむ事が多いですが、HTML5やajax、さらにC10K問題への対処を要する大量同時アクセスが生じるリアルタイムWebアプリケーションにおいてはJavascriptはピッタリです。また、バッチ処理的に使う場面でも、Webをクローリングしたり各種APIをマッシュアップしてデータを統合するなど、時間経過に伴ってデータの更新ももとめられるような準リアルタイム的な要件にも他の言語より優位性を発揮すると思います。

R - データマイニング

最近はやりのR言語。統計分析やデータマイニングにピッタリです。Python や他のツールを使う場合と比べてワンストップで前処理・分析・可視化が出来るので前処理がなんとか終わってCSVやリレーショナルDBまでデータ準備が出来たあとは強いです。

Julia - アルゴリズム実験

最近出たばっかりの言語ですが、FORTRANやMatlabのように科学技術計算のアルゴリズムをゼロから実装して効率よく計算させたい場面で力を発揮しそうです。ただ、大抵のアルゴリズムは様々な言語でライブラリが存在するため、Juliaを積極的に使う場面はとくにアルゴリズムの評価をしたいときじゃないでしょうか。ただ、アルゴリズムの研究をする人たちは今はまだC++やPythonやJavaやMatlabを使う事が多いので、Juliaがその立場に立てるのはもう少し先でしょう。

Java - トランザクションの保証

Javaは業務システムでよく使われています。技術者の数も多いですが、たぶんそれはWebでPHPプログラマが多いのと同じで業務システム開発の市場規模が大きいからなだけでしょう。言語自体の汎用性の高さ故にエンジニアが多いわけではないと思います。Javaが得意とするのは「トランザクションをきっちりやる」ようなアプリケーションじゃないでしょうか。企業における業務では「後戻り」がなく「約束」がやぶられないことがとても重要です。そういう意味でシステムが落ちずに稼働しつづけることはとても重要です。Javaのアプリケーションサーバを使えば一部のアプリケーションにバグがあっても全体としてはちゃんと動き続け、アトミックなトランザクションを再実行することで処理を継続できます。ScalaやGroobyやClojureを使う場合と比べて技術者の数が多いので業務システムのカスタム開発にはピッタリでしょう。

Scala - 高密度なビジネスロジック

ScalaはJVM系言語なのでトランザクション処理には強いです。JavaでなくScalaを使う理由はコードの抽象度を高めて複雑な処理を簡潔に書けるようにするためでしょう。スクリプト言語よりも実行効率が求められるハイトランザクションなシステムで特にビジネスロジックが高密度な時にしっくりくるんじゃないでしょうか。またそうしたビジネスロジックを外部からプラガブルにしたりドメイン特化言語（外部DSL）を構築したりする際もしっくり来そうです。

Groovy - 内部DSLフレームワーク

GroovyはRuby的なコンセプトをJVMの枠組みで最適に実装した言語です。積極的にメタプロを使う事が想定されていて内部DSLを作るのに向いていると思います。一番有名なDSLはパッケージ管理＆ビルド統合システムのGradleです。Groovyのメタプロを少し覚えればGradleのようなドメイン特化言語を要件に合わせて作る事が出来ると思います。関係者さえ把握出来ていれば良いような処理で、定型タスクとドメイン依存タスクがごちゃごちゃとたくさんあるようなケースに向いていると思います。

Clojure - コードの自動生成

LISPから生まれたJVM言語であるClojureは、もちろん汎用的な言語ですが強みは「コード生成」ではないかと思います。プログラムコードの生成はもちろん、HTMLや数式や音符などのマークアップコードをプログラム的に作るときに向いていると思います。例えば他の言語では通常、HTMLテンプレートエンジンとHTMLスクレイピングライブラリは別物ですが、ClojureではEnliveというライブラリで統合的に両方できます。そのくらい高い抽象度でデータを扱えるので、データ自体が何らかの「動くもの」を表現するような場合でも対応しやすいと思います。HTMLであればDOMツリーをClojure内部に持てば良いし、数式であれば数式相当のデータモデルを、音符ならトラックと音源情報などのモデルを、それぞれ内部に構成してそれらをいじくってコードに戻せばいいわけです。

C# - プロプライエタリシステム

C#を使う場面はJavaやScalaと近いと思いますが、.NET Frameworkはより完結度が高いと思います。つまり、オープンソースのライブラリなどを使わずとも元から用意されているものを使えばことたりるくらい部品がそろってます。またVisualStudioがものすごい良く出来ているので開発もそれをメインに使えばかなりの事が出来ます。もちろんCIやレポジトリ・イシュー管理は別のものを組み合わせて使う事も多いと思いますが、開発プロセスの多様性を減らす事が出来ます。なので、プロプライエタリなシステムを作る際にはものすごい大きな力を発揮するでしょう。

F# - 高度に自動化したエクセル

F#は.NET Framework上で動くだけあってMS Officeとの親和性は良いです。特にビジネスにおいてデファクトなエクセルは色んな分野で使われており、エクセルを触れる人の数は多いです。そのエクセルユーザのためにエクセル単体では実現しにくいような計算処理をするようなアプリケーションを提供する場合にF＃はピッタリでしょう。

Haskell - 処理を動的に組み合わせる

Haskellは純粋関数型という特徴はおなじみですが、ではどんな用途において他の言語より優位性があるのでしょうか。たぶん、Haskellが最もしっくりくるのは、コードを書く前に設計することが難しいような問題、コードを書きながら機能要件を考えるのが適するような問題じゃないかと思います。例えば、ファイナンスの投資戦略とか、医療診断の支援システムとか、そういう「新しい知識」がどんどん追加されるようなドメインで力を発揮すると思います。JavaでもDependency Injectionという方法があってシステム運用時にロジックをあれこれ切り替える事が出来ますが、Haskellの場合はそもそも関数合成を重ねて書いたものを遅延評価して動くので、いわば全ての処理依存を実行時にインジェクションして動くということと普通にやっているようなものです。Clojureはコード生成が得意と上で書きましたが、それに対してHaskellはあらかじめ用意した処理の組み合わせを動的に変えることが得意です。

Erlang - クラスタリングミドルウェア

Erlangはアクターモデルを超軽量プロセス（メモリ非共有なのでプロセスといってるだけでスレッドみたいなもの）という実装で使えるようにした言語です。他の言語に対する優位は何でしょう？ まずはその軽量プロセスでしょうが、他の言語でもコルーチン形式でリアクティブ処理を書けば同じ事は出来ます。なのでErlangの強みは言語仕様よりもエリクソンで作られた処理系にあるんじゃないかと思います。JVMと比べて同時接続過多な状況でも動作し、コルーチンをサポートするスクリプト言語よりも少ないメモリで動作するので、OSやミドルウェアレベルでの高密度な通信アプリケーションに向くのでしょう。ファイルサーバやメッセージキューといった計算クラスタ内部での（計算本体以外の）システム処理にマッチすると思います。

Prolog - ルールベースの情報処理

Prologはエキスパートシステムとして使われます。最近だとProlog由来の制約プログラミングというパラダイムがILogという製品で普及してIBMがそのILogを買収しました。Prologが得意とするのは「ルールの処理」です。ルール集に事例をぶっ込むとルール違反かどうかチェックして違反なら理由を教えてくれたり、何らかの専門的な診断ルールであれば診断結果と診断プロセスを出力したりできます。またILogのような制約論理プログラミングを使うとルールのもとでの最適解を計算することが出来ます。

*1:何か作り始めると「別の言語ならもっと簡単なコードになるんじゃないだろうか。。」という不安がよぎって開発がストップして別の言語で同じ処理を書いてみて「やっぱり一長一短だな」と思って戻る、みたいなことがしょっちゅうあります。

SRM612

R1288でDivision1に参戦。最近CheckiOやコンサルの仕事などでPythonをよく使っているのでPythonで参戦。

JavaだとKawigiEditというプラグインが便利なんだけどPythonはGreedというのが便利そうなのでそれを入れて開始前に2問くらい解いてた。

Easy

顔文字1個から出発して「1文字削除」、「クリップボードへコピー」、「ペースト」の組み合わせだけでちょうどN個にするのに必要な操作の最小回数を求める問題。N<=1000が条件として与えられている。まずは問題分析としてDP的な方法を考えたが「1文字削除」のことを考慮すると「文字数が1000を超えるような中間状態」を考慮しないといけなくて面倒だなと。たぶん倍の2000ちょっとくらいでDPすれば大丈夫なんだろうけどもっとシンプルに出来ないだろうか考えてたら、操作回数でイテレーションしてダイクストラ法みたいにやればいいのだとひらめく。それならシンプルだ。ということで以下のようなコードを書いてテスト通ってサブミット。

    def printSmiles(self, smiles):
        tbl,Q={(1,0):0},[(1,0)]
        while Q!=[]:
            now,clip=t=Q.pop(0)
            if now==smiles:
                return tbl[t]
            ts=[
                (now,now), # copy
                (now+clip,clip), # paste
                (now-1,clip), # delete --- (*)
            ]
            for t1 in ts:
                if t1 not in tbl:
                    tbl[t1]=tbl[t]+1
                    Q.append(t1)

で、サブミット後に次の問題を読んでる途中に上のコードの一文字削除(*)のところで「顔文字の個数Nがマイナスの状態」を作り出してしまう事に気づく。やばい。TopcoderSRMは2回目のサブミットはペナルティが課されるので、なんとか上記のコードでNがマイナスの状態が途中にあっても操作回数の最小解には影響しないことを頭の中で証明しようと試みる。しかしちょっと難しそうなので、上記のコードをコピペしてちゃんとマイナスの状態を除外するやつを書いて、サブミットしちゃったやつと2<=N<=1000の範囲で出力が一致するかを確かめる。僕の最新のMacBookProでも1分以上掛かってドキドキ。出た！あってる！問題ない！
ということで次の問題へ。

Medium

50x50の座標空間上の点をN個選び、x座標、y座標に分離してx座標だけソート、y座標だけソート、という風にして渡されたときに元のN個の座標をどれだけ正しく推定出来るか、確実に推定可能な個数Tを求めなさい、という問題。
問題の意味はすぐ分かった。しかしEasyで手間取ったのでこの時点で残り40分くらい。図に置き換えて考えてみる。この場合座標の具体的な値は関係なく、個数が問題なので縦棒N個と横棒N個を個数ごとにまとめて交差させた図を描きながら考えていた。どうにかうまいほうほうはないものか。
しかしさんざん色々検討したけど「あり得ない複雑度のメモ化＋全数探索」という方法くらいしか思いつかず、それでも時間オーバーしそうで書く気がしないままタイムアップ。

Hard

開いてない

結果＆感想

Easyは通った。MediumはEgor神のコードを見てみたら思いっきりグラフのフロー最小化問題に置き換えてコピペプログラミングしててガクブルだった。割と多くのレッドコーダーがグラフ理論に置き換えてやっていた。

今回は問題の分析に掛ける姿勢は良かったと思うが、分析するときに「知ってる基礎アルゴリズム」の量が一定数無いといくら考えても答えは出てこないという事態になりがちだと思った。「ひらめきは知識の組み合わせ」なので、もとの材料がやっぱりある程度必要だなと。メジャーどころのグラフアルゴリズムは一通り覚えて、具体的な問題への応用を学ばないと。

あと、最近CheckiOをやって思ったのは、TopcoderSRMだけが「高度で面白いコーディング」じゃないということ。例えば、近似アルゴリズム（Topcoderはマラソンマッチとかもあるけど）や機械学習やベイズ推定などのアルゴリズムとかいった数理的な素養がコアになるような分野とか、コード生成やLISPマクロのような分野とか、他にもいろいろな分野があるので、テーマを決めてそういうのも体で覚えるようにしていきたいなって最近思う。

R1288 -> R1372 自己ベスト更新。イエローコーダーまであと128点。3月中あと2回順調なら目標達成できるかも。頑張ろう。
http://community.topcoder.com/tc?module=MemberProfile&cr=23173042