Hatena::Grouptopcoder

TopCoder煮ブログ

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

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-07

StrengthOrIntellect (SRM424 DIV1 Medium)

| 23:57 | StrengthOrIntellect (SRM424 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - StrengthOrIntellect (SRM424 DIV1 Medium) - TopCoder煮ブログ

HPとMPがあってレベルアップのときにどう振り分けるか、みたいな問題。現在の strength と intellect が分かれば、そこから余剰ポイントと通過したミッションが定まるのでそれをベースに次の状態を求めていけることに気づいた。最悪時に同じ計算を何度もやってしまっていたので、メモして高速化してみたら、難なく System Test に通った。一応ソースを貼っておこう。

#include <vector>
#include <iostream>
using namespace std;

template<class T> inline int count_bit(T n){int r=0;while(n > 0){if(n&1)r++; n>>=1;}return r;}
int visited[1001][1001];

class StrengthOrIntellect {
public:
    int N;
    vector<int> SV, IV, PV;

    int solv(int S, int I){
        S = min(S, 1000);
        I = min(I, 1000);
        if(visited[S][I]) return visited[S][I];

        int points = 0;
        long long state = 0;
        for(int i = 0; i < N; i++){
            if(S >= SV[i] || I >= IV[i]){
                state += (1LL << i);
                points += PV[i];
            }
        }
        points = points - (S + I) + 2;

        int Smin = (int)1e9, Imin = (int)1e9;
        int Sind, Iind;
        for(int i = 0; i < N; i++){
            if((state & 1LL << i)) continue;
            if(Smin > SV[i]){Smin = SV[i]; Sind = i;}
            if(Imin > IV[i]){Imin = IV[i]; Iind = i;}
        }

        int ret = 0;
        if(points > 0 && Smin <= S + points){
            ret = max(ret, solv(Smin, I));
        }
        if(points > 0 && Imin <= I + points){
            ret = max(ret, solv(S, Imin));
        }

        return visited[S][I] = max(ret, count_bit(state));
    }

    int numberOfMissions(vector <int> strength, vector <int> intellect, vector <int> points) {
        N = strength.size();
        SV = strength;
        IV = intellect;
        PV = points;
        memset(visited, 0, sizeof(visited));
        return solv(1, 1);
    }
};

ただ DP で解いたほうが全体的にすっきりとしたソースになる。

VrmanVrman2012/07/10 01:49Whoever edits and publishes these atrilces really knows what they're doing.

itdcbmoevcitdcbmoevc2012/07/10 16:018wcDPn <a href="http://xkevcdxqtevw.com/">xkevcdxqtevw</a>

nsyzafooknsyzafook2012/07/12 12:18x6IGQS <a href="http://ucopfphvzofe.com/">ucopfphvzofe</a>

gojwfkgojwfk2012/07/12 17:48qezOlz , [url=http://ezuzdkbwcdug.com/]ezuzdkbwcdug[/url], [link=http://vdrugwwanyht.com/]vdrugwwanyht[/link], http://qbsozmxyjucd.com/

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-11-04

MaximumScoredNumber (SRM411 DIV2 Easy)

| 04:22 | MaximumScoredNumber (SRM411 DIV2 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - MaximumScoredNumber (SRM411 DIV2 Easy) - TopCoder煮ブログ

一瞬解けるんかいなと思ったが、sqrt を使えばいいことに気づいたら簡単だった。C++1位の人はもっと直接的に解いていた。O(n^2)程度なので n=10,000 なら余裕か。

LavarLavar2011/07/07 19:45I really neeedd to find this info, thank God!

vtxuruwvtxuruw2011/07/08 16:23W8foYR <a href="http://fbzjugefrypx.com/">fbzjugefrypx</a>

rcjfgipwrrcjfgipwr2011/07/09 22:12j5N45a , [url=http://sfijtazljxpz.com/]sfijtazljxpz[/url], [link=http://aayhcgqhudlf.com/]aayhcgqhudlf[/link], http://mntipnbnqluv.com/

hgtsmuxihgtsmuxi2011/07/10 18:45QqkhTz <a href="http://zxboumqybhoc.com/">zxboumqybhoc</a>

vgxjzaivgxjzai2011/07/11 23:57jZkxIe , [url=http://zlppcqjmqkxg.com/]zlppcqjmqkxg[/url], [link=http://thkrfjumvsvr.com/]thkrfjumvsvr[/link], http://zpdctbjhrccx.com/

2008-11-02

ContiguousCache (SRM410 DIV1 Medium)

| 22:06 | ContiguousCache (SRM410 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - ContiguousCache (SRM410 DIV1 Medium) - TopCoder煮ブログ

見当がつかないので解答をみる。DPな問題はどうも発想方法が分からん。ソースを読んでもしばらく理解できず。1度キャッシュした場所はずっとキャッシュされ続けているかと勘違いしていて余計に時間かかった。なんとなく理解できたが書ける気がしない。Read開始アドレスが addresses もしくはそこから K - 1 を引いたもののどちらかでよい、というところがいまいちしっくり来ない。

ContiguousCache2 (SRM410 DIV2 Easy)

| 23:29 | ContiguousCache2 (SRM410 DIV2 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - ContiguousCache2 (SRM410 DIV2 Easy) - TopCoder煮ブログ

ContiguousCache に苦戦したので憂さ晴らしに ContiguousCacheEasy にチャレンジ。簡単に解けるはずが、場合別けとアドレスの演算に苦戦して時間かかってしまう。解けたことは解けたけど…。

ClosestRegex (SRM410 DIV2 Hard)

| 00:29 | ClosestRegex (SRM410 DIV2 Hard) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - ClosestRegex (SRM410 DIV2 Hard) - TopCoder煮ブログ

text に最も近い正規表現にマッチするものを求める問題。正規表現は50文字までなのだけど、"a*b*c*d*..."のようなパターンだと正攻法で解いたら計算時間がひどいことになる。それを解決するためには、おそらく DP でなんとかするんだろうが、やっぱりひらめかない。DP 弱い。Match EditorialsDynamic Programming: From novice to advancedというリンクが。おお、こんな素敵なチュートリアルがあったのか! 他にも左メニューの「Algorithm Tutorials」には魅力的な文章がいくつも。このあたりをまずは一読しておくとよさそうだ。

一読して、そのあとにしばらく考えたらひらめいた。DP[i]には文字数が i の正規表現のうち、text にマッチする数が最小となるものを保存すればよい。atomでforを回して、DP[i] を更新していく。atom が * の場合には DP[i] を右短まで更新して、* がない場合には1つ進める。例えば、1) の例だと、最初の t* を解釈したときの DP は次のようになる。

DP[0]: 0  // ""
DP[1]: 0  // "t"
DP[2]: 1  // "tt"
DP[3]: 2  // "ttt"
DP[4]: 3  // "tttt"
DP[5]: 4  // "ttttt"
DP[6]: 5  // "tttttt"
DP[7]: 6  // "ttttttt"
DP[8]: 7  // "tttttttt"

次の p を解釈したらこうなる。

DP[0]  ∞ // ""
DP[1]  1  // "p"
DP[2]  1  // "tp"
DP[3]  1  // "ttp"
DP[4]  3  // "tttp"
DP[5]  4  // "ttttp"
DP[6]  5  // "tttttp"
DP[7]  6  // "ttttttp"
DP[8]  7  // "tttttttp"

DP[0] はありえないので∞にしている。こんな感じで続けていけばおk。

2008-11-01

表記変更

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

いままでは「SRM 423」のように書いてたけど、「SRM423」(SRM と数字の間にスペースを入れない)ほうが一般的なようなので、そっちに書き換えた。

TheEasyChase (SRM423 DIV1 Medium)

| 13:04 | TheEasyChase (SRM423 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - TheEasyChase (SRM423 DIV1 Medium) - TopCoder煮ブログ

最初は再帰で書いてたけどおそらくオーバーフロー。いろいろ考えたが方針が見えず、C++ 一位の人の回答を見る。解けた場所からスタートして行って、順番に移動量を逆算していってる。どちらが勝つ場合も同じアルゴリズムでいけてしまうようだ。そういわれてみればそういう気もするが理由がしっくり来ない。

復習

20:25 | 復習 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - 復習 - TopCoder煮ブログ

SentenceDecomposition (SRM411 DIV1 Easy)を再度解いてみる。そのまま解いてもダメだろうと思ってしばらく悩んで思い出した。復習しやすいように問題の記録をとっておくとよいんだろな。

AddElectricalWires (SRM410 DIV1 Easy)

| 23:06 | AddElectricalWires (SRM410 DIV1 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - AddElectricalWires (SRM410 DIV1 Easy) - TopCoder煮ブログ

時間はかかったが System Test OK。部分グラフを完全グラフにするまでに必要な枝数をカウントすればよい。gridConnections を含まない部分グラフはノード数が最大の部分グラフに併合する。C++1位の人の答えで答えあわせしたところ、順番に足していっていた。自分の回答は完成図の枝数から最初の枝数を引いていたが、1位の人のほうがスマートだ。あと、グループ分けするときに、自分の回答では幅優先探索していたが、1位の人は頂点の数だけループを回して浸透させていく方式を使っていた。時間が問題にならないのならこっちのほうがシンプルに書ける。