TopCoder

焼きなまし法のコツ Ver. 1.3

焼きなまし法そのものの解説は少しだけにして、焼きなまし法の使い方のコツをメインに書こうと思います。 焼きなまし法の概要 最適化(=最大値か最小値を求める)の手法の1つです。以下は擬似コードです。 あらかじめ、計算する時間を決める。 以下のスコー…

生放送「TopCoderでプログラムしてみた」コメントランキング

Competitive Programming (1) Advent Calendar 2018 - Adventar 12日目の記事です。 はじめに 競プロを最初に始めたのが、TopCoderに初参加した、2008年7月18日だそうです。10周年、めでたい!そして、生放送「TopCoderでプログラムしてみた」も、おそらくほ…

Marathon Match 100 のゴミメモ!

下書きで終わっていた記事が、残っていました。ゴミメモのままでしかないのですが、脱線に至るまでの経緯が、今見るとおもしろかったので、そのまま投稿。 50位以内だと、懐かしの旧TopCoder時代のTシャツがもらえるマッチでした。まだ現役なので、老兵ども…

TCO Announcement Fun Round - WaterfallFishingの反省

2017年5月の、ちょっと古いマラソンマッチですが、忘れないようにするために、書きました。 問題 https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16930&pm=14615川の幅 W (2≦W≦200) 川の長さ L (5≦L≦100) 川には、岩があ…

マラソンマッチの簡単な解法

まえがき この記事は、Competitive Programming Advent Calendar 2017 - Adventar 18日目の記事です。最近は、簡単にやるべきことでも、難しくやってしまうことが多く、それがマラソンマッチでの不振につながってるので、「簡単な解法」をネタに書きます。昔…

Topcoder Arenaを起動する方法とJavaブロックの回避

