TopCoder

Single Round Match 445 Div2

すごく久しぶりだ。ここしばらくレンダラーいじったりしてC++に触れていたせいか、だいぶ回復したように思える。後10分くらい回答時間があるけど全部submitしたのですることがない(いや撃墜の準備とかを普通はするんだろうけど)テストで落ちないことを祈りな…

Single Round Match 437 結果

250と500を両方正解して合計で550点取った。だいぶ回復したけどまだ一軍には戻れない。ぎりぎり点数が足りない。なんか境目あたりにガラスの天井があるように感じる(きっと気のせい)

Single Round Match 437 (Div2/1000point)

久しぶりに時間が十分余ったので1000点問題にも挑戦。「1からスタートして与えられた整数nまで何回の操作でたどり着けるかこたえなさい。やっていい操作は 1増やす 1減らす(元の値が1より大きい場合のみ) 累乗する(たとえば元の値が2なら4とか8とか16に変え…

Single Round Match 437 (Div2/500point)

「整数nを10進法表記にして、k回数字の入れ替えを行ってつくることのできる最大の値は何か」という問題。ただし0で始まる数字を作ってはいけない。それが避けられない場合は-1を返せ、とのこと。for文で前置インクリメントを使ってないのはよくないな。あと…

Single Round Match 437 (Div2/250point)

「数字を10進法で表現したときに、何種類の数字があるか答えなさい」という問題。sumはtoolboxからコピペした。accumulateくらいコピペしないでも書けるようにならないといけないか。あと0ULLってのはどうかと思った、T(0)でいいんじゃないのか。久しぶりに…

Single Round Match 436 (Div2/250pt)

友達関係のグラフを渡すので、「2ホップ以内の友達の数」が最も多い人の友達の数を返しなさいという問題。 vector<string> twof(friends); // copyこれでコピーを取れるのか(同一の文字列オブジェクトへの参照を持っているみたいな状態にならないか)不安で確認してし</string>…

累乗剰余のテスト

TopCoderとかでたまに出る「値が巨大になるのでNであまりを取って答えてね」のためにあまりを取る階乗とかを作って用意しておいた方がいいのかなー、なんてことをid:suztomoに話したらこんなサイトを教えてもらった: Spaghetti Source - べき剰余で、今読ん…

include.pyについて

言語化された解説がないので適当に説明。 // BEGIN CUT HERE #include "../lib/debugprint/debugprint.hpp" #include "../lib/toolbox.cpp" /*** AUTO_INCLUDE ***/ // END CUT HERE int main(){ DP(IsPrime()(97)); } DPはデバッグプリント用のマクロなので…

Single Round Match 430 (Div1/500point)

都市の座標と条件が与えられ、条件を満たすなるべく多いペア(2つの都市の「姉妹都市」関係)を作れ、という典型的なグラフ問題。条件とは「都市がminDistance以上離れている」と「一つの都市は最大maxPartner個の都市と姉妹都市になれる」の2つ。「ペアの個数…

Single Round Match 430 (Div1/250point)

正の整数xとkを与えるのでx + y = x | y となるようなyのうち小さい方からk番目のものを答えなさい、という問題。(説明が楽な問題だ!)x | yがx + yになるということは要するにx & y == 0ということだから、xとkを両方2進数で表現してxが1の所に0を挿入したk…

ランキング比較グラフ

http://blog.isocchi.com/2008/11/-topcoder.htmlおお、isocchiがさくっと作っている。すばらしい。やっぱり比較できると面白いね。そして1500点のちょっと下で団子になっている。1500点はガラスの天井なんだろうか。1500点はDiv1で2問目を時間内に解けるか…

SRM422

「重さの合計が与えられた上限を超えない部分集合を全部返す」というアルゴリズムをさらっと書けなかったので終わってから頑張った。 void find_all_subset( const vector<size_t> &elems, const vector<int> &weight, int weightLimit, vector<vector<size_t> > &result, int start=0, v</vector<size_t></int></size_t>…

iVocaで「TopCoderに出てくる英単語」を学習できるようにしました

出題する英単語は、TopCoderの過去の問題文から出現頻度をカウントして、Gutenbergプロジェクトの文章での出現頻度で割った「TopCoderに特別多く出てくる単語ランキング」を作って、その上位300位くらいから適当に面白そうな物を選びました。iVocaって、他人…

SRM421 Div1 normalがわからない

http://www.topcoder.com/stat?c=problem_statement&pm=10074&rd=13512 整数のリストが与えられる。これはケーキのサイズ。これを最大maxCuts回切って、一番大きい断片と一番小さい断片のサイズの差が一番小さくなるようにせよ、という問題。どうするんだこ…

戦線布告された

http://generation1986.g.hatena.ne.jp/n4_t/20081009 まずはnishioさんを追撃、であります。 今年の頭にも戦線布告されたんだけど http://d.hatena.ne.jp/nishiohirokazu/20080101/1199187895調べてみたら、12ポイント差だった。知らない間に背後につかれて…

SRM421 Div1 easy

http://www.topcoder.com/stat?c=problem_statement&pm=10104&rd=13512 直線上のx[i]の位置にm[i]の質量がn個並んでいる。万有引力は距離の二乗に反比例する。別のものを置いたときにプラス方向へ引く力とマイナス方向へ引く力が釣り合うポイントがn-1個ある…

TopCoder部

http://generation1986.g.hatena.ne.jp/keyword/TopCoder%E9%83%A8suztomoが頑張ってる!suztomo++ どんな問題が出るの?最初は二重ループをまわせれば解けるような問題が多いです.日本人にとっては英文で書かれている問題を読むのがつらいですが,なあにか…

逃した

終電で帰ってきて今0:50、当然0:00スタートの今回のSRMには参加できず。 だいたいラボの発表会の後の懇親会で、お酒を飲んでもいないのに眠くなってトチュからずっと寝ていたから覚えていたとしても間に合ってない。次回は19日の日曜日、午前1:00からだ。ふ…

Single Round Match 417

今回は何を考えたか唐突にやってみたくなったのでお風呂から参加です。風呂グラマって言いたいだけちゃうんか。昼間から多少目の調子が悪かったのだけど、今触ってみたら扁桃腺がかなり盛大に腫れている。あらら。昨日窓を開けて寝たのが行けなかったのかな…

Single Round Match 416 Div1 Easy

後で書く問題は「与えられた整数Nと2進数表記で立っている1の数が同じで、かつNより大きな最も小さい整数を答えなさい」というもの。まず1000とか1111とかのことを漠然と考えて「1000の時は10000と2倍になるから+1しながら探すとタイムアウトするなぁ」と思…

SRM 413 Div1

easyとmediumをsubmit, hardは問題文を読んだけども残り20分で実装できる気がしなくてぐだぐだ。gcdとlcmを実装したけどBoostにあるなぁ。boost::rationalってのの存在を知った。でもアルゴリズムは全然思いついていない。easyはその後のシステムテストで落…

次回は日曜1時から

なのにACアダプタを忘れるとは。。。明日の1時からだと思ってたからちょっと休めばいいかと思ったのだけど、あさっての1時だね。明日はNoPCデーにするしかないか。

Single Round Match 413 Div1

今回からDiv1で戦うことになりました。うは、みんな青とか黄色とか赤だ(当たり前) ここにいる全員が僕よりコードの書ける人だと思うとなんかすごいな。500点問題、回答した18人のうち14人がチャレンジされて落とされている。僕を含む。一見簡単なように思え…

SRM412 Div2

今回の問題は仕様が大きくて英語になれていない人が不利な問題だった印象。前回僕が牛久大仏からの帰りの車で参戦した回に比べるとアルゴリズム的にはさほど難しくないのではないか。境界を含むのか含まないのかとかに注意しないとテストケースで落とされそ…

Eclipse CDTでプレイする準備

やったこと EclipseでTopCoderプロジェクトを作成 Arenaのプラグインの設定でソースコードのテンプレートが出力されるディレクトリをTopCoderのワークスペースに設定 Eclipseでは行が折り返されないので問題文がとても見にくい。http://ahtik.com/blog/2006/…

Single Round Match 409 Div2

やはり終わった後すぐに書かないと書く気が減退するなぁ。今日の夜0:00からあったTopCoder SRM409がどんな感じだったかのあらすじ。 86チャットがなぜかTopCoderチャットになっている すねるujihisa 途中で接続が切れるyanbe 500点問題をsubmitする 1000点問…

Single Round Match 409 Div2 500pt

http://www.topcoder.com/stat?c=problem_statement&pm=9823&rd=12181&rm=297980&cr=22724714 問題を簡単に解説すると「文字列をたくさん渡すので、それをつなぎ合わせた大きな文字列を作ってください。ただし、なるべく小さく、おのおのの部分文字列の位置…

Single Round Match 408 Div1 500pt

難しい。なんとかsubmitしたけど190点。そしてシステムテストに落ちるな。あー、例のごとく処理時間超過だ。 問題の内容とかは後で書くことにして家に帰ろうかなぁ。 追記{ http://www.topcoder.com/stat?c=problem_statement&pm=8462&rd=12180 おおざっぱに…

Single Round Match 408 Div1 250pt

Div1(レーティングが高くないと参加できない一軍)の過去問を解いてみる。まだ一軍には入れないけど。問題:ろうそくが何本かある。夜の間ろうそくをつける。1日目は1本、2日目は2本点灯する。1日点灯するとろうそくは1インチ縮む。ろうそくの長さのvec…

Single Round Match 408 Div2 1000pt

練習がてらに解いてみる。問題は大まかに説明すると「赤玉と青玉が合計で奇数個入った袋があり、あなたがランダムに1個とり、敵が青玉を1個とる。最終的にあなたが最後に取る玉が青ならあなたの勝ち。」というもの。厳密な問題文はアカウントがあれば下の…