Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2013-10-05

SRM 593

| 02:59 | SRM 593 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM 593 - TopCoder煮ブログ

2 年ぶりの参戦。

14481402 (0pt 393位/830人)

--- (challenge: 0勝0敗)

HexagonalBoard (Easy)

Hex な盤面での色塗り問題。

最初は周りのコマ数で判定すればいいやーと思って書いてたら、サンプルが通らなくて無駄に悩んだ。

サンプルは

"XX-XX--
 "-XX-XXX"
  "X-XX--X"
   "X--X-X-"
    "XX-X-XX"
     "-X-XX-X"
      "-XX-XX-"}

となっていて、どの1コマを見ても、その周囲は 2 色で塗れそうに見える。

ただ、2 色で塗っていくと・・・

"XX-XX--
 "-XX-○●○"
  "X-X●--●"
   "X--○-○-"
    "XX-●-●X"
     "-X-○X-X"
      "-XX-XX-"}

と不整合がでるので、3 色目を導入する必要がある。

と気づいた時点で、DFS でやるべきなんだけど、力尽きた。どんな形でも最大 3 色あれば塗れるので、あとは

  • 何もなければ 0 色
  • すべてが孤立してれば 1 色
  • DFS で 2 色で塗れるか確認して、OK なら 2 色、ムリなら 3 色

とすればいけるはずなんだけど、時間切れ。


Challenge ではおかしそうなやつを見つけたけど、落とすサンプルを思いつかず時間切れ。実際、System Test に落ちていたので悔しいところ。

MayTheBestPetWin (Medium)

brute force で書いたらサンプル通らなかった。

まとめ

悲しい・・・。

2011-07-13

SRM 512 DIV1

| 02:06 | SRM 512 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM 512 DIV1 - TopCoder煮ブログ

1<<9 というキリ番の回。前回に引き続いて参加。

14121448 (163.88pt 424位/905人)

○-- (challenge: -25pt 0勝1敗)

MysteriousRestaurant (Easy)

250pt じゃなく 256pt だった。さすがキリ番の回。

N 日間 M 皿個の皿を出す料理店があって、それぞれの日の値段と手持ちの総額を与えられる。1回でもパスするとそれ以降食べられない。ある日に皿 m を選んだら、一週間後にも同じ皿を選ばなきゃいけない。最大何日食べ続けられるか。

最初、どうすりゃいいんだと途方にくれたが、1日でも食べられなかったらそこで終わりなので、支払い総額を最小にする選び方を最初の日からしていけばよいだけだと気づいた。ただし、8日目以降は、どの皿を選ぶのがにするのがトータルでのコストを抑えられるかを以前の週にさかのぼって再計算する必要がある。

ざっとコーディングして 188.88pt。チャレンジでは早とちりして失敗。-25pt…。

SubFibonacci (Medium)

与えられた数列からフィボナッチ数列の部分集合を2回取り出したときの最大長を求める問題。

ある数列がフィボナッチの部分集合かどうかを求める方法がさっぱり分からず諦める。

twitter の TL みてると2分探索でやるらしいのだが、それでもやっぱり分からん。

PickAndDelete (Hard)

5,1,2 が与えられたら、1、1~2、1~5 の順列の総数を数え上げる問題。総数が多いので mod して求める、という時点でいい方法が思いつかず。

まとめ

challenge してなかったら 294位。ちょっともったいなかった。

月之宮 帝月之宮 帝2011/07/22 22:58与えられた数列に対してmid(0~n)を決めて二つの数列に分割してから探索するだけで二分探索はしないんじゃないのでしょうか。分割後の探索は二分探索には関係ないですし。

2011-07-02

SRM 511 DIV1

| 03:17 | SRM 511 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM 511 DIV1 - TopCoder煮ブログ

ほぼ1年ぶりの参加。

13581412 185.05pt 409位/932人

○×- (challenge: 0)

Zoo (Easy)

2種類の動物がいて、それぞれが自分より背が高い同種類の数を応える、このときにありえる組み合わせの数を答えよ、という問題。

ソートしてから調べた。0,0,1,1,2,2,3,3,... のように2つずつ進めば正しい状態、どこかで 4,5,6,7... のように1つずつ出てくればそのあとは数が飛んでも2つ以上出てきてもアウト。

そんな感じで書いて、数が多い場合を試して submit。

    long long theCount(vector <int> answers) {
        sort(answers.begin(), answers.end());
        int n1 = 0, n2 = 0;
        for (int i = 0; i < answers.size(); i++){
            if (answers[i] == n1){
                n1++;
            } else if (answers[i] == n2){
                n2++;
            } else {
                return 0;
            }
        }

        long long ret = 1;
        for (int i = 0; i < n2; i++){
            ret *= 2LL;
        }
        if (n1 != n2){
            ret *= 2LL;
        }
        return ret;
    }

戻り値の型が long long なので慎重に書いたが、あとで考えれば最大値は 2^20 だったので long の範囲に収まる。だまされた。

FiveHundredEleven (Medium)

2人が交互にカードを順番に選択して、選択済みカードの OR が 511 になったら負け。2人とも十分に賢いとしたら勝つのはどちらか?、という問題。

カードの数が高々50枚なので総当りでいけそうだと思ったのだが、ロジックを書いている途中で「最適な出し方はどう書けばいいのか」でこんがらがってしまった。このタイプの問題、解けたことないから苦手なのだろう。

