回文に関連する実装が苦手です。回文について考えなければならないときはいつも気が重かったのですが、与えられた文字列から回文となる部分文字列を列挙する方法を@nico_shindanninさんがニコニコ生放送で解説していらっしゃいました。とても分かりやすい解…
STLやPythonで範囲指定の多くは左閉半開区間を基調にしています。しかし、std::string::substrでの範囲指定は大きく異なり、戸惑います。気が付くと実装時に繰り返し同じことを考え、無駄を感じていたのでまとめてみました。 以下はstring::substr - C++ Ref…
エラトステネスの櫛はN以下の素数を列挙するアルゴリズムとして知られています。まずは素数を列挙するナイーブな実装を行い、計算量を落としていきながらエラトステネスの櫛を考えてみることにします。次の実装の計算量はO(N2)です。 #include <iostream> #include <vector> #d</vector></iostream>…
素数を扱う簡単なアルゴリズムはO(√n)で行えます。以下の何れのアルゴリズムもO(√n)で行うことができます。 素数判定 約数の列挙 素因数分解 プログラミングコンテストチャレンジブックでは二つの式を使って簡潔に説明をしています(p. 111)。例えばnの素因数…
Codeforces # 223 Div. 2 http://codeforces.com/contest/381Codeforces # 223 Div. 2に参加。ABCが通り、2,492点。94位。部屋(Room 74)でも初めて1位となり、嬉しい回であった。レートは1,621から1,720へ。紫コーダーになった。今回のエントリではstd::lowe…
How To Defeat the Opponent 競技プログラミングのコンテストではゲームを模した様々な問題が出題される 問題の解法は様々だ シミュレーションによる解法 探索による解法 グラフの問題に還元する解法 コンテスト終了後によく話題になる、確率DP、期待値DPな…
SRM 594 Div I http://community.topcoder.com/stat?c=round_overview&er=5&rd=15706前回に引き続き250にはまりにはまり、45分で再提出。Room 17。レートは1308から1341へ。今回のエントリではSRM後に復習として考察した550のみを記載することにする。 Probl…
SRM 593 Div I http://community.topcoder.com/stat?c=round_overview&er=5&rd=15705250にはまりにはまり、55分。Room 41。レートは1231から1308へ。今回のエントリでは、SRM後に復習として考察した450のみを記載することにする。 Problem Status Points 250…
SRM 592 Div II http://community.topcoder.com/stat?c=round_overview&er=5&rd=10664練習。 Problem Status Points 250 LittleElephantAndBooks Passed System Test 215.14 500 LittleElephantAndPermutationDiv2 Passed System Test 475.77 1000 LittleEle…
Graph Theory グラフの用語をまとめます。順次更新。 Graph Theory グラフ理論。 List of graph theory topics - Wikipedia, the free encyclopedia Graph theory - Wikipedia, the free encyclopedia グラフ理論 - Wikipedia Connected Graph 任意の二頂点…
Codeforces Round # 185 Div II http://codeforces.com/contest/312Codeforces Round # 185 Div IIに参加。システムテストに不備があったようで、Unratedであった。 A. Whose sentence is it? http://codeforces.com/contest/312/problem/Aやるだけの問題で…
SRM 340 Div II http://community.topcoder.com/stat?c=round_overview&er=5&rd=10664練習。DP強化週間の一環。 Problem Status Points 250 CssPropertyConverter Passed System Test 248.20 500 ProblemsToSolve Failed System Test 0.00 1000 CsCourses Un…
TCO13 Round 2C http://community.topcoder.com/stat?c=round_overview&er=5&rd=15653250に9分。配信されたメッセージで題意を取り間違えていたことに気付くも、正しい実装が出来ず。チャレンジで撃墜された。Room 27。レートは1451から1422に下がった。 Pro…
TCO13 Round 1C http://community.topcoder.com/stat?c=round_overview&er=5&rd=15585250に16分。500に46分。チャレンジに1回失敗。511位でTCO13 Round1を通過。Room 34。レートは1323から1347に上がった。 Problem Status Points 250 TheArray System Test …
SRM 571 Div I http://community.topcoder.com/stat?c=round_overview&er=5&rd=15491250に21分。チャレンジ1回成功。220.76点。レートは1335から1440へ。Room 39。 Problem Status Points 250 FoxAndMp3 System Test Passed 170.76 500 MagicMolecule Opened…
SRM 570 Div I http://community.topcoder.com/stat?c=round_overview&er=5&rd=15490250に37分。チャレンジされ撃墜。レートは1474から1335へ。Room 21。 Problem Status Points 250 RobotHerb Challenge Succeeded 0.00 500 CentaurCompany Opened 0.00 100…
*1360481488* SRM 569 Div I http://community.topcoder.com/stat?c=round_overview&er=5&rd=15489 250に30分、500に42分。チャレンジ1回失敗。初めてDiv I Mediumを提出し、システムテストを通った。レートは1312から1474に上がったが、後の考察で明白なバ…
SRM 568 Div I http://community.topcoder.com/stat?c=round_overview&er=5&rd=15488250に30分。141.45点。前回に続き点数は低かったが、レートは1271から1312に上がった。Room 20。 Problem Status Points 250 TheSimilarNumbers System Test Passed 141.45…
Single Round Match 556 Round 1 http://community.topcoder.com/stat?c=round_overview&er=5&rd=15178250に75分を費やし、全く解けなかった。写経して自信を持って行ったチャレンジが失敗。合計-25.00点。レートは1236から1085へ。緑コーダーに。Room 28。 …
Single Round Match 555 Round 1 http://community.topcoder.com/stat?c=round_overview&er=5&rd=15177255に7分。555に45分。投稿した実装の検証に時間を割いたため955は開かなかった。合計487.93点。レートは1199から1236へ。念願の青コーダー。Room 80。 P…
Single Round Match 554 Round 1 http://community.topcoder.com/stat?c=round_overview&er=5&rd=15176250に12分。500に10分。1000の実装を始めたが、間に合わず。写経撃墜に成功。合計710.40点。レートは1111から1199へ。緑コーダー。Room 82。 Problem Sta…
Single Round Match 553 Round 1 http://community.topcoder.com/stat?c=round_overview&er=5&rd=15175250に7分。500も54分で提出したが、システムテストで落ちた。写経ミスでチャレンジ1回失敗。合計210.74点。レートは1123から1111へ。緑コーダー。Room 61…
Single Round Match 552 Round 1 http://community.topcoder.com/stat?c=round_overview&er=5&rd=15174250に10分。500に1時間ほどかけ、完成しなかった。合計227.00点。レートは何故か、1095から1123へ。緑コーダー。Room 68。 Problem Status Points 250 Fo…
Single Round Match 551 Round 1 http://community.topcoder.com/stat?c=round_overview&er=5&rd=15173250に6分。500に1時間ほどかけ、完成しなかった。合計239.62点。レートは1096から1095へ微減。緑コーダー。Room 62。 Problem Status Points 250 Colorfu…
Single Round Match 550 Round 1 http://community.topcoder.com/stat?c=round_overview&er=5&rd=15172250に6分。550に1時間ほどかけ、完成しなかった。合計239.48点。レートは1097から1096へ微減。緑コーダー。Room 76。 Problem Status Points 250 EasyCon…
OS X Mountain Lionにアップデートしました。私の環境には開発ツールが欠かせないのでXcodeもすぐインストールしました。LionのときはXcodeをインストールするだけでmake、g++等が使えるようになったので、特にチェックをしませんでした。 開発ツールに全く…
