TopCoder SRMに初参戦してみた。
学科で最近たくさんの人がやり始めたTopCoderなるものに初参戦してきた。
結果はちょっとくやしい。
TopCoderとは
TopCoderとはプログラミングコンテストの一種。
SRMでは、与えられた問題を解く関数を作る。仕様通りに動けば点数がもらえる。
もらえる点数は、短い時間で解けばそれだけ高くなる。
これまでの経歴によって各コーダーはランク付けがされ、低い順から白コーダー、緑コーダー、青、黄、赤コーダーとなる。
白と緑は二軍、青以上は一軍となり解くべき問題が変わる。
参戦
バイト先のCO-CONVというプログラミングのベンチャー企業のプログラマから「一発で一軍に行けたら褒めてあげよう」と言われていたので一軍に行けるよう意気込んでいた。
友人と下宿の部屋にこもり、SRMへの参戦登録。
開始の11時。
問題を見る。簡単な文章とは言え英語なので読むのに結構時間がかかる。
一問目。250点満点問題。
In archery, you shoot an arrow at a target and you get some number of points depending on where the arrow hits the target. In this problem, the target is a circle divided into N concentric rings and a central circle. The width of each ring and the radius of the central circle are equal. The point values assigned to each section of the target are given in the int ringPoints. The values are given in order, from innermost to outermost section, so ringPoints[0] is the number of points you get for hitting the central circle, and ringPoints[N] is the number of points you get for hitting the outermost ring. You are a beginning archer. Whenever you take a shot, the arrow always lands somewhere on the target, but it hits a random point, and all points on the target have an equal probability of being hit. Return the expected point value of your shot. Definition Class: Archery Method: expectedPoints Parameters: int, int Returns: double Method signature: double expectedPoints(int N, int[] ringPoints) (be sure your method is public) Notes - The probability of hitting a specific section of the target is defined as the area of the section divided by the total area of the target. - The expected point value of a shot is calculated as follows. For each section of the target, multiply its point value by the probability of hitting that section. The expected point value is the sum of all these values. - The returned value must have an absolute or relative error less than 1e-9. Constraints - N will be between 1 and 49, inclusive. - ringPoints will contain exactly N+1 elements. - Each element of ringPoints will be between 0 and 100, inclusive.
これは難なく解けた。サブミットの前にアルゴリズムに穴がないか考えるが、この手のものは例外的な処理は全く起こらないし大丈夫。提出。
これで約200点。まずまず順調。
ちなみに隣で解いていた友人は私が英語を読み終えた時点で１問目のコーディングを完了していた。Yahoo翻訳を使うなんて・・
次に2問目。500点満点問題。
Problem Statement NOTE: This problem statement contains superscripts that may not display properly if viewed outside of the applet. Your friend's birthday is approaching, and he wants his age to be written in candles on his cake. In fact, he has already placed several candles on the cake. The candles are arranged in a single row, and there are two different colors of candles. One color represents the digit '0' and the other color represents the digit '1'. You don't want to relayout the candles from scratch, so you have to determine if there's a base for which the existing candles spell out your friend's age. To simplify the task, you can choose any strictly positive base, not necessarily an integer one. For example, if the candles are "00010" and your friend's age is 10, then the candles spell out 10 in base 10 (decimal). If the candles are "10101" and your friend's age is 21, then you can say that "10101" is 21 in base 2 (binary). If the candles are "10100" and your friend's age is 6, then the candles spell out 6 in base sqrt(2)=1.41421356237.... Note that you are not allowed to rotate the cake, so "10" cannot be read as "01". You are given a String candlesLine, where the i-th character is the digit ('0' or '1') represented by the i-th candle in the row of candles on the cake. You are also given an int age, which is your friend's age. Return the positive base for which the candles represent your friend's age. If there is no such base, return -1, and if there are multiple such bases, return -2. Definition Class: AgeEncoding Method: getRadix Parameters: int, String Returns: double Method signature: double getRadix(int age, String candlesLine) (be sure your method is public) Notes - The number anan-1...a1a0 in base B is equal to an*Bn + an-1*Bn-1 + ... + a1*B + a0. - The returned value must have an absolute or relative error less than 1e-9. Constraints - age will be between 1 and 100, inclusive. - candlesLine will contain between 1 and 50 characters, inclusive. - Each character in candlesLine will be '0' (zero) or '1' (one).
式を書き、考える。
これは要するに多項式の方程式になる。
k^b0 + k^b1 + k^b2 + ... + k^bm = age (biはcandleLineのうち'1'となってるものの位置、kは求める答え)
方程式を直接解くことはできないので他の方法を考えることに。
この式の左辺は一部の例外を除いてかならず単調増加になる。
それなら、二分法で解いてやればいい。
最初に解が一つしかない場合や複数ある場合についての例外処理をした後で二分法を実施して解かせるようにする。
ここまでコーディングした時点で残り時間は5分／75分。
サンプルの値を代入して動くかをテストする。
動かない。細かいところでミスをしていた。修正。
もう一度テスト、さっきはじかれたテストは通った。
この時点で残りあと10秒。他のサンプルデータを試している時間はない。
他のテストはあきらめてコードを提出した。
５分の休憩のあと、「Challenge」が始まる。
他の人のコードを見て、「このコードだとこの入力の時に正しくない答えを返す」と見抜けば、その値を入力する。
確かに誤った答えを返したら「Challenge Succeeded」となり、自分に50ポイント加算される。（もしプログラムがその入力に対し正しく動いてしまえば、チャレンジは失敗となり25ポイント減点される。）
チャレンジで落とされたコードは0点となる。
人のコードを覗くまもなく、一瞬で私の500点問題が落とされた。
私のコードを落とした人は次々と他の人のプログラムのミスを見つけて落としていく。
私は結局一つもチャレンジできず。
結果
チャレンジの後は、「システムテスト」。問題作成側が用意したたくさんの入力データ全てに正しい答えを返すかをサーバーが調べ、全てのテストに通ったものが自分の得点となる。
私は250点問題は正解で得点201.35点。500点問題は既にチャレンジされ落とされている。
友人は約230点＋一つチャレンジを成功させて約280点となった。
今回は500点問題がほとんどの人がプログラムを書くも正しく動作しなかったようで、800人の二軍の中で500点問題を解けたのはたったの8人だった。
青コーダー、つまり一軍に入るにはランクが1200以上必要。
私は初参戦なのでランクは今回の201点から計算される。
ふたを開けてみると、なんとランク値1199・・・。
目指していた１軍に１点足りない。これは悔しい。とても悔しい。
友人は約1450で青コーダーの一番上の方だった。余裕で一軍。
他、所属サークルの交響楽団の先輩であり情報学科の先輩でもあるＫ氏は約1500点で黄色コーダー。一つ下の学科の後輩も青コーダー。
私よりも下の人も知り合いにいたけど、これだけいろいろ上にいるとやっぱり凹むなぁとか。
目標
とりあえず目下の目標を黄色コーダーになることに於いて頑張ろうと思う。
ただ、今回はどうやら500点問題を解けた人がほとんどいなかった影響で250点問題を解けただけでも高ランクを得られたという背景があるようなので次回以降も高ランクを得るのは難しいかも知れない。
でも頑張ろう。
