naoya_t@topcoder

SRM418

09.20+.2008

TopCoder SRM (Single Round Match) 参加３回目。

準備

• CodeProcessorのバージョンを2.0から1.2に落として再設定
• デフォルト言語をC++にする
• ビルド〜テストの練習のためにDIV2の250点の過去問をいくつか解く

本番

DIV	level	問題名	競技中	後で	System Test	備考
2	250	Towers	◎		passed
2	500	TwoLotteryGames	◎		passed	.. 75.51%
2	1000	BarracksEasy	途中
1	250	TwoLotteryGames				92.67%
1	500	StampsCollection		o	passed	10/4 https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20081004/p1
1	1000	(Barracks)

250点問題

一瞬問題の意味がわからず焦るが、なんとなく出来た。自分でもテストを２つぐらい追加してみた

500点問題

最大８桁のビット演算に直して解いた。こないだ出てきた __builtin_popcount() を使ってみた。

1000点問題

BFS + priority_queue で解いてみようとするが、コーディングが間に合わなかった。チャレンジタイムも（何人かのコードをちらっと見たぐらいで）1000点問題の続きを頑張っていた。解けたっぽいけど20〜30分ほどオーバー＞＜

チャレンジタイム

あまり盛り上がらない。1000点問題を取った人がチャレンジされていた。

システムテスト

部屋の１位の人（559.06）が250点問題で足下を掬われて、559.0点で部屋では１位になる。DIV2全体では46/824位。

レーティングが 1071 から 1207 に上がった。挑戦３度目にして Green Coder から Blue Coder に昇格。次はDIV1になるのかな。DIV2より問題が難しくなるらしいので時間をとって練習しよう。

SRM417

09.11+.2008

TopCoder SRM参加２回目(DIV2)。

サーバトラブルか何かのため、10分遅れてのスタート。

DIV	level	問題名	競技中	後で	System Test	備考
2	250	ReversedSum	◎		passed
2	500	TemplateMatching	F
2	1000	(TripleJump)	-
1	250	TemplateMatching	-	o	passed	12/22 ... 80.48%
1	500	CubeNets
1	1000	WalkingDistance

250点問題

　一瞬で解けた。部屋では一番、かな。

　テストとかプラグインで自動化できるんだよね・・・研究しておこう。

500点問題

　残りのほとんどの時間をこれに費やした。

　mapのイテレーションの書き方で悩んで時間をかなり無駄にしている。

　受けたチャレンジはかわしたが、システムテストでアウト。（あとで落ちた原因を解明したい）

1000点問題

　読む時間がなかったのが残念。（部屋ではsubmitなし）

　あとで読む。

250点問題で取った243.93点のおかげでレーティングが 1046→1069 にUP。

とりあえず1200超を目指して頑張る。というか500点問題がちゃんと取れるように頑張る。

TopCoder SRMに初挑戦＜SRM416＞

TopCoder SRM (Single Round Match) に初挑戦。

• ７月末にTopCoderのアカウントを作った→放置して９月
• とりあえず、一度やってみて流れを掴もう
• TopCoder SRM入門 - gnarl、技術メモ
• TopCoderでCodeProcessor+TZTester+FileEdit を見て外部エディタの設定をしてみた。

SRM416

09.04.2008

とりあえず、250点問題から順に解いてみた。

DIV	level	問題名	競技中	後で	System Test	備考
2	250	MostCommonLetters	◎		passed
2	500	NextNumber	撃沈			↓↓ ... 26.78%
2	1000	(DancingCouples)	-
1	250	NextNumber	-	o	passed	12/11 ※５分で解けた！238.74points https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20081211/p1 79.06%
1	500	(CustomDice)
1	1000	(RussianCheckers)

250点問題

もぞもぞもぞ。出来た

何か設定が間違っているのか、C++を選んでもJavaなテンプレートが出てくる＞＜

500点問題

すんなり解けた

1000点問題

解法は思いついたものの、C++でコード化するのに時間が足りなかった。（推定あと15分ぐらい）

チャレンジタイムが来たけど、どうすれば他の参加者のソースを見れるのか分からない → Summaryボタン

• 500点問題challenge成功された。0点＞＜

初レーティングは 1043 でした。1200 を超えるとDIV 1に上がれるそうです。

メモ

• 2^29とかで落ちる
• __builtin_popcount(unsigned int x) というのがある

