Hatena::Grouptopcoder

TopCoder煮ブログ

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

2014-04-12

2014 TCO Round 1A

03:14 | 2014 TCO Round 1A - TopCoder煮ブログ を含むブックマーク はてなブックマーク - 2014 TCO Round 1A - TopCoder煮ブログ

初の TCO 参加。予習で前回の SRM 616 といたら DIV 1 250 が解けたので気分をよくして開始。

14021603 1182.47 pt (39位/2424人)

○○○ (challenge: 0勝0敗)

EllysSortingTrimmer (250)

文字列のうちの一部分 L 個をソートして、後ろを削る関数がある。何度呼び出してもいいから、一番辞書順で手前になる文字を作りましょう、という問題。

何も考えずに、順番に「後ろから L 個をソートして、最後の 1 個を取り除く」という処理を L 個になるまでやったらいけた。

    string getMin2(string S, int L) {
        int N = S.size();
        for (int i = N - L; i >= 0; i--) {
            sort(S.begin() + i, S.end());
            if (i > 0) {
                S = S.substr(0, S.length() - 1);
            }
        }
        return S;
    }

sort と substr の順番を入れ替えたら、if も不要。

EllysScrabble (500)

文字列のうち、各文字を最大 maxDistance 個横の位置にずらすことができるので、辞書順で手前になるやつを作りましょう、という問題。

先頭の文字は 0~maxDistance のうち、辞書順で一番手間になるやつで決定。

同じように 2 番目は 1~maxDistance + 1 のうち、辞書順で一番手間になるやつ (ただし、さっき選んだやつ以外) でよさそう。おっと、maxDistance が 2、かつ、さっき 1 番目を選んだ場合は、必然的に 0 番目を選ばなきゃいけない。

といったことをコードにした。

    string getMin(string letters, int maxDistance) {
        string S = "";
        int N = letters.size();
        int Used[50];
        memset(Used, 0, sizeof(Used));

        for (int i = 0; i < N; i++) {
            if (i - maxDistance >= 0 && !Used[i - maxDistance]) {
                Used[i - maxDistance] = 1;
                S += letters[i - maxDistance];
                continue;
            }

            char c = 'Z' + 1;
            int index = -1;
            for (int j = -maxDistance; j <= maxDistance; j++) {
                if (i + j < 0 || i + j >= N) continue;

                if (!Used[i + j] && letters[i + j] < c) {
                    index = i + j;
                    c = letters[i + j];
                }
            }
            S += letters[index];
            Used[index] = 1;
        }
        return S;
    }

Challenge で見てたら、フラグの代わりに '*' に置き換えてる人がいて、それならもうちょっとシンプルに書けそう。

EllysLamps (1000)

ランプを全部消したいんだけど、スイッチが壊れてるやつがあって、隣を道連れにするケースがある。

最初の点いている状態は分かっているけど、壊れ方は分からない。最悪の壊れ方をしたときに、消えずに残るスイッチの個数を求めよ、という問題。

なんとなく、YN か NY の塊の個数を求めればいけるかとおもったけど、最後の example が通らない。

よくよく考えると、YYY が最悪の壊れ方をしたとき、1個残ることがある (前2つがそれぞれを道連れにして、最後の1つが手前を道連れにするケース)。

ってことで、先頭から YN、NY、YYY のブロックの個数を数えていけばおしまい。

    int getMin(string lamps) {
        int N = lamps.length();
        int ret = 0;
        for (int i = 0; i < N; i++) {
            if (i + 1 < N && lamps[i] != lamps[i + 1]) {
                ret++;
                i++;
                continue;
            }
            if (i + 2 < N && lamps[i] == 'Y' && lamps[i + 1] == 'Y' && lamps[i + 2] == 'Y') {
                ret++;
                i += 2;
            }
        }
        return ret;
    }

なんとなく動きそうなので submit したら、System Test 通った。