はじめに Topcoderで競技プログラミングをする場合、以下の2つの方法があります。 ウェブ版(ベータ)TopCoder Arena アプリ版 Competition Arena ウェブ版はずっとベータ版で開発終了停止している模様なので、懐かしのアプリ版を立ち上げたいところ(パス…

最小カットを使って「燃やす埋める」問題を解くスライドのフォロー

この記事は競技プログラマー向けです。 はじめに 以前、最小カットを使って「燃やす埋める」問題を解くというスライドを書きました。 最小カットを使って「燃やす埋める問題」を解く from shindannin www.slideshare.netこれに対して、tokoharuさんから、『…

TCO17 Marathon Round 1 (GraphDrawing) の反省

問題と1位の方(chokudaiさん)の解法 TCO2017R1 結果 力学モデル(バネ)で、長さ比に応じて力を加える。その後、貪欲法(一番悪い辺の点を、最も高得点になる場所へ移動)で解を改善。 45位/146位 652,515.28点。30位ぐらいの人ともかなりの点差が開いてい…

ビームスタックサーチについての勉強メモ

マラソンマッチ界隈でよく知られている通称chokudaiサーチ、それと似ていると言われてるビームスタックサーチ(beam-stack search)について、ちょっと調べてみました。論文はこちらです。 R Zhou, EA Hansen (2005) Beam-Stack Search: Integrating Backtrack…

累積和を使う動的計画法

この記事はCompetitve Programming Advent Calendar 2015の23日目の記事です。tanzakuさんに感謝 www.adventar.org 今回は、累積和を使う動的計画法についてです。TopCoderのDiv2上位ぐらいの人向けの難易度です。 問題 AtCoder Typical DP Conestの問題です…

ボツネタ集(だいたいランダムフォレスト)

どうでもよいまえがき 今回の記事を最後に、機械学習関係の記事は、しばらくお休みにします! 我流すぎて、機械学習の知識が不足していて、記事を書くのに妙に時間がかかる。 最近、機械学習マッチで結果を出してないので、その中で記事を書いても、自分の中…

ランダムフォレスト 特徴量の重要度(C++の実装例つき)

はじめに 今回の記事は、alfredplplさんの以下の記事とだいぶかぶっています…。図つきで、とても分かりやすい記事なので、お勧めです。こちらをはじめに読んだほうが良いと思います。Random Forestで計算できる特徴量の重要度 - なにメモ(なにかしらのメモ…

ランダムフォレストと他の機械学習(or統計)を組み合わせて使う

もしかしたら、プロにとっては当たり前のテクニックかもしれませんが、自分は初めて見たので書きたいと思います。また、おそらく大きい効果を出すのが難しいテクニックだと思われるので、まずは基本的なことを先にやったあとに試したほうがいいでしょう。追…

2015年 競技プログラミングの目標

評価 目標:2015年は100点以上 200~ 偉大すぎるので、誰かが奢ってくれるはず 150~199 PERFECT 120~149 GREAT 100~119 GOOD 60~99 進歩なし 30~59 怠惰・堕落(FUJIYAMAに乗る) 0~29 人としてダメ(FUJIYAMAに乗る) (なお、2014年は60点でした) 得点表 …

ランダムフォレストのつくりかた(C++の実装例つき)

この記事は24日目の記事のつづきです。前日の関連記事「ランダムフォレストのつかいかた」もありますので、こちらもよろしくお願いします。 ランダムフォレストのつかいかた - じじいのプログラミング ランダムフォレストは、機械学習の中でも、確率統計の知…

ランダムフォレストのつかいかた

この記事はCompetitive Programming Advent Calendar 2014 - PARTAKE24日目の記事です。関連記事に実装編もあります。 ランダムフォレストのつくりかた(C++の実装例つき) - じじいのプログラミング ランダムフォレストのつくりかた(C++の実装例つき) - …

マラソンマッチ Asteroid Tracker 惨敗反省メモ

問題 地上にあるレーダーを使って、宇宙からくるアステロイドの情報を効率よく集める。どのレーダーでどのアステロイドを捕捉するかを考える問題。 NASA's Asteroid Tracker - YouTube 結果 仮順位 21位/43位ですが、得点は、ほとんど最下位と変わらない…

混合ガウス分布のEMアルゴリズム、C++実装例(2次元のみ)

先日のTopCoderマラソンマッチ 「Octave Classifier(カテゴリー分けする機械学習系の問題)」で、使わずじまいに終わったC++のコードをアップします。混合ガウス分布のEMアルゴリズムについて、全く知らなかったので、 EM アルゴリズム実装(勉強用) - Mi ma…

TopCoder Marathon Match(機械学習・データマイニングもあるよ)

(2012年12月16日の記事を、Qiitaから移行したものです。)Machine Learning Advent Calendar 12/16の記事です。主催のnaoya_tさん、有難うございます。今回は、機械学習やデータマイニングを実際楽しみながら使えるTopCoder Marathon Matchの紹介をしようと思…

Marathon Match 74

(2011年10月29日の記事を移行したものです。) マラソンスタートしました(10/29) 前回の反省を生かして、文章化することにしました。 ファーストインプレッション(10/29) Anti..巡回セールスマン問題の最長路を求める問題かな?(注:間違いです!) 初期の点…

Marathon Match 72

(2011年7月22日の記事を移行したものです。) 結果 7位/44 Rating 1694→1783 裏マッチだったので、強いのはcolunさんだけなのに、7位。結果のわりには、レートは上がったのは、たまたま自分より上の順位の人が新規の方ばかりだったから。結果を反省せねばなり…

TCO11 Round 2

(2011年6月29日の記事を移行したものです。) 結果 136位/222 Rating 1795→1694このRoundで敗退かつレーティング的にも大敗北… 問題 複数の点がだいたいランダムに配置されている(点の数は50~5000)。それらの点を結んで多角形を作れ。 入力パラメータsides…

TCO11 Round 1

(2011年6月1日の記事を移行したものです。) 結果 62位/368 Rating 1754→1795 大反省点 調査してね(インターネットつかえます) 文字を置く・何か置く、やり直し(Undo)が可能な部分については、最初からやり直し可能な実装をしていかないと、だめです。 最初…

Marathon Match 68

(2011年6月1日の記事を移行したものです。) 結果 9位/147 Rating --→1754 大反省点 開始日になんでもいいから提出して追い込む! 準備完了までは集中! ちゃんとスコアがでるようになると、面白いので集中できる。準備の段階が面白くないので脱線しやすい) …

動的計画法が苦手な人が、動的計画法が超苦手な人へアドバイスしてみる

この記事は、Competitive Programming Advent Calendar Div2013(http://partake.in/events/3a3bb090-1390-4b2a-b38b-4273bea4cc83)の8日目の記事です。動的計画法(Dynamic Programming, DP)についての記事です。12/9 前編にサンプルプログラム(http://ide…

焼きなまし法のコツ Ver. 1.2

↓改訂版 Ver1.3はこちらから↓ shindannin.hatenadiary.com 2016年8月18日 Ver. 1.2 内容を更新しました。 4.遷移確率と温度の部分を全般的に修正 この記事は、Competitive Programming Advent Calendar Div2012の24日目の記事です。 http://partake.in/event…

TopCoder初心者向け 総当たり特集

この日記は、tanzakuさん主催のCompetitive Programming Advent Calendar - PARTAKEの記事です。普段、TopCoderのニコニコ生放送(http://com.nicovideo.jp/community/co78570)をしているのですが、最近は簡単な問題をじっくり解説するということが減ってき…

TopCoderで2年間プログラムしてみた

ニコニコ生放送「TopCoderでプログラムしてみた」 (http://com.nicovideo.jp/community/co78570)は、おかげさまで2周年を迎えることができました。この放送は、視聴者コメントに支えられている放送です(皆さんも私の放送よりコメントのほうに期待しているか…