→ Counts the total number of one bits in x. Note that x86 does not have an instruction to do this, so you end up calling a real function; however, this is still more convenient than having to write the function yourself.

→ http://www.topcoder.com/tc?module=Static&d1=features&d2=022006

TODO

23:05 |

Algorithm Tutorialsを読む

https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/19700110 参照

ライブラリ整備

使えるようになりたいアルゴリズム

• 黄金分割法（凸関数の三分探索）
  • http://mikilab.doshisha.ac.jp/dia/research/report/2003/0612/003/report20030612003.html
  • http://www.prefield.com/algorithm/math/findmax.html

• 拡張ユークリッド互除法
  • http://ja.wikipedia.org/wiki/%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95
  • http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/ExEuclid.html
  • http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/EuclidRec.html
  • http://d.hatena.ne.jp/takehikom/20080804/1217798940

Algorithm Tutorials

Tutorials | 21:41 |

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=alg_index

author	title
lbackstrom	The Importance of Algorithms
antimatter	How To Dissect a TopCoder Problem Statement
Dumitru	How to Find a Solution
leadhyena_inran	Planning an Approach to a TopCoder Problem (§1)(§2)
dimkadimon	Mathematics for TopCoders
lbackstrom	Geometry Concepts : 1.Basic Concepts / 2.Line Intersection and its Applications / 3.Using Geometry in TopCoder Problems
gladius	Introduction to Graphs and Their Data Structures : 1.Recognizing and Representing a Graph / 2.Searching a Graph / 3.Finding the Best Path through a Graph
supernova	Greedy is Good
Dumitru	Dynamic Programming: From novice to advanced
misof	Computational Complexity (§1)(§2)
Dan[Popovici] & mariusmuja	Using Regular Expressions
supernova	Understanding Probabilities
timmac	Data Structures
cucu	New Features of Java 1.5
timmac	Sorting
_efer_	Maximum Flow (§1)(§2)
misof	Representation of Integers and Reals (§1)(§2)
lovro	Binary Search
bmerry	A bit of fun: fun with bits
danielp	Range Minimum Query and Lowest Common Ancestor
DmitryKorolev	Power up C++ with the Standard Template Library : Part I / Part II - Advanced Uses
medv	Prime Numbers, Factorization and Euler Function
jmzero	An Introduction to Recursion : Part 1, Part 2
cpphamza	An Introduction to Binary Search and Red-Black Trees
bmerry	Line Sweep Algorithms
Zealint	Minimum Cost Flow : 1.Key Concepts / 2.Algorithms / 3.Applications
rasto6sk	Algorithm Games
boba5551	Binary Indexed Trees
TheLlama	Introduction to String Searching Algorithms
Zealint	Maximum Flow: Augmenting Path Algorithms Comparison
x-ray	Basics of combinatorics
NilayVaish	A New Approach to the Maximum Flow Problem
vlad_D	Disjoint-set Data Structures
luison9999	Using Tries
dcp	An Introduction to Multidimensional Databases
zmij	The Best Questions for Would-be C++ Programmers : Part 1 / Part 2
innocentboy	Primality Testing : Non-deterministic Algorithms
x-ray	Assignment Problem and Hungarian Algorithm

Feature Articles(抜粋)

21:41 |

http://www.topcoder.com/tc?module=Static&d1=features&d2=archive

C++

author	title
bmerry	Five things you didn't know about C++ (§1)(§2)(§3)
bmerry	Beginning TopCoder Competition with C++
Nickolas	A Number or a String - Parsing Your Input and Formatting Your Output in C++
Yarin	A Crash Course in the C++ STL
bmerry	GCC Hacks - Abusing C++ Extensions for Fun and Profit

Programming

author	title
bmerry	Linear recurrences
vorthys	Dynamic Programming
Modulator	Challenging 101
radeye	Functional Programming
leadhyena_inran	The eight seconds of death - Tips on preventing timeout
bmerry	Computational geometry with complex numbers
kernelknowledge	Design Patterns in C++ (§1)(§2)
Seiz3r	Writing code that writes code…
supernova	The Story of Petr Mitrichev - Target in Six Steps
bmerry	Understanding your algorithm rating - and why it changes
timmac	Encryption Algorithms / More on Encryption and Security

その他

author	title
dcp	A Crash Course in Relational Databases (§1)(§2)
dcp	A Crash Course in SQL (§1)(§2)