250 (0,0)から(X,Y)まで格子点上の移動で行く時に，縦横に動く時の速度と対角線に動く時の速度が与えられているとする．このとき最短到達時間を求めよという問題． 行き方としては(0,0)->(X,0)->(X,Y)と縦横移動のみで行く方法と(0,0)->(X,X)->(X,Y)(便宜上X…

250 シミュレーション. 過半数の判定のところで>=を>とタイプミスしたせいで再提出. 500 まず与えられたpatternから動いている部分を検出する.次に,patternを含みかつ検出した動いている部分に対して矛盾しないようなsymbolを列挙する,ここでsymbol取れなか…

ルーム内一位だったので賞金がもらえるみたいです．

250 アスタリスク*がひとつ入っているような文字列が2つ与えられる.それぞれの文字列において*に適当な文字列を入れたときに与えられた2つの文字列が同じになりえるかどうかを求めよという問題.複数ある場合は最も短いものを返す. 一つの文字列の*に他方の文…

順位は370位で，上位300しか通過できないのでRound 2落ち． 250 実は両方向の枝は全部無視して，閉路判定していいという罠．理由は片方向の枝で閉路ができないとき，トポロジカルソートを行って両方向の枝の向きを左から右につけるという風にすると閉路はで…

432位だったのでRound 2には進めるようです． 250 価格priceの商品Aを買う際に他の商品も一緒に買うとpriceが定められた割合だけ控除されるときに最適な買い方をしたときの合計金額を求めよという問題．ただし割引率は1,2,3の三通りしかない．また他の商品の…

前回が途中でサーバダウンのため中止になったので1日後の今日再び行われた． 250 点を与えられた条件で動かしていったときの最終状態を求めよというありがちな問題．218.97pt 500 与えられた重みつきグラフから非連結にならないように枝を除去した時のとれる…

250 与えられた数字Nをつなげていったときに最低何個つなげたらkの倍数になりますかという問題．できなかったら-1を返す． 数字をつなげるというのはNの長さをlとしたときに10^lかけて，Nを足すのと同じなのでmod kで考えていって0になるまで繰り返す．ただ…

250 最初，通分するものだと思って計算してて，そうすると答えがおかしくなったのでtは1からじゃなくて2以降から選ぶのかと思って，書き直す，それでもうまくいかなくて通分しなかったら直った．そしてtの選択範囲を間違えたまま提出． 500 stringsの値をど…

250 1..Nの数で最大の素因数がk以下のものの数を求めよという問題．ふるいを作るときに最大の素因数も一緒に更新してけばいい． 500 グラフが与えられて，今各頂点に情報を1種類だけ伝えることができ，このときその情報は伝えた頂点とまわりの頂点で共有され…

今回は特に送れず普通に届いた．TCO 2008のスケジュールがもう発表されてて，Rulesを見ると今回はOnline Round 3まで行かないと景品がもらえないようだ．

300 joker boxを一個固定して、残りの箱について2種類以上入っている物に関してはjoker boxに移動，同じ色のものが複数の箱にまたがっている場合は一個だけ残してあとは全部joker boxに移動すればよい．ただ2番目の処理を間違って落とされた． 500 ある区間…

今年初めてのSRM 250 データベースのデータ列が与えられたときに主キーとなりえるものの最小の長さと最大の長さを返せという問題． なぜか，最小の長さと候補数を返すと思っていてはまった． 属性の数が高々10なので全部試すだけ． 500 平面上の点がn( ある…

定員オーバーで参加できず．

Rate 1811->1804 250 LCM(2..9)=2520なので,条件を満たす数は2520個に1個はあるので最初から試してく． 500 1文字ごとの距離を足したものを比較するだけなんだけど，そもそも作るグラフが間違ってた． 500はPractice Roomで通ったからあれっと思ったんだんだ…

Rate1863->1812 275 まあよく読むとちゃんとunsorted sequenceを比較すると書いてあった． 500 flood fill 1000 一応送ったけど普通に間に合わなかった．

次回は講義とかぶって出られないので10月最後のSRM． Rating 1825->1863 10月全体では1632->1863なので今月は大上昇．このまま上がってほしいものだ． 250 英語を読む問題．書いてある通りにシミュレーションする． 500 DP．問題は数nが11で割り切れるかどう…

Rate 1774->1823 Rateは上昇，ただ250に20分近くかかっているのは反省．500はオーバーキルだというのはわかってるんだけど割当問題のライブラリを使用．O(VElog(VC))なので十分間に合う．900は方針は立ったんだけどコーディングが追い付かなかった． 10月に…

Rate 1747 -> 1774 Room placeは13位と微妙だったけど，Division placeは185位とそんなに悪くなかったのでかろうじてRateは上昇． 250 やるだけ．一瞬doubleの精度がどうなのかと思ったけどたぶん問題ないと思って提出．226.17pt 500 動的計画法．なんだけど…

TopCoderのアルゴリズム部門のアクティブな日本人参加者の参加時期に関する累積部門をグラフにしてみた．データはDataFeedで取ってこれるものを利用した．具体的にはActive Algorithm Coder Listで日本人のCoderリストをとってきて個々のAlgorithm Rating Hi…

初めのほうでトラブルがあったのでノーゲーム. 自分はchallenge phaseで全部落とされてたのでよかったといえばよかった(一応2つchallengeを成功させて100ptとってるのでRateはそんなには下がらなかったとは思う) 250 貪欲で取ると(countA , countB , maxA , …

Rate1632->1746 250 何も考えずにBFSしてこける．何を間違えたかというと ●→●→● ↓ ↓ ●←●上のような時にループがあると判定してた．そして去年の模擬国内予選のCでも似たようなことして間違えてたことを思い出した． 500 polylineどうしの接続関係をだしたら…

TCOのTシャツやっと届いたんだけど袋があいててフリスビーが入ってなかった．なんだかなあ．届くのが遅かったのは宛先に印刷ミスでJapanが書いてなかったせいのようだ．追記：フリスピーは郵便受けに入ってた．見落としたのはもう少しソリッドなものを想定し…

Rate 1665->1632 250 毎回の操作で作れる音量を全部列挙する． 500 2^10調べるのだけど，辞書順のものを返すというところでビットパターンがはじめの方のものが早いとかよく分からないことを考えてしまったせいで間違えた． 1000 マップの要素数 × 残りの時…

http://www.topcoder.com/stat?c=school_avg_rating University of TokyoがTop10に入った．*1国別ランキングも11位なのであともう少しでTop10に入る．学校別，国別のランキングで使うRatingはi位の人間に対してR^{i-1}(R=0.87)という重みを与えたWeighted me…

Rate 1614->1664 何か点数にだまされた気がする． 300 n^2の約数の中でmod 4をとったときに1となるものの個数と3となるものの個数を求めよという問題．nは10^9ぐらいまで． まず，nの約数をO(n^(1/2))で列挙する．約数の数はそんなには大きくならないので約…

レート1583->1614 初1600超え 250 数列に対して再帰的に規則を適応していった結果，結果が0になるように数列に要素を1個追加しなさいという問題．ちょっと計算すると各段階での末尾の和を求めればいいことがわかる． 500 与えられた複数の文字列をグルーピン…

Rate 1577 -> 1583 普通に3問いける問題セットだったと思うけど1000は落した，構文解析は苦手． 250 書いてある通りにやる 500 座標順でソートして左からなめてく，ただし左端と右端の点で座標が同じならば左端の点を優先する． 1000 Blockを左端と右端の文…

レジストはしたんだけど，あまりにも眠かったので参加せず．幸い1問も開いてない場合はRateの変動が起こらないようなのでよかった．

Rate 1374 -> 1500書いたコードと問題はこちらで見れます(TopCoderのアカウントが必要)． 300 辞書順にDFS．Validな日付しか来ないので，各月の日数の配列とかは用意する必要がなかった． 500 こっちはBFS. 状態をintでもつかStringでもつか，ちょっと判断に…