やけになって、return rand() % 2 == 0 ? ""Fox Ciel" : "Toastman"; というコードを書いたらチャレンジされた。

???? (Hard)

みてない。解けた人は2人だった。

まとめ

Easy はもう少し早く解きたかった。

2010-09-25

SRM 483 DIV1

| 03:51 | SRM 483 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM 483 DIV1 - TopCoder煮ブログ

2回連続0pt。いいのかこれで…。

14291358 0pt 464位/744人

BestApproximationDiv1 (Easy)

小数点以下6桁の数字を分数で表現せよ、という問題。

題意の読み取りにだいぶ時間かかってそのあと n/d を %f に sprintf しても数が合わない。%f はデフォルトで小数点以下6桁とみなすようだ。

精度が指定されていない場合には 6 として扱われる。

404 - エラー: 404

つまり7桁目を四捨五入してしまう。

ここで困って 7桁目以降を切り捨てるコードにして Submit した。

これがいけなかった。System Test で {853, "0.258749"} のケースで落ちた。

誤答したのは 207/800 = 0.258750 なのに割り算の結果は 0.25874999999999998 なので小数点6桁以下を切り捨てると 0.258749 になってこれを解にしてしまう。

他の人のソースを見てみると「%.15f」で sprintf している人は通っていた。こうすると小数点15桁目で四捨五入してくれて 9999... が続くようなケースにも対応できる。twitter を眺めてると %.8f でも通らないケースもあったようで double 周りは何かと危うい。

自力で小数点以下を計算している人が多かった。確かにそっちのほうが安全だろうな。次からはそうするべきだ。

ContiguousSubsequences (Medium)

選挙で勝つために影響力でかい人を説得するといいよ、という問題。題意だけ理解したが解法は思いつかず、時間もないので諦め。

Sheep (Hard)

羊を数える問題。900 点問題で多くの人が 500 より優先したようだが、System Test 後の twitter の眺める限りではバイナリサーチで答えた人がはげしく落ちていたらしい。自分もその域に達したい…。

まとめ

0pt だけど Petr と同じ点数!

ArinArin2012/07/10 06:03This arictle keeps it real, no doubt.

sfmuimsfmuim2012/07/10 16:26rEJzcO <a href="http://sopobaekagqd.com/">sopobaekagqd</a>

obbvvyixezobbvvyixez2012/07/12 12:40PtuXwp <a href="http://wopvtbcvvknr.com/">wopvtbcvvknr</a>

