Hatena::Grouptopcoder

TopCoder煮ブログ

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

2009-12-05

MazeMaker (SRM453.5 DIV1 Easy)

| 01:12 | MazeMaker  (SRM453.5 DIV1 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - MazeMaker  (SRM453.5 DIV1 Easy) - TopCoder煮ブログ

本番前の練習。あらかじめ与えられた迷路とスタート地点でどこにゴールを設置するとクリアに時間かかるようになるか。迷路をうろつく人の移動パターンがあらかじめ与えられている。

当然、総当りはダメなので悩んだが、スタート地点固定で最大距離を求める、ということなのでダイクストラ法で解けることに気づいた。あとは書いていくだけ。Row/Column を x/y に置き換えて書き始めてしまってかえって混乱してしまった。ダイクストラは queue 使えば簡単だということを覚えてたので TopCoder やる前よりかは早く書けるようになってるかも。

無駄は多かったが 264.75pt/500.0pt の時間で submit(DIV2 Midium のほうで解いたので)。System Test も一発で通った。C++ 一位の人のソースと見比べたらシンプルさでは負けるものの方向性は同じだった。

2009-08-18

SoldierLabeling (SRM446 DIV2 Easy)

| 23:26 | SoldierLabeling (SRM446 DIV2 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SoldierLabeling (SRM446 DIV2 Easy) - TopCoder煮ブログ

本番前の練習。指定された桁の数を数える問題。力ずくか悩んだけど、pow() して引き算すればいいと気づいて書く。-1 や +1 する条件が分からず試行錯誤。うまくいったコードで submit。こういうのを一発では思いつける人がうらやましい。234.26pt/250.0pt で System Test OK。ま、DIV2 の問題ですし。

(追記)正答者のソースみたら力ずくで計算しても間に合ったようだ。そんなものか。

2009-06-13

PaperAndPaintEasy (SRM441 DIV2 Medium)

| 02:50 | PaperAndPaintEasy (SRM441 DIV2 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - PaperAndPaintEasy (SRM441 DIV2 Medium) - TopCoder煮ブログ

本番前の練習。折り紙して色を染めたら、染められていない点はいくつ残るか、という問題。

色を塗る範囲が rectangle ではなくて点だと思って結果が合わずに悩む。x 方向で折るときに、左側の方が大きくなるケースが抜けていて悩む。

問題文をしっかり読まねば。。。

2009-01-19

GroupedWord (SRM432 DIV1 Medium)

| 00:27 | GroupedWord (SRM432 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - GroupedWord (SRM432 DIV1 Medium) - TopCoder煮ブログ

泥臭い方法しか思いつかなかったので泥臭く解いた。単語ごとに含まれる文字と先頭・末尾の文字を記憶しておく。

struct WORD{
    int flag;   // 含まれる文字
    int s;      // 先頭の文字
    int e;      // 末尾の文字
    string str; // 文字列全体
};

parts として与えられたものを WORD に変換して、適宜結合していきつつ、最終的に2つ以上残れば MANY、1つなら str を返すようにする。

Test case は全部通ったので、Submit したら System Test Failed。aab, bbb, bc のときに、aab と bc を先に結合していたので、aabc と bbb を IMPOSSIBLE と判断してしまっていた。ロジックをちょっと修正して、同じ文字だけで構成される part を最初に結合していくようにしたら通った。

C++ 一位の人の解も同じ感じの解き方のようだ。join1 で bbb を先に結合して、その後に通常の結合を実施していた。よく思いつくなぁ。

以下、自分の解。恥ずかしいぐらいに長い。

#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
using namespace std;

struct WORD{
    int flag;
    int s;
    int e;
    string str;
};

class GroupedWord {
public:
    WORD parseWord(string s){
        WORD w;
        w.str = "";

        w.flag = 0;
        char c = 0;
        for(int i = 0; i < s.size(); i++){
            if(c == s[i]) continue;
            c = s[i];
            int cf = 1 << (c - 'a');
            if(w.flag & cf) return w;
            w.flag += cf;
        }
        w.s = 1 << (s[0] - 'a');
        w.e = 1 << (s[s.size() - 1] - 'a');
        w.str = s;

        return w;
    }

    string restore(vector <string> parts) {
        int N = parts.size();
        vector<WORD> words(N);
        for(int i = 0; i < N; i++){
            words[i] = parseWord(parts[i]);
            if(words[i].str == "") return "IMPOSSIBLE";
        }
        for(int i = N - 1; i >= 0; i--){
            if(words[i].s == words[i].e){
                for(int j = 0; j < words.size(); j++){
                    if(i != j){
                        if(words[i].s == words[j].s){
                            words[j].str = words[i].str + words[j].str;
                            words.erase(words.begin() + i);
                            break;
                        }else if(words[i].s == words[j].e){
                            words[j].str += words[i].str;
                            words.erase(words.begin() + i);
                            break;
                        }
                    }
                }
            }
        }

        for(int i = 0; i < words.size() - 1; i++){
            for(int j = i + 1; j < words.size(); j++){
                int dup = words[i].flag & words[j].flag;
                if(dup == 0) continue;
                if(__builtin_popcount(dup) > 1) return "IMPOSSIBLE";

                WORD w;
                if(dup & words[i].s && dup & words[j].e){
                    w = parseWord(words[j].str + words[i].str);
                }else if(dup & words[j].s && dup & words[i].e){
                    w = parseWord(words[i].str + words[j].str);
                }else{
                    return "IMPOSSIBLE";
                }

                words.erase(words.begin() + j);
                words.erase(words.begin() + i);
                words.push_back(w);
                i = -1;
                break;
            }
        }

        return words.size() == 1 ? words[0].str : "MANY";
    }
}

2009-01-07

GroupedWordChecker (SRM432 DIV2 Easy)

| 21:43 | GroupedWordChecker (SRM432 DIV2 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - GroupedWordChecker (SRM432 DIV2 Easy) - TopCoder煮ブログ

一瞬、意味が分からなかったが分かってしまえば簡単。そのまま。

LampsGrid (SRM432 DIV2 Medium)

| 23:47 | LampsGrid (SRM432 DIV2 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - LampsGrid (SRM432 DIV2 Medium) - TopCoder煮ブログ

格子状のランプでなるべく多くの行を点灯させようという問題。ON/OFF は列ごとに行う。

2^50 の総当りだと時間足りないし、かといって点灯回数は1000とこちらも総当りは無理そう。

しばらく考えて、行ごとに点灯するときのパターンが固定だと気づいた。パターンごとに何行あるかを map に格納して、key ごとに K 回の点灯で実現できるかを調べていけばよい。

ゆっくり解いて30分ぐらい。集計と測定でループを2回書いたけど SRM432 - naoya_t@topcoderで紹介されていたコードは短い。確かに1回でいけますな。

一応自分のコード。

    long long L[50];
    int N = initial.size();
    int M = initial[0].size();
    map<long long, int> score;
    for(int i = 0; i < N; i++){
        L[i] = 0;
        for(int j = 0; j < M; j++){
            L[i] <<= 1LL;
            L[i] += (initial[i][j] == '0' ? 1 : 0);
        }
        score[L[i]]++;
    }

    int ret = 0;
    for(map<long long, int>::const_iterator p = score.begin(); p != score.end(); p++){
        if(ret > p->second) continue;
        int c = countbit(p->first);
        if(c == K || (c < K && (c - K) % 2 == 0)){
            ret = p->second;
        }
    }
    return ret;

ソートするかなーと思って、配列 L に格納したけど不要だった。

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/

2009-01-03

LaserShooting (SRM431 DIV1 Easy)

| 16:59 | LaserShooting (SRM431 DIV1 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - LaserShooting (SRM431 DIV1 Easy) - TopCoder煮ブログ

各所で簡単だと書かれていたが確かに簡単だった。ゆっくりやって231pt。System Test も一発OK。

PIをacos(-1)から求めたが、M_PI を使うとよさそう。Visual C++ では #define _USE_MATH_DEFINES してから math.h をインクルードする必要がある。

#define _USE_MATH_DEFINES
#include <math.h>

MegaCoolNumbers (SRM431 DIV1 Medium)

| 19:17 | MegaCoolNumbers (SRM431 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - MegaCoolNumbers (SRM431 DIV1 Medium) - TopCoder煮ブログ

39人しか解けなかった問題。難しい。見当つかん。

2008-12-18

LinearPolyominoCovering (SRM429 DIV2 Easy)

| 02:19 | LinearPolyominoCovering (SRM429 DIV2 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - LinearPolyominoCovering (SRM429 DIV2 Easy) - TopCoder煮ブログ

Register 逃した分を解いていった。

普通に解くだけ。AAAA がいけたら AAAA、だめなら BB、だめなら impossible。

SubrectanglesOfTable (SRM429 DIV2 Medium)

| 02:22 | SubrectanglesOfTable (SRM429 DIV2 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SubrectanglesOfTable (SRM429 DIV2 Medium) - TopCoder煮ブログ

リハビリ。何も考えずに書いたら6重ループぐらいになって時間内に終わらずに出戻り。諦めて解いた人の方針をぐぐって調べて、座標ごとに個数を求めればいいことが分かり、素直に書いたら4重ループで素直に解けた。

DIV2 の Mid=DIV1 の Easy が解けなかったのはやヴぁい…。リハビリがんばらねば。

早い人の答えをみたら、(x, y) の回数が ( x + 1 ) * ( y + 1 ) * ( W - x ) * ( H - y ); で求まってるんだけど、何でこの式でいけるのかがさっぱり分からん。教えて、誰か!

分かった。

x=0 のとき、x 方向に取り得るパターンは横幅が1のとき1、横幅が2のとき1…横幅が2mのとき1。つまり1+1+…1=W。x=1のときは横幅が1のとき1、横幅が2のとき2、横幅が3のとき2…。つまり、1+2+2+2+…+2+1=2W-2。同様に、x=3のとき1+2+3+3+…+3+2+1=3W-6。一般化して、xのとき1+2+…+x+x+…+x+(x-1)+…+1=(x + 1)(W - x)だと。x>W/2のときが不安になるけど、式を見ると対象性もあるので問題なさげ。で、xの取り得るパターンとyの取り得るパターンを掛け合わせれば答えになる。なるほどぅ。

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

TheEasyChase (SRM423 DIV1 Medium)

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

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

AddElectricalWires (SRM410 DIV1 Easy)

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

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

2008-10-29

TheTower (SRM423 DIV1 Easy)

| 00:35 | TheTower (SRM423 DIV1 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - TheTower (SRM423 DIV1 Easy) - TopCoder煮ブログ

chokudai さんに教えてもらったあとにじっくり考えて理解。

気付けば簡単なんだが・・・。

  1. x, y を独立に考えられる
    • マンハッタン距離なので、点が集まる座標は x と y を別々に考えてよい。
    • 以下の 2. では x 座標を求めることを考える(例0のパターン)。
  2. 集まる先の x 座標は n 個の点の x 座標のうちのどれかだと考えてよい
    • 例えば、2個の点だと、x0~x1 の間の全ての x 座標がありうる
    • 例えば、3個の点だと、x0 < x1 < x2 だとすると、最終的な座標は x1 以外にはありえない
      • x1 + 1 と x1 までの移動距離の違いを考えてみると分かりよい。
      • x1 に比べて、x1 + 1 は点0、点1 の2つが余計に1つ右に動き、その分、点2 の移動分が1つ減る。よって、x1 + 1 は x1 までに比べて、1つ移動量が多い。
      • 同様に、x1 に比べて、x1 - 1 は1つ移動量が多い
    • このように、必ずどれか1つの x 座標か、隣接する2つの x 座標の間に集まる(必ずしも中央の点に集まるわけではなさそう)
    • だから、n 個の点の x 座標のうちのどれかだと考えてよい(間になる場合はその両端のどちらかだと考えて無視していい)
  3. n 個の点の x, y を全て組み合わせた n^2 通りの座標について調べればよい
    • n 個の中から i 個の全ての組み合わせに対して移動距離を求めるのは大変
    • 魔法の作戦がある!
      • n 個の点のそれぞれと最終地点の距離を調べてソートする
      • ソート結果の最初の2つを足したものは、min(nC2の点から最終地点までの距離の和)である
      • 最初の3つを足したものは…以下同じ
  4. n^2 通りについて最小の移動距離が求まるので、その全ての点のうち最小のものを返せばよい

これを3分台で解ける人がいるのが理解できない……。

2008-10-28

BirthdayReminders (SRM412 DIV2 Medium)

| 03:43 | BirthdayReminders (SRM412 DIV2 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - BirthdayReminders (SRM412 DIV2 Medium) - TopCoder煮ブログ

順番に求めていけばいいかと思いきや、優先順位がちょっと厄介。ならば、全ての組み合わせでの誕生日を記憶しておいて、選ばれたものから次の誕生日で上書きしてやればよい。

STL の練習がてら、operator < を定義した構造体にデータを格納して、set に格納していった。こうすれば誕生日が近く、また、優先順位の高いものから順番に並んでくれる。多少ロジックミスで手間取ったが、System Test には合格。やったね。

上位の人の回答をみたらもっと直接的に解いていた。friendNames と occasions の2次元配列に次の誕生日を格納していって、最小のものを調べている。優先順位も occations が小さいものから調べていけば実現できてしまう。なるほどねー。

以下、ソース。

struct Birthday{
    int f;
    int date;
    int occ;
    int num;

    Birthday(int _f, int _date, int _occ, int _num)
        : f(_f), date(_date), occ(_occ), num(_num)
    {}

    bool operator <(const Birthday& bd) const{
        if(date < bd.date) return true;
        if(date == bd.date){
            if(occ < bd.occ) return true;
            if(occ == bd.occ){
                return f < bd.f;
            }
        }
        return false;
    }
};

vector <string> remind(vector <string> friendNames, vector <int> birthDates, int currentDate, vector <string> occasions, vector <int> days, int k)
{
    set<Birthday> s;
    for(int i = 0; i < friendNames.size(); i++){
        for(int j = 0; j < occasions.size(); j++){
            int n = (int)ceil(((double)currentDate - birthDates[i]) / days[j]);
            s.insert(Birthday(i, birthDates[i] + n * days[j], j, n));
        }
    }

    vector<string> v;
    for(int i = 0; i < k; i++){
        Birthday b = *s.begin();
        s.erase(s.begin());
        s.insert(Birthday(b.f, b.date + days[b.occ], b.occ, b.num + 1));

        ostringstream os;
        os << b.date << ". " << friendNames[b.f] << " " << occasions[b.occ] << " (" << b.num << ")";
        v.push_back(os.str());
    }

    return v;
}

2008-10-26

KPlanetaryAlignment (SRM414 DIV1 Hard)

| 22:57 | KPlanetaryAlignment (SRM414 DIV1 Hard) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - KPlanetaryAlignment (SRM414 DIV1 Hard) - TopCoder煮ブログ

難しそうだったので、とりあえず力技で解く。やはり入力の規模が大きくなると時間がかかりすぎるが、題材が面白かったこともあって勉強になった。


模範解答を探して結果を見たら解けた人は1人のみ。泥臭かったらどうしようと思ったがすごく綺麗なコード。惑星が k 個重なる組み合わせごとに、一直線になる周期を記録している。最後に、それぞれの組み合わせについて、数え上げていく。重複してカウントするのを防ぐために、k個同時を足して、k + 1個同時を引いて、k + 2個同時を足して、k + 3を引いて…としている。円がn個のベン図を考えると分かりよい。かっこいい。分子分母の情報が重要になるので、有理数クラスを作って表現しているところもポイント。

TreeCount (SRM413 DIV1 Hard)

| 01:05 | TreeCount (SRM413 DIV1 Hard) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - TreeCount (SRM413 DIV1 Hard) - TopCoder煮ブログ

きっと動的計画法なんだろうなと思ったものの、何から算出していくかが皆目検討つかず諦めて答えを見る。問題C++トップの人の回答は理解しにくかったので、全体トップの人の回答を読み進める。なんかうまく計算しているっぽいが、F と G の意味を掴みかねる。解けてる人は同じ方針のようなのだが…難しい…。

LavonLavon2011/07/08 02:06Gee whiz, and I tohught this would be hard to find out.

ezonlvzzezonlvzz2011/07/09 22:23JvdRbr , [url=http://nrkrnawayroz.com/]nrkrnawayroz[/url], [link=http://dahqqmnzaikt.com/]dahqqmnzaikt[/link], http://abtsyryszdck.com/

lsztkrmlsztkrm2011/07/11 01:06avBaTE <a href="http://jfonyhaisomt.com/">jfonyhaisomt</a>

dojczvlyoeydojczvlyoey2011/07/11 23:03iHNjn2 , [url=http://atbxicznuqng.com/]atbxicznuqng[/url], [link=http://jurrdqdadcrh.com/]jurrdqdadcrh[/link], http://sajjqxxxxowc.com/

2008-10-21

WorkersOnPlane (SRM422 DIV1 Hard)

| 01:28 | WorkersOnPlane (SRM422 DIV1 Hard) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - WorkersOnPlane (SRM422 DIV1 Hard) - TopCoder煮ブログ

しばらく考えて分からなかったので全体一位の人(neal_wuさん)のコードをみた。まず、ある W から到達できる G と S を列挙している。この情報を元に、次のような最大フロー問題を考える。

            /-S\
  /G---W---W--S-\
S--G--/     \-S--D
  \G---W---W--S-/

どの組み合わせを選ぶかは、最大で何本のフローを流せるかに帰着する。

問題を解くには Edmonds-Karp 法を使う。最短路を求めるところは、ちょっと工夫した深さ優先探索で実施している。(ゴールから順番に枝を確認していけば、自動的にそれは最短路になる)

一点、逆順に流れを記録している理由がよく分からん…。たしかに、これをしないと System Test で落ちている。

→ 試してみた。逆流する余地を残している。逆流して流れる場合は、イメージ的には以前の道を付け替えるような感じ。Edmonds-Karp 法での流量分減らす処理に対応している。

最大フロー問題と Edmonds-Karp 法が少し分かった気がする。

2008-10-19

BirthdayCake (SRM422 DIV2 Hard)

| 15:31 | BirthdayCake (SRM422 DIV2 Hard) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - BirthdayCake (SRM422 DIV2 Hard) - TopCoder煮ブログ

availableFruits を総当りで回すと 2^50 になってしまうので、friendsDislikings で回して 2^20 にする。これなら高々10^6程度。ただし、ビットフラグで管理すると 32bit に収まりきらないのでミスを連発。んーむ。特に、__builtin_popcount は int にキャストされてしまうので要注意。

CavePassage (SRM422 DIV1 Medium)

| 00:29 | CavePassage (SRM422 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - CavePassage (SRM422 DIV1 Medium) - TopCoder煮ブログ

解けている人の解法を見ると、次の方針でやっているようだ。

  • 2^N と行ったとき帰ったときの2通りの状態(=16384通り)がある。
  • それぞれを移りながらダイクストラ法で解いていく。
    • 16384^2 の状態をグラフとして持つのは大変なので、ノード一覧だけ保持して計算していく。
    • ダイクストラ法はメモリ量が少ない!!

C++ 一位の人のソースを理解したあとで暗証してみた。細かい部分がより分かるようになった。priority_queue を使わない方法も試してみて、ダイクストラ法への理解が深まった気がする。

2008-10-18

FloorIndicator (SRM421 DIV2 Hard)

| 14:27 | FloorIndicator (SRM421 DIV2 Hard) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - FloorIndicator (SRM421 DIV2 Hard) - TopCoder煮ブログ

普通に解いたら System Test にも通った。522pt。平均を求めるところで全組み合わせを列挙したら時間オーバーしそうだったので、各桁ごとに平均を出して足し合わせた。C++1位の人とだいたい同じソース。

WalkingDistance (SRM417 DIV1 Hard)

| 18:11 | WalkingDistance (SRM417 DIV1 Hard) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - WalkingDistance (SRM417 DIV1 Hard) - TopCoder煮ブログ

ダイクストラ法使って解こうとしたら撃沈。C++ トップの人のコードをみて学習。任意の2地点間の最短距離を求めるにはウォーシャル・フロイド法というのがシンプル。そのあとに、最短路の最大長のループを求めて、2で割って返してる。

wikipedia:ワーシャル-フロイド法, はてなダイアリー

DancingCouples (SRM416 DIV2 Hard)

| 22:52 | DancingCouples (SRM416 DIV2 Hard) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - DancingCouples (SRM416 DIV2 Hard) - TopCoder煮ブログ

力技で求めるしかなさそうだったので普通に再帰で。普通に System Test したら普通に時間オーバーになった。普通にキャッシュしたら普通に Sytem Test に通った。この問題、計算時間の見通しを立てにくい。

2008-10-13

NextNumber (SRM416 DIV1 Easy)

| 10:59 | NextNumber (SRM416 DIV1 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - NextNumber (SRM416 DIV1 Easy) - TopCoder煮ブログ

勢いよく Submit したが、System Test で撃沈。凡ミス。

C++ 一位の人の回答がスマートすぎる。

  1. (N & -N) で最下位ビットが分かる
    • 補数表現は最下位ビットが重複する
  2. 最下位ビットを足す
    • 必ず繰り上がりが起きてビット数が同じか小さくなる
  3. ビット数が小さくなったら、減った分だけ加算
    • (1 << num) - 1
    • (例)num が 3 のときは、7(111)

CubeNets (SRM417 DIV1 Medium)

| 18:22 | CubeNets (SRM417 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - CubeNets (SRM417 DIV1 Medium) - TopCoder煮ブログ

サイコロ問題。展開図を回すのではなく、展開図の上をサイコロを転がすとよいようだ。C++ 1位の人は、展開図全面をサイコロごろごろ転がして、全部の面に # がヒットしたら YES を返してる。なるほど…。

YearProgressbar (SRM420 DIV2 Medium)

| 18:57 | YearProgressbar (SRM420 DIV2 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - YearProgressbar (SRM420 DIV2 Medium) - TopCoder煮ブログ

勢いよく書いたが System Test で撃沈。うるう年の時に3月以降なら1日足すところを、if(M > 2 && isLeap(Y)) days++; とやっていた。月は 0 base で保持していたので、3月は 2。M >= 2 としたら成功。こんなしょぼいミスばっかり。

PrettyPrintingProduct (SRM420 DIV2 Hard)

| 23:22 | PrettyPrintingProduct (SRM420 DIV2 Hard) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - PrettyPrintingProduct (SRM420 DIV2 Hard) - TopCoder煮ブログ

上位桁と下位桁を別々に計算すればよい。方針は合っていたが、できる限り多く保持しようとして、long long が桁あふれしてしまった。

64bit で表せる数が 0~1.8*10^19。かけていく数は最大10^6なので、low, high ともに 10^12 ぐらいに留めるべきだった。

2008-10-12DIV1 Easy 集中特訓

ForbiddenStrings (SRM412 DIV1 Easy)

| 12:34 | ForbiddenStrings (SRM412 DIV1 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - ForbiddenStrings (SRM412 DIV1 Easy) - TopCoder煮ブログ

違うアルファベットが何個続いているかを覚えておいて数だけを計算。これも DP か。早くはないが、一発 OK。

ArithmeticProgression (SRM413 DIV1 Easy)

| 13:40 | ArithmeticProgression (SRM413 DIV1 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - ArithmeticProgression (SRM413 DIV1 Easy) - TopCoder煮ブログ

上界と下界を順番に調べていって、範囲が不正なら -1 とする。ほとんどできていたのに条件を1つ忘れて、System Test で撃沈…。細かいミスが多いのをなんとかせねば。

ShipLoading (SRM415 DIV1 Easy)

| 20:12 | ShipLoading (SRM415 DIV1 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - ShipLoading (SRM415 DIV1 Easy) - TopCoder煮ブログ

sort して upper_bound を使って。C++ 一位の人とほとんど同じコードだった。嬉しい。<algorithm> 便利!

2008-10-11

HoleCakeCuts (SRM411 DIV1 Medium) その2

| 00:15 | HoleCakeCuts (SRM411 DIV1 Medium) その2 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - HoleCakeCuts (SRM411 DIV1 Medium) その2 - TopCoder煮ブログ

その1の続き。塗り別け問題として解いてみた。冗長なところが多いけど、一発でSystem Test は通った。でも、慣れてないので時間かかった。

DIV2 で C++ 一位の人は、格子点の間を表現するために、座標を二倍にしていた。なるほど、すっきり。

DIV1 で C++ 一位の人は、驚くほどソースが短い。ケーキの外側を切れ目に含めてる。あとは、それぞれの四角が、hole によって分断される場合、なかったことになる場合を調べてる。鮮やかだなー…。

SentenceDecomposition (SRM411 DIV1 Easy)

| 03:52 | SentenceDecomposition (SRM411 DIV1 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SentenceDecomposition (SRM411 DIV1 Easy) - TopCoder煮ブログ

素直に解いたら System Test の 50! 通りになる場合で時間オーバー。撃沈。文字長で動的計画法すべきだった。DIV1 の 250 の正答率を上げねば。

JawadJawad2012/09/01 13:04I can't bieleve I've been going for years without knowing that.

kdvyqyavzjikdvyqyavzji2012/09/02 04:27Kpeubu <a href="http://mqmbkmhedzjw.com/">mqmbkmhedzjw</a>

pqtofnzpqtofnz2012/09/04 17:50GdHgEq , [url=http://swjxqfenbdnc.com/]swjxqfenbdnc[/url], [link=http://qhqvwwbnhitb.com/]qhqvwwbnhitb[/link], http://tpccblpzwmkt.com/

2008-10-08

HoleCakeCuts (SRM411 DIV1 Medium) その1

| 23:44 | HoleCakeCuts (SRM411 DIV1 Medium) その1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - HoleCakeCuts (SRM411 DIV1 Medium) その1 - TopCoder煮ブログ

勢いで解こうと悩んだが時間切れ。

しばらく頭を冷やして挑んだら、すごくかっこいい答えができた。たまにはコードをここに書いておこう。

int cutTheCake(int cakeLength, int holeLength, vector <int> horizontalCuts, vector <int> verticalCuts)
{
    int h = 0, v = 0;
    for(int i = 0; i < horizontalCuts.size(); i++){
        if(-holeLength <= horizontalCuts[i] && horizontalCuts[i] <= holeLength){
            h++;
        }
    }
    for(int i = 0; i < verticalCuts.size(); i++){
        if(-holeLength <= verticalCuts[i] && verticalCuts[i] <= holeLength){
            v++;
        }
    }

    int total = (horizontalCuts.size() + 1) * (verticalCuts.size() + 1);
    int inner = max(0, h - 1) * max(0, v - 1);
    total -= inner;

    if(h == 0) total += max(0, v - 1);
    if(v == 0) total += max(0, h - 1);
    return total;
}

ざっと解説。

  1. 穴に交わる数をカウントする
  2. 穴がなかったときに何個になるかを total に入れる
  3. 穴の中にある数を引く
  4. 穴があることで上下に分断される場合を加算する

図を描くと分かりやすい。

DIV2 の C++ トップの人は、塗り分け問題として解いていた。法則を導き出せないときは、そうやって機械的に解いた方が確実だろう。あとで試そう。

その2 に続く

2008-10-05DIV1 Medium 特訓中

CustomDice (SRM416 DIV1 Medium)

| 12:22 | CustomDice (SRM416 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - CustomDice (SRM416 DIV1 Medium) - TopCoder煮ブログ

んー、解けない…。

しばらく考えて方針は決まったがコードに落とせない。1位のコードを見たら見事。んー、読めるが書けない。

動的計画法の適用

一応まとめておく。

平均 M をみたす全ての組み合わせを見つけるために、さいころの値が変わる面の数を順番に増やしながら DP していく。

例えば、2面だったとして、合計が24(21 + 3)になる組み合わせ D3 は以下の2通り(1 2 3 4 5 6 からの差分で記している)。

1: 0 0 0 0 0 3
2: 0 0 0 0 1 2

2面が変わるときに合計が27(21 + 6)になる組み合わせ D6 は以下の3通り。

1: 0 0 0 0 0 6
2: 0 0 0 0 1 5
3: 0 0 0 0 2 4
4: 0 0 0 0 3 3

では、3面を変えるときを許容した場合、D6 の増分は D3 の要素数になる。

なぜか。D3 の各要素に 0 0 0 1 1 1 を足すと、3面変わるときに取りうる全ての組み合わせになるからだ。

具体例を見れば納得できるはず。

1: 0 0 0 0 0 6
2: 0 0 0 0 1 5
3: 0 0 0 0 2 4
4: 0 0 0 0 3 3
5: 0 0 0 1 1 4  (←0 0 0 0 0 3 + 0 0 0 1 1 1)
6: 0 0 0 1 2 3  (←0 0 0 0 1 2 + 0 0 0 1 1 1)

4面変わるときの D6 は同じように、D2 に 0 0 1 1 1 1 を足す。結果として、D6の組み合わせは次のようになる。

1: 0 0 0 0 0 6
2: 0 0 0 0 1 5
3: 0 0 0 0 2 4
4: 0 0 0 0 3 3
5: 0 0 0 1 1 4
6: 0 0 0 1 2 3
7: 0 0 1 1 1 3  (←0 0 0 0 0 2 + 0 0 1 1 1 1)
8: 0 0 1 1 2 2  (←0 0 0 0 1 1 + 0 0 1 1 1 1)
9: 0 1 1 1 1 2  (←0 0 0 0 0 1 + 0 1 1 1 1 1)
0: 1 1 1 1 1 1  (←0 0 0 0 0 0 + 1 1 1 1 1 1)

同じように、これに 1 1 1 1 1 1 を足したものは、D12 の6面変わるときの組み合わせを出すときに利用できる。

InfiniteSequence2 (SRM413 DIV1 Medium)

| 14:50 | InfiniteSequence2 (SRM413 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - InfiniteSequence2 (SRM413 DIV1 Medium) - TopCoder煮ブログ

そのまま再帰で計算するしかないんで、そのままコーディング。キャッシュしたら案の定、System Test で落ちた。トップのコードを読むと、キャッシュの範囲を限定していた。なるほど。一番参照される場所をメモリが許す範囲でキャッシュするわけか。

StringsAndTabs (SRM412 DIV1 Medium)

| 23:04 | StringsAndTabs (SRM412 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - StringsAndTabs (SRM412 DIV1 Medium) - TopCoder煮ブログ

出題文を読んで仕様を漏れなくきちんと実装していくだけ。複雑な仕様を丁寧に実装することが求められている問題。同じ音程の弦がある場合や音程が降順じゃない場合などは、Challenge Phase で追撃に使えそう。

リーディングとコーディングに時間かかったけど、System Test は一発で通って嬉しい。

2008-10-04

RedIsGood (SRM420 DIV1 Medium)

| 16:27 | RedIsGood (SRM420 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - RedIsGood (SRM420 DIV1 Medium) - TopCoder煮ブログ

4時間かかってやっと解けた。できたコードは30行ほど。4時間で30行って、だめすぎるプログラマだ…。

思考経路

  1. 再帰で解いていけばいいはず。効率よくするためにキャッシュいるよね。
  2. R, B の箱を作って、その中に期待値を突っ込んでいけ。
  3. 期待値の算出をしばし悩む。
  4. やっとできた。時間遅いけど、手元だと動くよね。
  5. TopCoder 鯖で実行すると、std::bad_alloc で落ちる。double×5001×5001 でメモリ足りない。ざっと200M か…。
  6. 困った。
  7. 困った。
  8. 困った。
  9. 動的計画法に変える。あれ、それでもメモリ量変わらん?
  10. あ、R, B の値を求めるとき、R-1, B と R, B-1 が分かれば十分なのか
  11. ということは、左上から順番に計算していけば、ほとんどキャッシュする必要ない。
  12. しばしコーディング。
  13. 慣れてないので時間かかる。
  14. できた。すぐ終わる。すごい。

感想

再帰だと上手くやらないと時間かかったりメモリ食いすぎたりする場合も、動的計画法だと簡単に書けた。具体例を実感できて有意義だった。まだ動的計画法に慣れていないので、いつ使うのか、どうやって使うのかが直感的に思いつかない。繰り返せば慣れるのかなぁ…。

TopCoder SRM 420 Div1 - chokudaiの日記(仮) がとても参考になった。ありがたや。

その後、早い人の解をみた。できたコードのエッセンスは同じだ。しかし、3分40秒で解いてるのがすごすぎる。コードが一瞬で頭の中にできあがって、あとは書くだけなんだろな…。

StringInterspersal (SRM414 DIV1 Medium)

| 00:16 | StringInterspersal (SRM414 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - StringInterspersal (SRM414 DIV1 Medium) - TopCoder煮ブログ

500点問題の練習。と思ったらすごく簡単だった。正答率50%。ま、そんなもんだろうな。番兵を最後におけばシンプルなコードになった。

CollectingPostmarks (SRM415 DIV1 Medium)

| 02:41 | CollectingPostmarks (SRM415 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - CollectingPostmarks (SRM415 DIV1 Medium) - TopCoder煮ブログ

制限時間に計算を終わらせる方法が分からない。そのまま調べると2^32通りになってしまう。案の定、System Test でタイムオーバー。諦めて模範回答を見る。

2分割する手法をとっている。

  1. 半分ずつ分割する
  2. それぞれの組み合わせで値と値段を求める(2^16×2=12万通り)
  3. それぞれの組み合わせで値でソート
  4. それぞれの結果を見比べて K を超えるものを調べていく(16^2=256通り)

なるほど。2分割してマージしてる。分割統治法か!

正答率14.58%。解けなくても仕方がないとするか。2^32 で解くところまでなら書けたので、あとは2分割することを思いつくかどうかだ。

2008-09-30

StampsCollection

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

DIV1 むずいの続き。

こないだ挫折した SRM418 DIV1 Level2 の StampsCollection の答えを読解。

  • グラフに置き換える
    • demand は節点
    • price は節点の重み
    • 同じ stamp を欲しがってる節点同士を枝で結ぶ

3) の例だとこんな感じ。

 ┌─┐    ┌─┐    ┌─┐
 │5│----│9│----│5│
 └─┘    └─┘    └─┘

誰が購入するかを決定することは、「枝を共有しないような節点を選ぶ」と等価になる。収入を最大化するということは、重みを最大化するように選ぶこととなる。つまり、これは最大次数が2の wikipedia:最大独立集合問題 だ、と。

上の例だと、左の2つの節点(5 と 9)を選択してしまうと、枝(Stamp 0)を2人が欲しがってしまうので NG。9(真ん中の節点)もしくは、5+5(両端の節点) のいずれかで、答えは10となる。

んー、言われれば納得するが思いつかない…。

で、解法。

  1. 深さ優先探索して節点をグループ分け
  2. 各グループについて、最大値を求める。
    • 最大次数2なので、一本道もしくは閉路のどちらか
    • 奇数番目、偶数番目だけを選んだときの最大値を求めればよし
    • ただし、閉路のときには少し気をつける

2008-09-29

CactusCount

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

DIV2 で5人しか答えられなかった CactusCount にチャレンジ。答えを導くコードは書けたものの、O(n^2) ぐらいで n=200 のときに時間かかりすぎ。

諦めて答えをみて勉強中。全体3位の人のソースが読みやすかったので読解。

「ループを探すにはDFS(深さ優先探索)で経路を記録すればよい」

なるほど。BFS(幅優先探索)でやろうとして破綻してた。DFS と BFS の性質を体で理解せねば。

2008-09-23

DIV1 むずい

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

練習で SRM418 DIV1 Level2 の StampsCollection を解いてみた。テストは通るんだけど、System Test が実行時間が長すぎて失敗。手元にテストを持ってきたら、確かに計算が終了しない。

正解者の答えを解析しようとがんばってるが、かなり難易度高い。恐るべし、DIV1。正答率12%、早い人でも40分近くかかってる模様。

→ (追記)SRM 418 - tsubosakaの日記 によると、「次数2以下のグラフの最大重み独立集合」という問題に帰着できるようだ。