TopCoder SRM 407
June 28th, 2008 | Published in Uncategorized
レッドカーペットみてビール3缶飲んで、さあて寝るかと歯を磨いてたら、TwitterからTopCoderがどうたらというポストが流れていて、あ、今夜24時からだったんだ! と気づいたのが23:50。あわてて参加しました。
250 問題 : SpiralWalking
Problem Statement
あたえられた矩形を時計まわりにぐるぐる周り、すべてのマス目を歩き尽くすまでに道にあったポイントを合計せよという問題。 ぐるぐる周るのってどうするんだっけや、とか壁を表現するのはどういうテクニックをつかうんだったけな、とか試行錯誤してるうちに40分くらいたって、やっとsubmit。ひどす。
コード:
bool visited[52][52];
class SpiralWalking {
public:
int totalPoints(vector levelMap) {
for (int i(0); i<52; i++) for (int j(0); j<52; j++) visited[i][j] = false;
for (int i(0); i<52; i++) {
visited[i][0] = true; visited[i][51] = true;
visited[0][i] = true; visited[51][i] = true;
}
int W(levelMap[0].size()), H(levelMap.size());
for (int i(0); i 0) {
dx = 0; dy = 1; turned = true;
} else if (dx < 0) {
dx = 0; dy = -1; turned = true;
} else if (dy > 0) {
dx = -1; dy = 0; turned = true;
} else if (dy < 0) {
dx = 1; dy = 0; turned = true;
}
}
if (4 == i) break;
if (not turned) score += levelMap[y-1][x-1]-'0';
visited[y][x] = true;
x += dx; y += dy;
}
score += levelMap[y-1][x-1]-'0';
return score;
}
};
我ながらこれはひどい。でもいちおうSystem Testにパス。
500 問題 : CorporationSalary
Problem Statement
詳しい説明は nishioさんとこを参照。
250より500の方が簡単じゃないか! 再帰でいっぱつやん! と5分くらいで書いてsubmit。
コード:
class CorporationSalary {
public:
long long calcSalary(int x, vector &salaries, vector &relations) {
if (-1 != salaries[x]) return salaries[x];
int count(0);
int total(0);
for (size_t i(0); i
}
long long totalSalary(vector relations) {
int N(relations.size());
vector salaries(N, -1);
for (int i(0); i
long long total(0);
for (int i(0); i
}
};
しかし、System Test でこけました。 原因を調べてみると、ふつうに桁溢れ。アホすぎる… ＞＜
終わってから、calcSalary の中を s/int total/long long total/ にして Practice Room でテストしてみるとちゃーんとパスしました。もったいない。
ひどい内容だったにもかかわらず、Ratingは +6 で 921 になりました。やっぱりもったいない。
やはりアルコール入れると集中力、注意力ともに低下してよくないですね ＞＜
TopCoder SRM 404
June 6th, 2008 | Published in Uncategorized
日本人にやさしい時間に始まった SRM 404 でした。404 TopCoder Not Found.
250 : Reading Books
Problem Statement : コード
配列をシーケンシャルに読んでいって、3種類のなにかを拾いあつめていく問題。んー、うまく言えない。 単純に要素をカウントしていくだけだとうまくテストケースをとおせないので、ちょっと考える必要がありました。ad-hocに書いてテストケースすべてがとおったところでsubmit。190pts。
500 : RevealTriangle
Problem Statement : コード
おもしろい問題。 穴ぼこだらけの三角形に、数字を入れていくという穴埋め問題ですね。 手でやると小学生でも解ける問題だけど、じっさいコードに落とすとなるとけっこう手強い。さんざん時間をかけて、テストケースをすべてとおしてsubmit。222ptsでした。コードが汚なすぎてわらえる。 TopCoderアカウントがある方は、これ を見て「これはひどい」と感じることでしょう。
結果
Challenge phaseで晩ごはんを食べているうちにSystem testを2つともパスし、Rating は 898→943 と 45点アップしました。ひさびさの緑コーダーに返り咲きです。うれしす。
コツコツつづけていくしかないですね。まずは250, 500の両方をコンスタントに解けるようにしていくことです。
TopCoder::SRM::401
May 7th, 2008 | Published in Uncategorized
ひさびさにTopCoderについて書き残してみます。 自分はまだまだへぼいのでDiv2の話。
Easy
問題, コード
二次元座標上の2点が与えられて、その線分上にある格子点 (端点は含まない) の数をかぞえる問題。
2点を通る線分は、
y = (y2-y1)/(x2-x1) * (x-x1) + y1
( x1 < x < x2 )
で表現できるので、(x, y) が格子点かどうかは (y2-y1)*(x-x1) が (x2-x1) で割り切れるかどうかで判断できます。
というコードを10分くらいで書いてsubmitし、200ptsを得たものの何か不安を感じて、
(x1, y1) = (0, 0), (x2, y2) = (0, 50), 期待する返り値: 49
のテストケースをローカルにつくったところ、みごとにアウト。 x2=x1 のケースが境界条件でした。
いそいでこの場合だけを特殊化して再びsubmitし、結果は150pts。ペナルティきつい ＞＜
Medium, Hard
どちらも問題は分かるし、解決策の背中は見えてくるんだけど、コードにできず。これじゃまだまだDiv2から抜けられないな…
Challenge
今回のEasyは、きっと境界条件の処理が甘いコードがあるにちがいないと踏み、さっきやったテストケースでchallengeしてみました。初めてchallengeに成功し、+50pts。
他のひともがんがんchallengeしており、Room内は死屍累々としていました。
結果
System Testで無事にEasyがとおり、こんなところ。 Ratingは前回よりも+30で894ptsになりました。あと+6で緑コーダー。
TopCoderが流行ってるみたいなので
April 25th, 2008 | Published in Uncategorized
自分の戦歴を晒してみる。
戦歴
2007.4.18 にRating 933 からスタート。乱高下の末、2008.1.15 に ハイスコアである Rating 1073 をマークしてGreen Coderになるも、深夜に参加する度Ratingを落とし、現在 Rating 822。
現在の目標はBlue Coderになることです。先は遠い… Challenge phase はおいといて、コンスタントに250,500,1000のすべてを解けるようになること。
なんでTopCoderに参加してるかというと、修行ですね。アルゴリズムの勉強、速く正確なコードを書けるようになること、他人のコードを読む力。
プログラミングしたいけどつくるネタをおもいつかないよー、という人がいると聞きます。 そんなときは、TopCoderにログインして、Practice Roomに入り、250点問題を解いてみてはどうでしょうか。わりと取り組みやすいので、自分の背中を押してあげるにはなかなか良いとおもうのです。
TopCoder::SRM::392
March 6th, 2008 | Published in Uncategorized
ここのところずっとRatingが下がりつづけていたので、挽回したいところでした。
-
250pts : とってもEasyな問題。ささっと解いて237.15pts。
-
500pts : 2つの文字列でワイルドカードの処理をする問題。40分くらいかけて書き、テストケースをぜんぶ通してsubmit。なんだけど、Challengeされて陥落。0pts。
- 1000pts : むずそうなので手つけず。こういうシンプルだけど頭を使う問題を考えつくのってすごい。
けっきょくChallengeもできずに250ptsを解いただけの237.15ptsでした。Room 6位でRatingは821→871と50pts up。まだ色無しコーダーです。しょぼいなー自分。
Room結果
TopCoderは、コードを書くだけじゃなくて読む力をつけることのできる場でもあると思いました。 Challenge phaseでは殺伐と他人のコードのアラを探し、試合終了後はハイレベルなレッドコーダーのコードを見て勉強したり、と。 ライブコーディングというか、できたてほやほやの良質なコードに触れることのできる良い機会だと思います。 みんなぜひ! そして僕より先に行かないでー。
TopCoder::SRM::380
December 5th, 2007 | Published in Uncategorized
ここのところ順調にRatingが伸びていたTopCoder::SRMの380でした。
Easy: LuckyTicketSubstring (code) 文字列処理と制御構造をちゃんと書けるか、みたいな問題。アルゴリズム設計にちょっと手間取りつつ、11分でsubmitして214.90pts。
Medium: LameKnight 最初おもいっきし問題文を勘違いしていて (引数の順序を逆と思っていた)、例がぜんぜん正しくないじゃないか、とか思ってしまい、スルー。
Hard: CompilingDecksWithJokers (code) なんていうんだろう、ポーカーのストレートをつくるようなかんじ? な問題。分かりそうで分からなかったんだけど、例を紙に書いてるうちに解き方を思いついて、急いでコードにしてsubmit。505.55ptsでした。
いざchallenge phaseになると、おびただしい数のchallengeが行われていて戦々恐々でした。自分も撃墜されなければいいな、と眺めているとあっさり撃墜されてしまい…
激しかったchallenge phaseを終えるとこんな感じ。medium,hardともに解けていたのは一人だけという。 
自分の結果としては、Ratingが-5ptsと最小限に食い止めた感。
Ratingはこんな感じで推移してます。ゆるやかな上昇曲線を継続させていきたい。
TopCoder::SRM::373
October 25th, 2007 | Published in Uncategorized
晴れた朝に始まったSRM::373でした。
Easy
TheEquation (コード)
高校数学っぽい問題。ちょっと頭をひねりながら解いて7分でsubmit。236.05ptsでした。 終了条件が甘そう…
Medium
StringFragmentation (コード)
キャンバスに文字列を書いていくときに、許容される最大のフォントのサイズはどれくらいか、という問題。 与し易しと見てあれこれやってるうちにローカルでテストをpassしたのでsubmit。55分で204.14ptsでした。
Hard
RectangleCrossings
手つけず。幾何の問題ですね。
結果
Easy/Mediumともに、System Testでfailしてしまいました。うわっちゃー。 Ratingは982→866と120ptsもダウンです。あいたたたた….. なかなかうまくいかないものです。
基礎力をつけねあ !
TopCoder::SRM::372
October 18th, 2007 | Published in Uncategorized
ひどいことになってしまった前回のリベンジを果たすべく臨んだSRM372でした。
Easy
DietPlan (コード)
文字列処理の問題。特定の文字が文字列に存在するかとかそういうの。 なんてことない問題だったんだけど、不必要に時間をかけてしまい、14分ほどでsubmit。203.08ptsでした。
Medium
RoadConstruction (コード)
特定のルールに従う交通整理を書きます。 なにより慎重さが求められる系。
込み入ったルールをうまくコードにするのに手間取り、残り5分というところでやっとsubmitでき、201.67ptsでした。
Hard
RainyDay
完全にスルー
結果
Challenge phaseをなんとか防御し、うまいことEasy/MediumともにSystem Testをpassできました。 テストが2つとも通るのは前々回以来の2度目です。この調子でやっていきたい。
Ratingは、がくんと落ちた前回に対してばばっと上昇し、前々回レベルに戻りました。917→982で緑coderのままです。
TopCoder::SRM::371
October 15th, 2007 | Published in Uncategorized
深夜に始まるSRMでした。ねむいよ。
Easy
CondorcetVoting (コード)
選挙で一番人気があるのは誰かという問題。 簡単じゃーんと書き始めるものの、いまひとつ眠気のせいか調子があがらず、15分ほどかかってsubmit。196.73ptsでした。
しかし、単純に投票者すべてについて足し算するだけで満足してしまっていて、後にChallengeで落とされてしまいました。0pts。otz。
Medium
SpiralRoute (コード)
四角形の端かららせんを描いていって、最後の座標を求める問題。 愚直に端から一歩ずつ進む実装を書いてsubmit。331.91ptsでした。
しかし、System testで落とされてしまいました。なぜかはまだ確認しておらず。0ptsになってしまいました。
Hard
FloodRelief
与えられた地図から、窪みの数を求める問題。 2問解けて (るつもりになって) いたので、面白いなあと思いながらいろいろ考えてみるも、できそうでできず状態に。
結果
アグレッシブなchallenge phaseとげんなりするsystem test phaseが終わり、結局0ptsでした。やれやれ。 Ratingは984→918と64ptsダウンです。それでもなんとかGreen Coderのまま。眠いのに無理してやると逆効果、ということですねー。
TopCoder::SRM::370
October 10th, 2007 | Published in Uncategorized
3連休明けの夜に始まったSRM::370でした。
Easy
Problem Statementに書いてある手順をそのままコードに書き下すstraightforwardまくりな問題。 さっさとsubmitして235.73ptsでした。
Medium
高校で習う確率の問題。ちと簡単すぎるんじゃない? と思いつつも、Exampleのテストケースはpassしたので思いきってsubmit。463.10ptsでした。
Hard
これはちぃとむずかった… いろいろ考えあぐねてみるも、ばしっと考えをコードにうつせず。 解くのは諦めて、Mediumで何が問題なのか考え直してみることに。
結果が出るまで
といいつつ、何もしないままCoding phaseおわり。Challenge phaseはいつもどおりスルー。 今日は誰からもchallengeされず、ほっと胸をなでおろしていました。
System testがなかなか終わらず (2時間かかってた)、その間 Roomに居るひとたちと、「500はなんかあるよな」「Div1のやつらはDPで解いてるぜ」「50!はintで収まらないよな」とかそういう話をしてました。 こうやってchatしている相手は世界中にいるんだけど、同じコンテキストを共有していると、すごい自然にしゃべれるのは不思議な気がします。
結果
首をながーくして待っていたSystem testがようやく終わり。結果は、Easy, Mediumともにpassで、698.83pts/Roomで3位でした。2つSystem testをpassしたのは初めてで、だいぶうれしい。
Ratingは851→985と134ptsのjump upでした。久々にGreen coderに返り咲きです。 この勢いを大事にするためにも、復習しとかなきゃです。
思うに、Mediumはいくらなんでも簡単すぎる。ほんとはなにかtrapをしかけていたんだけれど、そのtrapがうまく機能しなかったからみんな解けちゃった、みたいなことになってるんじゃないかと想像しています。