きままにものづくり

日々の気付いたことなんかを書いてます。

2013-08-01から1ヶ月間の記事一覧

SRM574

結果:0pt 問題を勘違いしていた。 TheNumberGame AにBとBのひっくり返したのが存在すれば、Manaoの勝ちになる。 この解法はすぐに思いついたが275ptであることに、注目してしまい余計な制限をかけてしまった。 両方のプレイヤーが数字を操作した後に、同じか…

SRM575

結果:0pt 歯が立たなかった。 TheNumberGameDivOne 漸化式を見つける問題だった。 こういう問題は、自分で例題を作り法則を見つけだすべきだった。解説では、省略されている証明を簡単にする。 Brusが勝利する条件は、 nが奇数 nが2の奇数乗() である。nが奇…

SRM576

結果:0pt (131.8) システムテストで落としてしまった。 ArcadeManao Div2のMediumと同じ問題。二分探索を用いた。 要素数が少ないので、線形探索で十分だった。答えが0の時を考慮しなかったため、システムテストで落ちてしまった。

Bug900285

https://bugzilla.mozilla.org/show_bug.cgi?id=900285 目次 説明 模索途中 解決法 説明 毎回インスタンスごとにsetFramePushedを呼び出して初期化しているのを、MacroAssemblerのコンストラクタを作成することで、まとめる。 模索途中 MacroAssembler(js/sr…

SRM577Div1

結果: 0pt またもや、0ptだった。 Easy問題で文字列同士が分割されているということに、気づくのに時間がかかった。しっかりと、書いてあるにも関わらず。 EllysRoomAssignmentsDiv1 初め期待値(expected)を見落としてしまい、全ての可能性の平均値と勘違い…

蟻本練習問題

蟻本に載っている練習問題を解いていきます。 初級編 2-1 深さ優先探索 POJ1979 POJ3009 AOJ 0118 AOJ 0033 幅優先探索 AOJ0558 POJ3669 AOJ0121 全列挙 POJ2718 POJ3187 POJ3050 AOJ0525 2-2 区間 POJ2376 POJ1328 POJ3190 その他 POJ2393 POJ1017 POJ3040 …

SRM578Div1

結果:0 pt Easyのモジュラ逆数の計算でバグを埋め込んでしまった。 バグ取りをしていたら、時間がなくなってしまった。 GooseInZooDivOne はじめ、モジュラ逆数を求めるのに拡張ユークリッドの互除法を用いた。 これ自体にはバグを埋め込まなかったが、時間…

SRM579Div1

結果:137.17 pt実装にかかる時間が多すぎた。 UndoHistory この問題は理解できたけど、実装に時間がかかりすぎた。しかし、実装が複雑になりそうな問題はしっかり考えてから実装しないと泥沼にはまるので、急ぐのも禁物。こればかりは、ひたすらコーディング…

TopCoder

Topcoderの問題を解いていきます。 解いたコードはgithubで公開しています。659 E M H 658 E M H 657 E M H 656 E M H 655 E M H 654 E M H 653 E M H 652 E M H 651 E M H 650 E M H 649 E M H 648 E M H 647 E M H 646 E M H 645 E M H 644 E M H 643 E M …

SRM580Div1

SRM

結果: 0 pt Easyでつまづいてしまい全然解けなかった。 習得したアルゴリズムに当てはめようとして、失敗した感じ。 アルゴリズムを身につけるのはとても大切だけど、中途半端な理解だと柔軟に思考できなくなってしまう。 EelAndRabbit セグメントツリー、bi…

IonMonkey spew

IonMonkey spewは、IonMonkeyの処理をトレースするツール。 使い方 IonMonkey spewはもともとIonMokeyに実装されているので、何かインストールしたりする必要はない。 まずは、デバッグモードを有効にしてmakeする。 cd DIR/mozilla-central/js/src ./config…

Bug852791

https://bugzilla.mozilla.org/show_bug.cgi?id=852791 目次 説明 解決法 説明 文字列どうしのconcatの時に、無駄なアセンブラが実行されている。 例えば、以下のようなコードは同じアセンブラが実行されるはずである。 var x = "hoge" var s = "f" + "oo" +…

SpiderMonkey

目次 説明 ツール バグフィックス 説明 ツール IonMonkey spew IonMonkey spewは、最適化の経路を出力するツール。どのような最適化が施されているのかを確認するのに便利。 バグフィックス Bug852791 Bug900285 Bug909997

Segment Tree(未完)

目次 説明 注意点 コード 説明 注意点 要素数は2のべき乗ごとになっている。 入力の最大が50だとする。MAX_Nを50とすると定義域外を参照してしまう。入力の大きさが50の時のnは64となる。この状態でupdate(50,0)を呼び出すと、kの値は113となってしまう。な…

最大フロー最小カット定理

最大フロー最小カット定理は、最大フロー問題に関する定理である。 この定理は、「最大フローと最小カットの容量は等しい」ということを示す。 目次 関連 証明 関連 この定理は、フォード-ファルカーソンが最大フロー問題に対して正しい答えを導くことを証明…

メンガーの定理

数論-証明-

グラフ理論-証明-

最大フロー問題 最大フロー最小カット定理 メンガーの定理

データ構造

データ構造に関しての説明をする。 Union Find Tree Binary Index Tree Segment Tree(未完)

グラフ理論-アルゴリズム-

グラフ理論に関するアルゴリズムを紹介する。 最短経路問題 ベルマン-フォード ダイクストラ ワーシャル-フロイド 最大フロー問題 フォード-ファルカーソン

数論-アルゴリズム-

主に初頭整数論におけるアルゴリズムを説明する。 テクニック MOD乗算 MOD指数演算 理論 ユークリッドの互除法 拡張ユークリッドの互除法 ポラード・ロー素因数分解 モジュラ逆数 中国余剰定理 素数判定 エラトステネスのふるい フェルマーテスト ミラーラビ…

フォード-ファルカーソン

フォード-ファルカーソン法は、最小フロー問題を解くアルゴリズムのひとつである。 目次 アルゴリズムの説明 計算量 コード アルゴリズムの説明 このアルゴリズムを説明する前に、残余ネットワークの説明をする。残余ネットワークとは、現状での流すことがで…