問題 http://code.google.com/codejam/contest/dashboard?c=433101#s=p2 それぞれ、g_0, ..., g_{n - 1} 人から成る n 個のグループが遊園地のジェットコースターに乗る。 ジェットコースターには k 人同時に乗れる。 ジェットコースターは1日に r 回走る。 …

pythonで、関数型プログラミングする時に便利なツール群。 itertools 色々なイテレータを簡単に作る。 functools 関数の引数の一部分を埋めて新しい関数を作るpartialなど operator 四則演算等のオペレータの関数版。map, reduceとかの引数に渡せる。 超簡単…

問題 http://www.topcoder.com/stat?c=problem_statement&pm=11284&rd=14430 (要ログイン) 何か、変なゲームの得点を最大にしろ。 持ち点0点からスタート 動作 A, B をそれぞれ nA, nB行う。 動作 A をすると、持ち点 += paramA / 1000 動作 B をすると、持…

問題 http://www.topcoder.com/stat?c=problem_statement&pm=11283&rd=14430 (要ログイン) 整数配列が与えられる。 それに一つ付け足して、等差数列 or 等比数列にしたい。 付け加える事のできる数字は何種類か 方針 素直に調べる。

問題 ブログの投稿は、基本的に simple-hatena-mode を利用させてもらっている。このモードでは、行頭で * を入力すると、自動的にタイムスタンプを挿入してくれる。これは便利なんだけど、小見出しを使いたい時には不便(はてな記法では、行頭で**とアスタリ…

topcoder等のプログラミングコンテスト用の練習をしていると、数独のようなパズルは、それ自体がパズルなのでは無くて、それを解くプログラムを書くというパズルに思えてくる。という訳で、書いてみた。何も考えてない、単なる深さ優先探索。

問題と概要 http://www.topcoder.com/stat?c=problem_statement&pm=11341(note : topcoderのサイトにログインしてないと、見れないようです。) いくつかの数字が書かれたカードがあって、そこからカードを任意の順番で引き抜く。あるカードを抜く時、そのカ…

問題 http://www.topcoder.com/stat?c=problem_statement&pm=11331 方針 最大の得点を達成するカードの組み合わせの中には、与えられたカードの中で最大の得点を持つカードと、そのカードの文字列を逆にした文字列を持つカードの中で最大の得点を持つカード…

問題 http://www.topcoder.com/stat?c=problem_statement&pm=11327 方針 同じ色の兎は同じ答えを返す。 ある兎の答えが n の時、その色の兎は丁度 n + 1 匹町の中にいる。 という条件に気を付けて数える。 答案

srm 499 は、参加登録を逃してしまって、参加出来なかった。。。 問題 http://www.topcoder.com/stat?c=problem_statement&pm=10763 方針 全探索 答案

細かいことは知らないけど、Rでは、とにかくforは使うべからず、apply系関数を使え、と叩きこまれている(誰に?)。分かった、分かったけど、じゃぁこんな時どうすんのよ?と、ずっと悩んでた。 temp for (i in 1:10) { x[i] z[i] temp } http://www.mathfinanc…

プログラミングコンテストチャレンジブック作者: 秋葉拓哉,岩田陽一,北川宜稔出版社/メーカー: 毎日コミュニケーションズ発売日: 2010/09/11メディア: 単行本（ソフトカバー）購入: 52人 クリック: 1,538回この商品を含むブログ (83件) を見るで、セグメント…

本番では、解き方が分からんかったんだけど、やっと分かったのでメモ。 このパズルでは、以下のように具体的な手順で、任意の状態から任意の状態に遷移出来ることを証明する。http://www.topcoder.com/stat?c=problem_statement&pm=11225&rd=14427にある図で…

背景 1年前の自分が、こんなデータを作っていた。 データ全体は、recordのリスト recordは、そのrecordが作成された時刻とdataを納めたリスト dataは、entryのリスト entryは、TYPE_A, TYPE_B, TYPE_Cの3つの数値ベクトルを納めたリスト。但し、長さ0かもし…

motivation ある関数の中で、データフレームをいじくり回したかった。が、いちいち [ 演算子とか $ 演算子とかでアクセスすると、コードが見辛くなってやだ、と思った。例えば、 plot(dat$x[dat$label=="a"], dat$y[dat$label=="a"]) みたいなコードは書きた…

evalは式を評価する関数 >> (setq x 1) 1 >> (eval x) 1 >> (eval 'x) 1 >> (eval ''x) x 初めてlispを触った時は、この挙動が理解出来なかった。が、式の評価ルールを段階的に当てはめると分かる、多分。まず、 式には 自己評価型式(自分自身に評価される) …

「lambda」は特別なシンボル。 シンボル lambda が先頭にあるリストは、関数定義と見なされる。 そして、そのようなリストは評価されるとそれ自身になる。 ただし、関数定義として妥当な形式を持ってないと適用される時にエラーになる >> ((lambda (x y) (+ …

M-x ielm で対話型のelispインタープリタ起動

setqはグローバル環境(っていうのかな)のシンボルに値を代入。letはローカル環境のシンボルに値を代入。 (list (setq z 1) (let 'w 1)) (1 1) (eval z) 1 (eval w) ; error

lispには、「シンボル型」があるということを理解する必要があるみたいだ。 >> (setq val 1) 1 >> (setq x 'val) val >> (setq y 'val) val >> (+ x y) ; + の引数にシンボル型が来ているのでエラー ; error >> (+ (eval x) (eval y)) ; eval してやると数値…

pythonは、「静的スコープ」らしい。ざっくりと覚えておくべきこと。 変数は、 関数のローカル環境 定義時(実行時では無いというのがポイント)の環境 グローバル環境、の順番に探される。 さらに、グローバル環境は、ファイル毎に独立している。 テストをし…

emacsのpythonモードでは、C-c C-c で現在のバッファを全部インタープリタに送ってくれるんだけど、ここで起動されたインタープリタのパスが変で、カレントディレクトリにあるモジュールがインポート出来なかった。 pythonでは、インポートするモジュールの…

選択出来るパッケージ SemiPar mgcv gam gam, SemiPar, mgcvの順で昔からある。

端っこから順番に条件を満たすか調べていく。 本番ではシステムテストで落ちた。 seq2の最初の要素が正であるかのチェックを忘れていた。 #include <sstream> #include <string> #include <vector> #include <map> #include <algorithm> #include <iostream> #include <utility> #include <set> #include <cctype> #include <queue> #include <stack> </stack></queue></cctype></set></utility></iostream></algorithm></map></vector></string></sstream>…

topcoder初参戦。 以下の繰り返し。 一番大きい数字を選んでポイントに加算。 選んだ数字を非負の範囲で1減らす。 #include <sstream> #include <string> #include <vector> #include <map> #include <algorithm> #include <iostream> #include <utility> #include <set> #include <cctype> #include <queue> #include <stack> #include <cstdio> #include <cstdlib> #i</cstdlib></cstdio></stack></queue></cctype></set></utility></iostream></algorithm></map></vector></string></sstream>…

幅優先探索で、行ける所全部に最小到達歩数を記録。 到達不可能地点があるかチェック。あるなら、return -1。無い場合、最大の最小到達歩数を返す。 障害物で行けない地点は、走査時に除いて考える。 #include <sstream> #include <string> #include <vector> #include <map> #include <algorithm> #in</algorithm></map></vector></string></sstream>…

結構考えて、時間ぎりぎりで解答が分かった。 列の中で同じ色が続いている部分を「連」と呼ぶことにする。色が4色あるので、連の両サイドがどんな色だったかを気にせずに必ず「(連の長さ) / 2」ステップで連の内部及び連の両端で同じ色が連続しないように出…

基本的には、全ジョブの所要時間合計が少ないユーザのジョブから実行すれば良い。 但し、辞書式順で最小のものを返すために、次のようなソート処理を行った。 各ジョブ番号iに対して [user[i]の全ジョブの所要時間合計, user[i]が最初に出てくるジョブ番号, …

2分探索 コメントで消しているのは、n買い目の支払い後の残高を明示的に書いた公式。これだと、テストケース0で駄目だった。 #include <sstream> #include <string> #include <vector> #include <map> #include <algorithm> #include <iostream> #include <utility> #include <set> #include <cctype> #include <queue> #include <stack> #include <cstdio> #i</cstdio></stack></queue></cctype></set></utility></iostream></algorithm></map></vector></string></sstream>…

第i月に入る収入は、第i月以降で最もリターンの高い投資機会(株とタイミングの組み合わせ)に全額投資するのが最も効率的 上の考察をそのままコードに落とすだけ。 maxGain=1で初期化しているので、ループの最初のretの更新ではretは変化しない。けど、こうし…