infvmeinfvme2012/07/12 18:11HvwWtF , [url=http://hiwjwyupsizo.com/]hiwjwyupsizo[/url], [link=http://hzhriredzsrc.com/]hzhriredzsrc[/link], http://gqptlxzzjgxa.com/

2010-04-04

SRM 466 DIV1

| 10:01 | SRM 466 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM 466 DIV1 - TopCoder煮ブログ

悲惨な回。再び1回で blue に降格。

15131429 0pt 577位/798人

LotteryCheating

与えられた N 桁の数を、約数が奇数個になるか 0 にするためには、何個の数を書き換える必要があるかを調べる。

エラトステネスの篩して、素因数分解して、約数の個数を求める関数を作った。時間かかったが submit した。

Intermission に最大の 9999999999 を与えたら返事来なかった。諦めた。System Test の結果見たら、9999999999 で Fail。でも、それ以外の値では問題なさそうだったので、最大値ぐらいは事前に試すべきだった。

上位の人は、小さい数から2乗していって与えられた数と異なる数字の数を列挙していた。「約数が奇数個 ⇔ 平方数」というのを利用している。なるほど...

約数が奇数個 ⇔ 平方数の簡単な証明

たとえば、ある数が N = Πpiai のように因数分解できるとき、約数の数は Π(ai+1) となる。

  • 約数の数が奇数になる→平方数:
    • 約数が奇数ということは、ai+1 が全ての i について偶数である。これはつまり、N が平方数ということになる。
  • 平方数→約数の数が奇数になる:
    • 平方数の場合は全ての an は偶数になってる。つまり、約数の数は奇数となる。

LotteryPyaterochka

5*N のグリッドから5つを選んだときに、一列に3つの数が含まれる確率を求める問題。

N>2 なら、求める条件を満たす行の組み合わせは {5}, {4,1}, {3,2}, {3,1,1} のいずれか。これを数え上げて全体の数で割ればいいはず。ただ、これに気づいたときには残り4分。

勢いで書いてビルドしてテストしたら通ったので submit。と思ったら、Easy の問題を実行していた…。よくよく調べてみたらサンプルすら通らず。なのに誰も Challenge せず。意外に気づかれなかったのか!?

DrawingBlackCrosses

見てない。

感想

Midium の問題から解けばよかったかも(?)。

2010-03-16

SRM464 DIV1

| 02:17 | SRM464 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM464 DIV1 - TopCoder煮ブログ

少し間が開いたがタイミングが合ったので参戦。

13991513 (174.86pt, 177位/776人)

○-- (challenge: 1success)

ColorfulStrings (Easy)

n 桁の colorful な数字の k 番目を求める問題。n が 2以上の場合は、同じ数字が含まれていてはだめ、01が含まれていてはだめなので、多くとも8桁までしかありえない。ということで、力技で全列挙しても問題なし。n が 1 のときは、0 や 1 を含むのを忘れずに。

全列挙してもいいことに気づいてなかったので、n が2以上のものから順番に桁を増やしつつ、DP 的に解いてみた。少し不安だったが、System Test に通って一安心。

Challenge では n が 1 のときを考えていないコードを発見して突っ込んだ。時間勝負だった模様。Yellow/Blue だけの部屋とはいえ、さすがに n=1 を考慮に入れてる人が多かった。さすが DIV1。

ColorfulDecoration

2^50 全列挙なわけもなく解けず。うわさによると2-Satらしい。

ColorfulMaze

開くだけ開いたが...

まとめ

2度目の Yellow になった。死守する。

終わったあとに http://twitter.com/kinaba/topcoder-jp を見てたら超絶高校生がいた。

No Rating -> 1934 1回でこんな上がるものなの? *Tw*

http://twitter.com/semiexp/status/10578196991

もちろん DIV2 の一位だし、DIV2 500 の問題と DIV1 250 の問題が同じで、DIV1 の誰よりも早く1位とほぼ同じタイミングで submit している。日本のTopCoder界に新星現る。日本数学オリンピックで入賞してたりする子らしい。末恐ろしい。

同級生らしき人のブログより。

(追記)出題者はhosさん

qnighyqnighy2010/03/17 18:05えーと、僕は情報オリンピックで銀、数学オリンピックで銅ですが、semiexpは情報オリンピックで金、ジュニア数学オリンピックで金なので、似たような経歴ですが違う人です。その発言をしている@semiexp(id:semiexp)がRating1934の本人で、僕は今回のSRMではだめだった人です。

nitoyonnitoyon2010/03/18 00:20コメントありがとうございます。
違う方なのはもちろん認識していたのですが、同一人物であるかのようにも読めてしまいますね。すいません。修正しておきます。
銅でもSUGE-------

qnighyqnighy2010/03/18 01:05あ、僕とsemiexpは学校も年齢も違います。

PetersonPeterson2012/07/12 17:13Keep on writing and cghuingg away!

hummughummug2012/07/12 23:46XTqPd8 <a href="http://dclheiggundu.com/">dclheiggundu</a>

ejadhaileobejadhaileob2012/07/15 06:04QV1cbq <a href="http://ovdumgmhcfnu.com/">ovdumgmhcfnu</a>

drzosmygddrzosmygd2012/07/15 11:06lUqFag , [url=http://gxmntjytgibs.com/]gxmntjytgibs[/url], [link=http://vchsycbvopnt.com/]vchsycbvopnt[/link], http://yjgbevfhszyt.com/

drzosmygddrzosmygd2012/07/15 11:07lUqFag , [url=http://gxmntjytgibs.com/]gxmntjytgibs[/url], [link=http://vchsycbvopnt.com/]vchsycbvopnt[/link], http://yjgbevfhszyt.com/

2010-02-06

SRM460

| 04:13 | SRM460 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM460 - TopCoder煮ブログ

今年最初。事前のウォーミングアップで前回の DIV2 Easy の System Test に落ちてしまって嫌な予感はしていたが。。。

14741399 (0pt, 427位/698人)

TheQuestionsAndAnswersDivOne (Easy)

一問一答インタビューで問題と答え(Yes or No)のリストを別々に作ってたけど、問題のリストがなくなっちゃった。問題は同じ問題を複数回出題していることもある。全ての問題は少なくとも1回は出題している。さて、問題のとりうる数は何通り? 問題数と回答数はいずれも 9 より小さい。

問題をなんとなく理解してからは、場合の数で解こうとするがうまくいかない。少し考えて、9^9 の総当りでチェックできるかと思いなおして白紙にして書き直す。が、やはり時間足りないんじゃないかと思って、場合の数で書き直し、やっぱり混乱して 9^9 で。気がついたら時間が終わっていた。。。

TheFansAndMeetingsDivOne (Medium)

開いて終わり。

XXXX (Hard)

見てもいない。

感想

0pt の割には rating は 1 しか下がらなかった →と思ったら激しく下がってた。

黄色になりたいなら、この問題は解けてなきゃいけないだろうな...

2009-12-23

SRM456 DIV1

| 13:06 | SRM456 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM456 DIV1 - TopCoder煮ブログ

今年最後の2週間ぶり。

13941474 (214.04pt, 191位/565人)

○-- (challenge: 1 success, 1 fail)

成績・ソース (要ログイン)

SilverDistance (Easy)

将棋の銀が目的地に到達するまで何回動かなきゃいけないかを計算する問題。日本人有利! 盤面は高々200万×200万。

引き算などを駆使して直接計算できそうだったが、計算ミスが怖かったので距離を狭める方向に移動していくループを書いて直接求めた。ただし、目的地の真上にいるような場合では回り込まないと到達できないので、下方向への移動を優先するようにした。

challenge phase では場合分けをミスってる人がいたので1人倒した。いろんな答えをみたが、人によって方針が違っていて面白い。id:chokudai 先生がこの問題、全体1位になっていて、脅威の2行コードだった。美しい。

CutSticks (Medium)

n個の棒をC回切って、K番目に長い棒の最大長を求める問題。全く方針が分からず、試行錯誤したが諦め。一番長いやつを半分にしていけばいいかと思ったが、そうじゃないケースもあって混乱して投げ出した。

challenge で半分に割ってるコードを見つけて「半分だけとは限らない。アホか」と戦いを挑んだが、アホなのは自分だった。2分探索のコードだった。2分探索で解くらしい。

FunctionalEquation (Hard)

1人しか解けてなかった。

2009-12-05

SRM454 DIV1

| 03:50 | SRM454 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM454 DIV1 - TopCoder煮ブログ

4ヶ月ぶりの参戦。いつも通りなスコア。

13731394

211.67pt (○××) 383位/699人

DoubleXor (Easy)

新しい演算子 ^^ を定義したときに N^^(N-1)^^…1 を計算しろ、という問題。左結合なので毎回計算しなきゃいけない。何か法則があるのかと悩んだが、素直に計算しても時間的に問題はなさそうだったので素直に計算して submit。211.67pt。

Challenge Phase で xor したあとに %10 するのを忘れてる人をみつけたが撃墜パターンを考えようとした瞬間に Challenge Succeeded になってて何もできなかった。同じ部屋だった id:cafelier さんがやっつけたようだ。

NumbersAndMatches (Midium)

DP っぽく解くには方針が思いつかないし、DFSっぽく解くには状態列挙で死にそうになった。1時間かけても解けないし、Challenge で他の人がどうやって解いてるのか見ても分からんし悲しい。この手の問題が解けないと yellow 浮上は遠い。

メモ:

MegaSum (Hard)

みてもいない。

2009-06-13

SRM442 DIV1

| 03:03 | SRM442 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM442 DIV1 - TopCoder煮ブログ

また2ヶ月ぶり。

13441371

184.98pt (○××) 365位/694人。

Underprimes (Easy)

素因数分解したときの要素数が素数になる数を求める問題。数は2~100,000なので一応時間には気を使う。

エラトステネスの篩で素数を列挙していく過程で「素数じゃないよフラグ」の変わりに「何個素数が含まれるか」を記録していくことにする。テストケースが通って、100,000 でも TLE にならないことを確認して Submit。

Challenge では 2~100,000 を2人に投げて1勝1敗。毎回素因数分解してる人がいて、TLE を狙ったが別に問題はなかったようだ。そこそこ力技でも解けたのか...

あとで試してみたら、確かに2~100,000のすべてを2~√100,000で割り算してもそんなに時間かからなかった。高々10万回の演算なら問題ないのか。

BedroomFloor (Medium)

5×5の網代模様のような床をつくるために必要な床材の個数を求める問題。5×5の格子点からはみ出たところは、1×5の床材を適宜カットして埋める。

境界条件が複雑すぎて能力を超える。こういうの苦手…。地頭力がないことがばれますね。

NowhereLand (Hard)

ちょっとみたけど諦め。

感想

Easy がちゃんと解けてよかった。撃墜できたけど、半分運だった気もする。

2009-04-19

SRM438 DIV1

| 03:06 | SRM438 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM438 DIV1 - TopCoder煮ブログ

2ヶ月ぶり。300点問題が予想以上にハードだった。

13221344 (0pt, 191位)

0点だったけど上がったという微妙な結果。

UnluckyIntervals (Easy)

題意をつかむのに20分ぐらいかかった。そのあと、1つずつ順番に求めていく作戦でコーディング。問題の TestCase が通ったので、そのまま submit。

Challenge Phase で勢いよく落とされる。999, 1001 で 999, 1000, 1001 の順になるということらしい。

場当たり的に求めて行く作戦はやはり弱い。ある程度かっこよく解く作戦を取れるようにならねば。

EndlessStringMachine (Midium)

s が 50 までならとけるんだろうけど、1000000000 って…。解けてる人は program で for 文まわしてた。んー、そうしなきゃいけないんだろうけど、どういうことなんだろう。

FeudaliasWar (Hard)

一瞬みてあきらめ。

2009-02-13

SRM435 DIV1

| 12:54 | SRM435 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM435 DIV1 - TopCoder煮ブログ

250 が簡単だった。落とさなかったので少し戻った。

12411326 (227.71pt, 235位)

CellRemoval (Easy)

速度は気にせず、各ノードについて「子供がいるか」「親が remove されていないか」を調べた。高々 n^2 なので余裕。

DNADeletion (Medium)

DP な気はしていたが式ができず。まだまだ鍛錬が必要。

CompanyRestructuring (Hard)

500 が解けずに一瞬見たが、500 より難しそうだったのですぐに諦め。

まとめ

250 がちゃんと解けてよかったです。

2009-02-07

SRM434 DIV1

| 04:08 | SRM434 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM434 DIV1 - TopCoder煮ブログ

だめー!! 0点

13001241

前回の善戦のおかげで、なんとか青はキープ。次はない…。

FindingSquareInTable (Easy)

ループが入り組んで混乱して諦めた。変に最適化しようとしてしまったが、素直に4重ループ書けばよかったようだ。最初に方針を決めなきゃな、と痛感。実力不足です…。

HexatridecimalSum (Medium)

  • 最初、10進数に戻すコードを書いていたが、明らかに 36^50 が long long に収まりきらない
    • 文字のままがんばらなきゃいけない。
  • 桁が上のものから Z に置き換えていくようにすればいいことに気づく。
  • Test Case 2 が通らない
  • 最後の加算するコードに誤りがあると信じてデバッグ
  • ダメ
  • 時間切れ
  • あとで確認したら、同じ数字は全部置き換えるところを忘れてた!

んー。解けたはずなのに悔しい。

時間がかかったのは、上の桁から判定していく作業。i と s.size() - i が大量に出てきて混乱してしまった。上位の人の答えを見てテクニックを盗む。

XXXXXX (Hard)

見てない。

まとめ

反省点が多い。

GeralynGeralyn2011/07/10 04:08Your article perfectly shows what I needed to know, thakns!

rxpneerxpnee2011/07/10 16:28L6LbkJ <a href="http://dkbiqormanar.com/">dkbiqormanar</a>

znawihcgznawihcg2011/07/11 19:28rd9Sbw , [url=http://dmalqhfjjmxd.com/]dmalqhfjjmxd[/url], [link=http://tjjlgywwhmkh.com/]tjjlgywwhmkh[/link], http://tusvscmndbip.com/

eveflytxeveflytx2011/07/12 17:29VCVOJ4 <a href="http://rohqyiocswre.com/">rohqyiocswre</a>

ltquhxgltquhxg2011/07/12 22:02dtGtLV , [url=http://dzarhwolpmbn.com/]dzarhwolpmbn[/url], [link=http://gnnspdoegvwz.com/]gnnspdoegvwz[/link], http://ltsooreekkfx.com/

2009-01-22

SRM433 DIV2

| 10:01 | SRM433 DIV2 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM433 DIV2 - TopCoder煮ブログ

やっと DIV1 に戻れた…。

oxo + 2 * 50 - 1 * 25

11361300

なんと DIV2 で5位。SRM433 Overview のページにも自分の名前が…!

RoyalTreasurer (Easy)

sort して計算して終わり。int でも問題なし。

MagicWords (Medium)

8 だから行けるかと思って next_permutation して計算。一応メモ化しておいた。Challenge Phase ではメモしてない2つを蹴落とした。そのあと、System Test 失敗。TLE ではなかったから、ロジックのミスなのかなぁ。あとで。

MakingPotions (Hard)

商品の交換レートが決まってるので LOVE を手に入れるにはいくらかかる?という問題。数式のパースに手間取ったが、面白い問題だった。

DP かと思ったけど思いつかなかったので泥臭く実装。デバッグに手間取って諦めかけたが、終了間際に問題の Test Case を全部通ったので勢いで Submit。そのまま System Test にも通った。

感想

DIV1 でがんばるぞー

2009-01-07

SRM432 DIV2

| 15:30 | SRM432 DIV2 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM432 DIV2 - TopCoder煮ブログ

気づかなかった。TopCoder Open in 2009のメールは来てたけど、SRM の通知は届かなかったぞ?

KaleighKaleigh2011/07/22 22:40This article ahcieved exactly what I wanted it to achieve.

zfheyhxzfheyhx2011/07/23 17:29Se43py <a href="http://vmwznwwadodd.com/">vmwznwwadodd</a>

jyjyozjparjyjyozjpar2011/07/23 22:14Y5NYXE , [url=http://pkdnrubsxigg.com/]pkdnrubsxigg[/url], [link=http://dsgtnofwuklq.com/]dsgtnofwuklq[/link], http://ydxgxqliwsxo.com/

zyynmjpdazyynmjpda2011/07/25 21:35DAcasi <a href="http://nwntvgsssznt.com/">nwntvgsssznt</a>

xqtexmjkwzxqtexmjkwz2011/07/26 00:57wkX3mk , [url=http://fivzffwazwyz.com/]fivzffwazwyz[/url], [link=http://lmbouqeprmwa.com/]lmbouqeprmwa[/link], http://cmczbpqluwvp.com/

2008-12-25

SRM431 DIV2

| 23:15 | SRM431 DIV2 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM431 DIV2 - TopCoder煮ブログ

まだ DIV2...

11361168 (oox)

500点問題に不備があったので Rate は反映されないらしい(Div-II will not be rated

MegaCoolNumbersEasy (Easy)

最初の20分ぐらい、間違えて SRM430 DIV1 Hard の問題を解いていた。なんかおかしいと思ってよく見たら問題を間違えていて、解きなおしたらすごく簡単だった。イージーミスが多いのう…。char[3] に4文字書き込んでしまっていたが、System Test は通った。よかった。

FallingPoints (Medium)

題意を掴みづらかったが分かれば簡単。

SumAndProduct (Hard)

むずい。素因数分解したがそこから先が。どうやら、相加相乗平均の定理を使うらしい。なるほどなー。気づかないよ・・・。

感想

DIV1 で年を越したかった…。DAMEPO

2008-12-20

SRM430 DIV2

| 04:48 | SRM430 DIV2 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM430 DIV2 - TopCoder煮ブログ

10091136 (○xx)

DIV1 に戻れなかった…。

CreateGroups (Easy)

DIV2 の Easy でしょ、簡単でしょ、と思ったが甘くて少し悩む。250点じゃなくて275点問題なだけはある。とはいえ楽勝。他の人に比べてあまりきれいじゃないけど泥臭く解いた。OK。

BitwiseEquations (Medium)

n のビットが立ってるところを左にシフトしてやればおk。勢いよく書いてsubmitしてよゆーじゃん、と思ってたらSystem Testで落ちた。(k & 1) << n といったコードを書いていて、k が int であったために 32bit shiftになっていた。((long long)k & 1) << n として System Test に成功することを確認。うー…。shinhさんに倣って書き取り練習を敢行する。

long long long long long long long long long long long long long long long long long long long long long long long long long long long long long long long long long long long long long long

1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL

ImageTraders (Hard)

絵が順番に色んな人の手元を渡っていく中で、最大何人の手に渡るかを求める問題。普通に深さ優先探索して submit したんだけど、最悪の場合に 14! になって実行時間がひどい。メモ化して resubmit した。Challenge Phaseではメモ化してない人を2人やっつけた。

いい気になってSystem Testの結果をみたら落ちてる。メモ化するときのパラメータが不足していたようだ。購入済みの人、現在の値段だけをキーにしてメモしていたが、最後に購入したのが誰なのかもキーにする必要があった。そういえばそうだなぁ…。あーーーー。あと一歩だったのに。

2008-12-11

SRM429

| 01:08 | SRM429 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM429 - TopCoder煮ブログ

Regiter 逃した…。ショック。

2008-12-02

SRM428 DIV1

| 23:51 | SRM428 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM428 DIV1 - TopCoder煮ブログ

-50pt。しぼー

13641099

一気に落ちたな…。DIV2 で修行してきます…。

f:id:nitoyon:20081203005133j:image

TheLuckyString (Easy)

next_permutation を使うコードは一瞬でできたんだけど、手元で10秒たっても帰ってこなかったので別の方法を考えることに。いろいろ悩んで高速化して、Submit。Challenge では next_permutation を使ってる人を撃墜しにかかったら2回連続失敗。よく考えたら、手元では Debug 版でビルドしてた。最適化してビルドしたら余裕で時間内に終わりやがる。結局自分のソースは System Test で落ちて -50pt。ま、next_permutation 使ってたとしても、事前に sort するの忘れてたので結局同じような結果になってただろう。

TheLongPalindrome (Medium)

これ分からんなー。n がでかいからどうしようもないので、k でループする方法を考えたが思いつかん。

TheStringGame (Hard)

終了間際に読みかけたが、同じ部屋に Submit している人がいなかったのでやめ。

教訓

  • 最適化オプションはONに
  • next_permutation の前に sort

CynthiaCynthia2012/07/12 13:44I'm impressed by your writing. Are you a profsesoinal or just very knowledgeable?

zntishlzntishl2012/07/12 23:22ffVL8d <a href="http://qztfougzgfzq.com/">qztfougzgfzq</a>

anfabjanfabj2012/07/15 02:59YAp5V0 <a href="http://rezjmaqxnqov.com/">rezjmaqxnqov</a>

jypuczajypucza2012/07/15 10:42S5trWw , [url=http://qkujzogwyobf.com/]qkujzogwyobf[/url], [link=http://plidwzjoiafl.com/]plidwzjoiafl[/link], http://gfqueuecdrab.com/

2008-11-27

SRM 427 DIV1

| 23:40 | SRM 427 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM 427 DIV1 - TopCoder煮ブログ

600と900がいいところまでい行った気がしたのが嬉しかった。

12971364

DesignCalendar (Easy)

よく分からんが GCD っぽくねーと思って適当に数式こねくり回したら例題が全部解けるようになったので勢いで Submit。そのまま System Test も通って212.32pt。

LocateTreasure (Medium)

できたーと思ったんだけど、Challenge された。むうー。あとで。

PSequence (Hard)

あと数秒でできたのに…と思ってあとで System Test に通したら時間オーバー。適当に状態を記憶すべきだったようだ。でもあとちょいな感じ。

2008-11-23

SRM426 DIV1

| 21:33 | SRM426 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM426 DIV1 - TopCoder煮ブログ

コンディションは悪くなかったが、しばらく練習をサボっていたため、STL の使い方を忘れかけていて、てこずってしまった。。

13161297

下がり続けて DIV2 が見えてきた…。

ShufflingMachine (Easy)

問題文の解読に20分、方針の決定に10分、コーディングに20分。圧倒的に時間がかかりすぎ。特に、K の意味が分からず悩みこんでしまったのが痛い。コーディングではソーティングする方法が思いつかず、10分近く悩んでしまった。結局、勢いで書いて提出。

CatchTheMice (Medium)

20分でできるか厳しかったが一応考えた。最初、時間が離散かと思ったんだけど、連続値でもよいようなので2分探索でいけそうだなー、と思った時点で残り1分。時間があれば解けてた気はするが、残り1分ではさすがにどうしようもない。Challenge Phase で探索開始の時間が小さすぎる人はいないか探したがさすがにいなさそうだった。

LongStraightRoad (Hard)

開いてない

NenaNena2012/07/09 18:17Holy szhinit, this is so cool thank you.

myjntlubvmyjntlubv2012/07/10 15:12pP8p09 <a href="http://emyrrezppwtn.com/">emyrrezppwtn</a>

yjwtloktfyjwtloktf2012/07/10 21:08uPae9E , [url=http://dfovrmtqqutv.com/]dfovrmtqqutv[/url], [link=http://kunyabzuxwtl.com/]kunyabzuxwtl[/link], http://razvjxyefmyq.com/

uzptkpuuzptkpu2012/07/12 11:308nPvsa <a href="http://baktotvunyqs.com/">baktotvunyqs</a>

buyjeditvnbuyjeditvn2012/07/12 16:59oNsgh1 , [url=http://lhqumtwvbhga.com/]lhqumtwvbhga[/url], [link=http://zrrhwdscshfm.com/]zrrhwdscshfm[/link], http://jqirnpmdwmzq.com/

2008-11-12

SRM425 DIV1

| 02:55 | SRM425 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM425 DIV1 - TopCoder煮ブログ

とても眠いという最悪のコンディションで迎え、頭が回らなかったので途中で諦めて風呂に入った。

0pt だけど思ったほど下がらなかった。

14231316

CrazyBot

4^14 と微妙だけど、途中でだめなルートが増えてくるからなんとかなるかなーと思って再帰で書いたけど、test case 4 が時間内に終わらず、いい方法あるんかねーと悩んだが思いつかず諦め

stl::set 使ってたが、配列に書き直したらすんなりいった。要素数が最大14なんだからset使う意味はないわな。

PiecesMover

xy平面苦手ー

RoadsOfKingdom

問題名がかっこいい。

2008-11-06

SRM424 DIV1

| 23:06 | SRM424 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM424 DIV1 - TopCoder煮ブログ

500点問題に壁を感じますね。

222.43pt - 25pt = 197.33pt。

14591423

微減。

ProductOfDigits

√n まで回すの? どうするの? と思ったが、2ケタ以上の値で素因数分解できた段階で -1 だと確定するので、2,3,5,7 でひたすら割ればよし。最後に、8(=2*2*2) と 9,6,4 の数を調整して submit。9から2まで割っていけばそんなめんどくさいことしなくても解けた模様。ついつい素数にとらわれてしまった。

StrengthOrIntellect

いけたと思ったが && と || を勘違いして失敗。修正して System Test が通ったとしたら痛すぎる。→と思ったら最悪時に2^50になってた。ダメだー。

ProductOfPrices

20万個の要素の差分をどうやって計算するのかが思いつかない。

ShannaShanna2011/07/09 17:38Great stuff, you hpeeld me out so much!

hzysanzhzysanz2011/07/10 00:53lkLGDS <a href="http://ehvmspmmwiiu.com/">ehvmspmmwiiu</a>

vpzbwuivpzbwui2011/07/10 21:17PXq8a1 , [url=http://hzpblwtuqbzv.com/]hzpblwtuqbzv[/url], [link=http://vlanpfyetnvc.com/]vlanpfyetnvc[/link], http://zdsalmvcjbiw.com/

sdpbxnsrdbsdpbxnsrdb2011/07/11 20:25IiILLo <a href="http://szkkohahdbur.com/">szkkohahdbur</a>

iasbeyiiasbeyi2011/07/12 21:49MVbYP8 , [url=http://ftptvqzwxyfg.com/]ftptvqzwxyfg[/url], [link=http://jpxfjmjgmdwe.com/]jpxfjmjgmdwe[/link], http://ysgjwwenwmpy.com/

ANdresANdres2013/02/18 00:59This is a rlealy intelligent way to answer the question.

esljbeynesljbeyn2013/02/21 12:46Zgb7Bc <a href="http://gnxzctwhcgaf.com/">gnxzctwhcgaf</a>

uxbodmojquxbodmojq2013/02/21 17:11hgdSJa , [url=http://xzcnkwaorkhz.com/]xzcnkwaorkhz[/url], [link=http://icyjaaeecqgl.com/]icyjaaeecqgl[/link], http://thlomltijlcz.com/

2008-10-29

SRM423 DIV1

| 11:56 | SRM423 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM423 DIV1 - TopCoder煮ブログ

撃沈。むずい。

15141459

0点だからしかたなし。

TheTower

題意がつかめず撃沈。普通に解いても爆発するので、何らかの工夫が必要なんだろうが思いつかん。

TheEasyChase

素直に書いてみたが何らかのバグがあり撃沈。たぶん、バグがなくても時間内に終了しなかったと思われる。

(追記) 結果がでたあとに、同じ room 内の人に適当に自分が考えた Test case(盤面が20x20で適度に追いかけっこが発生するもの)を与えると撃沈した。ダメもとで乱発すればよかったのかもしれん。

TheBeautifulBoard

一瞬見たが諦め。

2008-10-19

SRM422 DIV1

| 03:28 | SRM422 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM422 DIV1 - TopCoder煮ブログ

250 と 500 を解けたつもりになったが、500 を Challenge された。全体的に点数が低めだったらしく、ついに Yellow に!

14601514

SRM 422 DIV1 全体では312位、TopCoder 全体では1132位。

PrimeSoccer

14分で解いて204pt。組み合わせを求めるところで時間かかってしまった。パスカルの三角形使うのがシンプルなのかなぁ。対偶で計算したけど、そのまま求めている人も多かった。

→上位の人は1回のインターバルで0回入る確率から順番に、n回のインターバルでどうなるかを順番に求めていってる。動的計画法か。

CavePassage

最大で N=13 ってことは 2^N * N^3 のアルゴリズムだったとしても高々10^7ぐらいなので力技コース。がんばって書き下したつもりだったが、詰めの甘さを発揮して Challenge で追撃された。思い当たる節を修正して System Test に提出してみたがやっぱり撃沈。根本的にどこかでバグがあるようだ。

(追記) 分かった。行った人と違う人が帰ってきてもいいのか! 自分の方針だと、{{3, 3, 6}, {1, 1, 1}, {"YYY", "YYY", "YYY"}, 6} が -1 になる。しかも、帰ってくる人が複数の場合もある。これは想定外!

WorkersOnPlane

見てすらいない。

感想

500を解きたかった…。が、今の実力ではこれは無理だ…。

今回から、TopCoder部 - ハチロク世代Skype chat に参加してみた。楽しい。

2008-10-09

SRM421 DIV1

| 02:02 | SRM421 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM421 DIV1 - TopCoder煮ブログ

250と500を解けたつもりになったが、250 が System Test で落ちた。

12681460

うっひょい。250 が行けてたら、Yellow だったなぁ…。

EquilibriumPoints

ちょっと時間かかった。計算式はあっていたが、誤差以内に収まるかどうかをきちんと検証していなかったので System Test に落ちた。

両端の差が 1e-9 以下になるまで半分ずつつめて行く必要あり。100回ループ回してる人もいた。1000/2^100 は 1e-9 以下になるのは当たり前。そういう概算に強くならねば。

CakesEqualization

20分ぐらい戦略誤って解いていて、諦めかけた瞬間にひらめいた。最初にひらめいてれば、あと15分は縮められたはず…。

TeamManagement

残り10分ぐらいで問題だけみた。友達関係をグラフに見立てて、深さ優先で探索していけばいいような気がする。あとで。

感想

初めて DIV1 の 500 が解けた! 250 も解けてれば、レートがかなり上がっただろうに。残念。

2008-10-03

SRM420 DIV1

| 21:27 | SRM420 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM420 DIV1 - TopCoder煮ブログ

1問だけ解けた。

12421268

SolitaireSimulation

前回 0 だったので、慎重に解いたら18分かかった。ostringstream を初めて使ったり、multiset を初めて使ったりしてるうちに、時間を浪費してしまった。上位の回答を見ていると、vector を std::sort してそのまま使ってる人が多い。ふむふむ。

RedIsGood

なんか難しそうだったのでパス。意外に解けてる人が多かった。あとで。

ChangeOMatic

簡単そうに見えて挑戦するも、時間内に解けず。遅い。トップダウンで方針は決定したものの、ボトムアップで書いて悩んでるうちに、全体を見失って混乱してしまった。あとで。

感想

DIV1 の 500 を解けたことがない。そこを解けるようにならないと、yellow は遠い。

2008-09-26

SRM419 DIV1

| 20:27 | SRM419 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM419 DIV1 - TopCoder煮ブログ

3回目。一問も解けなかった…。

1388 -> 1242

なんとか DIV1 に残ってる。

Undo

勢いよく書いたら境界条件でしくっていて、Challenge で撃墜された。

さすが、DIV1。ミスへのツッコミが厳しい。どちみち、System Test で失敗してたけど。

NimForK

しばらく悩んだが、紙に状態を書き出したら方針が見えてきた。が、時間切れ。

CactusAutomorphisms

ちょっと見たがすぐに諦め。4人しか解かず、正解した人は1人。

2008-09-21

SRM418 DIV2

| 14:07 | SRM418 DIV2 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM418 DIV2 - TopCoder煮ブログ

2回目。

1193 -> 1388

DIV2 で23位で blue coder へ。次回からは DIV1 だ!

Towers (250pt)

設問意図をつかむのに少し手間取ったが、分かってしまえば素直に書けた。201.48pt

TwoLotteryGames (500pt)

文章が短い。nCm の組み合わせを求めるときに、1 << n を for で回してみた。あとで見たら、他の人も同様の戦略を取っていたようだ。422.16pt

(追記) DIV1 の1問目と同じ。DIV1 の人の回答をいくつか見たが、パスカルの三角形を使って二項係数を求めていた人や、自分と同じ戦略ながら __builtin_popcount を使ってビット数をカウントしてる人もいた。__builtin_popcount は g++ の内部関数の模様。ずるいので、VC++ に移植して手元でビルドが通るようにしておくとよさげ。

template<class T> inline int __builtin_popcount(T n){return (n==0)?0:(1+__builtin_popcount(n&(n-1)));}

BarracksEasy (1000pt)

例題を解くための戦略を決めて解くコードは書いて送信。700pt ほどで成功したが、System test で失敗。総当りで調べるべきだった。正答率は 12.26% とかなり低め。

(追記)総当りにしたら成功した。ちなみに、DIV1 の問題は同じ問題の上限が50→5000に増えたバージョン。こうなると総当りは不可。

[Topcoder] SRM 418 DIV 2 - いそっちノート に一発で解く方法が載っているが、実は、この解法では DIV1 の System Test に失敗した。どのタイミングで bar を倒すかを場合分けしなきゃいけないようだ。DIV1 は奥が深い…。

1位の人の回答を見た。驚くほどすっきりしている。すげーなー。

2008-09-12

SRM417 DIV2

| 09:54 | SRM417 DIV2 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM417 DIV2 - TopCoder煮ブログ

初参加。

0 -> 1193

ReversedSum

逆順にするところでちょっと悩んだが瞬殺。240.19pt。

TemplateMatching

意味がつかめず撃沈。あとで。0pt。

TripleJump

一様分布を2回実施したときの分布の算出に手間取って時間切れ。集計中にやっと解けた。精進が必要。0pt。