https://docs.google.com/document/d/1O5v5d_iY9zV0slI8fgKhZosDsYDNSZVsOXeL2Cui0DM/pub によると DP で解く必要あるらしいが、DP 苦手なので無理矢理かいてしまった。

2013-10-06

HexagonalBoard (SRM 593 Div1 Easy)

| 21:42 | HexagonalBoard (SRM 593 Div1 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - HexagonalBoard (SRM 593 Div1 Easy) - TopCoder煮ブログ

方針は http://topcoder.g.hatena.ne.jp/nitoyon/20131005/1380995960 で固まっていたので、あとは書くだけ。

単純ミスで 1 回、System Test 落ちたあと、再提出で pass。ダメな感じ。

あと、最大 3 色だというところの証明がパッと出てこない。

#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
#define _USE_MATH_DEFINES
#include <math.h>
#include <string.h>
using namespace std;

// -xx
// x*x
// xx-
int neighbor[][2] = {{0,-1},{1,-1},{-1,0},{1,0},{-1,1},{0,1}};

class HexagonalBoard {
    bool visited[50][50];
    int color[50][50];
    vector<string> b;
    int N;
public:
    int search(int x, int y, int col) {
        visited[y][x] = true;
        color[y][x] = col;
        int ret = 1;
        for (int i = 0; i < 6; i++) {
            int xx = x + neighbor[i][0];
            int yy = y + neighbor[i][1];
            if (xx < 0 || yy < 0 || xx >= N || yy >= N) {
                continue;
            }
            if (b[yy][xx] == 'X') {
                ret = max(ret, 2);
                if (visited[yy][xx]) {
                    if (color[yy][xx] != -col) {
                        ret = 3;
                    }
                } else {
                    ret = max(ret, search(xx, yy, -col));
                }
            }
        }
        return ret;
    }

    int minColors(vector <string> board) {
        b = board;
        N = b.size();
        memset(visited, 0, sizeof(visited));
        memset(color, 0, sizeof(color));
        int ret = 0;

        for (int y = 0; y < N; y++) {
            for (int x = 0; x < N; x++) {
                if (b[y][x] == 'X' && !visited[y][x]) {
                    ret = max(ret, search(x, y, 1));
                }
            }
        }
        return ret;
    }
};

MayTheBestPetWin (SRM 593 Div1 Medium)

| 23:37 | MayTheBestPetWin (SRM 593 Div1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - MayTheBestPetWin (SRM 593 Div1 Medium) - TopCoder煮ブログ

時間をかけても全く分からないので http://topcoder.g.hatena.ne.jp/kojingharang/20131006#1381050540Java 2 位の uwi さんのソースで理解した。

  • 選手 n ごとに最速タイム A[n] と最低タイム B[n] が分かっている (2 <= N <= 50, 1 <= A <= 10,000, 1 <= B <= 10,000)。
  • 2 つのチーム S, T に分けてリレーを行う。チームの人数は違ってもよい。
  • 一番緊迫する試合を見たいので、とりうる時間差が最小となるようなチームわけにしたい。このときの時間差を求める。

総当りで実装すると、すべてのチーム分けに対して

max(|S fast - T slow|, |S slow - T fast|)

の最小値を求めればよい。2 ^ 50 通りなので爆発して総当りは不可能。


SumA, SumB を計算しておく。

次のようにする。

  • SumA = ΣA = A[0] + A[1] + ... + A[n-1]
  • SumB = ΣB = B[0] + B[1] + ... + B[n-1]
  • C[i] = A[i] + B[i]

とする。

    int calc(vector <int> A, vector <int> B) {
        int SumA = 0, SumB = 0;
        int N = A.size();

        // SumA, SumB を計算
        for (int i = 0; i < N; i++) {
            SumA += A[i];
            SumB += B[i];
        }

ここで数式変換。

|S fast - T slow| = |ΣA[s] - ΣB[t]|
                  = |(SumA - ΣA[t]) - ΣB[t]|
                  = |SumA - ΣC[t]|
|S slow - T fast| = |ΣB[s] - ΣA[t]|
                  = |(SumB - ΣB[t]) - ΣA[t]|
                  = |SumB - ΣC[t]|
(s in S, t in T)

となる。

あとは、ΣC[t] のとりうる値が分かればよい。イメージで言ってしまえば、SumA, SumB のなるべく中間の値を取るようにグループ T を選びましょう、という問題になる。

DP

といっても、グループ T の取り方はたくさんある。ここで DP が登場。時間をキーに DP する。

ΣC[t] のとりうる範囲は 0~SumA + SumB の中に限定される。この範囲の bool な配列 dp をつくって、とりうるなら true、とらないなら false として調べていく。

  • すべての選手がチーム S にいるケースでは ΣC[t] は 0。dp[0] のみを true にしておく。
  • 選手 0 がチーム S に参加する可能性を考えると、ΣC[t] は 0 か C[0] をとりうる。dp[0+C[0] ] を true にする。
  • 選手 1 がチーム S に参加する可能性を考えると、ΣC[t] は 0, C[0], C[1], C[0] + C[1] をとりうる。dp[0+C[1] ] と dp[C[0]+C[1] ] を true にする。

こんな感じで 0~SumA + SumB の範囲について、ΣC[t] がとりうる範囲のフラグを立てていく。

        // 時間をキーにした dp 配列を準備
        // C[i] = A[i] + B[i] が取る得る値かどうかを格納する
        bool* dp = new bool[SumA + SumB + 1];
        memset(dp, 0, sizeof(bool) * (SumA + SumB + 1));
        dp[0] = true;
        for (int n = 0; n < N; n++) {
            for (int i = SumA + SumB; i >= 0; i--) {
                if (dp[i]) {
                    dp[i + A[n] + B[n]] = true;
                }
            }
        }

すべての選手を列挙したら、dp 配列には ΣC[t] がとりうる値のみフラグがたった状態になっている。

最小値を求める

ΣC[t] の範囲内のすべての値について max(|SumA - ΣC[t]|, |SumB - ΣC[t]|) を計算する。この最小値が求めるべき値となる。

        // C[i] のそれぞれの値について、
        // max(|S fast - T slow|, |S slow - T fast|) を求める。
        // その中での最小値を調べる
        int ret = SumA + SumB;
        for (int i = 0; i <= SumA + SumB; i++) {
            if (dp[i]) {
                int maxdiff = max(abs(SumA - i), abs(SumB - i));
                ret = min(ret, maxdiff);
            }
        }

おしまい。自力で分かる気がしない・・・。

以下、ソース。

続きを読む

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人しか解けてなかった。

CutSticks (SRM456 DIV1 Medium)

| 23:40 | CutSticks (SRM456 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - CutSticks (SRM456 DIV1 Medium) - TopCoder煮ブログ

n個の棒をC回切って、K番目に長い棒の最大長を求める問題。上位の人のソースを読んで意図を解読した。

最大C回切ることが許されているときに、長さが m 以上となる棒がK個以上あるかを求めることができる。

この長さ m を 0 と無限長の中点から始めて、m 以上か m 以下かで2分探索していく。

上位の人のソースを解読して、自分なりに書き換えてコメントいれた。ループ回数に最大回数が入ってるのは二分探索の罠を回避するため。

高レート部屋でこの定番が使えなかったのが痛いけど、見るべきは「二分探索の終了条件」です

例えば、差が1e-9以下になったらーとかいってたら、出来るだけでかいのをぶち込みますっ

仮数部が確か52bitしかないはずだから、まぁ16桁くらいまでなのかな、だとすると、答えが1e10くらいのものをぶち込まれたときに、差がそれ以下にならずに無限ループに入ったりしちゃうわけです

ただこれは入るときと入らないときがあるから落とせない、ってのが難しいところですorz

chokudaiのブログ - chokudaiのブログ

奥が深い。。。

以下、ソース。

class CutSticks {
public:
    // 最大C回切ることが許されているときに、
    // 長さが m 以上となる棒の数を返す
    int Count(vector<int> sticks, double m, int C){
        // 戻り値
        int ret = 0;

        for(int i = 0; i < sticks.size(); i++){
            // i 本目の棒の長さを s とする
            int s = sticks[i];

            // i 本目の棒が m より小さいときは数には含まれない
            if (s < m) continue;

            // 最大何回切れるかを求める
            // s が 2 * m 程度のときは、1回切ることができる
            int count = int(s / m) - 1;

            // count の上限を残り切れる回数 C にする
            count = min(count, C);

            // 戻り値を(切れる回数+1)だけ増やす
            ret += count + 1;

            // 残り切れる回数 C を更新する
            C -= count;
        }

        return ret;
    }

    double maxKth(vector <int> sticks, int C, int K) {
        // 左端、右端を設定する
        double l = 0;
        double r = 1e9;

        // 回数制限用のカウンタ
        int count = 0;

        // 差が小さくなるか500回ループしたら終わる
        while(fabs(l - r) > 1e-10 && count < 500){
            // 中点を取得する
            double m = (l + r) / 2.0;

            // m 以上となる棒が K 個以上のときは
            // 求めるべき値は m より大きい。
            if(Count(sticks, m, C) >= K){
                l = m;
            } else {
                r = m;
            }

            count++;
        }

        return r;
    }
};

2009-12-06

NumbersAndMatches (SRM454 DIV1Comments Medium)

| 18:06 | NumbersAndMatches (SRM454 DIV1Comments Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - NumbersAndMatches (SRM454 DIV1Comments Medium) - TopCoder煮ブログ

答えを見ても全く分からずに一日悩んだ。いろいろ探す過程で「今回の500は簡単」という発言をみて萎える。

今回は、桁の数を増やしながら計算するのが一番外側のループ。表に記憶するのは、1つ前の桁の過不足を含んだ数の個数。

DP

追加数と減少数の表をまず作る

del\add01234
010000
100000
200000
300000

最初に処理する桁が「2」のときは、それぞれの数に移動したときの数を記録する。

del\add01234
010100
101300
200100
301200

(0,0)は2から2に遷移するとき(つまり移動は発生しない)。(1,1)が2から1に遷移するとき(1個減らして1個追加、つまり1回の移動)。

(2,1)は2から0,6,9に遷移するとき。たとえば、2から0に遷移するには2個追加して1個減ったらいける。このままだと過不足が発生しているが、この次の桁で1個減らす遷移が発生すると、過不足は解消される。

さて、次の桁。

たとえば次の桁が「2」のときは、2から10通りの数に移る場合の移動を計算する。この移動方法を(0,0)からだけじゃなく、その他の数字がある場所全てに適用して、2桁目を変えた全パターンについて移動先の数を求める。

こんな感じで全ての桁について DP 表を更新したら、最後に K 個の対角線の数を足し合わせる。対角線というのは、マッチの移動が過不足なく行えた場所。

ソース

cafelier 先生のソースを解読してコメントつけてみた。

続きを読む

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++ 一位の人のソースと見比べたらシンプルさでは負けるものの方向性は同じだった。

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-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 方向で折るときに、左側の方が大きくなるケースが抜けていて悩む。

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

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

UnluckyIntervals (SRM438 DIV1 Easy)

| 01:10 | UnluckyIntervals (SRM438 DIV1 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - UnluckyIntervals (SRM438 DIV1 Easy) - TopCoder煮ブログ

本番 の System Test のときにだいたいの方針は理解したので書き下していくだけ。にも関わらず時間がかかる。だめだなぁ。

submit したら、Test Case 4 で落ちる。{2}, 1 というもの。前後 n 個はチェックしていたはずだが、n - 1 しか見ていなかった。境界条件で落とされた。んむー。境界条件に迷わされないために、ちょっと多めに計算しておいたほうがよいんだろうな。

ソース。無駄が多い。

続きを読む

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

SRM438 (延期)

02:04 | SRM438 (延期) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM438 (延期) - TopCoder煮ブログ

システムの調子が悪くて1日延期。途中、SRM438 が何度も消えたり、Enter したら同じようなレーティングの人ばっかりだったり、再度 Register させられたり、部屋に入れというポップアップでクライアントが凍ったり、なかなか楽しい1時間であった。

練習で SRM437 DIV2 の 250 と SRM333 DIV2 の 250 を解いた。ちょっとした練習になった。

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

HexatridecimalSum (SRM434 DIV1 Medium)

| 12:23 | HexatridecimalSum (SRM434 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - HexatridecimalSum (SRM434 DIV1 Medium) - TopCoder煮ブログ

リベンジ

実戦では「桁が上のものから Z に置き換えていくようにすればいい」という方針で時間切れだったので、続きを書いてみた。が、System Test に通らない。しばし考えて間違いだったと気づく。反例は、YZ,Z0,Z0,...,Z0 で k=1 のようなケース。Y を Z に置き換えても高々360増えるだけだが、0 を Z に置き換えたら36×(Z0の個数)増えて、360を超える。

つまり、数字ごとに増分を計算していかなきゃいけない。作戦を変更して書き直し。増分は double に格納していく。増分の比較ならばそこまで精度は細かくなくてよいだろう、と信じる。

やってみたらうまくいった。合計2時間ほど格闘してしまった。

C++1位の人を見てみる

C++1位の人のソースをみてあまりのシンプルさに驚く。

  1. numbers を全部足した文字列を計算する。
  2. 0~Y までのそれぞれを Z に変換したときの増分を文字列で持つ
  3. 増分の大きなもの(文字列の比較でOK)から k 個を 1. の結果に足していく。

ちょっとしたコツ:

  • 桁が違うとややこしいので、000 を各数字の最初に埋めておく。最後に先頭の 0 を取り除いて返す。

自分のソース

以下、自分のソース。

続きを読む

FindingSquareInTable (SRM434 DIV1 Easy)

| 13:53 | FindingSquareInTable (SRM434 DIV1 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - FindingSquareInTable (SRM434 DIV1 Easy) - TopCoder煮ブログ

本番では混乱したまま書き始めてうまく行かなかった問題。開始座標と増分の4重ループで素直に書けた。なんと…。

上位の人のソースを読んだ感想。

  • for のループを横に連ねてタブの階層を減らしたほうがよさそうだ。
  • perfect square かの判別は (int)sqrt(1.0*n) を2乗して n と比較すればよい。
    • 自分は sqrt して modf したけど一時変数がいるのがかっこ悪いし誤差が怖い。

以下、自分のソース。

続きを読む

nishiohirokazunishiohirokazu2009/02/08 18:43mod系がダメな理由の一つはnが0になりうるって点かと。

2009-02-07

MagicWords (SRM433 DIV2 Medium)

| 00:29 | MagicWords (SRM433 DIV2 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - MagicWords (SRM433 DIV2 Medium) - TopCoder煮ブログ

解けなかった問題。あとで確認したら TLE だった。

本番で Submit したところの

if(s == s2.substr(i, N)) count++; 

を、次のように修正したら通った。

if(strncmp(s.c_str(), s2.c_str() + i, N) == 0) count++; 

要約:substr はコスト高いよね

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-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 を先に結合して、その後に通常の結合を実施していた。よく思いつくなぁ。

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

続きを読む

2009-01-07

SRM432 DIV2

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

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

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

LocateTreasure (SRM427 Medium)

| 01:16 | LocateTreasure (SRM427 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - LocateTreasure (SRM427 Medium) - TopCoder煮ブログ

できなかった理由

  • dig を再帰的に適用していなかった
  • 周期が何回あらわれるかを求めるところで、周期に至るまでの初期ごにょごにょするところで、ちょっとしたインデックスの計算ミス
  • Kの数が周期運動に入るよりも前のときの扱いができていなかった

結局3箇所ぐらいできていなかったわけで、まだまだ先は長いことがよく分かった。

C++ 1位の人のソースを見たが、方針自体は同じだった。

g:topcoder

01:31 | g:topcoder - TopCoder煮ブログ を含むブックマーク はてなブックマーク - g:topcoder - TopCoder煮ブログ

g:topcoder の人が増えてきていい感じ。

中でも id:cafelier さんが コンテスト中に考えてたことを執拗に全部書き残している様がとても参考になる。

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-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位の人は頂点の数だけループを回して浸透させていく方式を使っていた。時間が問題にならないのならこっちのほうがシンプルに書ける。

2008-10-29

SRM423 DIV1

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

撃沈。むずい。

15141459

0点だからしかたなし。

TheTower

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

TheEasyChase

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

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

TheBeautifulBoard

一瞬見たが諦め。

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 が小さいものから調べていけば実現できてしまう。なるほどねー。

以下、ソース。

続きを読む

比較関数

| 09:43 | 比較関数 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - 比較関数 - TopCoder煮ブログ

上で貼り付けたソースは

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

と冗長な感じだったけど、Java 1位の人のソースを見ていて、次のようにシンプルに書けることが分かった。

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

シンプルだと分かりやすい。

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個のベン図を考えると分かりよい。かっこいい。分子分母の情報が重要になるので、有理数クラスを作って表現しているところもポイント。

Match Overview の Collect %

| 23:03 | Match Overview の Collect % - TopCoder煮ブログ を含むブックマーク はてなブックマーク - Match Overview の Collect % - TopCoder煮ブログ

Collect %
  = Submission Accuracy
  = Correct / Submitted * 100
  = (Submitted - Failed by Challenge - Failed by System Test) / Submitted * 100
  • Submissions が少ない → 解かずに諦めた人が多い
  • Collect が少ない → はまりポイントがある

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

upper_bound と lower_bound(とdistance)

| 23:28 | upper_bound と lower_bound(とdistance) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - upper_bound と lower_bound(とdistance) - TopCoder煮ブログ

upper_bound と lower_bound が返す場所への理解が曖昧だったので、実証コードを書いて理解を深めた。

図にするとこんな感じ。

  1   1   3   3   5
  | upper_bound 0
          | upper_bound 1
          | upper_bound 2
                  | upper_bound 3

  1   1   3   3   5
  | lower_bound 0
  | lower_bound 1
          | lower_bound 2
          | lower_bound 3

upper_bound はその数を超える最初の場所を指す。lower_bound はその数以下の最大の数字を指す。同じ値が複数あった場合、upper_bound も lower_bound も先頭を指す。

以下、少し長いけど実証コード。イテレータの場所をインデックス番号で取得するために std::distance() を使ってみた。イテレータはポインタみたいに引き算で差分ができなくて悩んだ。


void main(){
    vector<int> v;
    v.push_back(1); v.push_back(1);
    v.push_back(3); v.push_back(3);
    v.push_back(5);

    vector<int>::iterator p;
    p = upper_bound(v.begin(), v.end(), 0);
    cout << distance(v.begin(), p) << endl; // 0
    p = upper_bound(v.begin(), v.end(), 1);
    cout << distance(v.begin(), p) << endl; // 2
    p = upper_bound(v.begin(), v.end(), 2);
    cout << distance(v.begin(), p) << endl; // 2
    p = upper_bound(v.begin(), v.end(), 3);
    cout << distance(v.begin(), p) << endl; // 4

    p = lower_bound(v.begin(), v.end(), 0);
    cout << distance(v.begin(), p) << endl; // 0
    p = lower_bound(v.begin(), v.end(), 1);
    cout << distance(v.begin(), p) << endl; // 0
    p = lower_bound(v.begin(), v.end(), 2);
    cout << distance(v.begin(), p) << endl; // 2
    p = lower_bound(v.begin(), v.end(), 3);
    cout << distance(v.begin(), p) << endl; // 2
}

2008-10-22

間違えた

12:35 | 間違えた - TopCoder煮ブログ を含むブックマーク はてなブックマーク - 間違えた - TopCoder煮ブログ

SRM 423 は来週だった。

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

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 に参加してみた。楽しい。

コードテンプレート

| 14:01 | コードテンプレート - TopCoder煮ブログ を含むブックマーク はてなブックマーク - コードテンプレート - TopCoder煮ブログ

いまのテンプレート。HTML は FileEdit の設定で HTML として出力するようにしている。

#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
#define _USE_MATH_DEFINES
#include <math.h>
#include <string.h>
using namespace std;

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

class $CLASSNAME$ {
public:
	$RC$ $METHODNAME$($METHODPARMS$) {
		
	}

	$TESTCODE$
};

// BEGIN CUT HERE
int main(){
	$CLASSNAME$ __test;
	__test.run_test(-1);
}

// END CUT HERE
2009/01/03
M_PI を使うために #define _USE_MATH_DEFINES を追加
2013/10/06
memset を使うために string.h を追加

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 にキャストされてしまうので要注意。

TZTester 改

| 22:54 | TZTester 改 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - TZTester 改 - TopCoder煮ブログ

TZTester ビルド - TopCoder煮ブログ - TopCoder部 の続き。

http://tech.nitoyon.com/misc/topcoder/

  • コードを整形してテストを追加・修正しやすくした
  • 配列の要素が空のときにエラーにならないようにした

memset と std::fill

| 00:14 | memset と std::fill - TopCoder煮ブログ を含むブックマーク はてなブックマーク - memset と std::fill - TopCoder煮ブログ

memset はバイト単位で値を設定する。int の配列や double の配列を特定の値で初期化する場合は、std::fill を用いるべし。

// 0 はうまくいく
int A[10];
memset(A, 0, sizeof(A));
// A[0] -> 0
// A[1] -> 0

// が、1 は意図しない結果に
memset(A, 1, sizeof(A));
// A[0] -> 16843009 (=0x01010101)
// A[1] -> 16843009 (=0x01010101)

// そういう時は std::fill
fill(A, A + 10, 1);
// A[0] -> 1
// A[1] -> 1

fill の第二引数は最後の要素 + 1の場所を指定する。vector などの end() と同じ扱い。

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 に通った。この問題、計算時間の見通しを立てにくい。

TZTester ビルド

| 00:30 | TZTester ビルド - TopCoder煮ブログ を含むブックマーク はてなブックマーク - TZTester ビルド - TopCoder煮ブログ

TopCoderでCodeProcessor+TZTester+FileEdit - Gulfweed を参照してプラグインを導入してみて快適になっている。

ただ、TZTester の吐くコードが気に食わなかったのでソースを修正してビルドしてみた。

  1. JDK をインストール (1.4.2 でいけた)
  2. http://www.topcoder.com/contest/classes/ContestApplet.jar をダウンロードしておく
  3. ソースを http://www.topcoder.com/tc?module=Static&d1=applet&d2=plugins から入手
  4. コンパイル: javac -classpath ContestApplet.jar -deprecation TZTester.java
  5. jar 化: jar cvf TZTester.jar TZTester.class
  6. 既存の TZTester.jar に上書きして ARENA を再起動

ひとまずは、テストコードに適度に改行を入れて、自分でテストを追加しやすいようにした。空の vector でコンパイルエラーになるバグも修正したい。→改善した http://topcoder.g.hatena.ne.jp/nitoyon/20081019/1224424489

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> 便利!

std::accumulate

| 20:19 | std::accumulate - TopCoder煮ブログ を含むブックマーク はてなブックマーク - std::accumulate - TopCoder煮ブログ

コンテナの値を加算するには std::accumulate が便利。numeric の include も忘れずに。

使用前:

// vec は vector<string> とする
string s = ""
for(int i = 0; i < vec.size(); i++){
    s += vec[i];
}

使用後:

#include <numeric>

string s = accumulate(vec.begin(), vec.end(), string());
// 第3引数は初期値

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 によって分断される場合、なかったことになる場合を調べてる。鮮やかだなー…。

vector の検索

| 00:23 | vector の検索 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - vector の検索 - TopCoder煮ブログ

for で回すのは面倒。2分探索を使えばよい。

使用前:

// value を探す
bool found = false;
for(int i = 0; i < v.size(); i++){
  if(v[i] == value){
    found = true;
    break;
  }
}

if(found){
  // 見つかったときの処理
}

使用後:

#include <algorithm> // sort, binary_search
using namespace std;

sort(v.begin(), v.end());
if(binary_search(v.begin(), v.end(), value)){
  // 見つかったときの処理
}

binary_search するためには sort が必須なので注意。

begin() と end() をいちいち書くのが面倒なので

#define ALL(A) (A).begin(),(A).end()

のようなマクロを書いてる人がそこそこそいるようだ。

最小値演算子・最大値演算子

| 03:48 | 最小値演算子・最大値演算子 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - 最小値演算子・最大値演算子 - TopCoder煮ブログ

g++ 独自の演算子。deprecated と warning は出るが動く。

a <? b
数値 a と b のうち小さいほうを返す最小値演算子
a >? b
数値 a と b のうち大きいほうを返す最大値演算子
http://www.asahi-net.or.jp/~WG5K-ICKW/html/online/gcc-2.8.1/gcc_4.html#IDX416
a <?= b;

a = min(a, b);

と同じ。

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

日本人上位coder

| 18:11 | 日本人上位coder - TopCoder煮ブログ を含むブックマーク はてなブックマーク - 日本人上位coder - TopCoder煮ブログ

はてな界隈で SRM キーワードで探してきた中から、yellow 以上の人をピックアップ。

問題の振り返りをブログでしてくれてるので、非常に参考になる。

とてもじゃないけど追いつけなさそうで絶望的になる…。

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 は遠い。

algorithm の壁

| 23:48 | algorithm の壁 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - algorithm の壁 - TopCoder煮ブログ

std::sort 便利。vector をソートするには

sort(vec.begin(), vec.end());

とする。第3引数で関数オブジェクトを渡す比較方法を変えられる。greater を渡すと降順になる。

sort(vec.begin(), vec.end(), greater<int>());

関数オブジェクトおもしろい。

map みたいなこともできる。

vector<int> vec;
vec.push_back(1);
vec.push_back(3);
vec.push_back(2);
transform(vec.begin(), vec.end(), vec.begin(), negate<int>());
// -1 -3 -2

全部の要素の正負が反転する。

要素を足すには plus 関数オブジェクトの片方を束縛してやる。

transform(vec.begin(), vec.end(), vec.begin(), 
  bind1st(plus<int>(), 1));
// 2 4 3

count_if なんかも便利そう。remove_if は終端の場所が iterator で帰ってくるので要注意。

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

SRM419 DIV1

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

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

1388 -> 1242

なんとか DIV1 に残ってる。

Undo

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

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

NimForK

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

CactusAutomorphisms

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

DP

20:33 | DP - TopCoder煮ブログ を含むブックマーク はてなブックマーク - DP - TopCoder煮ブログ

topcoder 結果報告のブログを見てると、「DP」という言葉がでてくる。どうやら「動的計画法」のことらしい。最初の状態から状態を保存しつつ計算していく感じか。wikipedia:動的計画法が詳しい。

2008-09-23

DIV1 むずい

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

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

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

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

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。